Turn-Restrictions with via ways

[oxidase]

Outcome of discussion with @MoKob:

Tagging scheme of osm restrictions using ways http://wiki.openstreetmap.org/wiki/Relation:restriction#Prohibitory_restriction
OSRM does not handle restrictions ways with via role and
ignores via.way restrictions in RestrictionParser parser
at https://github.com/Project-OSRM/osrm-backend/blob/master/src/extractor/restriction_parser.cpp#L168-L172

For example, in germany-latest there are 1404 such relations with 1331 (95%) one-via-way relations
relations.txt

Possible approaches and their respective drawbacks:

1. modify graph creation
   • hidden turns within the new edges
   • parallel edges -> new edges non start
2. additional contraction
   • contract relation vertices first (breaks contraction order)
   • pass restrictions along to the contraction
   • only allows to handle simple isolated intersections first

For future work:

• longer restrictions (more than one via ways)
• non-isolated restrictions that can have overlapping ways

Related issues:
#483 relation http://www.openstreetmap.org/relation/2339761 has a via node restriction and will not be affected by the change
#2634 https://www.openstreetmap.org/relation/6187972 has one via way restriction and must be fixed with the first step
#1828 looks like an implementation of the first approach

/cc @MoKob

[MoKob]

The aim of this discussion ticket was to have a full overview of the different cases. Without the discussion we had, I don't think that anyone else can follow along the implementation.

We have to flesh out this issue so the approaches are clear.

[oxidase]

The problem statement can be described with the figure

where relation:restriction has way members a (from role), r (via role), c (to role).
The example covers no_u_turn restrictions, like https://www.openstreetmap.org/relation/6413098 ,
but there is a number of multi-via restrictions, like https://www.openstreetmap.org/relation/6210904 that do not allow specific turns.

One possible and straightforward approach is to modify graph creation during the extraction stage and do not include edges that are in restricted paths. This will require an addition of artificial edges for allowed paths. There are some problems besides the big number of additional edges for multi-via restrictions:

• new edges will hide turns, for example turn r-d in the new edge a-e
• additional edges will be parallel to original ones, new edges must not be used as starting edges
  

Another solution proposed by @MoKob is based on removing shortcuts that correspond to restriction relations. The steps are:

• collect restrictions during the extraction stage
• pass restrictions to the contraction
• contract via restriction nodes before other nodes (this will break contraction order)
• if the contractor must add a shortcut that corresponds to from - via - to restricted path
  than do not add the shortcut to the contraction graph

For example, for the restricted path a-r-c, nodes 3 and 4 must be contracted before 1, 2, 5, 6
(the graph has one-way edges for simplicity):

Let say 4 is already contracted. Contraction of 3 without witness paths will create shortcuts
1-6, 5-2, 5-6. Shortcut 1-2 must be ignored, because it corresponds to the restricted path a-r-c.
Afterwards the routing algorithm will not route via the restricted path a-r-c, because the shortcut 1-2 does not exist in the contraction graph.

The problem may occur when the core size is small and a restricted path is not contracted, so internal nodes of restricted relations must be contracted prior to other nodes and must be in the core.
In the limiting case without contraction or if some restrictions are not contracted, the way restrictions check must be performed during the routing stage.

Also contraction of overlapping restrictions, like

with two restrictions e-a-r and a-r-c that have overlapping edges a and r must be handled correctly.
The contraction order of the restrictions internal nodes 2,4,5 can be arbitrary, but filtering must ignore
shortcuts when the restricted path is a subpath in the shortcut. In the example, contraction orders 5-2-4 and 2-5-4 will create a shortcut for path e-a-r-c where restrictions e-a-r and a-r-c are subpaths, so the shortcut 1-3 must not be added to the contraction graph.

[MoKob]

In the lights of having MLD around, we need to rethink how we want to handle these types of restrictions.

Reducing via-ways to via-nodes

Any via-way restriction can be reduced by one in length by replicating some edges and forbidding turns. For example on a one-way restriction, we could add additional edges for all allowed final steps and only allow turning onto them at the first node.

A restriction of (ab) via (bc) to (cd) could be transformed into (ab) via (b) to 2 by adding two additional edges.

