Prevent u-turns at tower nodes that are connecting different OSM ways

[camelCaseSucks]

This route includes an illegal u-turn in the middle of the bridge

https://graphhopper.com/maps/?point=45.501467%2C-122.661254&point=45.501237%2C-122.66142

OSRM returns the expected route

https://www.openstreetmap.org/directions?engine=fossgis_osrm_car&route=45.5015%2C-122.6613%3B45.5012%2C-122.6613

[easbar]

Thanks for reporting!

This seems to be a u-turn, because if I set u_turn_costs to infinity I get the same route as on OSRM:

https://graphhopper.com/maps/?point=45.501467%2C-122.661254&point=45.501237%2C-122.66142&ch.disable=true&u_turn_costs=-1

Apparently there is a tower node in the middle of the bridge, even though there is no junction. There is a region border though:

@karussell any idea why we get a tower node here?

Btw: I ran into another problem: When I click on the above link (in @camelCaseSucks comment) and then change the vehicle to foot and back to car again I get another route once again, because for some reason turn_costs=false is appended to the url...

[karussell]

@karussell any idea why we get a tower node here?

No, this looks strange. As this is the main issue for me here - should I rename the issue title?

because for some reason turn_costs=false is appended to the url...

outch, this is likely yet another bug in the UI :/

[otbutz]

@karussell any idea why we get a tower node here?

https://www.openstreetmap.org/way/587574521

[easbar]

https://www.openstreetmap.org/way/587574521

What do you think is suspicious here?

[otbutz]

It might be the line crossing the bridge

[easbar]

It might be the line crossing the bridge

Yes, it really looks like it is :) But this is just a region border, so it should not even be considered by our OSM parser? If it was a ferry I would totally understand what happens because this would create a 'ghost junction' : #1858

[boldtrn]

Isn't it because the way in OSM is cut at the region border, so we get a tower node by definition? If one wants to avoid that, you would have to merge the features in OSM.

[easbar]

When GH parses OSM it first checks which of the nodes are really junctions (it counts how many ways there are for every node). And only for real junctions (>2 ways) a tower node is introduced. Otherwise the ways are simply merged into one GH edge (at least this is what I thought so far). But sure you are right this merging would only work if the tags were the same. However, here it looks like they are:

https://www.openstreetmap.org/way/123374695

vs

https://www.openstreetmap.org/way/587574521

But I am pretty sure there are similar cases where the tags are different and then we would have the same problem despite the merging.

[karussell]

Ah, yeah. This is the reason ...

And only for real junctions (>2 ways) a tower node is introduced.

... as soon as 2 ways use the same node a tower node is introduced: https://github.com/graphhopper/graphhopper/blob/master/reader-osm/src/main/java/com/graphhopper/reader/osm/OSMReader.java#L550

and there is no merging code. And even if such merging code would exist the question is really how we could avoid tower node creation when the tags would be different.

Related #758

[easbar]

and there is no merging code

Ah ok so we never merge multiple ways, but we make sure that we do not split single ways when there is no real junction (and use pillar nodes instead). I think this is where my confusion came from.

Ok so in summary the problem is that there can be u-turns at nodes that are not junctions, simply because they connect two OSM ways.

[karussell]

We might have to rethink about when we can allow U-turns because this depends on many things like the vehicle, the circumstances at the junction, the road class (or width), the traffic (or average/max speed) and other things.

We partially already do that when we say that a U-turn is only possible at junctions (due to the space) but we do not make it vehicle-dependent which should be easy as well (e.g. motorcycle vs. car vs. bike). And the road-property-dependency is likely even more important (but probably a bit trickier to implement). E.g. in this issue here it is a primary road and we could say we do not allow U-turns even for junctions (at primary roads)?

[easbar]

Yes we definitely should make this more specific. This probably will decrease performance, but certainly leads to higher quality routing. For the present case we could use road_environment (no u-turns on bridges, ever)? But really we should probably start with a list of cases where u-turns should / should not be allowed (and at which cost).

[otbutz]

... as soon as 2 ways use the same node a tower node is introduced: https://github.com/graphhopper/graphhopper/blob/master/reader-osm/src/main/java/com/graphhopper/reader/osm/OSMReader.java#L550

and there is no merging code. And even if such merging code would exist the question is really how we could avoid tower node creation when the tags would be different.

So any street which is split up in multiple connected OSM ways is going to produce tower nodes at its joints?

[karussell]

At the moment we create a tower node as soon as an OSM node is used from two or more OSM ways (or if it is terminal). This already depends on the vehicle, i.e. if just car is configured then only car-accessible OSM ways are considered.

[otbutz]

Would it make sense to mark tower node candidates if they're used by exactly two ways and demote them in cases like this one?

[karussell]

It surely reduces the number of edges (but by how much?) but I'm unsure if it is worth the effort. Additionally it won't help in many other scenarios to prevent U-turns.

[boldtrn]

I proposed such a merging algorithm several years ago (I'd say 4-5 years ago). I had a working prototype. I remember that the number of reduced edges was not that big (I think it was <5%). At this time this did not consider relations like turn restrictions etc. which would further reduce this. That said, I think this would be an interesting feature. Unfortunately, I can't find the discussion anymore, it was here in Github, IIRC in a PR of mine.

[boldtrn]

Ah, I was able to find it: https://github.com/graphhopper/graphhopper/issues/69#issuecomment-279610098

Here is the link to the commit: https://github.com/boldtrn/graphhopper/commit/362bea4d015b9973f17aae920f45a30a205be6b2

I didn't actually contracted anything, I just hacked a counter that counts how many edges could be contracted. Sorry if I raised any false hopes :). Back then we tested it for worldwide and saw 4% contractable edges.

[easbar]

That said, I think this would be an interesting feature.

Why do you think the merging would be an interesting feature? Because it might improve performance? Or because it prevents unnecessary u-turns? Or instructions? Or do you mean a better u-turn handling would be interesting? To me it seems like the most important part is the u-turn handling and merging some edges with identical tags would only be a part of the solution (at best). But maybe it has other advantages.

[boldtrn]

It always bothered me in OSM if ways are split without a good reason, and I merged quite few over the years by hand :). So I do have a history with that issue. I agree better u-turn handling would be awesome, but we might be able to handle this differently as well.

