Incorrect handling of turn restrictions sharing the same via-way

[Vectorial1024]

Describe the bug
I have recently discovered that in some uncommon cases, Graphhopper simply fails to produce the correct driving path. It is as if Graphhopper thinks the relevant roads does not exist.

There is no apparent explanation as to why the best path is not discovered by Graphhopper. The following items were checked, but feel free to double check:

• Relevant OSM data: turn restrictions OK, access OK
• Local Graphhopper "debug" routing graph: vehicle access OK

One wild guess is that the relevant roads got wrongly rejected while doing CH.

To Reproduce

I offer 1 of the possibly many cases for consideration.

(Note: this is a left-hand-drive case!!! But hopefully, this does not disqualify the bug.)

Case: https://graphhopper.com/maps/?point=22.343482%2C114.131477&point=22.337654%2C114.137139&profile=car&layer=OpenStreetMap

It seems the detour is unnecessary.

Expected behavior
Indeed, the detour is unnecessary. IRL drivers would do this:

System Information
N/A; reproduced via official Graphhopper Maps.

Screenshots & Logs
(Provided)

---

More cases in the neighbourhood, to show the "disappearance" of the affected road segments:

This does not work: https://graphhopper.com/maps/?point=22.343482%2C114.131477&point=22.340576%2C114.130486&profile=car&layer=OpenStreetMap

Update: thanks to @ratrun 's comments, I reviewed the situation and realized for this specific case, Graphhopper is working as intended and I got a false alarm; however the other cases are still valid.

This does not work: https://graphhopper.com/maps/?point=22.337536%2C114.137059&point=22.3377%2C114.137113&profile=car&layer=OpenStreetMap

But curiously, this works: https://graphhopper.com/maps/?point=22.337536%2C114.137059&point=22.343259%2C114.131432&profile=car&layer=OpenStreetMap

[ratrun]

I verified that it works locally if you deactivate the turn restriction support. So this seems to be some kind of bug in the turn restriction handling. First I suspected that this turn restriction causes it: https://www.openstreetmap.org/relation/2118776 . But this is not the case. Even after removing this relation for the osm input file the problem persists.

After more checking I verified that it is this relation: https://www.openstreetmap.org/relation/14472712

[Vectorial1024]

Thanks @ratrun for somehow finding the "hidden" turn restriction! To be honest, that specific relation did NOT appear in the OSM iD editor, but the iD editor surely can feel its presence because it refused me to delete the relevant ways.

I actually have another location that also has this kind of problem. Seeing how the original case might be confusing, I am now offering the 2nd case for this bug. And I think I can generalize the situation a bit.

---

Describe the bug

When IRL roads are constructed in a specific pattern, and when those roads are correctly mapped in OSM, then Graphhopper fails to produce any correct path as if those roads do not exist. It is probably related to "advanced" turn restriction handling. #446

(Road pattern to be provided in another comment)

To Reproduce

I am offering another location to show the bug because the previous case might be confusing in the OSM iD editor (but the previous case is still valid). Consider the previous case as a "primer".

Case: https://graphhopper.com/maps/?point=22.306284%2C114.164927&point=22.302891%2C114.158458&profile=car&layer=OpenStreetMap

It seems the detour is especially strange and unnecessary.

Expected behavior

Indeed, the detour is very strange and unnecessary, because:

System Information
N/A; reproduced via official Graphhopper Maps.

Screenshots & Logs
(Provided)

---

Just like the previous case, here are some more neighbourhood cases. This time there will be more because the junctions here are more complicated.

This doesn't work: https://graphhopper.com/maps/?point=22.305958%2C114.166221&point=22.30953%2C114.162755&profile=car&layer=OpenStreetMap

(Notice how it uses the middle road.)

This doesn't work: https://graphhopper.com/maps/?point=22.305958%2C114.166221&point=22.308996%2C114.163633&point=22.314424%2C114.1607&profile=car&layer=OpenStreetMap

(Notice how it also uses the middle road.)

This doesn't work: https://graphhopper.com/maps/?point=22.305958%2C114.166221&point=22.314424%2C114.1607&profile=car&layer=OpenStreetMap

(This case is not "incorrect" per se, but rather it is unnecessarily inaccurate.)

Should be enough cases to show the situation.

[Vectorial1024]

What really is going on?

A pattern can be seen in both cases, and here I shall show it.

IRL, the roads are built and marked like this:

This "middle entrance slip" is always elevated/sunken. This setup allows for uninterruptible entrance to two diverging highways while the highway itself branches.

