Assert during map-matching path unpacking

[danpat]

It seems that some combinations of traffic/turn cost data can lead to the following assertion being thrown:

[assert] /Users/danpat/mapbox/osrm-backend/include/engine/routing_algorithms/routing_base.hpp:223
in: void osrm::engine::routing_algorithms::BasicRoutingInterface<osrm::engine::datafacade::BaseDataFacade, osrm::engine::routing_algorithms::MapMatching<osrm::engine::datafacade::BaseDataFacade> >::UnpackPath(const DataFacadeT &, RandomIter, RandomIter, const osrm::engine::PhantomNodes &, std::vector<PathData> &) const [DataFacadeT = osrm::engine::datafacade::BaseDataFacade, Derived = osrm::engine::routing_algorithms::MapMatching<osrm::engine::datafacade::BaseDataFacade>, RandomIter = std::__1::__wrap_iter<const unsigned int *>]: *std::prev(packed_path_end) == phantom_node_pair.target_phantom.forward_segment_id.id || *std::prev(packed_path_end) == phantom_node_pair.target_phantom.reverse_segment_id.id
libc++abi.dylib: terminating

The assertion is triggered with this request:

http://localhost:5000/match/v1/driving/-122.505588,37.872619;-122.505702,37.872678?annotations=true&geometries=geojson

which represents this:

With no traffic data/turn penalty data applied, it works as expected. The problem thus seems to be either an edge-case caused by the data, or something we're doing wrong when applying traffic data.

After chatting with @TheMarex, a suspect is https://github.com/Project-OSRM/osrm-backend/blob/master/include/contractor/graph_contractor.hpp#L826

[danpat]

On the assumption that @TheMarex was onto something, I dug into contractor.hpp. It looks like the CH algorithm depends on the data in the .enw file - but those node weights are not being updated if traffic data is applied.

[MoKob]

I've tracked down the problem to the following issue:

due to the values put into the engine, we end up with negative initial segments that before could only happen if you looked at a route from s to s. Since we now don't have that guarantee anymore, we find invalid loops where none should exist, resulting in the assertion to trigger.

The problem is related to loops on initial segments. I'll see if I can correctly filter these cases.

Also: We are now routing on negative weights in a CH. The code was not designed to do so.

[MoKob]

Capturing from chat after a discussion with @TheMarex.

The problem we experience is related to negative turn penalties and the offset computation in the geospatial query. The offset computation currently does not consider the turn-penalties correctly. If the turn penalty is too negative, we can perform a first relaxation that still offers negative weights (which should not be the case).

The issue is essentially already fixed with the implementation of #77 #2399. Right now there is no easy fix around this problem, though, since we cannot separate turn penalties from our offsets right now.

We are treating this as a known issue for v5.5, since negative turn penalties are unintended usage so far. With #77 implemented (hopefully v5.6), we should be able to correctly handle this problem without introducing brittle and hacky code for a quick fix.

[TheMarex]

I just looked into the code for this and the main problem is again indexing: For #77 we index turn penalties by edge-based-edge id. However the problem in this specific case is that the offset of the first phantom node will be wrong. To fix this we would need indexing based on edge-based-node id: That is not that trivial since the turn penalty, of course, depends on which edge you turn on and is not static by edge-based-node id.
In #77 we only fixed the duration of each step after we actually have a route.

Thinking about this more, we might want to rewrite the way we handle start nodes in our search code. At the moment we have the following behavior that utilizes negative initial weights:

a ---> b --(x)--> c ----> d

1. Determine the duration of the edge (a->b->x) that will not be traversed because you start in the middle of the segment.
2. Add the start node to the heap, but set the initial weight to -offset instead of 0.
3. The initial relax step performed by the Dijkstra algorithm will then add all neighbors of the start node with edge-based-edge weight + (-offset) yielding the correct-ish distance for them to the start node

We could switch to only ever using positive weights:

1. Determine the ratio of duration of the edge that still has to be traversed (x->c->d / a->b->c->d). (note: this is the inverse of the current approach)
2. Add the source with distance 0
3. Add all outgoing neighbors with radio * edge-based-edge-weight

In the second approach we would need to have a modified relax step for the start node, that actually does not use the edge-based-edge weight.

In both cases the current approach for the target node just work, since we only pay turn penalties when turning from a node, not when arriving.

[miccolis]

👋 Any updates here? Will landing issue 77 as it's written now help these situations? ...or is there still work to do?

[danpat]

@miccolis this bug is still outstanding if negative turn penalties are applied.

[springmeyer]

For those of you that have been looking into this, does this stack trace look like the same underlying issue? (Segfault in a release build)