I gave this a bit more thought. I fear automatic merging might create issues with things like SpatialRuleLookup. The edge we discussed above is cut at a region border. If we would be using a SpatialRuleLookup for these regions, we could tag one part of the way to region A the other part of the way to region B. If we merge these roads, this is not that easy anymore.

[otbutz]

I gave this a bit more thought. I fear automatic merging might create issues with things like SpatialRuleLookup. The edge we discussed above is cut at a region border. If we would be using a SpatialRuleLookup for these regions, we could tag one part of the way to region A the other part of the way to region B. If we merge these roads, this is not that easy anymore.

Is this really an issue? Streets which are crossing country borders will very likely differ in tags and shouldn't be merged. If we end up introducing more finegrained rules e.g arbitrary user defined regions, the OSM material won't fit those borders either way.

Edit: example for a street crossing a country border: https://www.openstreetmap.org/way/37702141#map=19/49.20374/6.95871

[boldtrn]

Streets which are crossing country borders will very likely differ in tags and shouldn't be merged

For major roads crossing a country this is probably not an issue. But when you use other regions, like states or smaller regions like municipalities, this might be.

Also smaller roads crossing a country might be different, and are often not even cut at the border.

https://www.openstreetmap.org/way/106628707 https://www.openstreetmap.org/way/380937474

If we end up introducing more finegrained rules e.g arbitrary user defined regions, the OSM material won't fit those borders either way.

Yes they won't always, but when we merge them on top of this, ways get longer and harder to classify.

But yes, it might be an edge case.

[dbadura]

Hello, I found similar problem on road with several ways.

Bad: https://graphhopper.com/maps/?point=50.223965%2C18.990002&point=50.221075%2C18.989643&locale=pl&elevation=true&profile=car&ch.disable=true&use_miles=false&selected_detail=Elevation&layer=Omniscale Good: https://graphhopper.com/maps/?point=50.223965%2C18.990002&point=50.221075%2C18.989643&locale=pl&elevation=true&profile=car&ch.disable=true&use_miles=false&selected_detail=Elevation&layer=Omniscale

[JakeSmarter]

There is more stuff like this: In this case, routing should either calculate a loop or a route to the nearest turning circle, like that at the end of “Winding Wood Court”.

I can only urge you to fix this asap because for years now people, especially novice OSM contributors like all kinds of delivery and ride sharing drivers, have been fixing the map by adding non-sense no_u_turn restriction relations with identical ways in the from and to roles. And, it is very difficult to explain to people

1. that there is nothing wrong with the map but their routing algorithm is broken,
2. what exactly turn restriction relations are in OSM,
3. what turn restrictions are for in OSM, and
4. what they are not for.

Things go even so far as that companies like Lyft hire masses of more or less oblivious people to map no u-turn traffic signs with turn restriction relations, while not understand and not explaining to their payed mappers that turn restriction relations only map the flow of traffic instead of the legal situation on the road (like traffic_signs do).

Because of all of the above, you can find more and more things like this in the OSM database: I do not know how difficult it is to fix this but please please fix it because the OSM database gets littered with superfluous and broken turn restriction relations by oblivious and novice contributors (and even commercial “contributors”).

[easbar]

Thanks for your input, I will take a look at this. IMO one big problem with turn restriction mapping is also this (still uncommented) issue: https://github.com/openstreetmap/iD/issues/9346

[easbar]

In this case, routing should either calculate a loop or a route to the nearest turning circle, like that at the end of “Winding Wood Court”.

From the algorithmic point of view this problem is already solved. GraphHopper accounts for the time it takes to do u-turns at a junction or the end of a dead-end street. It will then decide whether it is better to do such a u-turn or some kind of loop etc. should be used. In the present example it suggests the u-turn. I tried this for different values of the u_turn_costs parameter and it seems that above a value of 80 it suggests another route:

Here is another (live) example:

What is not so clear, though, is at which junctions it is possible to do a u-turn and how long it would take to turn around at a specific junction. This is less of an algorithmic, but more of a data issue. So far GraphHopper uses the same u-turn costs for every junction and every end of a dead-end street. Which OSM tags do you think can be useful to improve on this? Turning around at the end of 'Winding Wood Court' seems reasonable, but unfortunately the (node) tag turning_circle is currently not considered by GraphHopper. Reducing the u-turn-costs at turning_circles would certainly be an improvement and likely fix your present example. However, this tag isn't used very often. Currently there are only around 7100 cases on taginfo.

while not understand and not explaining to their payed mappers that turn restriction relations only map the flow of traffic instead of the legal situation on the road (like traffic_signs do).

Which OSM wiki are you referring to here, and when do you think traffic_sign should be used over a restriction relation? Which values of the traffic_sign tag do you think are relevant for turn restriction aware routing?

Btw if you have more examples like these, please share them.

[JakeSmarter]

Thank you @easbar for your extensive answer. I like that. It shows that you are taking this issue seriously, and rightly so because imho this has gotten out of hand. I am not sure how many other routers are affected but Graphhopper seems to have many big scale customers which leads to the aforementioned consequences of “novice mappers fixing the map”.

From the algorithmic point of view this problem is already solved. GraphHopper accounts for the time it takes to do u-turns at a junction or the end of a dead-end street. It will then decide whether it is better to do such a u-turn or some kind of loop etc. should be used.

:+1: for covering this algorithmically! However, imho no amount of “time saving” cost is going to outweigh the cost of an accident.