This approach does not scale well with multi-hop restrictions, as the number of edges we need to add grows exponentially. The number of long multi-hop restrictions should be small, though.

The obvious benefit of this approach is that it should work both on MLD and CH.
We would have to consider some side-effects though:

• snapping to new edges should never be allowed (by default, if we don't add them to the r-tree)
• guidance needs to consider these duplicated edges (don't make the intersection at b from a 4 to a 6 way intersection)
• ending on bc would be prevented, with the above modelling and would require an additional third road (dead end) not connected to c anymore
• we would have to store meta-data on edges that contain maneuvers

CH

for the CH, the above considerations should still hold true.

MLD

On MLD we could make our base algorithm aware of turn restrictions. As long as we ensure via-ways don't cross border nodes, we could make the base level customisation aware of turn restrictions, just as the unpacker. This would require a deeper state for the search algorithm, though, and potentially multiple different sources a node can be reached from.

E.g. in the above example we would need to be able to reach c from different origins to see if we can reach d.
This would complicate the search algorithm in a way that I don't see promising.

From the current point of view, I would suggest biting the sour grape and to replicate edges in the graph. Most restrictions should be easy enough to get away with a few edges only. We could start of doing single way restrictions and handle these.

[MoKob]

@oxidase I've done some small visualisation to capture what I was talking about before on the call:

As you can see, we require an additional weight for every node based on a possible history.

This kind of method is impossible on CH, since we do not have access to the search history in full.

Ways this could be implemented in MLD do not strike me as favourable, since we would need to be able to access search history of edges hidden in the overlay, whenever a turn is part of a cell border.

We would require storing the last k nodes for every edge in the overlay to see if these k nodes are part of a k way turn restriction.

We would have multiple weights for any node (even though it would be enough to store these for every node that is part of a via-way turn restriction) making the search more complicate.

Will have to give it a bit more though, before I can really say what each approach would fully entail, though.

[michaeltandy]

A few years ago I implemented support for this in a Contraction Hierarchies based pather.

My approach was to pre-process the map, replacing each node of the graph with as many NodeAndState objects as there were states relevant to passing through the node.

The state I tracked included the set of turn restrictions that were active. So for example if there was a turn restriction A->B->C, you could be at node B with the turn restriction active, if you'd arrived from A; or if there was some other way to reach B there would be another NodeAndState without that turn restriction active. (I also used the NodeAndState to keep track of U-turns, use of private roads and suchlike)

Once I'd figured out every NodeAndState it was possible to access and the connections between them, the result was a graph that Contraction Hierarchies would work on just fine.

Anyway, here's my point: You don't have to store a long history just in case there's a long turn restriction - by preprocessing you only need complicate the graph when there are actual turn restrictions that can really be active.

Of course, we can imagine degenerate cases (a huge grid with a hundred turn restrictions per node) but I haven't seen any in the OSM data I've looked at.

[MoKob]

Based on @michaeltandy suggestions, I've drawn up this sketch for duplicating edge-based nodes. This still duplicates edges / nodes, but looks conceptually well suited for implementation on top of the edge base graph factory.

We would require to do the following:

• create restricted edge based nodes based on parent states the node can be reached from (see node and state concept) ($b$ and $b_a$)
  • these nodes might have different states, if they are part of multiple turn restrictions
• on creating the edge based edges
  • ensure that we connect from / to to their respective state-nodes
  • ensure that we connect via nodes (which represent ways) only to allowed successors

The result is essentially the same as in #2681 (comment), reducing the restrictions from via-ways to via-nodes, but conceptually easier, since we don't do it in the node-based graph generation but rather in the edge-based-graph generation.

[MoKob]

On challenge here: conditional via-way restrictions. We currently do not offer any way of detecting these turns onto parallel ways.

[danpat]

Basic support for turn restrictions with via ways has landed with the OSRM 5.10 release.

[danpat]

Conditional restrictions with via ways landed in OSRM 5.11. Closing here, woo!

[MoKob]

@danpat can you branch out a ticket for multi-via-way restrictions?

[danpat]

@MoKob ah, thanks for the reminder, I forgot about that. I've opened #4439, but given how rare those are, I suspect that ticket is going to hang around for a long time.