Extend routing.xml to represent the routing cost of intersections

[david-gpu]

Describe the idea

In the real world, routing quality is highly dependent on the street intersections found along the way, and a big factor in that is the kind of highways that enter/exit that intersection. For example, an intersection between two residential streets is very different from an intersection between a residential road and a multi-lane secondary road, especially when the user is cycling. And whether the intersection has traffic lights or not is also very important.

As of today, routing.xml has a section called obstacle dedicated to tracking the cost associated with points. However, it only takes into account the tags associated with that point, ignoring completely any highways that enter/exit that point.

Expected behaviour

It would be very useful to add a new section to routing.xml dedicated explicitly to the cost of crossing an intersection. This section would be semantically similar to the existing obstacle section, containing a sequence of select elements, but instead of matching based on the tags of the point, it would match based on the type of highway we are navigating through and the type of highway that intersects our route.

The select element could contain the following attributes:

• value (mandatory): The routing cost associated with this intersection, measured in seconds.
• t (optional; default=match): Key of tag belonging to this point.
• v (optional; default=match): Value of tag associated with key above.
• nav from (optional; default=match): Type of highway that the route is currently navigating through. E.g. residential means we are currently navigating through a way tagged as highway=residential.
• int to (optional; default=match): At least one of the ways that enters/exits this intersection (other than nav) is tagged as highway=<int>. The next way in the route is tagged as highway=<to>.

Here's an arbitrary example that would improve cycling/micromobility safety:

<point attribute="intersection">
    <select value="2" to="residential"/> <-- When our route intersects with a residential road, things are easy -->
    <select value="20" t="highway" v="traffic_signals"/> <!-- Any intersection with traffic signals is fairly safe -->
    <select value="100" to="secondary"/> <!-- An unprotected intersection with a secondary road is undesirable -->
...

Alternatives you've considered

Perhaps an alternative way of representing the cost of traversing an intersection would be changing the semantics of the penalty_transition section, so that the penalty is applied not only when the navigation route enters a particular way, but also when the navigation route crosses an intersection with that type of way.

However, we still need to differentiate between intersections with different levels of safety. For example, an intersection without traffic lights is not as safe as an intersection with traffic lights.

Context

No response

[vshcherb]

There will be definitely some challenges with bidirectional search of A*. Probaly it should be solved differently as introducing artifical points at intersection so penalty could be applied to them. Probablly these could be enhanced with penalty_transition

[david-gpu]

You make a good point about bidirectional search -- I didn't think of that.

Let's use the specific example that I ran into. In this map you can see two different ways to travel West to East:

1. From Kingsdale Ave, across the unprotected intersection with Bayview Ave, towards Wycliffe Cr.
2. From Empress Ave, across the traffic lights at Bayview Ave, towards Citation Dr.

From personal experience, and from the Strava Global Heatmap, it is very clear that the first option is almost suicide and the second option is safe, thanks to the traffic lights. Even cars avoid the first option, even though it is (surprisingly) legal.

I like the idea of creating virtual points to represent intersections. It simplifies the 1-to-N relationship to multiple 1-to-1 relationships, and I think it takes care of the bidirectional routing algorithm as well: you only need to swap the "to" and "from" ways.

Another benefit of these virtual points would be handing the fact that in many parts of the USA and Canada vehicles are allowed to turn right while their traffic light is still red (i.e. right turn on red), so the real-world routing cost of going through an intersection depends on which direction you turn. Each of the options could be represented with a separate virtual point, where the penalty of a right turn on red would be lower than the other options.

[vshcherb]

This definetely should be done on preparation stage data as most routing algorithm are incompatible with neighboring edges penalties like Dijkstra. With new propagateToNodes we could calculate the edges of residential network and then probably add penalty if traffic_signal is not present

[david-gpu]

Let me clarify to make sure we are on the same page. What I'm proposing doesn't require neighboring edges penalties. Instead, the graph would be (virtually?) transformed to replace each OSM intersection (i.e. every point with three or more ways entering/exiting it).

Let me illustrate with the same example as before. This is how OSM looks now; the minor street Kingsdale Ave travels West to East and intersects with a major road Bayview Ave that travels North to South.

And here is how that single intersection point would be (virtually) transformed to represent the different ways one can cross that intersection. I believe this eliminates the need for neighboring edges penalties. What we are doing is transforming an N-to-N intersection into multiple 1-to-1 edges, where each possible way to traverse the intersection can now have a different penalty:

I have placed the virtual points all around so that they are visible on the map, but in the actual implementation they would all be in the same position as the original intersection.

[vshcherb]

that would be even more complicated but first of all each intersection without traffic light should have a special point that penalty could be assigned. Then it should be possible (in future) to apply reduction of penalties if they are consequent, it could be useful for traffic lights as well, however it still sounds very tricky to implement

[david-gpu]

This method doesn't introduce any neighboring edges penalties because the virtual ways that are traversed in order to travel South when you arrive from the West are different from the virtual ways that are traveled when you came from the North or the East. The code only needs to apply a different penalty depending on whether you go straight, turn left or turn right (plus u-turns).

It is not necessary to add any actual points or vertices, even in memory. They are just an abstraction to represent that when you travel from the West and turn South you are following a different "virtual way" to get to the same location.

Let me offer another way of representing these virtual ways which is basically equivalent to what I showed earlier, but perhaps easier to understand. Each virtual way represents one way of traversing the intersection: straight ahead, turn left and turn right.

In other words, if there are N ways that meet at an intersection, you can think of it as having N virtual entry nodes and N virtual exit nodes. Between each virtual entry node and each virtual exit node there is a virtual one-way edge that represents the cost of performing that specific turn at the intersection. It shouldn't affect with any of the existing assumptions in the routing algorithm. It just adds an implicit penalty step that represents the turn:

• When the algorithm is going forwards, it adds the penalty of the turn to the cost of each way of exiting the intersection.
• When the algorithm is going backwards, it adds the penalty of the (reversed) turn to the cost of each way of entering the intersection.

The cost of entering and exiting the intersection is thus performed implicitly and atomically.

For example, if you are coming from the West, there are three ways you can exit the intersection and the turn penalty is accumulated to each of them.

Anyway, I'll leave it there. I'm probably misunderstanding the difficulty of implementing this.