Detour computation - implementation guidance

[Fkawala]

I'm investigating the possibility to implement Geisberger et al. [1] proposal for fast detour computation using OSRM.

So far I've toy-ed around with the OSRM-as-a-library example.

From what I get the manyToManySearch function could do pretty much the core calculation presented in section 3. Hence, to compute the acceptable detours for a ride, I would save the search_space_with_buckets for the upward search space and for the downward search space. Does that sounds reasonable ? If so how/where should I start ? Do have some documentation that might helps me ?

Best regards, François.

[1] http://lekv.de/pub/Mitfahr-Paper.pdf

[danpat]

@Fkawala It sounds like you're already looking at the parts of the code you need.

libosrm.a doesn't expose any of the underlying graph access methods - you will need to add a "plugin" to OSRM that is exposed in the bindings, and/or the HTTP interface exposed by osrm-routed.

Happy to answer any more specific questions you've got - this looks like a very interesting algorithm :-)

[Fkawala]

@danpat Thanks for your kind response, I'll ping for help if needed!

[Fkawala]

@danpat I used your PR #3652 to understand how to define a new plugin, that went quite well.

My new "detour" plugin should run a bi-directional Dijkstra which have no difference from search function, but a custom relaxOutgoingEdges function. The customized relaxOutgoingEdges function would update the SearchSpaceWithBuckets.

How could I do that without doing neither a massive code duplication nor a breaking the current routing algorithms ?

[daniel-j-h]

If you want to introduce customization points maybe have a look at policy-based design. The basic idea is to inject different behavior by means of template functions. The compiler can then look through your glue code and churn out the appropriate code for you at compile time. Here's an example:

https://github.com/Project-OSRM/osrm-backend/pull/1515/files

[Fkawala]

@daniel-j-h Thanks for the advice! Just to be sure, is that correct that you suggest me to do as it is done for DIRECTION "parameter" of the routingStep function ?

I'm kind of lost in the routing algorithms, If I do modify the template of the relaxOutgoingEdges function will I have to modify both CH and non-CH routing algorithms ?

[daniel-j-h]

The routing algorithms are namespaced to ch and mld - your relaxOutgoingEdges function is namespaced here.

If you want to implement your feature on ch you have to change the ch-namespaced code and keep the routing algorithm generic function free ch-specific from modifications.

I can recommend taking a look at {include,src}/routing_algorithms/routing_base* and go from there.

[TheMarex]

@Fkawala Would using the forwardRouteStep functions from the many_to_many.cpp file work for you?

If yes, I would recommend trying to move those to the routing base that Daniel mentioned and have both ManyToMany and your detour algorithm use it. Since there is no MLD version of M2M yet anyway, you would probably also not break anything. 😉

[Fkawala]

@TheMarex from what I get from [1] and OSRM the fast detour computation would be quite faster with a bi-directional Dijkstra running on a HC preprocessed graph, so I guess that M2M is not the best candidate. What do you think ?

[1] http://lekv.de/pub/Mitfahr-Paper.pdf

[TheMarex]

The many-to-many algorithm uses a bi-directional Dijkstra with search-buckets under the hood, which seems to be what you need here, right?

[Fkawala]

My bad, I did not checked the source before my last response, sorry about that.

After a careful reading I'm still perplex about the manyToManySearch algorithm, is it described in pseudo-code somewhere ?

Would you care to explain me the difference between the forwardRoutingStep [source] function and the backwardRoutingStep [source] function ?

Bottom line, If M2M boils down to a bi-directional Dijkstra when provided with a single (source, target) pair, I agree with you and I'll focus on M2M.

[TheMarex]

This is the original paper this is based on, but please note that at the time this was published CH did not exist yet (they use Highway Hierarchies, but the approach in general can be transferred to any hierarchical pre-processing method).

The backwardRoutingStep does two things: Update the heap, like a normal backward-Dijkstra search, but also update the search buckets: A list of labels for every node in the search space that basically contains (target, distance_to_target) for every target node that reaches the node.

The forwardRoutingStep again executes a normal forward-Dijkstra but at every node checks the search buckets for targets that have reached this node. If this is true, we have found a middle node and can write the final distance into the correct cell in the matrix.

[Fkawala]

Thanks! I should have connected the dots already (the Knopp et al. article you've cited is also cited by Geisberger et al. in their fast detour computation article).

[Fkawala]

I dug a little bit / toyed around with some std::cout and the debugger. The result puzzles me and I would prefer to fully understand M2M+HC before doing anything else. I explain below what I did and why the results are odd to me.

I ran a M2M search with one single origin (Paris, France) and one single destination (Marseille, France). Given the size of the graph (full France OSM extract is about 12M nodes after contraction) and the distance between origin and destination (600km). I expected tens of thousands calls to the backwardRoutingStep. Yet I observe only 1200 calls to backwardRoutingStep. How can it be so few before the query heap is empty ? I can assume that is a direct consequence of the graph contraction and the backward constraint, but I would be more confortable If one could confirm.

Using the same M2M settings I tried to gain more insights on the contracted network. To do so I check the OSM node identifiers for nodes examined by backwardRoutingStep. These nodes are scattered all over the France and I fail to map that the intuition behind HC. For instance here are the four first nodes examined by backwardRoutingStep :

1. new node examined 365138491 with target_weight 45
2. new node examined 142297 with target_weight 88
3. new node examined 33643703 with target_weight 296
4. new node examined 142041 with target_weight 340

These nodes are literally on the four corners of the France. How is that possible ? Also I wonder what represent the target_weight ? May be I'm not reading the information where I should ? I used the facade.GetOSMNodeIDOfNode I am right ? Otherwise, what I am missing ?

[TheMarex]

@Fkawala These results are in line with how Contraction Hierarchies work. There is no rigorous theoretical proof on why the CH search space is so small for road networks but the intuition is that a road network contains few important points that most longer routes will cross. These points are connected by shortcuts and allow you to "jump" efficiently from one side to the other side of the country.

These shortcut edges is also why you see edges going to all over the map.

[Fkawala]

@TheMarex thanks !

[Fkawala]

I try to go further than the initial solution proposed by Geisberger et al.

More precisely, I would like to allow detours that imply for the passenger to move from her-his departure (resp. arrival). To do that, I would need to borrow code from #3652 / Phast. Ideally the calculations I'd do for the passenger would use the foor.lua profile to compute paths / distances from a pedestrian POV. Is that sound feasible to do computations wrt to two different lua profiles ?

[SiarheiFedartsou]

Stale.