In the present example it suggests the u-turn. I tried this for different values of the u_turn_costs parameter and it seems that above a value of 80 it suggests another route

I do not know what the upper limit for u_turn_costs is but in my understanding it should be set to the upper limit by default. Why? Simply because of safety considerations, it is almost always a bad idea to suggest a U-turn to any driver at any arbitrary junction node. Sure, in the handful of cases left from ”almost always” users should be able to tweak a U-turn cost parameter, if they really have to and know what they are doing. But again, (I do not have any hard evidence numbers) in about 99.9 % of use cases users do not need to and should not tweak such a parameter. Reality proves that almost no user is aware that such a parameter exists or even what it does. Hence, people start “fixing the map”.

Imho, costing a U-turn even in jurisdictions that allow a U-turn at a junction by default is still a dangerous idea, and a futile one at best. Why? Because as you have mentioned yourself, the data simply does not exist to make a safe assumption and consequently do proper safe costing.

What is not so clear, though, is at which junctions it is possible to do a u-turn and how long it would take to turn around at a specific junction. This is less of an algorithmic, but more of a data issue. So far GraphHopper uses the same u-turn costs for every junction and every end of a dead-end street. Which OSM tags do you think can be useful to improve on this?

I do not think you should try or even can solve this problem with any tag or mapping scheme. Think about it, mappers would have to pre-cost every node on its potential for a safe (and swift) U-turn for every type of vehicle. The shear amount of data and man hours you would require renders this approach unfeasible. So, imho this is a dead end.

But, if you really want to know, in order to serve those 0.1 % of user cases, they could use a tag like u_turn_cost=0…1. Still, I do not think this would be a reasonable nor fair thing to do.

Turning around at the end of 'Winding Wood Court' seems reasonable, but unfortunately the (node) tag turning_circle is currently not considered by GraphHopper. Reducing the u-turn-costs at turning_circles would certainly be an improvement and likely fix your present example.

So, my advice would be to set the u_turn_costs parameter to its upper limit by default first. Not because it is my opinion but because it is the safe thing to do and because this is what most users’ natural and intuitive assumption is. And second, lets definitely make Graphhopper consider (or cost adequately) turning_circle and turning_loop, maybe also junction=roundabout ways and highway=mini_roundabout nodes.

Which OSM wiki are you referring to here…

I cannot direct you to a specific section in the OSM Wiki. It is just that when you take some time to think about these things you get to certain conclusions. A few OSM contributors have written very interesting and helpful blog posts especially about the application of turn restrictions. If I could only find these again… Neither they nor I claim to be completely correct regarding turn restrictions but we are getting close. It might be a good idea to extend the description of turn restrictions in the OSM Wiki with these considerations.

Anyhow, I still want to answer your questions as far as I can and time permits: By their very nature traffic signs represent the legal situation on the road .

when do you think traffic_sign should be used over a restriction relation?

It depends on what you are trying to map. Do you want to map, or in other words, model the flow of traffic? Then use a turn restriction relation. However, you have to consider that you are just modelling here, not mapping the legal situation. Why is this so? Because you can model the legal situation on the road with different equivalent turn restrictions. A or exactly one turn restriction can model the exact legal effect but it does not have to.

But, if you want to map the legal situation on the road then use the traffic_sign tag. Why? Because by their very nature traffic signs have legal effect. Simply put, one should be aware whether one maps legal data or an effect of legal data. Sometimes, one does both at the same time, sometimes not. Most often, like in the case of turn restrictions, one wants to map legal effects but often enough people map/model legal data.

Which values of the traffic_sign tag do you think are relevant for turn restriction aware routing?

Due to the traffic_sign’s value syntax it depends on the jurisdiction of the traffic sign. For example, in the US you could have values like (including but not limited to) US:R3-1, US:R3-2, or US:R3-4. Generally speaking, mapping traffic signs for routing will not be very helpful. Not only because of the syntax but mainly because when you are mapping for routing you are interested in representing or modeling the flow of traffic.

Having said that, people should still not map a legal no U-turn restriction designated by traffic sign with a no_u_turn relation with identical ways in the from and to roles because it does not help any safe and sane routing algorithm. Yes, it may help in those 0.1 % cases where users want U-turn costing below u_turn_costs’ upper limit but just the relation’s data cost is totally unfair to the other 99.9 % of users. Besides, as you have already mentioned, users who want U-turn costing not only should but have to use far more data to get to a sane and safe u_turn_costs value. So, littering a no_u_turn restriction relation into the OSM database at any arbitrary junction node just because some routing algorithm is not good enough, one does not have, or is unable to aquire enough other data for estimating one’s U-turn cost is just lazy (or lame excuse) for overburdening the OSM database (and the vast majority of other users). No offense please, I am not talking about just Graphhopper here. This applies to every routing algorithm using the OSM database. In other words, routing algorithms should not offload their shortcomings on the map (database) nor their users. Neither should users feel the need to “fix the map” because their routing algorithm does not behave intuitively.

[JakeSmarter]

Reducing the u-turn-costs at turning_circles would certainly be an improvement and likely fix your present example. However, this tag isn't used very often. Currently there are only around 7100 cases on taginfo.

:open_mouth: Last time I checked there are 2,212,841 turning_circle nodes and 154,949 turning_loop nodes.

[JakeSmarter]

Thanks for your input, I will take a look at this. IMO one big problem with turn restriction mapping is also this (still uncommented) issue: https://github.com/openstreetmap/iD/issues/9346

Oh sure, inadequate tools do not help much either. :wink: But, I do not blame iD (or any other editing tool) nor think that’s the core problem here because sooner or later novice contributors get the hang of it and create complete routing effective turn restriction relations. The point here is that they have no idea how routing works nor that there is costing involved especially for U-turns.

