A * Algorithm for very large graphs, any thoughts on cache shortcuts?

Question

I am writing courier / logistics simulations on OpenStreetMap maps and realized that the basic A * algorithm, as shown in the figure below, will not be fast enough for large maps (e.g. Greater London).

The green nodes correspond to those that have been placed in the open dialing / priority queue, and due to the huge number (the entire map is approximately 1-2 million), it takes about 5 seconds to find the drawn route. Unfortunately, 100 ms per route is my absolute limit.

Currently, nodes are stored both in the adjacency list and in the 2D 100x100 spatial array.

I am looking for methods where I can exchange pre-processing time, space and, if necessary, route optimality, for faster requests. The direct Haversin formula for heuristic costs is the most expensive function according to the profiler - I have optimized my main A * as much as possible.

For example, I thought, if I select an arbitrary node X from each quadrant of a 2D array and run A * between each, I can save the routes to disk for future simulations. When prompted, I can start the A * search only in quadrants to go between the pre-calculated route and X.

Is there a better version of what I described above, or maybe another method that I should pursue. Thank you very much!

For the record, here are some test results for arbitrary weighting of heuristic costs and calculation of the path between 10 pairs of randomly selected nodes:

Weight // AvgDist% // Time (ms) 1 1 1461.2 1.05 1 1327.2 1.1 1 900.7 1.2 1.019658848 196.4 1.3 1.027619169 53.6 1.4 1.044714394 33.6 1.5 1.063963413 25.5 1.6 1.071694171 24.1 1.7 1.084093229 24.3 1.8 1.092208509 22 1.9 1.109188175 22.5 2 1.122856792 18.2 2.2 1.131574742 16.9 2.4 1.139104895 15.4 2.6 1.140021962 16 2.8 1.14088128 15.5 3 1.156303676 16 4 1.20256964 13 5 1.19610861 12.9 

Amazingly increasing the coefficient to 1.1, the execution time was almost halved, keeping the same route.

Answer 1

You must be able to do this much faster when trading optimality. See Acceptability and Optimality on Wikipedia.

The idea is to use the epsilon value, which will lead to a solution no worse than 1 + epsilon compared to the optimal path, but this will lead to the fact that the algorithm will consider fewer nodes. Note that this does not mean that the returned solution will always be 1 + epsilon times the optimal path. This is the worst case. I do not know exactly how this will behave in practice for your problem, but I think it is worth exploring.

You are provided with a series of algorithms that rely on this idea on Wikipedia. I believe that this is your best choice for improving the algorithm and the ability to work on time, while maintaining good paths.

Since your algorithm deals with millions of nodes in 5 seconds, I suppose you also use binary heaps for implementation, right? If you executed them manually, make sure they are implemented as simple arrays and that they are binary heaps.

Answer 2

There are special algorithms for this problem that do a lot of preliminary calculations. From memory, a preliminary calculation adds information to the graph, which uses A * to obtain a much more accurate heuristic than the linear distance. Wikipedia gives the names of several methods at http://en.wikipedia.org/wiki/Shortest_path_problem#Road_networks and says that the leader of Hub Labeling is the leader. A quick search on this subject appears http://research.microsoft.com/pubs/142356/HL-TR.pdf . The elder using A * is located at http://research.microsoft.com/pubs/64505/goldberg-sp-wea07.pdf .

Do you really need to use Haversine? To cover London, I would think that you could take flat land and use Pythagoras, or keep the length of each link on the chart.

Answer 3

There's a really wonderful article Microsoft Research wrote on this subject:

http://research.microsoft.com/en-us/news/features/shortestpath-070709.aspx

Original paper posted here (PDF):

http://www.cc.gatech.edu/~thad/6601-gradAI-fall2012/02-search-Gutman04siam.pdf

Essentially, there are a few things you can try:

• Start with both the source and destination. This helps to minimize the amount of wasted work that you will perform when moving from source to destination.
• Use landmarks and highways. Essentially, find some positions on each map that usually take paths, and do some preliminary calculations to determine how to effectively move between these points. If you can find a way from your source to a landmark, then to other attractions, and then to your destination, you can quickly find a viable route and optimize from there.
• Explore algorithms similar to the reach algorithm. This helps to minimize the amount of work that you will perform while going through the graph, minimizing the number of vertices that need to be considered in order to find the right route.

Answer 4