In terms of the OSM graph, because the middle section is the same road, it looks something like this:

        -- U1 --           -- U4 -->
       /        \         /
 -- A -    C1 -- C2 -- C3 
       \        /         \
        -- B1 --           -- B4 -->

With the following possible paths after considering turn restrictions:

P1: U1 -> C2 -> C3 -> U4
P2: C1 -> C2 -> C3 -> U4
P3: C1 -> C2 -> C3 -> B4
P4: B1 -> C2 -> C3 -> B4 

Maybe the turn restriction code is not able to handle multi-via turn restrictions, but something must have happened that prevents the "main roads" from being used, and instead allows the slip road full turn access to both highway exits.

There are several possible turn restriction representations for the above case, and I show one of them:

The union of:
U1 -> C2 -> C3 -> U4: relation left-only U1 U4 via U1-C2, C2-C3
B1 -> C2 -> C3 -> B4: relation no-left B1 B4 via B1-C2, C2-C3
No turn restrictions on C1 -> C2 -> C3 -> U4
No turn restrictions on C1 -> C2 -> C3 -> B4

---

We can always "disappear" the problem by splitting the way C2-C3, to create the nodes {B2, B3, U2, U3} with the appropriate roads and restrictions, but that will violate the OSM style guides and trigger some mappers. We will have to deal with it here.

[easbar]

Thanks for reporting this, I will have a look.

[ratrun]

Hi @easbar !
I did some more detailed investigations on the initially reported situation .

Besides the already mentioned restriction relation https://www.openstreetmap.org/relation/14472712 the second restriction relation https://www.openstreetmap.org/relation/14472711 needs to be considered. The problem occurs only if both these relations are active.

[easbar]

Thanks, good to know. Did you create a minimal OSM file that shows the issue? That's the first thing I would do to be able to debug the error.

[ratrun]

Thanks, good to know. Did you create a minimal OSM file that shows the issue? That's the first thing I would do to be able to debug the error.

Yes, this is what I did. If I understood the situation correctly it should be coverd by the following test:

    @Test
    void viaWay_no_withOverlap_issue2907() {
        //  0        3
        //   \a  s  /b
        //    1----2
        //   /c     \d
        //  4        5

        int a = edge(0, 1);
        int b = edge(3, 2);
        int c = edge(4, 1);
        int d = edge(2, 5);
        int s = edge(1, 2);

        BooleanEncodedValue turnRestrictionEnc = createTurnRestrictionEnc("car");
        r.setRestrictions(Arrays.asList(
                new Pair<>(GraphRestriction.way(a, s, d, nodes(1, 2)), RestrictionType.NO),
                new Pair<>(GraphRestriction.way(c, s, b, nodes(1, 2)), RestrictionType.NO)
        ), turnRestrictionEnc);

        assertEquals(NO_PATH, calcPath(0, 5, turnRestrictionEnc)); // a-s-d
        assertEquals(NO_PATH, calcPath(4, 3, turnRestrictionEnc)); // c-s-b
        assertEquals(nodes(4, 1, 2, 5), calcPath(4, 5, turnRestrictionEnc)); // c-s-d
        assertEquals(nodes(0, 1, 2, 3), calcPath(0, 3, turnRestrictionEnc)); // a-s-b
    }

[easbar]

This is a bug indeed.

[easbar]

@Vectorial1024

We can always "disappear" the problem by splitting the way C2-C3, to create the nodes {B2, B3, U2, U3} with the appropriate roads and restrictions, but that will violate the OSM style guides and trigger some mappers. We will have to deal with it here.

Is this really so? Let's look at this example again:

The two roads (yellow and red) are completely separated from each other. It is neither possible to enter the yellow lane from the red entrance nor to leave the yellow lane towards the red exit (and vice versa). So basically two roads that are not connected to each other are first merged into a common OSM way and then separated again using turn restrictions?

For example this is problematic when snapping a start/destination to this road, because it is impossible for the router to tell which road the driver is on. I also checked Apple Maps which seems to ignore the turn restriction entirely, i.e. suggesting a potential dangerous/illegal switching between the lanes.

[Vectorial1024]

@easbar your description of the problem is quite accurate. Yes, the yellow line and the red line are the only valid (through) paths in this system.

---

The OSM mapper perspective is that, referring to the modified diagram:

the blue area is 1 segment only. Looking at the physical structures, there can only be 1 road, and cannot be 2 roads. Therefore, the OSM perspective refuses to split the yellow-red joint part into 2 roads to "disappear" the problem.

---

And yeah, if you just say "I started in the middle", then even if you give me any of the 2 exit paths, there is no problem, because the system simply don't know. The main problem is, if I know where I came from such as in the provided case, then there is always only 1 possible exit for each entrance.