Now, I understand the dilemma for delivery app developers; where they have to compute a global optimal multi-stop route first with U-turn cost set to 0, and then break up the multi-stop route into local sub-routes with some safe and reasonable U-turn cost value. But again, imho u_turn_costs should default to its upper limit or just below the cost of a turning_circle or turning_loop. I am sorry, should I have mixed up the order of comparison. I hope you get what I mean. :wink:

[easbar]

leads to the aforementioned consequences of “novice mappers fixing the map”.

Do you have some examples/links to OSM where we can see such fixes? I found one here: https://www.openstreetmap.org/relation/13045491, but it is already one year old.

for covering this algorithmically! However, imho no amount of “time saving” cost is going to outweigh the cost of an accident.

If we did not cover this algorithmically we wouldn't be able to calculate such routes at all. There can always be situations where u-turns are the only possible option, like a curbside constraint pointing towards the end of a dead-end street: One has to turn around to get out of such a street again, otherwise we would not find a path at all. This is the reason the u_turn_cost parameter cannot be infinite.

But I see your argument that at least for navigation applications it might very often be better to suggest some kind of 'loop' rather than doing a u-turn.

I do not know what the upper limit for u_turn_costs is but in my understanding it should be set to the upper limit by default. Why? Simply because of safety considerations, it is almost always a bad idea to suggest a U-turn to any driver at any arbitrary junction node.

There is no real upper limit and at least in theory it can be set to a very large, but finite, value. Actually I thought the (hosted) GraphHopper API already uses a very large value, but there seems to be another issue with this that makes the algorithm behave as if it was smaller. We are currently investigating this. And again, I think I mostly agree that suggesting some kind of loop is better than suggesting a u-turn.

Sure, in the handful of cases left from ”almost always” users should be able to tweak a U-turn cost parameter, if they really have to and know what they are doing. But again, (I do not have any hard evidence numbers) in about 99.9 % of use cases users do not need to and should not tweak such a parameter. Reality proves that almost no user is aware that such a parameter exists or even what it does. Hence, people start “fixing the map”.

This is mostly a server-side parameter that (client-side only) users can not change. The u-turn costs can be changed per request for our flexible algorithms, but in most cases they will be fixed for each profile.

I do not think you should try or even can solve this problem with any tag or mapping scheme. Think about it, mappers would have to pre-cost every node on its potential for a safe (and swift) U-turn for every type of vehicle. The shear amount of data and man hours you would require renders this approach unfeasible. So, imho this is a dead end.

I'm not sure about this. Of course mapping the costs explicitly for each node won't be possible, but for example the highway tag could be an indicator to figure out if doing a u-turn is feasible or not, but yes, it won't be a good fit in every case.

For a safe and/or comfortable driving experience I think applications need to find a good way to tell drivers they need to turn around at the next suitable spot, and not just show them the next turn of the calculated route. Say, for example the route contains a u-turn (or some loop that avoids it), then an informed driver can find the next spot where this is possible and turn around instead of blindly following the route.

So, my advice would be to set the u_turn_costs parameter to its upper limit by default first. Not because it is my opinion but because it is the safe thing to do and because this is what most users’ natural and intuitive assumption is.

Yes, like I said, I think I agree the value should be rather high, because a higher value leads to long loops in the worst case, while a too low value can lead to impossible u-turns and drivers will be left with a route they cannot follow.

And second, lets definitely make Graphhopper consider (or cost adequately) turning_circle and turning_loop, maybe also junction=roundabout ways and highway=mini_roundabout nodes.

I already started implementing this for nodes tagged as highway=turning_circle and highway=turning_loop here: #2761

I cannot direct you to a specific section in the OSM Wiki. It is just that when you take some time to think about these things you get to certain conclusions. A few OSM contributors have written very interesting and helpful blog posts especially about the application of turn restrictions. If I could only find these again… Neither they nor I claim to be completely correct regarding turn restrictions but we are getting close. It might be a good idea to extend the description of turn restrictions in the OSM Wiki with these considerations.

Ok, I think if you are concerned about what is currently being mapped in OSM I think you really need to engage with the mapping community and make sure their opinion is clearly stated in the Wiki. If there is no consensus written down as OSM Wiki how can mappers agree about what to do. Everybody might get to their own 'certain conclusions'. From my data consumer / routing point of view I'm happy to help figuring out what kind of tagging is useful for routing applications, but ultimately this needs to be written down in the wiki.

Generally speaking, mapping traffic signs for routing will not be very helpful. Not only because of the syntax but mainly because when you are mapping for routing you are interested in representing or modeling the flow of traffic.

Typically, OSM mapping shouldn't be done for routers specifically, but turn restrictions might be an exception, because routing is the only reason turn restrictions are mapped at all? So far GraphHopper does not make use of traffic_sign mapping, but only considers turn restrictions. With regards to u-turns it comes down to the question what is the default. We could either assume doing a u-turn is possible everywhere unless there is a no-u-turn instruction. This corresponds to a small (global) u-turn cost and tagging no-u-turn will be useful or even necessary. Or we could assume that doing a u-turn is basically never possible, which corresponds to a large (global) u-turn cost. In this case no-u-turn relations will hardly ever be needed or useful. At first sight it seems logical to add no-u-turn tagging to OSM, because there are traffic signs that indicate this (just like for normal turn restrictions), but tagging this everywhere to satisfy the routers, even in places where there is no 'no u-turn' sign, would be the wrong thing to do.

Do you suggest that:

• routers should try to avoid u-turns as much as possible by default everywhere, including at junctions where there is no traffic sign or turn relation (a large u_turn_cost parameter in our case)
• restriction relations should mostly be used for left/right/normal turns, but not really for u-turns?
• no-u-turn traffic signs can still be mapped using the traffic_sign tag in OSM for completeness, but they won't really be used by routing software

That would sound reasonable to me.

