Problem with motorway_link

[karussell]

There seems to be something wrong with a snapping of motoway (it uses motorway_link instead):

See discussion here: https://discuss.graphhopper.com/t/4193/

Here is the gpx: file.txt

Will investigate until I can reproduce this in an integration test

[michaz]

Thanks, but not a bug -- this is just what the model does. The quality metric you are using yourself in the screenshot (distance vs. beeline distance) actually gets worse when I force the result to the motorway.

Don't forget the parameters. When I set the measurement error sigma (GPS accuracy) to 10.0, I get the result you are looking for.

Another way of putting it:
In your example, the black line is closer to the motorway_link than to the motorway.
On the other hand, the point (in the middle) is closer to the motorway than to the motorway_link.

The parameter is how important those two criteria are, relative to each other.
"My GPS is very accurate" == "Prefer the road segment close to the input point (even more)"

[michaz]

Perhaps we should emphasize somewhere that sigma is actually an important parameter that changes the behavior of the algorithm. "GPS accuracy" is just .. like.. a justification. It doesn't mean that it must be literally the accuracy of your GPS.

[karussell]

Ah, ok. This makes sense. And the speed is currently not taken into account ... got it.

Let's assume that the user wants to avoid snapping to motorway_link instead motorway and cannot make the error sigma smaller, is there a way to still make it working by e.g. using some custom weighting? Or would something like this only be possible when we additionally take into account the time from the GPS and compare this against the speed (or weighting) stored in the graph?

[michaz]

I think changing the sigma is exactly that custom weighting, for what we can do at the moment.

For sure, "leaving a motorway and re-entering it is unlikely" is a rule that makes sense. (But can't be modelled with this algorithm for the same reason in cannot be modelled in routing -- it requires a memory, or backtracking). Maybe even "faster routes are more likely than slower routes", though I'm not sure how that interacts with the distance criterion.

Let's just communicate that there are trade-offs -- for every rule we put in, we may be overfitting it to a specific case. The next person may actually really drive on the motorway_link for whatever reason, and we wouldn't match it.

[michaz]

(I see a point in the code where extra penalties for such extra rules should go, but that's more a project than a quick fix for this case.)

[michaz]

Opened #149.

[karussell]

And would a rule like "use the time provided from the GPS track and compare it to the estimated times we get from the graph" be possible?

I see a point in the code where extra penalties for such extra rules should go

This would be cool :)

[INRIX-Trang-Nguyen]

Thanks both for looking into issue. I still don't understand is why adjusting the speed of motorway link to a very low value (20 kph) influence the decision, esp since we've selected "FastestWeighting" for route calculations? I've verified that distance for the motorway edge is shorter than the motorlink edge, yet after viterbi, the motorway link is still chosen.

Yes, the results can be influenced by the measurement error sigma but making the sigma smaller would break map matching for trips with high GPS drift and wouldn't work for us since we batch process millions of trips.
At the same time, we would like the ability to influence penalties for certain types of road classifications and can't find an easy way to do this with the current implementation. A future hookin would be very useful but what can be done in the meantime?

As a side comment, the current MapMatching implementation hardcodes the vehicle weighting implementation to FastestWeighting (line 112) rather than using what is configured in AlgorithmOptions. I realize this was a workaround but it doesn't allow customizations of the behavior.

[michaz]

I still don't understand is why adjusting the speed of motorway link to a very low value (20 kph) influence the decision

Don't know about 20kph, but when I set it to a very small value (like 2 kph), the result changes because no route at all is found to points on that road (because we have a search cutoff for time). So the other candidate wins.

I've verified that distance for the motorway edge is shorter than the motorlink edge

The criterion is the difference between road distance and beeline (Euclidean) distance. In the example I am working with, this favors the motorway_link route, because it is less convex, because it is to the left of the motorway, in a left-turn, in a left-driving country. The green line is literally closer in length to the black line that it would be otherwise. By about 4 meters, in the case depicted by the screen shot above.

A future hookin would be very useful but what can be done in the meantime?

The places where your custom criteria should go are computeEmissionProbabilities and computeTransitionProbabilities in MapMatching. The weighting alone doesn't do it, because it is only used to get transition (==route from observation to observation) candidates, not to score them. It is the routing weight, not a map-matching weight. (At least in theory, your mileage may vary.)

Emission probability is the probability of a GPS observation O given that you are on a point on a road S. In our implementation, depends on the distance between O and S. Could be made to depend on road category, too.

Transition probability is the probability of going from S1 to S2 given that being at S1 produced O1 and being at S2 produced O2. In our implementation, this calculates the fastest route from S1 to S2, and then compares its length with the line from O1 to O2.

but what can be done in the meantime?

Hope this helps. Otherwise, if there's a budget, we could work with you on this. Feel free to PM.

[michaz]

To be clear, I agree that the more desirable solution in this case would be the motorway, and I'm not denying that there may be a bug. I'm just still thinking that in this case the model is doing what we think we told it to.

[michaz]

And would a rule like "use the time provided from the GPS track and compare it to the estimated times we get from the graph" be possible?

@karussell I'll pull out the paper again next time I touch this, but I think the authors said that you would need really good estimated times in your graph, otherwise this introduces more noise than it removes.

[INRIX-Trang-Nguyen]

@michaz - thanks for the clarification. I would under the impression that the calculation of transition probabilities would also take into consideration the time from S1->s2 as well but you're right, it only uses the euclidean distance with a slight penalty for u-turns. Perhaps assign a slight penalty based on estimated times or road classifications might help in this case? The distance difference between the motorway and motorway link are very small in many of the cases I've seen.

[INRIX-Trang-Nguyen]

Another possibility is to have the router handle path penalties based on the type of weighting chosen.
Thus, Path could expose a getPenalizedDistance method that can be used to influence viterbi decisions. If weightings could handle u-turns, this would cleanup the extra logic to assign extra penalties for u-turns prior to the computation of transitional probabilities.