A* search algorithm
|
|
The A* search algorithm (pronounced "A star") is a graph search algorithm that finds a path from a given initial node to a given goal node (or one passing a given goal test). It employs a "heuristic estimate" that ranks each node by an estimate of the best route that goes through that node. It visits the nodes in order of this heuristic estimate. The A* algorithm is therefore an example of best-first search.
| Contents |
Intuition
Let's consider a motivating example. Say you are standing at intersection A, and you would like to go to an intersection B that you happen to know is north of where you currently are. In this case the intersections are the vertices of the graph and the roads are edges.
If you do a breadth-first search like Dijkstra's Algorithm dictates, you would search all points within a fixed circular radius, gradually expanding this circle to search intersections farther and farther away from your starting point. This might be an effective strategy if you don't know where your destination is, such as police searching for a criminal in hiding.
However, it is a waste of time if you have more information. A better strategy is to explore the intersection directly to the north first, because it's the closest vertex to B. Then, the roads permitting, you would continue to explore intersections closer and closer to the goal B. You might have to occasionally backtrack, but on typical maps this is a much quicker strategy. Moreover, it can be proved that this strategy will find the best possible route, just as breadth-first search does. This is the essence of A* search.
However, A* is not guaranteed to perform better than simpler search algorithms. In a maze-like environment, the only way to reach your destination might be to travel south first and eventually turn around. In this case trying nodes closer to your destination first may cost you time.
Overview
A search algorithm that is guaranteed always to find the shortest path to a goal is called admissible. If A* uses a heuristic that never overestimates the distance (or in general, the cost) to the goal, A* can be proven to be admissible. A heuristic that makes the A* search admissible is itself called an admissible heuristic.
If the estimate simply always returns zero, which is never an overestimate, then A* will effectively perform Dijkstra's algorithm and still find an optimal solution, albeit not as quickly. The best possible heuristic, although usually impractical to compute, is the actual minimal distance to the goal. One example of a practical admissible heuristic is the straight-line distance to the goal on a map.
It can be proven that A* considers no more nodes than any other admissible search algorithm, provided that the alternative algorithm does not have a more accurate heuristic estimate. In this sense, A* is the computationally most-efficient algorithm that's guaranteed to find the shortest path.
Description
A* begins at a selected node. Applied to this node are the "cost" of entering this node (usually zero for the initial node). A* then estimates the distance to the goal node from the current node. This estimate and the cost added together are the heuristic which is assigned to the path leading to this node. The node is then added to a priority queue, often called "open".
The algorithm then removes the next node from the priority queue (because of the way a priority queue works, the node removed will have the lowest heuristic). If the queue is empty, there is no path from the initial node to the goal node and the algorithm stops. If the node is the goal node, A* reconstructs and outputs the successful path and stops. This path reconstruction from the stored closed nodes (see below) means it is not necessary to store the path-so-far within each node.
If the node is not the goal node, new nodes are created for all admissible adjoining nodes; the exact way of doing this depends on the problem at hand. For each successive node, A* calculates the "cost" of entering the node and saves it with the node. This cost is calculated from the cumulative sum of costs stored with its ancestors, plus the cost of the operation which reached this new node.
The algorithm also maintains a "closed" list of nodes which have been checked. If a newly generated node is already in this list with an equal or lower cost, no further processing is done on that node or with the path associated with it. If a node in the closed list matches the new one, but has been stored with a higher cost, it is removed from the closed list, and processing continues on the new node.
Next, an estimate of the new node's distance to the goal is added to the cost to form the heuristic for that node. This is then added to the "open" priority queue, unless an identical node with lesser or equal heuristic is found there.
Once the above three steps have been repeated for each new adjoining node, the original node taken from the priority queue is added to the "closed" list. The next node is then popped from the priority queue and the process is repeated.
Intuition about why A* is admissible and computationally optimal
There is an intuitive explanation of why A* is both admissible and considers fewer nodes than any other admissible search algorithm. The intuition rests on the recognition that A* has an "optimistic" estimate of the cost of a path through every node that it considers -- optimistic in that the true cost of a path through that node to the goal will be at least as great as the estimate. But, critically, as far as A* "knows", that optimistic estimate might be achievable.
When A* terminates its search, it by definition has found a path whose actual cost is lower than the estimated cost of any path through any open node. But since those estimates are optimistic, A* can safely ignore those nodes. In other words, A* will never overlook the possibility of a lower-cost path and so is admissible.
Suppose now that some other search algorithm A terminates its search with a path whose actual cost is not less than the estimated cost of a path through some open node. Algorithm A cannot rule out the possibility, based on the heuristic information it has, that a path through that node might have a lower cost. So while A might consider fewer nodes than A*, it cannot be admissible. Accordingly, A* considers the fewest nodes of any admissible search algorithm that uses a no more accurate heuristic estimate.
Monotonicity
The "open" and "closed" bookkeeping is not necessary if it can be guaranteed that the first path generated to any node is the shortest one. This situation arises if the heuristic is not only admissible but monotonic, meaning that the difference between the heuristics of any two connected nodes does not overestimate the actual distance between those nodes. This is a form of the triangle inequality. Not all admissible heuristics are monotonic, but straight-line distance on a map is.
References
- P. E. Hart, N. J. Nilsson, B. Raphael: A Formal Basis for the Heuristic Determination of Minimum Cost Paths, IEEE Transactions on Systems Science and Cybernetics SSC4 (2), pp. 100-107, 1968.
- P. E. Hart, N. J. Nilsson, B. Raphael: Correction to "A Formal Basis for the Heuristic Determination of Minimum Cost Paths", SIGART Newsletter, 37, pp. 28-29, 1972.
External links
- Justin Heyes-Jones' A* algorithm tutorial (http://www.geocities.com/jheyesjones/astar.html)
- Another A* Pathfinding for Beginners (http://www.policyalmanac.org/games/aStarTutorial.htm)
- Amit's Thoughts on Path-Finding and A* (http://theory.stanford.edu/~amitp/GameProgramming/)
- Sven Koenig's Lifelong Planning A* vs. A* demo (http://www.cc.gatech.edu/fac/Sven.Koenig/greedyonline/applet.html)
- Remko Tronçon and Joost Vennekens's JSearch demo (http://www.cs.kuleuven.ac.be/~remko/jsearchdemo/): demonstrates various search algorithms, including A*.de:A*-Algorithmus