Having said that, people should still not map a legal no U-turn restriction designated by traffic sign with a no_u_turn relation with identical ways in the from and to roles because it does not help any safe and sane routing algorithm.

Yes, I agree. However, the situation is different for turn relations with via-ways that are used to represent no-u-turn signs between different lanes, but you already excluded these, because in this case the from and to roles will be different as well.

No offense please, I am not talking about just Graphhopper here. This applies to every routing algorithm using the OSM database. In other words, routing algorithms should not offload their shortcomings on the map (database) nor their users. Neither should users feel the need to “fix the map” because their routing algorithm does not behave intuitively.

Yes, but GraphHopper really cannot be blamed here, because currently it even ignores no_u_turn restrictions: https://github.com/graphhopper/graphhopper/issues/2570. So if somebody tries to fix an unwanted u-turn by adding such a no_u_turn restriction to OSM (an unmodified instance of) GraphHopper will still suggest the u-turn.

open_mouth Last time I checked there are 2,212,841 turning_circle nodes and 154,949 turning_loop nodes.

Yes, sorry, my bad. Maybe I was looking at ways using these tags, not nodes, or something.

Oh sure, inadequate tools do not help much either. wink But, I do not blame iD (or any other editing tool) nor think that’s the core problem here because sooner or later novice contributors get the hang of it and create complete routing effective turn restriction relations. The point here is that they have no idea how routing works nor that there is costing involved especially for U-turns.

The problem here is that unaware iD users destroy restriction relations, because once they modify ways the (almost invisible) turn relations become stale and there is not even a warning that indicates this. I think this is unfair for both users who spent the time to map these relations and those who destroy them unintentionally without being told about this when all they wanted to do was improving something. I'm quite surprised there is still no reaction from the iD developers on this topic, because showing a warning would really help here and wouldn't even be hard to implement. I even offered to do it myself. But this is not directly related to the topics we discussed here.

Now, I understand the dilemma for delivery app developers; where they have to compute a global optimal multi-stop route first with U-turn cost set to 0, and then break up the multi-stop route into local sub-routes with some safe and reasonable U-turn cost value. But again, imho u_turn_costs should default to its upper limit or just below the cost of a turning_circle or turning_loop. I am sorry, should I have mixed up the order of comparison. I hope you get what I mean. wink

I'm not entirely sure I understood what you mean, but wouldn't the global optimal multi-stop route also depend on the (u-)turns one needs to do for the local routes? At least in theory there should be no reason to not consider u-turn costs for the global optimization, but do include it for the local one?

[JakeSmarter]

leads to the aforementioned consequences of “novice mappers fixing the map”.

Do you have some examples/links to OSM where we can see such fixes? I found one here: https://www.openstreetmap.org/relation/13045491, but it is already one year old.

I have just recently removed some here: https://www.openstreetmap.org/changeset/132897711 Perhaps you can download just the changeset and recreate how it looked before. It was one giant mess of U-turns. Please, note all the superfluous U-turn relations I had to delete.

Another example: https://www.openstreetmap.org/changeset/109903470 Just by looking at the relations that have been created in this changeset you will easily understand that something has gone off rails here. Sure, that particular OSM contributor was a novice when the changeset was created and also apparently did not understand how turn restriction relations work but we have to look deeper why the user did it in the first place. You can find the initial reason in the changeset’s comment. Although it speaks of “some map issues”, it actually means that the user has had some ill advised U-turn encounters in his/her routing app and assumed that because the routing algorithm is more or less perfect (or immutable for his/her purposes), there has to be something wrong with the map. Perhaps that user was even encouraged by the routing app’s developers to “fix the user’s problem” by “fixing the map”?

You can find many similar examples in the Seattle, WA area too.

I do not know for sure whether Amazon uses Graphhopper for its routing apps but I have a gut feeling they might do. Amazon is not an outlier here, many other delivery and ride sharing employees suffer from similar problems and try to mitigate this issue by “fixing the map”.

If we did not cover this algorithmically we wouldn't be able to calculate such routes at all. There can always be situations where u-turns are the only possible option, like a curbside constraint pointing towards the end of a dead-end street: One has to turn around to get out of such a street again, otherwise we would not find a path at all. This is the reason the u_turn_cost parameter cannot be infinite.

Please, excuse me for not being a routing expert but isn’t this a special case? I would assume that from a routing perspective there is no U-turn involved in this case. You start a fresh route search in the only feasible direction?

For a safe and/or comfortable driving experience I think applications need to find a good way to tell drivers they need to turn around at the next suitable spot, and not just show them the next turn of the calculated route. Say, for example the route contains a u-turn (or some loop that avoids it), then an informed driver can find the next spot where this is possible and turn around instead of blindly following the route.

:thinking: The thing is that experience and reality have proven that there is no safe or comfortable way of saying to drivers to make a U-turn.

Long time ago, when in-car-navigation was new, companies like TomTom and many car makers encountered basically the same problem. Initially, drivers were told to “make a U-turn when possible or safe”. And, guess what? Drivers did whatever they wanted, mostly dangerous stuff and accidents, because they felt the pressure to comply with navigation as soon as possible. For many drivers this kind of pressure increased the longer it took them to do the U-turn. You can imagine that operating any heavy machinery under pressure is not a good idea. It is just how human psyche works. So, the solution was to basically avoid these rather dangerous “make a U-turn when possible or safe” messages at any cost. U-turns are not dangerous per se but it is a very unnatural maneuver for most drivers, especially in areas they are not familiar with. Most of the time, drivers go from A to B and this is also what they expect from their navigation. They do not care if there is a loop involved in the route. They want to get safely and stress free to their destination.

Typically, OSM mapping shouldn't be done for routers specifically, but turn restrictions might be an exception, because routing is the only reason turn restrictions are mapped at all?

True.

