Complex turn-restriction invalidates edge marked as kPermanent

[purew]

Here's what happens on Bayfront ave in Singapore. The first expansion in forwards search goes for the shortest path and marks the edges as permanent. But at the last turn, the complex turn-restriction no-uturn kicks in and prevents further expansion.

Then, the astar evaluates going west and correctly coming back from the eastward direction. But now it stops because it finds the edge already marked as permanent.

Test-case

curl http://localhost:8002/route --data '{"locations":[{"lat":1.282185,"lon":103.859650,"street":"Sheares Link"},{"lat":1.282493,"lon":103.859421,"street":"Sheares Link"}],"costing":"auto","units":"miles", "date_time": {"type": 1, "value": "2019-05-02T15:00"}}'

Note: The test-case only exhibits this behaviour in timedependant forward search. Bidirectional manages to avoid this deadlock due to expanding from reverse direction.

Proposed solution

We don't mark edges as permanent if they are part of a complex restriction.

[dnesbitt61]

Good catch and an interesting case. However, I don't think it will be sufficient to just not mark this as permanently labeled. The case for temporary labels is such that it replaces the predecessor in the priority queue only if the new path to the end of the edge results in a lower cost than the prior path. I think additional special case logic is required (near line 197 in astar.cc). The problem I see is that if you update the predecessor to allow the alternate path that avoids the Uturn, then you would generate bad paths for any route that just goes right onto Bayfront Ave and continues (not a Uturn).

[purew]

The problem I see is that if you update the predecessor to allow the alternate path that avoids the Uturn, then you would generate bad paths for any route that just goes right onto Bayfront Ave and continues (not a Uturn).

Some more discussion at https://github.com/valhalla/valhalla/pull/2109#pullrequestreview-329361207

[purew]

Addendum

In order to find the optimal path in a situation involving complex restrictions, an edge's status as kPermanent becomes a function of the future path expanded. It becomes prohibitively expensive to fully evaluate this function to find the optimal path which means we need to find an appropriate approximation.

The complete reset of all edges part of the complex restriction (called v2 and implemented in https://github.com/valhalla/valhalla/pull/2109) is a rather aggressive approach. It does ensure a path is found but the path may be sub-optimal.

Alternative approach - v3

@kevinkreiser and I came up with an alternative approach, called v3. V3 would only reset edges on the complex restriction if the edge can be shown to not fork to multiple paths or join from multiple roads.

We can track whether a predecessor edge forks to multiple paths in the Expand* functions, similar to the recently implemented u-turn detection and then set a bit on the predessor. We can track whether a edge joins from mutiple paths by setting the same bit during the EdgeLabel.Update(...) call.

Path forward

We'll merge the currently implemented aggressive approach, called v2 to master to at least produce a path although it may be sub-optimal in some situations.

In a follow-up PR, a two-tiered approach will be implemented: Begin with v3 (which should find the optimal path in many situations but wont find any path in some situations). If this approach fails to find a path (and a complex restriction was encountered) fall back to v2 which should at least find a path.

Addendum v3

Some test-paths considered that v3 would handle:

[purew]

Tracking implementation of version 3 in https://github.com/valhalla/valhalla/issues/2193