search

valhalla / valhalla

Open Source Routing Engine for OpenStreetMap
https://valhalla.github.io/valhalla/
Other
4.3k stars 661 forks source link

Bidirectional A* Route fails if the best connection is on a shortcut #4527

Open knaveofdiamonds opened 5 months ago

knaveofdiamonds commented 5 months ago

Symptoms

Routes fail with an InvalidUrl error if using the OSRM serializer or "Could not fin candidate edge used for origin/destination label" produced here: https://github.com/valhalla/valhalla/blob/master/src/thor/bidirectional_astar.cc#L1287

This happens rarely - it will be when the connection point between the forward and reverse route is on a shortcut.

Cause

The index stored on the edgestatus for one of the edges has been incorrectly set to 0 (as retrieved here: https://github.com/valhalla/valhalla/blob/master/src/thor/bidirectional_astar.cc#L1189)

This means that the wrong edge is looked for in the find_percent_along method (just whatever the edge is in index 0, I think the connection point rather than the destination edge) so this exception is raised: https://github.com/valhalla/valhalla/blob/master/src/thor/bidirectional_astar.cc#L41

Ultimately this seems to be being caused by this line in ExpandInner: https://github.com/valhalla/valhalla/blob/master/src/thor/bidirectional_astar.cc#L207 - if you comment out this line it fixes the bug.

I don't understand all the logic in this block around why setting kSkipped needs to exist for shortcut edges - why they can't just be treated like any other edge, so I don't know if removing that line has other implications. I'm also not sure how easy it is to create a test case that demonstrates this problem.

nilsnolde commented 5 months ago

yeah I was recently hip-deep in that code and it's quite frustrating as you need to know all the properties and assumptions of those objects (shortcuts etc) which are used there, so it ends being a rabbit hole somewhat. I remember I had a very similar problem when I was porting most of that code to the CostMatrix.

can you include the actual request causing this?

knaveofdiamonds commented 5 months ago

can you include the actual request causing this?

Annoyingly the request that I found that triggers this is one using a custom motorcycle profile, and given the trigger condition for this bug is so sensitive to the exact route (because the 2 routes need to meet precisely on a shortcut) won't be much use to you.

nilsnolde commented 5 months ago

sounds like a pain to reproduce yeah :D fwiw, just finding a connection of both trees on a shortcut should be the norm rather than the exception. a custom profile shouldn't make a difference for the routing algo, I think all sensitive things are const for costing.

in summary, not sure it'll be easy for us to find an example of your observation. it'd greatly accelerate a fix if you'd be able to reproduce this with public code.

nilsnolde commented 5 months ago

one thing that popped up in my mind (but didn't go and check): we need to restore shortcuts when the path is assembled, mostly for guidance purposes. and that particular code to restore shortcut edges has indeed some problems and I'm not sure, but it might actually simply return the shortcut edge in case it couldn't recover anything. in any case, that's likely the culprit.

knaveofdiamonds commented 5 months ago

it might actually simply return the shortcut edge in case it couldn't recover anything. in any case, that's likely the culprit.

This isn't the problem - by the time we get to form path, we essentially only have half of the route because of the incorrect indexes. (Perhaps I should be explicit - I'm not guessing with the chain of logic in the ticket description - I inserted debug logging for the problematic request I made to check).

It would be good to know what the intent/purpose of https://github.com/valhalla/valhalla/blob/master/src/thor/bidirectional_astar.cc#L201-L209 is - can this whole special case for shortcuts just be removed?