Or we could assume that doing a u-turn is basically never possible, which corresponds to a large (global) u-turn cost. In this case no-u-turn relations will hardly ever be needed or useful.

I think that although this may not be the most efficient basic assumption, especially in those jurisdictions that legally allow a U-turn at arbitrary junctions by default, this is the smarter and safer assumption.

Do you suggest that:

• routers should try to avoid u-turns as much as possible by default everywhere, including at junctions where there is no traffic sign or turn relation (a large u_turn_cost parameter in our case)

:+1: Yes.

• restriction relations should mostly be used for left/right/normal turns, but not really for u-turns?

no_u_turn restrictions can and should be mapped. But, only where it makes sense from a flow of traffic or routing point of view. When you assume (or come to the conclusion) that only a safe router is a router with a very high U-turn cost by default then one class of no_u_turn restriction relations becomes obsolete, namely those that have identical ways in the from and to roles. Why? Because a safe and sane router always optimizes for a loop or a turning_circle (or the like) first and will basically almost never suggest a U-turn at an arbitrary junction node.

• no-u-turn traffic signs can still be mapped using the traffic_sign tag in OSM for completeness, but they won't really be used by routing software

Right, because of the above assumption about a safe and sane router.

[easbar]

Just by looking at the relations that have been created in this changeset you will easily understand that something has gone off rails here.

Yes, I see, this is unfortunate.

Please, excuse me for not being a routing expert but isn’t this a special case? I would assume that from a routing perspective there is no U-turn involved in this case.

Yes, it is a special case, but one that needs to be covered. But if the u-turn costs are sufficiently high u-turns will only be suggested for this special case (when there really is no other option). Actually there always needs to be some kind of constraint (like a one-way road, turn restriction, etc.) for a u-turn to occur, otherwise there would always be a path that does not go to the place where the u-turn occurs at all.

You start a fresh route search in the only feasible direction?

You cannot tell what is the feasible direction without calculating the route. For example if you want to prevent u-turns at the stops of a multi-stop route you need to constrain the starting direction at each stop. And once you do that you might find you are in the situation where going into this direction it is not possible to turn around without a u-turn. Imagine this road network where you arrive at s from the West. Your only options are doing a u-turn at s, or continuing in Eastern direction and doing a u-turn somewhere. You can't tell if turning around without a u-turn is possible without exploring the road network (running the routing algorithm). But once you found the route and see it includes a u-turn you could tell the driver to turn around wherever possible, right when she gets back to the car and even before she starts driving to the next stop.

         -------
         |
----s-------------------
            |  |  |

The thing is that experience and reality...

Thanks for your input, this sounds reasonable.

Ok, I think there are basically two issues here:

1) GraphHopper (using default settings and the hosted API) suggests u-turns too often 2) Some mappers add too many non-sensical no_u_turn restriction relations to OSM

For 1) we need to think about our settings and there is an issue with the relationship of the priority and u_turn_costs in CustomWeighting (the meaning of the u_turn_costs parameter changes once the priority is below 1), something we are currently investigating.

For 2) I think it is most important to use the OSM wiki to communicate what should and should not be mapped. Not only for mappers adding these relations but also for those removing them again, so there is something they can argue with. Contacting these mappers / companies directly could also help.

The issues could or could not be related. Like I said, GraphHopper currently still ignores the no_u_turn tag: #2570, so 'fixing' the map does not even change anything, at least when using vanilla GraphHopper.

[JakeSmarter]

Thank you for acknowledging the issue with understanding.

Just FYI, it is interesting to see how different routers come to different solutions in this case. I like OSRM's solution. :wink:

[otbutz]

GH should yield a similar result with the PR from @easbar: https://github.com/graphhopper/graphhopper/pull/2761

[easbar]

Yes, with #2761 I got the same route as OSRM (using the turning circle at the end of Winding Wood Court). And when I increased the u_turn_costs (without this PR) I got the Valhalla route plus another alternative:

[Arcturuss]

At first sight it seems logical to add no-u-turn tagging to OSM, because there are traffic signs that indicate this (just like for normal turn restrictions), but tagging this everywhere to satisfy the routers, even in places where there is no 'no u-turn' sign, would be the wrong thing to do.

It is already done in some cities. Not 100% coverage of course, but close to >90%.

Simply because of safety considerations, it is almost always a bad idea to suggest a U-turn to any driver at any arbitrary junction node.

Maybe it is in your country, but in many others it's not. There is at least two cases where u-turns aren't something special:

• dedicated u-turn lanes
• regular city junctions with traffic lights.

The thing is, in many cases it's necessary to use curbside constraint, otherwise the router will suggest illegal turns in the middle of the road (yes, this means every other OSM router I know is broken by design). And with this constraint it's also necessary to correctly suggest u-turns, respecting mapped restrictions and in some cases implicit restrictions.

example

This is the case I'm talking about. Without curbside constraint every router will suggest the red path from A to B, not respecting which side of the road you are on. Here it means taking forbidden u-turn across the street, and then either another forbidden u-turn or stopping on the other side of the street and walking across. With Graphhopper one can account for that, but then u-turns become a problem. Currently I can either forbid them altogether (the default), or allow them anywhere regardless of the restrictions (the blue line on the picture). Both are unusable. 

[easbar]

It is already done in some cities. Not 100% coverage of course, but close to >90%.

Can you please provide some links to the cases or mention some of the cities you have in mind?

Maybe it is in your country, but in many others it's not.

I'm not sure this depends on the country much. I think it is pretty clear that there are always junctions where u-turns are possible and/or reasonable and others where they are inappropriate, dangerous or even impossible. So whichever default is used it will be wrong in many cases. Suggesting a u-turn to a driver that might be dangerous or impossible seems a lot more problematic to me than avoiding it and suggesting an alternative (possibly longer) route instead. Don't you agree?