GraphHopper makes two things faster, non-heuristic, and flexible routes (note: I'm an author and you can try it online here )

• A less obvious optimization is to avoid mapping 1: 1 OSM nodes to internal nodes. Instead, GraphHopper uses only nodes as nodes and saves about 1/8 of the nodes passed.
• It has effective tools for A *, Dijkstra or, for example, one-to-many Dijkstra. Which makes the route less than one possible in all of Germany. The (non-heuristic) bidirectional version of A * makes it even faster.

This way you can get quick routes for greater London.

In addition, the default mode is the speed mode, which makes all orders of magnitude faster (for example, 30 ms for European routes), but less flexible, since it requires preliminary processing ( Hierarchy of abbreviations ). If you don’t like it, just turn it off, and then fine-tune the included streets for the car, or perhaps it’s better to create a new profile for trucks, for example. exclude office streets and paths that should give you an extra 30 percent boost. And as with any bidirectional algorithm, you can easily implement a parallel search.

Answer 5

I think it's worth thinking about your idea with the "quadrants." More strictly, I would call it low-resolution route search.

You can select X connected nodes that are close enough and treat them as a single low-level node. Divide your entire graph into such groups and you will get a low resolution graph. This is the preparation phase.

To calculate the route from source to destination, first identify the low-resolution nodes to which they belong and find the low-resolution route. Then improve your result by finding the route on a high-resolution graph, however restricting the algorithm to only nodes that belong to hte low-resolution nodes of a low-resolution route (you can also consider neighboring low-resolution nodes to some depth).

It can also be generalized to multiple resolutions, not just high / low.

In the end, you should get a route that is reasonably close to optimal. It is locally optimal, but it can be slightly worse than optimally globally to some extent, which depends on the jump resolution (i.e., the approximation you make when a group of nodes is defined as a single node).

Answer 6

There are dozens of variations of A * that may fit the bill here. However, you should think about your use cases.

• Are you limited by memory (as well as cache)?
• Can you parallelize the search?
• Will your implementation of the algorithm be used in only one place (for example, in Greater London, and not in New York or Mumbai or somewhere else)?

It is not possible to find out all the information that you and your employer will know. So your first stop should be CiteSeer or Google Scholar: find documents that handle pathfinding with the same common set of constraints as you.

Then reduce the selection to three or four algorithms, perform prototyping, check how they scale and finish them. You must remember that you can combine different algorithms in the same road search program, based on the distance between points, time remaining, or any other factors.

As already mentioned, based on the small scale of your target area, a Haversine drop is probably your first step, saving valuable time on costly trigger estimates. NOTE. I do not recommend using the Euclidean distance in lat, lon coordinates - reprogram your map, for example. transverse Mercator near the center and use the Cartesian coordinates in yards or meters!

Precompiling is second, and changing compilers may be the obvious third idea (switching to C or C ++ - see https://benchmarksgame.alioth.debian.org/ for more details).

Additional optimization steps may include getting rid of dynamic memory allocation and using effective indexing to search among nodes (I think the R-tree and its derivatives / alternatives).

Answer 7

I worked for a large navigation company, so I can say with confidence that 100 ms should get you a route from London to Athens, even to the built-in device. Greater London will be a test card for us, because it is conveniently small (easily fits into RAM - in fact, this is not necessary)

Firstly, A * is completely out of date. Its main advantage is that it "technically" does not require pre-processing. In practice, you need to pre-process the OSM card to get valueless benefits.

The main way to give you tremendous speed acceleration is through arcs. If you split the card in a 5x6 partition, you can allocate 1 bit position in a 32-bit integer for each partition. Now you can determine for each edge whether this is really useful when traveling to the {X,Y} section from another section. Quite often, the roads are bidirectional, and this means that only one of the two directions is useful. Thus, one of the two directions has a bit set, and the other is cleared. This may not seem like a real advantage, but it means that at many intersections you reduce the number of options to consider from 2 to 1, and it takes only one bit operation.

Answer 8

A * usually comes with too much memory, not a time delay.

However, I think it would be useful to first calculate only the nodes that are part of the "big streets", you usually chose a highway over a tiny alley.

I think you can already use this for your weight function, but you can be faster if you use some priority queue to decide which node to check next for further travel.

You can also try to reduce the graph only by nodes that are part of inexpensive edges, and then find a way from the beginning / end to the nearest of these nodes. Thus, you have 2 ways from the beginning to the "big street" and "big street" to the end. Now you can calculate the best path between the two nodes that are part of the "big streets" in the reduced graph.

Answer 9

Old question, but still:

Try using different heaps that are "binary heap". The “best bunch of asymptotic complexity” is definitely the Fibonacci bunch, and this wiki page got a good overview:

https://en.wikipedia.org/wiki/Fibonacci_heap#Summary_of_running_times

Please note that the binary heap has simpler code and is implemented on the array, and array traversal is predictable, therefore the modern processor performs operations with the binary heap much faster.

However, given the data set is large enough, other heaps will win the binary heap due to their complexity ...

This question seems big enough.