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

Question

I'm writing a courier/logistics simulation on OpenStreetMap maps and have realised that the basic A* algorithm as pictured below is not going to be fast enough for large maps (like Greater London).

The green nodes correspond to ones that were put in the open set/priority queue and due to the huge number (the whole map is something like 1-2 million), it takes 5 seconds or so to find the route pictured. Unfortunately 100ms per route is about my absolute limit.

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

I'm looking for methods where I can trade off preprocessing time, space and if needed optimality of the route, for faster queries. The straight-line Haversine formula for the heuristic cost is the most expensive function according to the profiler - I have optimised my basic A* as much as I can.

For example, I was thinking if I chose an arbitrary node X from each quadrant of the 2D array and run A* between each, I can store the routes to disk for subsequent simulations. When querying, I can run A* search only in the quadrants, to get between the precomputed route and the X.

Is there a more refined version of what I've described above or perhaps a different method I should pursue. Many thanks!

For the record, here are some benchmark results for arbitrarily weighting the heuristic cost and computing the path between 10 pairs of randomly picked 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

Surprisingly increasing the coefficient to 1.1 almost halved the execution time whilst keeping the same route.

Beatrice

I think you should try ask there: cs.stackexchange.com – Hoarfrost

A modification to the algorithm that allows for each segment to be weighted (e.g. 8-lane highways have a cost of 1 per unit distance while unpaved dirt tracks have a cost of 50, and all the things in between...) would be one possible starting point. Although you then have the massive task of classifying all the segments you get from the map provider, if they don't already have suitable data associated with them... – Molybdenous

Don't have time to write a full answer, but the state of the art involves finding small separators. Don't settle for approximate results -- very annoying to debug. – Coworker

Are you interested in one to one routes or in computing a distance matrix? Perhaps you can find some hints here: stackoverflow.com/questions/430142 – Fanatic

There must be a way to do this because online mapping products can compute a route around the world instantly. – Steiger

@Steiger - an optimal one? And what kind of "route around the world" are we talking about? For around the world we're probably talking airplanes or cruise ships, which significantly reduces the search space. OP seems to be dealing with streets. – Pavier

@Pavier I doubt it's optimal. The OP doesn't require optimality. I was thinking about a route from the south of Spain to the last mile of Russia or so. google.com/maps/dir/Madrid,+Spain/Russia,+Moskow/… Took about 2 seconds to load the page for a 40h drive and 4000km. – Steiger

@Steiger - ah, well, if it's not optimal it's pretty easy actually. Look how fast the OP manages to find non-optimal paths with the epsilon trick. Combined with better hardware and the fancier methods others have posted, you can definitely do very very well. – Pavier

Try pre-processing the graph using "Arc-Flags"; it's pretty simple and should also give you a nice speedup. – Glomeration

@Steiger These routers don't necessarily just use plain A* but instead Contraction Hierarchies, see GraphHopper and OSRM for really fast routing across dozens of countries and hundreds of kilometers. – Glottalized

@scai: Popular routers definitely do not use A*. At my previous employer we did the math and found that for the serioues players, route recalculation on long routes was too fast to be explained by A*. That said, we suspected they didn't use Contraction Hierarchies either. That's a bit outdated. – Cowardly

Related: programmers.stackexchange.com/questions/261163/… – Victoriavictorian

code.google.com/p/ai-algorithmplatform/wiki/pathfinding is interesting as well, and works blazingly fast. Basically it's multilevel A* and prunes unused quads. – Cagey

You can do A* with landmarks. The idea is you take a landmark and precompute the distance to all nodes in your graph from the landmark. Then, when you have a search query, you use this data to generate a minimally optimistic heuristic (see: admissible and consistent). You should also research "reach" – Barclay

Answer 1

You should be able to make it much faster by trading off optimality. See Admissibility and optimality on wikipedia.

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

You are given a number of algorithms that rely on this idea on wikipedia. I believe this is your best bet to improve the algorithm and that it has the potential to run in your time limit while still returning good paths.

Since your algorithm does deal with millions of nodes in 5 seconds, I assume you also use binary heaps for the implementation, correct? If you implemented them manually, make sure they are implemented as simple arrays and that they are binary heaps.

Pavier

Thanks, I did not think to try it and it improves the speed quite a bit without much penalty. Just multiplying the heuristic cost by 1.5 gives a 91.8km in 200 ms compared to 88.3km in 5 seconds. I will experiment further with varying this as the algorithm runs. – Beatrice