There is at least two cases where u-turns aren't something special: dedicated u-turn lanes regular city junctions with traffic lights.

I'm not sure what you are trying to say. Yes, there are junctions with dedicated u-turn lanes and some with traffic lights, and doing a u-turn there might be possible. So generally there are junctions where doing a u-turn is possible and safe. But like I said, there are also many junctions (and even more nodes in GraphHopper that one probably wouldn't even call a junction, but that technically are junctions for GraphHopper because they are connecting different edges) where doing a u-turn is dangerous or impossible, so I think the better default is avoiding u-turns in general.

And with this constraint it's also necessary to correctly suggest u-turns, respecting mapped restrictions and in some cases implicit restrictions.

When curbside constraints are used some routes can become impossible without doing a u-turn. In many other cases driving some kind of loop can also work, even though that might not be ideal, because there might be a route that uses a legal/reasonable u-turn.

Without curbside constraint every router will suggest the red path from A to B, not respecting which side of the road you are on. Here it means taking forbidden u-turn across the street, and then either another forbidden u-turn or stopping on the other side of the street and walking across.

Yes, if the road is mapped as a single way in OSM there is no way one can tell there are separate lanes and without curbside information it is not clear going from A to B directly is not the desired route.

Currently I can either forbid them altogether (the default), or allow them anywhere regardless of the restrictions (the blue line on the picture). Both are unusable.

You can choose the u_turn_costs parameter anywhere between 0 (the blue line) and infinity (the default). If you use a finite value the u-turns may occur if they are necessary but will be generally avoided (in this case the route would probably do some kind of loop). Using a high, but finite value is a compromise: You might get routes that take a detour, even though a shorter route would be possible doing a u-turn, but on the other hand you are also avoiding u-turns that might be dangerous. It appears to me that you are mostly concerned about the detour?

[JakeSmarter]

At first sight it seems logical to add no-u-turn tagging to OSM, because there are traffic signs that indicate this (just like for normal turn restrictions), but tagging this everywhere to satisfy the routers, even in places where there is no 'no u-turn' sign, would be the wrong thing to do.

It is already done in some cities. Not 100% coverage of course, but close to >90%.

This should not have happened and should not happen. It just bloats the database and wastes compute cycles when routing. I am not sure why exactly this happened but routing algorithms with broken basic assumptions may have contributed to it. People, especially those companies who payed people to add this bloat data, should take responsibility and remove it from OSM.

Maybe it is in your country, but in many others it's not.

This has nothing to do with the country or more specifically, the traffic code you consider. As a general rule; just because something is legal or is not forbidden by regulations does not imply that it is also safe or smart to do, or even physically possible. For example, most jurisdictions do not forbid jumping out the window, yet it is neither safe nor smart to do. The same goes for traffic code rules. Just because some traffic codes allow or do not forbid u-turns on specific junctions (often with traffic signals only) by default, it does not mean that it is always safe or smart to do a u-turn on every (such) junction.

We are talking here about sane and safe global routing algorithm assumptions, not legal rules or restrictions. OSM turn restriction relations have been designed for mapping the flow of traffic (for routers). Hence, OSM turn restriction relation instances can be identical to legal restrictions on the road but they do not always have to. They should only be used when needed to restrict the modeled default flow of traffic, not to override any traffic code’s legal default.

• dedicated u-turn lanes

These have never been disputed nor they have had an effect on routing. Dedicated u-turn lanes are a traffic flow and safety tool for road engineers. Roads with dedicated u-turn lanes are by definition designed for safe u-turns and often employ dedicated road geometry, which is also consequently reflected in OSM data. Hence, as long as the road geometry has been properly mapped in OSM, routing algorithms always have, can, should, and will route u-turns there if needed.

• regular city junctions with traffic lights

Again, you are referring to the traffic code only without considering safety when routing (and finally driving). The issue is that OSM has no data type to indicate how safe or unsafe it is to make a u-turn at any junction (except for topology data derived from road geometry data, or potentially maybe no_u_turn restrictions in rare cases but this is rather the exception than the rule).

The thing is, in many cases it's necessary to use curbside constraint, otherwise the router will suggest illegal turns in the middle of the road (yes, this means every other OSM router I know is broken by design).

No. No routing algorithm will suggest a u-turn on sections (edges) between junctions (junction nodes). It is just that routing algorithms search for the shortest path from A to B and it has no clue (input parameter) which side of the road you are on.

Without curbside constraint every router will suggest the red path from A to B, not respecting which side of the road you are on.

This is not a bug or some deficiency but the effect of pure theory. Anyhow, what you can do already is to add an intermediate destination on the same edge you start your route in the direction you want to go. Note that this does not and will not invalidate the general assumptions on safe and sane u-turns, and the routing algorithm is going to compute a loop if necessary.

[Arcturuss]

Can you please provide some links to the cases or mention some of the cities you have in mind?

Ukraine, Belarus, major cities in Russia, other ex-USSR countries.

Example

https://www.openstreetmap.org/node/4810494980 Street with a double solid line mapped as a single line in OSM, and junctions (service ways) with restrictions for left turn and u-turn. https://yandex.ru/maps/-/CDrkf28x street view 

Suggesting a u-turn to a driver that might be dangerous or impossible seems a lot more problematic to me than avoiding it and suggesting an alternative (possibly longer) route instead. Don't you agree?

Maybe; maybe not. It depends on the user/driver and their specific use case. That's why it's configurable, right?

I'm not sure what you are trying to say.

Sorry, maybe that's because I have two different things in mind.

First, the general observation, not about any specific case. People do u-turns all the time, at least in the cities I lived in. So when the router ignores potential route with the u-turn the driver knows is legal and safe, and suggests 2x longer route instead, there's a strong chance this router will go out of the window. Same with suggesting u-turn where it's not legal or impossible.

