Graphhopper: Rare bug for stall on demand

[karussell]

Currently I'm facing an issue when stall_on_demand=true (if false it disappears). It is very rare and hard to reproduce in a unit test.

The reason is likely in DijkstraBidirectionCH.entryIsStallable:

adjNode.weight + weighting.calcWeight(iter, !reverse, getIncomingEdge(entry)) < entry.weight

It returns true although it should return false. In my case it is the 4th decimal place: 35.643+50.2975 < 50.297522

So, when I round to the precision we currently use in CHGraphImpl:
Math.round(entry.weight / 1000f) * 1000f
the problem disappears. But maybe it is related to virtual nodes because the special case is a QueryGraph with 3 locations where the fastest route B->C crosses point A.

[easbar]

Thanks a lot for debugging, I am sure this took a lot of time to figure out!
Quite suprisingly I think I ran into the same issue recently and could narrow it down to this:

map: core/files/andorra.osm.pbf
query: `http://localhost:8989/maps/?point=42.486984%2C1.493152&point=42.479849%2C1.49162&point=42.494536%2C1.499766&locale=en-US&vehicle=car&weighting=fastest&elevation=false&stall_on_demand=true&use_miles=false&layer=Omniscale`

I used (not sure if this plays a role):

  prepare.min_network_size: 200
  prepare.min_one_way_network_size: 200

It is also related to the via point (removing it or even changing the order of the points) makes the problem dissapear, just as well as setting stall_on_demand to false.

Interestingly this problem does not happen on more recent versions of the same map (the oldest I found was still from 2018), so might be an option to diff the maps to see what has changed.

If it turns out that the problem is due to the floating point number comparison I think we could simply use some epsilon in the above condition.

So, when I round to the precision we currently use in CHGraphImpl:

Exactly which numbers did you round ?

[karussell]

Interesting, indeed :) !

Exactly which numbers did you round ?

I meant that I used

adjNode.weight + weighting.calcWeight(iter, !reverse, getIncomingEdge(entry)) < Math.round(entry.weight / 1000f) * 1000f
// (We could also use `entry.weight - 1/1000f`)

instead of

adjNode.weight + weighting.calcWeight(iter, !reverse, getIncomingEdge(entry)) < entry.weight

The reason for the 1000f is the precision we use for the shortcut weight in CHGraphImpl. I also think that we could reduce the chance that this happens via increasing the precision of the shortcut weight - see #1544.

Another wild guess for the reason: the shortcut weight precision is limited to the 1000f compared to the very precise weight calculated from two VirtualEdgeIteratorState's?

[easbar]

Another wild guess for the reason: the shortcut weight precision is limited to the 1000f compared to the very precise weight calculated from two VirtualEdgeIteratorState's?

I also remember recently having problems with virtual edges that did not seem to have the right distance (I'm on it :))

[easbar]

I have a failing integration test here: https://github.com/graphhopper/graphhopper/tree/issue_1574

There are many ways to make it pass:

• as @karussell suggested fixing the stall on demand condition (rounding)
• do not add geometries during parsing the map
• do not set roundabout bits during parsing
• increasing the min subnetwork size

I have tried to reproduce the problem by building the graph manually using graph.edge... using the output of GHUtility.printGraphForUnitTest, but unfortunately to no avail so far :(

[easbar]

Math.round(entry.weight / 1000f) * 1000f

It should be Math.round(entry.weight*1000f)/1000f, probably what you meant. The other formula returns zero for all weights < 1000, so basically always (-> nothing gets stalled).

Anyway I am now 99.9% sure think I finally understood the problem and it is related to CH/stall-on-demand and virtual via nodes. Removing the geometries, not using the roundabout bit or using another subnetwork size only fixes the problem because another hierarchy is created I guess.

[karussell]

probably what you meant.

Ups! Sure!

I have a failing integration test here: https://github.com/graphhopper/graphhopper/tree/issue_1574

Great. Will also have a look and guess about it

[easbar]

I could reproduce the bug in a unit test with only 8 nodes, it is quite involved.

https://github.com/graphhopper/graphhopper/blob/f63b30ccbf37d9558c830b61a7608d3bc19b4a2c/core/src/test/java/com/graphhopper/routing/ch/PrepareContractionHierarchiesTest.java#L425-L434

[easbar]

I am wondering if an option would be to set the CH level of virtual nodes to the minimum CH level of their neighbornodes (can be virtual nodes as well). Right now we do this (imagine the vertical position to represent the CH level) and x to be virtual nodes (could be multiple).

  a             
            b
    x x x

which allows going 'down' from a to b, because of the virtual node(s). so instead do this:

   a          
    x x x b     

This way the virtual nodes should not change the behavior of CH ? Another way would be to ignore via virtual nodes completely: first find the closest 'real node' from virtual start/target nodes on the query graph, then run CH on the plain CH graph (without virtual edges). Finally we could of course try to fix the rounding in certain places...

[karussell]

I could reproduce the bug in a unit test with only 8 nodes, it is quite involved

Really great you got something recreated :+1:

I am wondering if an option would be to set the CH level of virtual nodes to the minimum CH level of their neighbornodes

Sounds reasonable but why would this fix the problem? Isn't this even more restrictive?

first find the closest 'real node' from virtual start/target nodes on the query graph, then run CH on the plain CH graph (without virtual edges)

This is cumbersome. I tried this for non-CH (i.e. without the QueryGraph logic) but the search got too complex. Best thing would be of course we could hide the virtual node complexity for the algorithms (but this is also not fully possible for landmarks)

Update:

Sounds reasonable but why would this fix the problem? Isn't this even more restrictive?

Ah, you mean that the search from b can proceed after x x x and finds a and does not has to wait until the forward search from a comes to the first x? This sounds indeed better. Still it seems to be only necessary if we don't take into account the rounding.

Update:

Still it seems to be only necessary if we don't take into account the precision for the SOD condition.

It looks like your test case breaks SOD (returns true for 3->0) even with Math.round(entry.weight)! So the rounding problem there can't be the reason but the LevelEdgeFilter for the virtual nodes does also not cause the problem as the branch for the virtual nodes is never called in that case.
Ok, the rounding works if we exclude visiting the same edge in entryIsStallable.

Update:

The problem is that due to the virtual nodes we traverse to lower level nodes (assumed level is infinity, due to 'always accept'). In correct CH we would never get to those nodes. And this mistake leads to a wrong decision when doing the stalling. This case happens only when the rounding of the shortcut weight is smaller than the path with the (higher precision) virtual edges but then leads to "connection not found" as the stalling stops further traversing based on incorrect information.