Opened 2 years ago

Last modified 21 months ago

#1323 new defect/bug

No route found when shortest route involves forbidden U-turn

Reported by: mvglasow (2) Owned by: KaZeR
Priority: major Milestone:
Component: core Version: git master
Severity: normal Keywords: routing
Cc: http://wiki.navit-project.org/index.php/user:mvglasow, (2)

Description

Certain combinations of road layouts and turn restrictions cause Navit to not find a route at all. To reproduce:

After some time of calculation, route_status will indicate that no route was found.

If you set the current position a little further north on DK8 (around the center of Katrynka), Navit will find a route again and instruct the driver to go south.

Further analysis revealed the following:

  • Navit assumes that the shortest route from Białystok to Vilnius is to go from DK8 to DK19, going through Hrodno. (Going through Belarus, this route is impractical because of visa requirements, which Navit doesn't know about, and the best way is indeed to proceed north on DK8 until at least Augustów.)
  • At the given position, the road has two separate carriageways. When on the northbound carriageway, the shortest way would be to do a U-turn at the end of the split – but that is not allowed, represented by a turn restriction.
  • There are no further ways off the dual-carriageway section until the split.

As a result, the shortest route would be to go north until the carriageways join, after that turn around as soon as possible, then go back on the same road. This includes going through at least one point in the map twice, which Navit currently cannot handle.

In short, this situation occurs whenever:

  • We're on a road with split carriageways.
  • The best route goes over the carriageway in the opposite direction.
  • We're approaching a point where the two carriageways join and a "no U-turn" (or "only straight") restriction is present
  • There are no ways through which we could leave the dual-carriageway section before the end of the dual-carriageway section.

We might be able to solve this together with a setting to avoid U-turns ("when possible, please turn around") when routing. This could be implemented in the following way:

  • Treat the road we're currently traveling on as a one-way road for the purpose of routing. (Traveling means that our speed exceeds a certain threshold and our bearing is close to that of the road, or close to its opposite. The margin for bearing should probably be somewhere from +/-30° to +/-45° – allow for some tolerance because bearing from the GPS may be quite botched on some devices, and long turns may introduce more errors.)
  • When at the end of the road we have only one legal option to continue, apply the temporary one-way restriction also to the next road.
  • Probably some logic to turn this behavior on and off dynamically. We'll want to auto-enable it when a situation like the above is detected, and auto-disable it when we're on a dead end road. Otherwise, we should let the user decide.

Change History (7)

comment:1 Changed 2 years ago by mvglasow (2)

  • Summary changed from No route found when shortest route involves turn restriction to No route found when shortest route involves forbidden U-turn

comment:2 Changed 2 years ago by jandegr

Hi,

Cases where a loop has to be made because of turn restrictions are known already for a while. One documented such case is on the forum, https://forum.navit-project.org/viewtopic.php?f=8&t=576 Once I had a solution I found a few more such cases. https://circle-artifacts.com/gh/jandegr/routing-qa/85/artifacts/0/tmp/circle-artifacts.FZOJsmk/Brussels_turn_restriction.yamlmetric.png https://circle-artifacts.com/gh/jandegr/routing-qa/85/artifacts/0/tmp/circle-artifacts.FZOJsmk/Vienna_turn_restriction.yamlmetric.png

I have been discussing a possible solution with Zoff and the above links give the results of such a test.

The bad news is it uses plenty more memory but it does not take much longer to calculate a route, but the worst news is it requires a lot of work to code it :(

Some more info on it can be found here : https://www.mapbox.com/blog/smart-directions-with-osrm-graph-model/

Unfortunatly I did not forsee turnarounds, so for this case no solution yet.

regards, Jan

Last edited 2 years ago by jandegr (previous) (diff)

comment:3 follow-up: Changed 2 years ago by tryagain

Can we have memory usage left intact if only crossings, which have turn restrictions, would be edge-extended?

There seems to be a separate phase where turn restrictions for the whole already built graph are analyzed, and we could insert this logic there.

comment:4 in reply to: ↑ 3 Changed 2 years ago by jandegr

Replying to https://wiki.navit-project.org/index.php/user:tryagain:

Can we have memory usage left intact if only crossings, which have turn restrictions, would be edge-extended?

There seems to be a separate phase where turn restrictions for the whole already built graph are analyzed, and we could insert this logic there.

Maybe, but that exercise was started to explore the possibility of calculating the cost of a turn or a maneuvre in routing, with a forbidden turn being just the most costly sample of a turn. As kind of a surprise a bunch of cases involving turn restrictions got solved even before I started calculating the cost of allowed turns. But since there are some issues with route_path, navigation and demovehicle I'd like to keep the extended graph 'All purpose' untill those issues are solved.

comment:5 Changed 2 years ago by mvglasow (2)

In the meantime I have coded a solution for the turnaround case. Here's a brief outline of the solution:

  • If we have only one passable segment leading away from the current position, enable "forced path start" mode. That is, follow the one segment we can take.
  • At each subsequent point, stay in forced path start mode as long as we have only one option to continue (not counting the segment through which we came in).

Forced start path mode ends in one of the following ways:

  • We have reached a point where we have no more routable segments (other than the one through which we came in). In this case, stop (we really have no route, except if we do a U-turn).
  • We have reached a point at which we have multiple routable segments.

In the second case, return to least-cost routing in the following way:

  • If we have a least-cost segment at the current point and it does not coincide with the segment through which we came in, use it.
  • Else, add a traffic distortion to block one segment, then recalculate:
    • If the least-cost path goes back through the segment through which we came in, block that segment.
    • If the least-cost path requires us to make a turn forbidden by a restriction, block the segment after the forbidden turn.

This has solved things for my test case. Code is still a bit crude and needs some refinements. The current state of my work can be viewed at:

https://github.com/navit-gps/navit/compare/trunk...mvglasow:trac1323

It will only help when the first segments at the current position are constrained in that way, and the forbidden maneuver is on the constrained path.

More test cases are welcome.

comment:6 Changed 22 months ago by jandegr

Hi, I have some simpeler code now that handles all the situations I posted before and uses less extra memory. Since I still don't allow U-turns, in this case it now does a P-turn a few kilomters further on the road. https://circle-artifacts.com/gh/jandegr/routing-qa/250/artifacts/0/tmp/circle-artifacts.fg6q8uW/RTE_Trac_1323_2.yamlmetric.png https://circle-artifacts.com/gh/jandegr/routing-qa/250/artifacts/0/tmp/circle-artifacts.fg6q8uW/RTE_Trac_1323_2.yamlmetric.gpx

comment:7 Changed 21 months ago by mvglasow (2)

  • Cc http://wiki.navit-project.org/index.php/user:mvglasow (2) added
Note: See TracTickets for help on using tickets.