I have tried using a .net SortedList and an array based binary heap from a library and the list was marginally quicker. – Beatrice

@Beatrice - if you're using .net, have you tried to add parallelism? Maybe try to add it to the part that updates a node's neighbors. I'm not sure if it'll help, but it's worth trying to replace a for loop with a Parallel.For. – Pavier

I do use Parallel.ForEach on the entities that will be making use of A*, so all CPU power is used. I don't think small scale parallelisation will make much difference, especially with the synchronisation and overhead. – Beatrice

Something must be wrong there. .net SortedList<TKey, TValue> is implemented using a sorted array, it has O(n) for insert/delete (unless you always add items at bottom of the array). A heap, when properly implemented, has O(log n) instead. It should be faster. Check there for a quite good max heap implementation : referencesource.microsoft.com/#System.Core/System/Linq/Parallel/… For A*, you need the opposite but it's easy to adapt. – Klepht

Nowdays, (unless you are constraint in memory resources) it doesn't make sense to trade optimality, when continental queries can be processed in milliseconds. – Piet

Answer 2

There are specialist algorithms for this problem that do a lot of pre-computation. From memory, the pre-computation adds information to the graph that A* uses to produce a much more accurate heuristic than straight line distance. Wikipedia gives the names of a number of methods at http://en.wikipedia.org/wiki/Shortest_path_problem#Road_networks and says that Hub Labelling is the leader. A quick search on this turns up http://research.microsoft.com/pubs/142356/HL-TR.pdf. An older one, using A*, is at http://research.microsoft.com/pubs/64505/goldberg-sp-wea07.pdf.

Do you really need to use Haversine? To cover London, I would have thought you could have assumed a flat earth and used Pythagoras, or stored the length of each link in the graph.

Ballyrag

Thanks, I'll give those a read. Pythagoras can be way off even for very short distances unfortunately. Switching it out leads to suboptimal routes surprisingly often. – Beatrice

gis.stackexchange.com/questions/58653/… – Beatrice

@Beatrice - You have to reproject the map (think a locally centered transverse Mercator projection)! – Metalworking

There is a simple plane projection: github.com/graphhopper/graphhopper/blob/master/core/src/main/… See also the links in the comment – Bookplate

Answer 3

There's a really great article that Microsoft Research wrote on the subject:

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

The original paper is hosted here (PDF):

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

Essentially there's a few things you can try:

1. Start from the both the source as well as the destination. This helps to minimize the amount of wasted work that you'd perform when traversing from the source outwards towards the destination.
2. Use landmarks and highways. Essentially, find some positions in each map that are commonly taken paths and perform some pre-calculation to determine how to navigate efficiently between those points. If you can find a path from your source to a landmark, then to other landmarks, then to your destination, you can quickly find a viable route and optimize from there.
3. Explore algorithms like the "reach" algorithm. This helps to minimize the amount of work that you'll do when traversing the graph by minimizing the number of vertices that need to be considered in order to find a valid route.

Halidom

Thanks. I did read that article and I was today trying to come up with ways to implement some form of the landmarks approach. The issue for me was not knowing how to pick the landmarks based on the data I had. Highways aren't so easy to identify for me either. I did experiment with reach, but I found the performance gains were negligible. Looking at Microsoft's images, bidirectional Djikstra and A* seem to be not a lot faster than what I've got a the moment, though I've yet to implement either. – Beatrice

Step 2 is known as Contraction Hierarchies. – Cowardly

@Cowardly with landmarks it is a different beast -> ALT – Bookplate

Answer 4

