Implement avoid landmark preprocessing

[TheMarex]

To augment our routing algorithms with a dynamic technique, we need a heuristic that is both flexible and fast. The canonical approach here is using the ALT algorithm which combines A* with landmarks. To use this algorithm we need a pre-processing stage that finds important nodes in the graph called landmarks that let's us estimate the distance for all other nodes. The amount of landmarks and their quality is the biggest driver for performance with ALT, it makes sense to invest time in the technique.

The technique that usually yields the best speedups is called "avoid landmarks" that successively chooses landmarks based on shortest-path trees. The basic idea is to find the sub-tree that has no good landmark yet and pick a leaf from that sub-tree. See approach is described briefly in [4].

API Changes

Tooling

Adds a new tool called osrm-landmark that runs after osrm-extract / osrm-partition and can be used to generate standalone ALT data.

Implementation Changes

• Implement a new tool that loads an .ebg file
• Determine a good set of initial landmarks using the Avoid heuristics
• Use MaxCover to trim down on initial solutions

Reading Material

[1] Bauer et al. Combining Hierarchical and Goal-Directed Speed-Up Techniques for Dijkstra’s Algorithm [2] Goldberg et al. Computing the Shortest Path: A* Search Meets Graph Theory [3] Fuchs On Preprocessing the ALT-Algorithm [4] Goldberg et al. Computing Point-to-Point Shortest Path from External Memory

[HendrikLeuschner]

Hi @TheMarex , I as wondering why you are implementing the ALT algorithm for use in dynamic scenarios when OSRM normally uses MLD. As far as I understood, MLD can be dynamically augmented with data in OSRM (e.g. traffic (https://github.com/Project-OSRM/osrm-backend/wiki/Traffic)). Is there an inherent disadvantage to using MLD with different dynamic weightings? To me, ALT, being based on pure Dijkstra, seems to have a scaling problem towards longer routes. Am I missing something?

Thanks for the feedback Hendrik

[TheMarex]

To me, ALT, being based on pure Dijkstra, seems to have a scaling problem towards longer routes. Am I missing something?

That is true, but this is not about fast weight updates. If you need to specify parameters like height restrictions (which are typically scalar like height <= 3.5m) at runtime you can not pre-compute weights for MLD for every height limit. If you combine that width restrictions and all possible combinations of the two, it quickly because very infeasible. In that case you could use a simple ALT based algorithm to serve these "dynamic" queries, albeit slower.

This would also only be the first step. ALT can easily be combined with both CH and MLD to create hybrids that would be both fast and flexible.

[TimMcCauley]

@TheMarex makes sense, thank you very much for clarifying this. Out of curiosity - can you give a ~rough estimate in regards to how long it will take you to implement the landmarks algorithm?

By the way, have you had a look at Core-ALT? It looks promising but the drawback - if I understand correctly - is that it's dependant on CH again - meaning the ability to service "dynamic" queries is lost?

And customizable CH have the same issue as MLD with the overlay graphs I guess...

[TheMarex]

By the way, have you had a look at Core-ALT?

Yeah this is what we want to work towards for CH + ALT. The trick is to keep every road that you would need to avoid in the Core. This highly depends on the data but for most cases that should be a relatively small part of the road network. For further search space optimizations you can also contract some of the avoidable paths if you keep additional constraints in mind (e.g. for a node v you can contract it, if u -> v -> w is never a shortest path between any neighbors u and w).

[github-actions[bot]]

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