Mismatch between /route and /sources_to_targets APIs for "auto" costing model

[AlexandrBasan]

After the last update of Valhalla, we started seeing weird behavior and mismatches between /route and /sources_to_targets APIs for the "auto" costing model. For some reason, the "auto" costing option for the matrix returns nulls. When you build a direct route for "auto," it works fine. It also works for the "truck" costing option for route and for matrix.

Matrix for costing "auto" (does NOT work)
https://valhalla1.openstreetmap.de/sources_to_targets?json={"sources":[{"lat":33.61980715,"lon":-117.6996384}],"targets":[{"lat":33.62013665,"lon":-117.6990124}],"costing":"auto"}

Route for costing "auto" - (works)
https://valhalla1.openstreetmap.de/route?json={"locations":[{"lat":33.61980715,"lon":-117.6996384},{"lat":33.62013665,"lon":-117.6990124}],"costing":"auto","directions_type":"none"}

Matrix - changed to "truck" - (works)
https://valhalla1.openstreetmap.de/sources_to_targets?json={"sources":[{"lat":33.61980715,"lon":-117.6996384}],"targets":[{"lat":33.62013665,"lon":-117.6990124}],"costing":"truck"}

I found similar issues, and we also tried to change kDefaultMaxupTransitions as mentioned in the other issue, but without much success. Any help is appreciated!

[lexxanderdream]

I have a similar problem. On the new version, approximately 1-2% of stops (US) are not available when calculating the matrix. But they are available when make a single route. I can provide specific examples if needed.

[nilsnolde]

I did a LOT of work recently on that algorithm (full refactor, lots of new features) and it's totally possible that some edge cases are screwed up. I'm still in the process of more enhancements, I might look into this before digging any possible hole even deeper.

Can you somewhat pinpoint when things started not working? What was the "version" (probably commit?) you were using before?

[lexxanderdream]

Can you somewhat pinpoint when things started not working? What was the "version" (probably commit?) you were using before?

Sorry but I couldn't determine the version, we are using gis-ops docker valhalla image since October 10, 2023. Everything worked well in this version. About a month ago we decided to upgrade, installed the latest version on the new server and started having problems with it.

[nilsnolde]

Dates are even better. That was before most of the work I did I think. But it'll still be easy to replicate, the OP has very minimal examples. I'll get to that tmrw hopefully.

[nilsnolde]

found the problem: your set of coordinates wants to get from a road onto a parking area in front of a supermarket or so. the problem is that the way leading onto the parking area is tagged with service = driveway out of which Valhalla makes a "destination-only" edge. we don't allow expansion over destination only edges on a first pass and as it happens the destination is trapped inside a region cut off by destination-only edges so it can't ever leave there and forward expansion can't enter there for the same reason.

however, we do allow routing over destination-only edges in a second pass (which is why routing those works). recently I added that ability to the CostMatrix algorithm as well, so if you put thor.costmatrix_allow_second_pass: true into your config and restart the service, it'll work.

do note, this is a mapping error, valhalla is doing the right thing here. service = driveway is not correct here, see https://wiki.openstreetmap.org/wiki/Tag:service%3Ddriveway:

When not to use the service=driveway tag:
Paths in or around a parking lot (amenity=parking) are tagged with highway=service without service=* on the entrance and exit ways, as well as any way that forms the "trunk" or perimeter of the lot, connecting multiple parking aisles (service=parking_aisle).

[nilsnolde]

do feel free to post other matrix requests which are failing with that config option and we'll re-open here.

I probably changed smth while doing the big CostMatrix refactor. sounds like it's now doing the right thing though.

[nilsnolde]

hm, I kinda question the "right thing" in how we handle destination-only. we also have a (undocumented) request option to penalize those edges. I wonder if the penalty (default 10 mins IIRC) is not enough and we could actually allow them on a first pass as well? I think @dnesbitt61 was questioning that too somewhere sometime. what do you think @kevinkreiser ?

[lexxanderdream]

@nilsnolde Thanks a lot for your help! I changed the config option and now it works. Will this have a significant impact on slowing down performance? or any other qualities of work?

I have another example in suburban area, that worked in the previous version, but does not work in the new one.

Matrix:
https://valhalla1.openstreetmap.de/sources_to_targets?json={"sources":[{"lat":41.230756,"lon":-77.433095}],"targets":[{"lat":41.23343,"lon":-77.42725}],"costing":"auto"}

Route:
https://valhalla1.openstreetmap.de/route?json={"locations":[{"lat":41.230756,"lon":-77.433095},{"lat":41.23343,"lon":-77.42725}],"costing":"auto","directions_type":"none"}

I also began to notice an error in the logs when building a route between these points:
2024/03/15 07:31:13.059208 POST /route HTTP/1.1
2024/03/15 07:31:13.059405 [INFO] Got Loki Request 7
2024/03/15 07:31:13.060292 [INFO] Got Thor Request 7
2024/03/15 07:31:13.060380 [INFO] algorithm::bidirectional_a*
2024/03/15 07:31:13.060795 [ERROR] Forward search exhausted: n = 2,2
2024/03/15 07:31:13.061040 [INFO] algorithm::bidirectional_a*
2024/03/15 07:31:13.061360 [INFO] Got Odin Request 7

Is it related to the same problem? This is a very trivial route.

[nilsnolde]

This is a very trivial route.

"trivial" routes are the nemesis of bidirectional search 😄 you'll notice that bicycle will work as /route does, because it's using a unidirectional matrix algorithm.

it'd be perfect if you could paste a link to https://valhalla.openstreetmap.de/ as well for the waypoints.

[nilsnolde]

ah, what's likely happening here: also bidir a* probably can't find the connection on the forward tree (which is exhausting) but on the reverse tree. I bet the same is true for matrix: try thor.costmatrix_check_reverse_connection: true. now that will decrease performance by a significant chunk. but it's the nature of the problem, either one lives with some unconnected pairs for some edge cases or swallows some performance degradation. fwiw, #4613 will more than make up for that loss of performance.