felix-geovelo
commented
9 months ago 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 : https://github.com/Project-OSRM/osrm-backend/blob/31e31a63d062fb804f5f4695ed3036ca7a269ead/include/engine/geospatial_query.hpp#L528-L539
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[bot]
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:
In an ideal scenario, all four queries would be routable. Furthermore, for the symmetric scenarios
from a to bandfrom 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->dThe 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
from a to b
Scenario 2
Take the second scenario from the test feature. Here we invalidate segment
b->aThe transformation from original graph to edge-based contraction hierarchy graph is as follows:Applying the route search...
from c to d
from d to c
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?