[Vectorial1024]

@ratrun yeah your suggested test case succinctly summarizes the problem.

[easbar]

Looking at the physical structures, there can only be 1 road, and cannot be 2 roads.

Ok I get this. For OSM a simple rule would be that one 'physical structure' is one element/way. But there can very well be two 'roads' on the same 'structure'. Here they are only separated by a (triple) white line drawn on the concrete, but this could just as well be a fence or similar that cannot be crossed physically. So I really wonder what purpose such a 'simple' rule is supposed to have. Why are we mapping roads (and turn restrictions!) in OSM in the first place, if not to use them for routing? Merging these two (legally) separated roads into one feature makes it impossible to tell which one is which, even though in reality they are in fact two different roads: You can only drive on either one and depending on which one you are driving you only have certain legal options where you can go.

And yeah, if you just say "I started in the middle", then even if you give me any of the 2 exit paths, there is no problem, because the system simply don't know.

But this in itself is a problem. Say you are trying to use a navigation system which is just using the GPS position and OSM. It won't be able to tell on which road you are and thus cannot suggest a route correctly. The system does not know because the road network data is insufficient. But why should OSM not try to provide accurate road network data? Like I said if this wasn't the goal I wouldn't really understand why roads and turn restrictions are mapped at all.

The main problem is, if I know where I came from such as in the provided case, then there is always only 1 possible exit for each entrance.

Yes, the single/merged OSM way (representing the two lanes) plus the turn restrictions specify this situation accurately. However, the problems are that:

1. For the use-case I described above where we'd like to snap a starting position to the correct lane the OSM data is insufficient.

2. Implementing such turn restrictions accurately is quite a task if at all worth it, which is why the routing engines (not only GraphHopper) partly ignore them.

I think 1) would be reason enough to use two separate OSM ways for these two separate roads. For those who do not agree: Would there be two ways if they were separated by a fence? A guardrail? A wall? A green area? Where do we draw the line here and why?

Regarding 2) we are facing the same situation here as in this discussion where we encountered the same problem for a 'ONLY' turn restriction: #2689 (comment)
We decided to simply ignore these cases as they would be more complicated than the already complicated cases we are supporting so far. Unfortunately overlapping 'NO' turn restrictions are much more common and cannot be easily ignored. I'm currently trying to separate those we can already handle correctly from the ones that are more complicated and as a first step would then ignore the latter.

[easbar]

I found several more such cases (@lukasalexanderweber did you notice something similar maybe?), e.g.:

• way that is a via member of these two turn restriction relations resulting in a bad route
• another such case bad route
• way that is a via-member of both a 'no' and an 'only' turn restriction: bad route

They are all instances of the same pattern illustrated by @ratrun's example: A via-way member is used by two or more turn restrictions. With our current approach we would have to add additional artificial edges to make this work. For this reason we already excluded these cases for 'only'-turn restrictions (see #2689) and we need to do this for 'no'-turn restrictions as well.

There is an interesting catch, though. A very common case is the following:

    |
A---B---C
    |
D---E---F
    |

where (in a right-driving country) it is forbidden to do u-turns like D-E-B-A and C-B-E-F. In this case there are two via-way turn restrictions with B-E as via-member. However, the restrictions use this way in different directions. This is important, because in this case our approach is still correct. It only fails if there are two via-way restrictions that use a common via-way in the same direction, so we can keep this important class turn restrictions.

[ratrun]

With our current approach we would have to add additional artificial edges to make this work. For this reason we already excluded these cases for 'only'-turn restrictions (see #2689) and we need to do this for 'no'-turn restrictions as well.

Following the link, the interesting discussion you had there and the already existing attempts I would prefer to go the more complicated way with adding of additional artificial edges and not again ignore the situation and just log it. But that is just my opinion from an outside view of someone who does not need to maintain the solution!

[easbar]

I agree that ultimately we should support this fully, but for now I think ignoring the restrictions is already an improvement. I did this in #2921. They are also not ignored both, but if there are two or more only the first one will be considered.

[easbar]

It will take a couple of days until this is live on graphhopper.com/maps

[lukasalexanderweber]

    G
    |
A---B---C
    |
D---E---F
    |
    H

thanks for the fix @easbar and sorry for the circumstances.

Just for me to clarify if there are the two no restrictions

D-E-B-A
H-E-B-G

only one of them (the one which comes first) will be considered?

And the same goes for

C-B-E-F
G-B-E-H

a combination can coexist, e.g.

D-E-B-A + C-B-E-F

[easbar]

Yes, exactly. And no need to be sorry :)