I think this is not the case where one can strongly de-prioritize u-turns, trading potential longer routes for assumed safety. Both will be considered broken.

Second, the specific use case where this issue is more clear and even critical: calculating routes for taxi drivers. There is a taxi company in my city that is using routing on the OSM data (possibly OSRM, but I don't know for sure). They need to calculate the exact route the driver will take (including specific side of the street) to measure the distance and display the price. Because of that long detours are not acceptable, as well as impossible/illegal u-turns.

Currently they have an issue with routing that I showed in the picture in the previous post. They don't know how to fix this in the router, so they are trying to 'fix' the map by splitting the streets in two ways (even where that is against common practice) and messing up everything around in the process. Our local OSM community had enough of this and we wanted to suggest them a better router.

Anyhow, what you can do already is to add an intermediate target on the same edge you start your route in the direction you want to go

That's a good workaround, thanks!

[JakeSmarter]

Suggesting a u-turn to a driver that might be dangerous or impossible seems a lot more problematic to me than avoiding it and suggesting an alternative (possibly longer) route instead. Don't you agree?

Maybe; maybe not. It depends on the user/driver and their specific use case. That's why it's configurable, right?

There is no maybe. The router has no way of telling without adequate data how safe or unsafe a u‑turn maneuver may be (or whether it is even physically possible) at an arbitrary junction node, except for turning_circle and turning_loop. Period. Furthermore, the statistics and experience of routing vendors regarding u‑turns have been conclusive for a very long time.

The u‑turn cost is configurable to be able to compute multi‑stop routes (which is far more complex than most people think at first glance because it requires multi‑stage route searching) and because there are corner cases in certain situations where you have to run multiple searches with different parameters in order to get to a solution.

Second, the specific use case where this issue is more clear and even critical: calculating routes for taxi drivers. There is a taxi company in my city that is using routing on the OSM data (possibly OSRM, but I don't know for sure). They need to calculate the exact route the driver will take (including specific side of the street) to measure the distance and display the price. Because of that long detours are not acceptable, as well as impossible/illegal u-turns.

Currently they have an issue with routing that I showed in the picture in the previous post. They don't know how to fix this in the router, so they are trying to 'fix' the map by splitting the streets in two ways (even where that is against common practice) and messing up everything around in the process. Our local OSM community had enough of this and we wanted to suggest them a better router.

Then they have to:

1. use the right tool for their needs, like a sane router,
2. configure the router for their purpose correctly, and
3. stop mapping for any router but map to OSM guidelines only.

Furthermore, taxi companies or ride sharing services that have to project the cost and route for a customer can only do what it says: project. In this business it is impossible to always project the exact cost ahead of time, that’s the nature of things. Just think about accidents or any other unforeseeable event on the road that is going to lead to a detour. Hence, sometimes customers will pay more, sometimes less than the projected price after the ride. Usually, there is something like a ±5% tolerance deemed acceptable in the final price. Or, there is a minimum price added on top of the projected price to account for these unforeseen detours.

No router is perfect. And, like with everything, you have to know your trade. Sometimes you have to reconfigure the router and sometimes you have to edit the map because the map is not perfect either. But, never edit the map for anything specific but to mapping guidelines only.

https://www.openstreetmap.org/node/4810494980 Street with a double solid line mapped as a single line in OSM, and junctions (service ways) with restrictions for left turn and u-turn.

AFAKT, this junction has been mapped largely correctly, except for the dead data no_u_turn relation, which is complete non‑sense. Additionally, imho this only_right_turn relation would have been better mapped with no_left_turn. Note that no_left_turn ≭ only_right_turn. Neither are legally and in effect and traffic signs equivalent.

[easbar]

Maybe; maybe not. It depends on the user/driver and their specific use case. That's why it's configurable, right?

Yes, you're right what is the better default certainly depends on the specific use case and it is a good thing it is configurable. For actual driving/navigation I would still prefer a detour over a possibly dangerous or illegal u-turn. The aware driver will still be able to find a spot to turn around safely (that the router's data might not contain), and a less aware driver might not even notice there was a detour at all when driving a bit of a loop.

when the router ignores potential route with the u-turn the driver knows is legal and safe, and suggests 2x longer route instead, there's a strong chance this router will go out of the window. Same with suggesting u-turn where it's not legal or impossible.

That is exactly the problem. Whichever default one uses there will be lots of cases where the opposite setting would have been better. So the real question here is how the false cases can be reduced, i.e. how can we find locations in OSM data where u-turns are reasonable and where they need to be avoided as much as possible? And what is the default (in OSM)? For example should the default assumption be that u-turns are nowhere possible and possible u-turns need to be tagged explicitly? Or should it be that u-turns are possible basically everywhere (at all 'junctions'?) unless there is a no_u_turn restriction? Or maybe this should depend on some tags like highway, lanes etc.? I could not find an answer to this question in the OSM wiki. And as long as there is no agreement there, mappers won't know how to map and router developers won't know how to interpret the data.

They don't know how to fix this in the router, so they are trying to 'fix' the map by splitting the streets in two ways (even where that is against common practice) and messing up everything around in the process. Our local OSM community had enough of this and we wanted to suggest them a better router.

This is very bad of course. Maybe the best the OSM community can do would be establishing clear guidelines how turn restrictions should be mapped? Which brings me back to my previous question. Unless the guidelines are clear it is hard to hold anyone accountable for tagging or not tagging something? What do you think GraphHopper can do about this?

[karussell]

The problematic routes are now fixed:

• https://graphhopper.com/maps/?point=50.223965%2C18.990002&point=50.221075%2C18.989643&profile=car
• https://graphhopper.com/maps/?point=45.501467%2C-122.661254&point=45.501237%2C-122.66142&profile=car

See https://github.com/graphhopper/graphhopper/commit/da748e6ae80271e4b69f1b6f341687ee836f5b9b