A* search algorithm
A* search algorithm
- A*** (pronounced "A-star") is a graph traversal and [[pathfinding]] algorithm that is used in many fields of computer science due to its completeness, optimality, and optimal efficiency. Given a weighted graph, a source node and a goal node, the algorithm finds the shortest path (with respect to the given weights) from source to goal.
One major practical drawback is its <math>O(b^d)</math> space complexity where is the depth of the shallowest solution (the length of the shortest path from the source node to any given goal node) and is the branching-factor (the maximum number of successors for any given state). In practical travel-routing systems, it is generally outperformed by algorithms that can pre-process the graph to attain better performance, as well as by memory-bounded approaches; however, A* is still the best solution in many cases.
Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute (now SRI International) first published the algorithm in 1968. It can be seen as an extension of Dijkstra's algorithm. A* achieves better performance by using heuristics to guide its search.
The A* algorithm terminates once it finds the shortest path to a specified goal, rather than generating the entire shortest-path tree from a specified source to all possible goals.
History
A was created as part of the Shakey project, which had the aim of building a mobile robot that could plan its own actions. Nils Nilsson originally proposed using the Graph Traverser algorithm for Shakey's path planning. Graph Traverser is guided by a heuristic function , the estimated distance from node to the goal node: it entirely ignores , the distance from the start node to . Bertram Raphael suggested using the sum, . Peter Hart invented the concepts we now call admissibility and consistency of heuristic functions. A was originally designed for finding least-cost paths when the cost of a path is the sum of its costs, but it has been shown that A* can be used to find optimal paths for any problem satisfying the conditions of a cost algebra.
The original 1968 A paper claiming that consistency was not required, but this was shown to be false in 1985 in Dechter and Pearl's definitive study of A's optimality (now called optimal efficiency), which gave an example of A with a heuristic that was admissible but not consistent expanding arbitrarily more nodes than an alternative A-like algorithm.
Pseudocode The following pseudocode describes the algorithm:
<syntaxhighlight lang="pascal" start="1"> function reconstruct_path(came_from, current) total_path := {current} while current in came_from.keys: current := came_from[current] total_path.prepend(current) return total_path
// A* finds a path from start to goal. // h is the heuristic function. h(n) estimates the cost to reach goal from node n. function a_star(start, goal, h) // The set of discovered nodes that may need to be (re-)expanded. // Initially, only the start node is known. // This is usually implemented as a min-heap or priority queue rather than a hash-set. open_set := {start}
// For node n, came_from[n] is the node immediately preceding it on the cheapest path from the start // to n currently known. came_from := an empty map
// For node n, g_score[n] is the currently known cost of the cheapest path from start to n. g_score := map with default value of Infinity g_score[start] := 0
// For node n, f_score[n] := g_score[n] + h(n). f_score[n] represents our current best guess as to // how cheap a path could be from start to finish if it goes through n. f_score := map with default value of Infinity f_score[start] := h(start)
while open_set is not empty // This operation can occur in O(Log(N)) time if open_set is a min-heap or a priority queue current := the node in open_set having the lowest f_score[] value if current = goal return reconstruct_path(came_from, current)
open_set.remove(current) for each neighbor of current // d(current,neighbor) is the weight of the edge from current to neighbor // tentative_g_score is the distance from start to the neighbor through current tentative_g_score := g_score[current] + d(current, neighbor) if tentative_g_score < g_score[neighbor] // This path to neighbor is better than any previous one. Record it! came_from[neighbor] := current g_score[neighbor] := tentative_g_score f_score[neighbor] := tentative_g_score + h(neighbor) if neighbor not in open_set open_set.add(neighbor)
// Open set is empty but goal was never reached return failure
</syntaxhighlight>
- Remark:** In this pseudocode, if a node is reached by one path, removed from open_set, and subsequently reached by a cheaper path, it will be added to open_set again. This is essential to guarantee that the path returned is optimal if the heuristic function is admissible but not consistent. If the heuristic is consistent, when a node is removed from open_set the path to it is guaranteed to be optimal so the test ‘tentative_g_score < g_score[neighbor]’ will always fail if the node is reached again. The pseudocode implemented here is sometimes called the *graph-search* version of A*. This is in contrast with the version without the ‘tentative_g_score < g_score[neighbor]’ test to add nodes back to open_set, which is sometimes called the *tree-search* version of A* and require a consistent heuristic to guarantee optimality.
Example An example of an A* algorithm in action where nodes are cities connected with roads and h(x) is the straight-line distance to the target point:
- Key:** green: start; blue: goal; orange: visited
The A* algorithm has real-world applications. In this example, edges are railroads and h(x) is the great-circle distance (the shortest possible distance on a sphere) to the target. The algorithm is searching for a path between Washington, D.C., and Los Angeles.
Implementation details There are a number of simple optimizations or implementation details that can significantly affect the performance of an A implementation. The first detail to note is that the way the priority queue handles ties can have a significant effect on performance in some situations. If ties are broken so the queue behaves in a LIFO manner, A will behave like depth-first search among equal cost paths (avoiding exploring more than one equally optimal solution).
When a path is required at the end of the search, it is common to keep with each node a reference to that node's parent. At the end of the search, these references can be used to recover the optimal path. If these references are being kept then it can be important that the same node doesn't appear in the priority queue more than once (each entry corresponding to a different path to the node, and each with a different cost). A standard approach here is to check if a node about to be added already appears in the priority queue. If it does, then the priority and parent pointers are changed to correspond to the lower-cost path. A standard binary heap based priority queue does not directly support the operation of searching for one of its elements, but it can be augmented with a hash table that maps elements to their position in the heap, allowing this decrease-priority operation to be performed in logarithmic time. Alternatively, a Fibonacci heap can perform the same decrease-priority operations in constant amortized time.
Special cases Dijkstra's algorithm, as another example of a uniform-cost search algorithm, can be viewed as a special case of A where for all x. General depth-first search can be implemented using A by considering that there is a global counter C initialized with a very large value. Every time we process a node we assign C to all of its newly discovered neighbors. After every single assignment, we decrease the counter C by one. Thus the earlier a node is discovered, the higher its value. Both Dijkstra's algorithm and depth-first search can be implemented more efficiently without including an value at each node.
Properties ### Termination and completeness On finite graphs with non-negative edge weights A is guaranteed to terminate and is complete, i.e. it will always find a solution (a path from start to goal) if one exists. On infinite graphs with a finite branching factor and edge costs that are bounded away from zero (<math display="inline">d(x,y)>\varepsilon>0</math> for some fixed <math>\varepsilon</math>), A is guaranteed to terminate only if there exists a solution. They considered a variety of definitions of Alts and P in combination with A's heuristic being merely admissible or being both consistent and admissible. The most interesting positive result they proved is that A, with a consistent heuristic, is optimally efficient with respect to all admissible A-like search algorithms on all "non-pathological" search problems. Roughly speaking, their notion of the non-pathological problem is what we now mean by "up to tie-breaking". This result does not hold if A's heuristic is admissible but not consistent. In that case, Dechter and Pearl showed there exist admissible A-like algorithms that can expand arbitrarily fewer nodes than A on some non-pathological problems.
Optimal efficiency is about the set of nodes expanded, not the number of node expansions (the number of iterations of A's main loop). When the heuristic being used is admissible but not consistent, it is possible for a node to be expanded by A many times, an exponential number of times in the worst case. In such circumstances, Dijkstra's algorithm could outperform A by a large margin. However, more recent research found that this pathological case only occurs in certain contrived situations where the edge weight of the search graph is exponential in the size of the graph and that certain inconsistent (but admissible) heuristics can lead to a reduced number of node expansions in A searches.
Bounded relaxation thumb|A* search that uses a heuristic that is 5.0(=ε) times a consistent heuristic, and obtains a suboptimal path While the admissibility criterion guarantees an optimal solution path, it also means that A must examine all equally meritorious paths to find the optimal path. To compute approximate shortest paths, it is possible to speed up the search at the expense of optimality by relaxing the admissibility criterion. Oftentimes we want to bound this relaxation, so that we can guarantee that the solution path is no worse than (1 + ε) times the optimal solution path. This new guarantee is referred to as ε*-admissible.
There are a number of ε-admissible algorithms:
Weighted A/Static Weighting's. If ha(n) is an admissible heuristic function, in the weighted version of the A search one uses , as the heuristic function, and perform the A search as usual (which eventually happens faster than using ha since fewer nodes are expanded). The path hence found by the search algorithm can have a cost of at most ε times that of the least cost path in the graph. Convex Upward/Downward Parabola (XUP/XDP). Modification to the cost function in weighted A to push optimality toward the start or goal. XDP gives paths which are near optimal close to the start, and XUP paths are near-optimal close to the goal. Both yield <math>\epsilon</math>-optimal paths overall. :<math>f_{\text{XDP}}(n) = \frac{1}{2\epsilon} \left[ \ g(n) + (2\epsilon - 1) + \sqrt{(g(n)-h(n))^2 + 4\epsilon g(n)h(n) } \ \right]</math>. :<math>f_{\text{XUP}}(n) = \frac{1}{2\epsilon} \left[ \ g(n)+h(n) + \sqrt{(g(n)+h(n))^2+4\epsilon (\epsilon-1)h(n)^2} \ \right]</math>. Piecewise Upward/Downward Curve (pwXU/pwXD). Similar to XUP/XDP but with piecewise functions instead of parabola. Solution paths are also <math>\epsilon</math>-optimal. :<math>f_{\text{pwXD}}(n) = \begin{cases} g(n)+h(n), & \text{if } h(n) > g(n) \\ g(n) + (2\epsilon-1)h(n)/\epsilon, & \text{if } h(n) \le g(n) \end{cases}</math> :<math>f_{\text{pwXU}}(n) = \begin{cases} g(n)/(2\epsilon-1)+h(n), & \text{if } g(n) < (2\epsilon-1)h(n) \\ (g(n) + h(n))/\epsilon, & \text{if } g(n) \ge (2\epsilon-1)h(n) \end{cases}</math> Dynamic Weighting uses the cost function , where <math>w(n) = \begin{cases} 1 - \frac{d(n)}{N} & d(n) \le N \\ 0 & \text{otherwise} \end{cases}</math>, and where is the depth of the search and N is the anticipated length of the solution path. Sampled Dynamic Weighting uses sampling of nodes to better estimate and debias the heuristic error. <math>A^_\varepsilon</math>. uses two heuristic functions. The first is the FOCAL list, which is used to select candidate nodes, and the second hF is used to select the most promising node from the FOCAL list. Aε selects nodes with the function , where A and B are constants. If no nodes can be selected, the algorithm will backtrack with the function , where C and D are constants. AlphA attempts to promote depth-first exploitation by preferring recently expanded nodes. AlphA uses the cost function <math>f_\alpha(n) = (1 + w_\alpha(n)) f(n)</math>, where <math>w_\alpha(n) = \begin{cases} \lambda & g(\pi(n)) \le g(\tilde{n}) \\ \Lambda & \text{otherwise} \end{cases}</math>, where λ and Λ are constants with <math>\lambda \le \Lambda</math>, π(n) is the parent of n, and ñ* is the most recently expanded node.
Complexity As a heuristic search algorithm, the performance of A is heavily influenced by the quality of the heuristic function <math display="inline">h(n)</math>. If the heuristic closely approximates the true cost to the goal, A can significantly reduce the number of node expansions. On the other hand, a poor heuristic can lead to many unnecessary expansions.
Worst case In the worst case, A expands all nodes <math display="inline">n</math> for which <math display="inline">f(n)=g(n)+h(n) \leq C^{}</math>, where <math display="inline">C^{*}</math> is the cost of the optimal goal node.
Why it cannot be worse Suppose there is a node <math display="inline">N'</math> in the open list with <math display="inline">f(N') > C^{}</math>, and it's the next node to be expanded. Since the goal node has <math display="inline">f(goal)=g(goal)+h(goal)=g(goal)=C^{}</math>, and <math display="inline"> f(N') > C^{} </math>, the goal node will have a lower f-value and will be expanded before <math display="inline">N'</math>. Therefore, A never expands nodes with <math display="inline"> f(n) > C^{*} </math>.
Why it cannot be better Assume there exists an optimal algorithm that expands fewer nodes than <math display="inline"> C^{} </math> in the worst case using the same heuristic. That means there must be some node <math display="inline"> N' </math> such that <math display="inline"> f(N') < C^{} </math>, yet the algorithm chooses not to expand it.
Now consider a modified graph where a new edge of cost <math display="inline"> \varepsilon </math> (with <math display="inline"> \varepsilon > 0 </math>) is added from <math display="inline"> N' </math> to the goal. If <math display="inline"> f(N')+\varepsilon<C^{*} </math>, then the new optimal path goes through <math display="inline"> N' </math>. However, since the algorithm still avoids expanding <math display="inline"> N' </math>, it will miss the new optimal path, violating its optimality.
Therefore, no optimal algorithm including A could expand fewer nodes than <math display="inline"> C^{} </math> in the worst case.
Mathematical notation The worst-case complexity of A is often described as <math display="inline">O(b^d)</math>, where <math>b</math> is the branching factor and <math display="inline">d</math> is the depth of the shallowest goal. While this gives a rough intuition, it does not precisely capture the actual behavior of A.
A more accurate bound considers the number of nodes with <math display="inline">f(n) \leq C^{}</math>. If <math>\varepsilon</math> is the smallest possible difference in <math display="inline">f</math>-cost between distinct nodes, then A may expand up to: {{center|<math>O\left(\frac{C^{*}}{\varepsilon}\right)</math>}}
This represents both the time and space complexity in the worst case.
Space complexity The space complexity of A* is roughly the same as that of all other graph search algorithms, as it keeps all generated nodes in memory. Other cases include an Informational search with online learning.
Relations to other algorithms What sets A* apart from a greedy best-first search algorithm is that it takes the cost/distance already traveled, , into account.
Some common variants of Dijkstra's algorithm can be viewed as a special case of A where the heuristic <math>h(n) = 0</math> for all nodes; A itself is a special case of a generalization of branch and bound.
A* is similar to beam search except that beam search maintains a limit on the numbers of paths that it has to explore.
Variants Anytime A Block A D Field D *Fringe Fringe Saving A (FSA*) Generalized Adaptive A (GAA*) *Incremental heuristic search Reduced A [[iterative-deepening-a|Iterative deepening A (IDA)]] *[[jump-point-search]] Lifelong Planning A (LPA*) New Bidirectional A (NBA*) [[sma|Simplified Memory bounded A (SMA)]] [[theta]]
A* can also be adapted to a bidirectional search algorithm, but special care needs to be taken for the stopping criterion.