GraphHopper does two things more to get fast, none-heuristic and flexible routing (note: I'm the author and you can try it online here)

1. A not so obvious optimization is to avoid 1:1 mapping of OSM nodes to internal nodes. Instead GraphHopper uses only junctions as nodes and saves roughly 1/8th of traversed nodes.
2. It has efficient implements for A*, Dijkstra or e.g. one-to-many Dijkstra. Which makes a route in under 1s possible through entire Germany. The (none-heuristical) bidirectional version of A* makes this even faster.

So it should be possible to get you fast routes for greater London.

Additionally the default mode is the speed mode which makes everything an order of magnitudes faster (e.g. 30ms for European wide routes) but less flexible, as it requires preprocessing (Contraction Hierarchies). If you don't like this, just disable it and also further fine-tune the included streets for car or probably better create a new profile for trucks - e.g. exclude service streets and tracks which should give you a further 30% boost. And as with any bidirectional algorithm you could easily implement a parallel search.

Bookplate

Answer 5

I think it's worth to work-out your idea with "quadrants". More strictly, I'd call it a low-resolution route search.

You may pick X connected nodes that are close enough, and treat them as a single low-resolution node. Divide your whole graph into such groups, and you get a low-resolution graph. This is a preparation stage.

In order to compute a route from source to target, first identify the low-res nodes they belong to, and find the low-resolution route. Then improve your result by finding the route on high-resolution graph, however restricting the algorithm only to nodes that belong to hte low-resolution nodes of the low-resolution route (optionally you may also consider neighbor low-resolution nodes up to some depth).

This may also be generalized to multiple resolutions, not just high/low.

At the end you should get a route that is close enough to optimal. It's locally optimal, but may be somewhat worse than optimal globally by some extent, which depends on the resolution jump (i.e. the approximation you make when a group of nodes is defined as a single node).

Antoniaantonie

Answer 6

There are dozens of A* variations that may fit the bill here. You have to think about your use cases, though.

• Are you memory- (and also cache-) constrained?
• Can you parallelize the search?
• Will your algorithm implementation be used in one location only (e.g. Greater London and not NYC or Mumbai or wherever)?

There's no way for us to know all the details that you and your employer are privy to. Your first stop thus should be CiteSeer or Google Scholar: look for papers that treat pathfinding with the same general set of constraints as you.

Then downselect to three or four algorithms, do the prototyping, test how they scale up and finetune them. You should bear in mind you can combine various algorithms in the same grand pathfinding routine based on distance between the points, time remaining, or any other factors.

As has already been said, based on the small scale of your target area dropping Haversine is probably your first step saving precious time on expensive trig evaluations. NOTE: I do not recommend using Euclidean distance in lat, lon coordinates - reproject your map into a e.g. transverse Mercator near the center and use Cartesian coordinates in yards or meters!

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

Extra optimization steps may include getting rid of dynamic memory allocation, and using efficient indexing for search among the nodes (think R-tree and its derivatives/alternatives).

Metalworking

Answer 7

I worked at a major Navigation company, so I can say with confidence that 100 ms should get you a route from London to Athens even on an embedded device. Greater London would be a test map for us, as it's conveniently small (easily fits in RAM - this isn't actually necessary)

First off, A* is entirely outdated. Its main benefit is that it "technically" doesn't require preprocessing. In practice, you need to pre-process an OSM map anyway so that's a pointless benefit.

The main technique to give you a huge speed boost is arc flags. If you divide the map in say 5x6 sections, you can allocate 1 bit position in a 32 bits integer for each section. You can now determine for each edge whether it's ever useful when traveling to section {X,Y} from another section. Quite often, roads are bidirectional and this means only one of the two directions is useful. So one of the two directions has that bit set, and the other has it cleared. This may not appear to be a real benefit, but it means that on many intersections you reduce the number of choices to consider from 2 to just 1, and this takes just a single bit operation.

Cowardly

For London, one major advantage is that you get these bits set on bridges as well. A* can suffer quite a bit from unnecessarily crossing the river and getting stuck on the other bank. – Cowardly

Answer 8

Usually A* comes along with too much memory consumption rather than time stuggles.

However I think it could be useful to first only compute with nodes that are part of "big streets" you would choose a highway over a tiny alley usually.

I guess you may already use this for your weight function but you can be faster if you use some priority Queue to decide which node to test next for further travelling.

Also you could try reducing the graph to only nodes that are part of low cost edges and then find a way from to start/end to the closest of these nodes. So you have 2 paths from start to the "big street" and the "big street" to end. You can now compute the best path between the two nodes that are part of the "big streets" in a reduced graph.

Laplace

Answer 9

Old question, but yet:

Try to use different heaps that "binary heap". 'Best asymptotic complexity heap' is definetly Fibonacci Heap and it's wiki page got a nice overview:

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

Note that binary heap has simpler code and it's implemented over array and traversal of array is predictable, so modern CPU executes binary heap operations much faster.

However, given dataset big enough, other heaps will win over binary heap, because of their complexities...

This question seems like dataset big enough.

Fourchette