Inconsistent routes when snapping endpoints to same way, with traffic updates

[mjjbell]

Documenting a quirk I found when writing tests for #5953. It touches on some OSRM implementation details which might be relevant in other scenarios.

Issue

Given a way and traffic updates that invalidate a segment of the way, routes between two endpoints snapped to this way are inconsistent.

N.B. This only affects the contraction hierarchy algorithm.

The problem can be summarised in this test feature:

Feature:

    Background: single way
        Given the node map
            """
            a   b   c   d
            """

        And the ways
            | nodes   |
            | abcd    |

        And the profile "turnbot"

    Scenario: invalid segment, fail to find route
        Given the contract extra arguments "--segment-speed-file {speeds_file}"
        And the customize extra arguments "--segment-speed-file {speeds_file}"
        And the speed file
        """
        3,4,0
        """

        When I route I should get
            | from | to | route      | weight |
            | b    | a  | abcd,abcd  | 20     |

        When I route I should get
            | from | to | code      |
            | a    | b  | NoRoute   |


    Scenario: invalid segment finds u-turn route
        Given the contract extra arguments "--segment-speed-file {speeds_file}"
        And the customize extra arguments "--segment-speed-file {speeds_file}"
        And the speed file
        """
        2,1,0
        """

        When I route I should get
            | from | to | route       | weight |
            | c    | d  | abcd,abcd   | 20     |
            | d    | c  | abcd,abcd   | 40     |

In an ideal scenario, all four queries would be routable. Furthermore, for the symmetric scenarios from a to b and from d to c, only one is routable, and the latter is only finds a path via a u-turn (see the additional weight).

In Detail

Input Snapping

A way can consist of multiple segments. Traffic updates can change the edge weights/speeds for individual segments. Segments can also be invalidated, indicating that it can not be used in a route.

Input locations are snapped to a position along a way, i.e. a position on one of the segments.
The current behaviour for snapping locations to ways with invalid segments is as follows:

Targets: The snapped location is a valid target, as long as all segments before the snapped position are valid.

Sources: The snapped location is invalid if any of the segments are invalid, regardless of their relative position to the snapped location.

This asymmetry is due to the way in which route weights are calculated. Without going into the details, all segment weights of the first way are used in the search, so they all must be valid.

Graph Contraction

Scenario 1

Take the first scenario from the test feature. Here we invalidate segment c->d
The transformation from original graph to edge-based contraction hierarchy graph is as follows:

It's worth noting the graph is so trivial that none of the contraction hierarchy ranking criteria apply, so the order between the two nodes is randomly selected. This is deterministic, so we always have rank(reverse(abcd)) > rank(forward(abcd)).

Applying the route search...

from b to a

• We can't snap a source to the forward way as it contains an invalid segment.
• Both the source and target snap to the reverse way with a positive weight path between them.
• ROUTE FOUND

from a to b

• Again, we can't snap a source to the forward way.
• Both the source and target snap to the reverse way, but the path between has negative weight.
• The graph edge from the forward way is not traversable, as the reverse way already exists in the backward heap with a smaller weight.
• NO ROUTE FOUND

Scenario 2

Take the second scenario from the test feature. Here we invalidate segment b->a
The transformation from original graph to edge-based contraction hierarchy graph is as follows:

Applying the route search...

from c to d

• We can't snap a source to the reverse way as it contains an invalid segment.
• Both the source and target snap to the forward way with a positive weight path between them.
• ROUTE FOUND

from d to c

• Again, we can't snap a source to the reverse way.
• Both the source and target snap to the forward way, but the path between has negative weight.
• We can traverse the graph edge representing the u-turn in the forward graph. From here we now have a match on the reverse way with a positive weight.
• ROUTE FOUND (with u-turn)

Summary

This issue has two characteristics.

• The asymmetry between target and source phantoms. Traffic updates to segments behind a source location can invalidate a route even if the path from the source to the first turn is valid. Is there a way to alter the route weight calculation to accommodate this?

• Given the source/target asymmetry, the CH contraction order - and in this case the randomness of the rank selection - determines which routes are found. If the contraction node ranks are flipped, the no-route/u-turn results would also flip for the symmetric cases. I also noticed differences between results caused by CH contraction randomness in another test. Are there assumptions needed for CH to work that are not being adhered to in OSRM due to various real-life complexities (snapping, traffic updates, endpoints on same edge, etc)? Or are these test cases not representative of real-world graphs?

[felix-geovelo]

Hello !

I encouter the first problem (asymetry between source and target) since I invalidate some parts of some way of my graph with --segment-speed-file option (but I'm working with MLD here)
So, in particular situation, source might be snapped to a valid section of a way that contains invalid sections. This led to a NoRoute output. This situation should be avoided at snapping time. A valid section of a way that contains invalid section will never be a valid source

This problem lies in this part of the code I think :

osrm-backend/include/engine/geospatial_query.hpp

Lines 528 to 539 in 31e31a6

	const auto forward_weights = datafacade.GetUncompressedForwardWeights(geometry_id);
	if (forward_weights[data.fwd_segment_position] != INVALID_SEGMENT_WEIGHT)
	{
	forward_edge_valid = data.forward_segment_id.enabled;
	}
	const auto reverse_weights = datafacade.GetUncompressedReverseWeights(geometry_id);
	if (reverse_weights[reverse_weights.size() - data.fwd_segment_position - 1] !=
	INVALID_SEGMENT_WEIGHT)
	{
	reverse_edge_valid = data.reverse_segment_id.enabled;
	}

When snapping, it only check if the selected section has valid edge weight but according to your post, source is not valid if one section in the same way is invalid, and target is not valid if previous section of the same way are invalid.

Then, I propose the folliwing code to fix snapping logic and avoid snapping to valid but invalid edge :

const auto forward_weights = datafacade.GetUncompressedForwardWeights(geometry_id);
if (std::find(forward_weights.begin(), forward_weights.end(), INVALID_SEGMENT_WEIGHT) ==
    forward_weights.end())
{
    forward_edge_valid = data.forward_segment_id.enabled;
}
const auto reverse_weights = datafacade.GetUncompressedReverseWeights(geometry_id);
if (std::find(reverse_weights.begin(), reverse_weights.end() , INVALID_SEGMENT_WEIGHT) ==
    reverse_weights.end())
{
    reverse_edge_valid = data.reverse_segment_id.enabled;
}

[github-actions]

This issue seems to be stale. It will be closed in 30 days if no further activity occurs.