search

bmwcarit / barefoot

Java map matching library for integrating the map into software and services with state-of-the-art online and offline map matching that can be used stand-alone and in the cloud.
Apache License 2.0
665 stars 186 forks source link

Issue about the [matcher.lambda]'s adaptive setting #88

Open liuyialfred opened 6 years ago

liuyialfred commented 6 years ago

Hi, our group is trying #on barefoot. When reading the wiki and source code I came across the parameter matcher.lambda. It is adaptively set as the function of sampling time:

double beta = lambda == 0 ? (2.0 * Math.max(1d, candidates.one().time() - predecessors.one().time()) / 1000): 1 / lambda;

It works in our experiments. But I noticed in the original paper of Paul Newson and John Krumm, the parameter is set related to the distance of sampling points and route points.

Would you tell about how you decide the adaptive parameter only considering sampling time, while the intuition may relate the parameter to distance. #

smattheis commented 6 years ago

In their paper, Newson and Krumm used a probability model that uses the distance to determine the probability of a route being the transition between two matching candidates. The idea is to be time-independent since time can vary due to traffic jams, traffic lights etc. However, in a closed and non-representable dataset, we found that shortest paths let traces often go over hedges and ditches especially if sampling rates are low, i.e., 60 seconds intervals or more between two position measurements. The intuition was that if we would manually route between position samples, we would choose paths like a router which is usually fastest path plus it considers some factor that represents influence of the road type. Therefore, you will see that the probability model implemented here uses the time-priority cost function to determine the probability of a path. As a consequence, lambda parameter must be chosen to be an expectation value of the time-priority based probability model which is naturally the time interval of two position measurements, converted from microseconds to seconds, multiplied with a factor of some kind of average road type factor, here chosen 2. The positive side effect is that it is now also adaptive to varying sampling rates since the expectation value to be found is nothing else but the given time interval instead of an "artificially" and statically chosen value. Further, I never encountered any problem of being time-dependent because the only practical direction to vary in time is that a vehicle takes longer because of traffic jams and traffic lights which, however, naturally increases the density of samples in space (if we assume a static sampling rate) and, hence, smoothes the effect of traffic jams and traffic lights again naturally.

As said, this was evaluated with a closed and non-representable dataset, but feel free to evaluate it yourself if you have some good dataset. You can also easily adapt the probability model of this library if you like. Also, if you find a general improvement of the probability model be sure that it will be implemented in barefoot ASAP. :)

CallumWang commented 6 years ago

Thanks for you explanation about this. I notice that you use this statement: final double base = 1.0 * spatial.distance(predecessors.one().point(), candidates.one().point()) / 60; By this, you mean that the straight line speed between two points is estimated as 60m/s? How do make this decision?