Program terminated with signal SIGSEGV, Segmentation fault.
Thread 1 (Thread 0x7fc4bd722700 (LWP 8651)):
#0  0x00007fc4be44b13b in void osrm::engine::UnpackCHPath<osrm::engine::datafacade::BaseDataFacade, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, void osrm::engine::routing_algorithms::BasicRoutingInterface<osrm::engine::datafacade::BaseDataFacade, osrm::engine::routing_algorithms::DirectShortestPathRouting<osrm::engine::datafacade::BaseDataFacade> >::UnpackPath<__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > > >(osrm::engine::datafacade::BaseDataFacade const&, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, osrm::engine::PhantomNodes const&, std::vector<osrm::engine::PathData, std::allocator<osrm::engine::PathData> >&) const::{lambda(std::pair<unsigned int, unsigned int>&, osrm::contractor::QueryEdge::EdgeData const&)#1}>(osrm::engine::datafacade::BaseDataFacade const&, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, osrm::engine::datafacade::BaseDataFacade const&, void osrm::engine::routing_algorithms::BasicRoutingInterface<osrm::engine::datafacade::BaseDataFacade, osrm::engine::routing_algorithms::DirectShortestPathRouting<osrm::engine::datafacade::BaseDataFacade> >::UnpackPath<__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > > >(osrm::engine::datafacade::BaseDataFacade const&, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, osrm::engine::PhantomNodes const&, std::vector<osrm::engine::PathData, std::allocator<osrm::engine::PathData> >&) const::{lambda(std::pair<unsigned int, unsigned int>&, osrm::contractor::QueryEdge::EdgeData const&)#1}&&) () from /usr/local/src/app/node_modules/osrm/lib/binding/node-osrm.node
#1  0x00007fc4be449ab4 in void osrm::engine::routing_algorithms::BasicRoutingInterface<osrm::engine::datafacade::BaseDataFacade, osrm::engine::routing_algorithms::DirectShortestPathRouting<osrm::engine::datafacade::BaseDataFacade> >::UnpackPath<__gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > > >(osrm::engine::datafacade::BaseDataFacade const&, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, __gnu_cxx::__normal_iterator<unsigned int*, std::vector<unsigned int, std::allocator<unsigned int> > >, osrm::engine::PhantomNodes const&, std::vector<osrm::engine::PathData, std::allocator<osrm::engine::PathData> >&) const () from /usr/local/src/app/node_modules/osrm/lib/binding/node-osrm.node
#2  0x00007fc4be4418d4 in osrm::engine::routing_algorithms::DirectShortestPathRouting<osrm::engine::datafacade::BaseDataFacade>::operator()(osrm::engine::datafacade::BaseDataFacade const&, std::vector<osrm::engine::PhantomNodes, std::allocator<osrm::engine::PhantomNodes> > const&, osrm::engine::InternalRouteResult&) const () from /usr/local/src/app/node_modules/osrm/lib/binding/node-osrm.node
#3  0x00007fc4be43e50e in osrm::engine::plugins::ViaRoutePlugin::HandleRequest(std::shared_ptr<osrm::engine::datafacade::BaseDataFacade>, osrm::engine::api::RouteParameters const&, osrm::util::json::Object&) const () from /usr/local/src/app/node_modules/osrm/lib/binding/node-osrm.node
#4  0x00007fc4be3d893c in osrm::engine::Engine::Route(osrm::engine::api::RouteParameters const&, osrm::util::json::Object&) const () from /usr/local/src/app/node_modules/osrm/lib/binding/node-osrm.node
#5  0x00007fc4be3d4e00 in void node_osrm::async<std::unique_ptr<osrm::engine::api::RouteParameters, std::default_delete<osrm::engine::api::RouteParameters> > (*)(Nan::FunctionCallbackInfo<v8::Value> const&, bool), osrm::engine::Status (osrm::OSRM::*)(osrm::engine::api::RouteParameters const&, osrm::util::json::Object&) const>(Nan::FunctionCallbackInfo<v8::Value> const&, std::unique_ptr<osrm::engine::api::RouteParameters, std::default_delete<osrm::engine::api::RouteParameters> > (*)(Nan::FunctionCallbackInfo<v8::Value> const&, bool), osrm::engine::Status (osrm::OSRM::*)(osrm::engine::api::RouteParameters const&, osrm::util::json::Object&) const, bool)::Worker::Execute() () from /usr/local/src/app/node_modules/osrm/lib/binding/node-osrm.node

[danpat]

@springmeyer possibly, but hard to say - if the assertion isn't thrown, we end up in an undefined state, possibly leading to a SEGFAULT. Do you have any more details on where this trace came from? (i.e. the request that triggered it, profile used, OSRM version, etc?)