A* search algorithm

In computer science, A* (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.

The algorithm was first described in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael.

The name A* came about because it was originally presented as the optimal version (denoted by the *) of another algorithm, which was dubbed algorithm A.

Intuition

Consider the problem of route finding, for which A* is commonly used. A* incrementally builds all routes leading from the starting point until it finds one that reaches the goal. But, like all informed search algorithms, it only builds routes that appear to lead towards the goal.

To know which routes will likely lead to the goal, A* employs a heuristic estimation of the distance from any given point to the goal. In the case of route finding, this may be the straight-line distance, which is usually an approximation of road distance.

What sets A* apart from best-first search is that it also takes the distance already travelled into account. This makes A* complete and optimal, i.e., A* will always find the shortest route if any exists. It is not guaranteed to perform better than simpler search algorithms. In a maze-like environment, the only way to reach the goal might be to first travel one way (away from the goal) and eventually turn around. In this case trying nodes closer to your destination first may cost you time.

Algorithm description

A* maintains a set of partial solutions, i.e. paths through the graph starting at the start node, stored in a priority queue. The priority assigned to a path

x

is determined by the function

f(x) = g(x) + h(x)

Here, $g(x)$ is the cost of the path so far, i.e. the weight of the edges followed so far. $h(x)$ is the heuristic estimate of the minimal cost to reach the goal from $x$ . For example, if "cost" is taken to mean distance travelled, the straight line distance between two points on a map is a heuristic estimate of the distance to be travelled.

The lower $f(x)$ , the higher the priority (so a min-heap could be used to implement the queue).

function A*(start,goal) var closed := the empty set var q := make_queue(path(start)) while q is not empty var p := remove_first(q) var x := the last node of p if x in closed continue if x = goal return p add x to closed foreach y in successors(p) if y not in closed enqueue(q, extend_path(p,y)) return failure

Here, successors(p) returns the set of paths created by extending p with one neighbor node. It is assumed that the queue maintains an ordering by $f$ -value automatically.

In the closed set (closed), all paths generated so far are recorded, so as to avoid repetition and cycles (making this a graph search). The queue is sometimes analogously called the open set. The closed set can be omitted (yielding a tree search algorithm) if either a solution is guaranteed to exist, or if the successors function is adapted to reject cycles.

Properties

Like breadth-first search, A* is complete in the sense that it will always find a solution if there exists one.

If the heuristic function $h$ is admissible, meaning that it never overestimates the actual minimal cost of reaching the goal, then A* is itself admissible (or optimal) if a closed set is used. If no closed set is used, then $h$ must also be monotonic (or consistent) for A* to be optimal. This means that it never overestimates the cost of getting from a node to its neighbor. Formally, for all nodes $x,y$ where $y$ is a successor of $x$ :

h(x) \le g(y) - g(x) + h(y)

A* is also optimally efficient for any heuristic $h$ , meaning that no algorithm employing the same heuristic will expand fewer nodes than A*, except when there are several partial solutions where $h$ exactly predicts the cost of the optimal path.

Relation to uniform-cost search

Dijkstra's algorithm is a special case of A* where the heuristic is a constant function such as

h(x) = 0

for all

x

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.

Intuition about why A* is not computationally optimal

A* is considered to be computationally optimal in terms of how many nodes it considers, and the above comparison with any other algorithm A argues that A* will always expand fewer nodes than A. However, this comparison assumes that no additional information is available. The A* algorithm is often used on road maps and maps in computer games. These maps are often but not always planar (edges do not cross), and the heuristic used by A* does not take advantage of this. These maps are also spatially coherent (nodes close to a given node are also close to each other), and A* does not take advantage of this either. On graphs with these characteristics, an algorithm that takes advantage of this information can outperform A*; neither of these characteristics can be encoded in the A* heuristic. Although these alternative algorithms do not handle general graphs as A* does, they are nevertheless useful, since many common applications of pathfinding have graphs with known characteristics.

Complexity

The time complexity of A* depends on the heuristic. It is exponential in the worst case, but is polynomial when the heuristic function h meets the following condition:

|h(x) - h^*(x)| \le O(\log h^*(x))

where $h^*$ is the optimal heuristic, i.e. the exact cost to get from $x$ to the goal.

Memory use

More problematic than its time complexity is A*'s memory usage. Several variants of A* have been developed to cope with this, including iterative deepening A*, memory-bounded A* (MA*) and simplified memory bounded A*.

Another informed search algorithm that is optimal and complete if its heuristic is admissible is recursive best-first search (RBFS).

References

External links

Justin Heyes-Jones' A* algorithm tutorial
Herbert Glarner's Interactive Single Step Simulation in VB 6.0, implemented as a DLL, including a GUI allowing simulation in user-defined grids.
Another A* Pathfinding for Beginners (note: incorrectly states that A* always needs a "closed set")
Amit's Thoughts on Path-Finding and A*
Sven Koenig's Demonstration of Lifelong Planning A* and A*
Tony Stentz's Papers on D* (Dynamic A*) Path-Finding
Remko Tronçon and Joost Vennekens's JSearch demo: demonstrates various search algorithms, including A*.
Sune Trudslev's Path finding in C# article

Graph algorithms | Trees (structure) | Routing algorithms | Search algorithms | Combinatorial optimization

Gourt Home::Gourt :: A* search algorithm