# A*

> Source: https://aiwiki.ai/wiki/a
> Updated: 2026-04-26
> Categories: Algorithms, Artificial Intelligence
> From AI Wiki (https://aiwiki.ai), a free encyclopedia of artificial intelligence. Quote with attribution.

**A\*** (pronounced "A-star") is a best-first [graph](/wiki/graph) search algorithm that finds a least-cost path from a start node to a goal node. It evaluates candidate paths using the function *f(n) = g(n) + h(n)*, where *g(n)* is the actual cost from the start to node *n* and *h(n)* is a [heuristic](/wiki/heuristic) estimate of the remaining cost from *n* to the goal. When the heuristic is admissible (never overestimates the true remaining cost), A\* is guaranteed to return an optimal solution. The algorithm was introduced in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael at the Stanford Research Institute (SRI) as part of the [Shakey the Robot](/wiki/shakey_the_robot) project, and it remains one of the most widely taught and deployed algorithms in [artificial intelligence](/wiki/artificial_intelligence), used in video-game pathfinding, robot motion planning, route planning, puzzle solving, and parsing of probabilistic grammars.

## Intuition

A\* is what happens when you take Dijkstra's algorithm and give it a sense of direction. Dijkstra spreads outward in concentric rings of cost from the start, eventually reaching the goal but expanding many nodes that lie nowhere near it. A\* uses a heuristic to bias the search toward nodes that look closer to the goal, so it expands fewer nodes while still keeping Dijkstra's optimality guarantee whenever the heuristic is admissible.

Think of it as planning a road trip. The cost so far, *g(n)*, is what your odometer says. The heuristic, *h(n)*, is your best guess of how far you still have to go (often a straight-line distance). At each step, A\* picks the city with the smallest total estimated trip length *g(n) + h(n)*. As long as the guess never exceeds the true distance, the first city A\* visits that is the destination must be reached by the shortest road network path.

If *h(n)* = 0 for every node, A\* degenerates into Dijkstra's algorithm. If you ignore *g(n)* and rank nodes by *h(n)* alone, you get greedy best-first search, which is fast but does not guarantee an optimal path. A\* sits in the middle, using both pieces of information to be both efficient and correct.

## History

A\* came out of work on Shakey, a wheeled mobile robot built at the Stanford Research Institute (now SRI International) between 1966 and 1972. Shakey was the first general-purpose mobile robot able to reason about its own actions, and it needed an algorithm that could plan a route across a known indoor environment while avoiding obstacles.

Nils Nilsson had earlier proposed a method called the Graph Traverser. Bertram Raphael suggested combining the cost so far with a heuristic estimate of the remaining cost into a single evaluation function *f = g + h*. Peter Hart formalized the conditions under which the resulting search is guaranteed to find an optimal solution, introducing the notions of admissibility and consistency for heuristic functions. The three published their work in 1968 as "A Formal Basis for the Heuristic Determination of Minimum Cost Paths" in *IEEE Transactions on Systems Science and Cybernetics*.

The original 1968 paper claimed that A\* is optimally efficient, in the sense that no other admissible algorithm with the same heuristic information could expand fewer nodes. The proof in that paper had a flaw, and the authors published a correction in 1972 in *SIGART Newsletter* clarifying that the optimal-efficiency result holds when the heuristic is consistent and ties are broken consistently. The algorithm itself, and the optimality result for admissible heuristics, were not affected.

Hart later said that the name "A\*" came from internal SRI notation: the family of algorithms parameterized by an evaluation function was called "A", and the asterisk denoted the optimal member of the family (the version with admissible heuristics). The notation stuck.

## Formal definition

A\* operates on a weighted [graph](/wiki/graph) *G = (V, E)* with non-negative edge costs. Given a start node *s* in *V* and either a single goal *t* or a goal predicate, the algorithm searches for a path from *s* to a goal that minimizes the sum of edge costs.

The key quantities are:

| Symbol | Meaning |
|---|---|
| *g(n)* | Best known cost of a path from the start *s* to node *n* found so far. |
| *h(n)* | Heuristic estimate of the cost of a cheapest path from *n* to a goal. |
| *f(n) = g(n) + h(n)* | Estimated cost of a cheapest path from *s* to a goal that passes through *n*. |
| *h\*(n)* | The true (optimal) remaining cost from *n* to a goal. |
| *C\** | The optimal solution cost from *s* to a goal. |

A\* maintains two collections of nodes:

- The **open set** (also called the frontier or OPEN list) contains nodes that have been discovered but not yet expanded. It is typically implemented as a priority queue keyed by *f(n)*.
- The **closed set** (also called CLOSED) contains nodes that have already been expanded. It is used to avoid re-processing nodes when the heuristic is consistent.

At each iteration A\* removes the node with the smallest *f*-value from the open set, generates its successors, computes their *g*, *h*, and *f* values, and inserts them into the open set (or updates them if a cheaper path is found). The algorithm terminates when it removes a goal node from the open set.

### Admissibility and consistency

A heuristic *h* is **admissible** if for every node *n* in the graph,

*h(n)* <= *h\*(n)*

that is, *h* never overestimates the true cost to reach a goal. Admissibility is what makes A\* optimal in tree search and is the property invoked in most introductory proofs.

A heuristic *h* is **consistent** (also called **monotone**) if for every node *n* and every successor *n'* of *n* reached through edge cost *c(n, n')*,

*h(n)* <= *c(n, n')* + *h(n')*,

with *h(goal)* = 0. This is a triangle-inequality condition. Every consistent heuristic is admissible, but not every admissible heuristic is consistent. Consistency guarantees that the *f* values along any path are non-decreasing, which lets A\* close each node permanently the first time it is expanded; with admissible-but-inconsistent heuristics, the graph-search version of A\* must be willing to re-open nodes (or use a closed-list check that compares *g* values) to remain optimal.

## Pseudocode

The canonical reference implementation is the graph-search variant. The following pseudocode assumes a consistent heuristic and uses a priority queue ordered by *f(n)*:

```
function A_star(start, goal, h):
    open_set := priority queue ordered by f-value
    open_set.insert(start, f = h(start))
    came_from := empty map           // for path reconstruction
    g_score := map with default value of +infinity
    g_score[start] := 0
    f_score := map with default value of +infinity
    f_score[start] := h(start)

    while open_set is not empty:
        current := open_set.pop()    // node with lowest f_score
        if current == goal:
            return reconstruct_path(came_from, current)

        for each neighbor n' of current:
            tentative_g := g_score[current] + cost(current, n')
            if tentative_g < g_score[n']:
                came_from[n'] := current
                g_score[n'] := tentative_g
                f_score[n'] := tentative_g + h(n')
                if n' not in open_set:
                    open_set.insert(n', f_score[n'])
                else:
                    open_set.decrease_key(n', f_score[n'])

    return failure  // no path exists

function reconstruct_path(came_from, current):
    path := [current]
    while current in came_from:
        current := came_from[current]
        path.prepend(current)
    return path
```

When the heuristic is only admissible (not consistent), the algorithm is correct as written if a closed list is omitted, or if the closed list permits re-opening a node when a cheaper *g* score is later discovered.

## Properties

### Completeness

A\* is complete on graphs with finite branching factor and a positive lower bound *epsilon* > 0 on edge costs, provided a solution exists. Under these conditions there are only finitely many paths whose total cost is below the optimal *C\**, so the algorithm cannot expand nodes forever without reaching a goal.

### Optimality

If *h* is admissible, the tree-search version of A\* returns an optimal solution. If *h* is consistent, the graph-search version (which avoids re-expanding closed nodes) is also optimal. The standard proof argument: when A\* is about to expand a goal node *t*, the *f*-value of *t* is *g(t) + h(t) = g(t)*, the actual cost of the path found. Any other node *n* still on the open set has *f(n) <= f(t)*, since *t* was selected as the minimum. Because *h* is admissible, *f(n)* is a lower bound on the cost of any complete path through *n*, so no unexpanded path can be cheaper than *g(t)*.

### Optimal efficiency

For a fixed admissible heuristic, no other algorithm in a comparable class can expand strictly fewer nodes than A\* without risking missing the optimal solution. This was the result Hart, Nilsson, and Raphael set out to prove and is the result clarified in their 1972 correction. The technical statement requires careful conditions on the class of competing algorithms and on tie-breaking, but the intuition is that any node with *f(n) < C\** must be examined by any algorithm that is guaranteed to find an optimal path with the same heuristic information.

### Time and space complexity

In the worst case, A\* explores a number of nodes exponential in the depth of the optimal solution:

*O(b^d)*

where *b* is the branching factor and *d* is the depth of the goal. A tighter bound depends on the quality of the heuristic. If *h* is within a constant factor of *h\**, the search remains exponential, but the base of the exponent is smaller. A common analytical bound is *O(b^(epsilon \* d))* where *epsilon* is the relative error of the heuristic. With a perfect heuristic (*h = h\**), A\* expands only the nodes on the optimal path and runs in *O(d)* time.

Space complexity is the same order as time complexity in the worst case, because every generated node is held in memory through the open and closed sets. This is the practical limit of A\* on large state spaces, and is what motivates the memory-bounded variants discussed below.

## Heuristic functions

The choice of heuristic is the single biggest performance lever in A\*. A weak heuristic gives correct but slow search; a strong heuristic gives correct and fast search. Common heuristics for grid-based pathfinding are summarized below, where *(x1, y1)* and *(x2, y2)* are the coordinates of the two nodes:

| Heuristic | Formula | Movement model |
|---|---|---|
| **Manhattan distance** | *|x1 - x2| + |y1 - y2|* | 4-directional grid movement (up, down, left, right). |
| **Euclidean distance** | *sqrt((x1 - x2)^2 + (y1 - y2)^2)* | Movement at any angle (continuous space). |
| **Chebyshev distance** | *max(|x1 - x2|, |y1 - y2|)* | 8-directional grid movement when diagonal cost equals straight-line cost. |
| **Octile distance** | *max(dx, dy) + (sqrt(2) - 1) \* min(dx, dy)* where *dx = |x1 - x2|* and *dy = |y1 - y2|* | 8-directional grid movement when diagonals cost sqrt(2) times the straight cost. |
| **Zero heuristic** | *h(n) = 0* | Reduces A\* to Dijkstra's algorithm. Useful when no domain knowledge is available. |

For sliding-tile puzzles such as the 8-puzzle and 15-puzzle, classic heuristics include the number of misplaced tiles, the sum of Manhattan distances between each tile and its target square, and pattern databases that store optimal subproblem costs. For routing on road networks, popular heuristics include great-circle distance, landmark-based ALT (A\*, Landmarks, and Triangle inequality), and contraction-hierarchy-derived bounds.

### Dominance

Given two admissible heuristics *h1* and *h2*, *h2* is said to **dominate** *h1* if *h2(n) >= h1(n)* for every node *n*. A dominating heuristic produces an A\* search that expands no more nodes than the dominated heuristic, while remaining admissible. The maximum of two admissible heuristics is itself admissible and dominates each, so combining heuristics by taking the maximum is a standard trick. The trade-off is computational: a stronger heuristic typically takes longer to evaluate per node.

## Variants

Decades of research have produced a family of A\*-style algorithms tailored to different constraints. The most widely used are:

| Variant | Year | Key idea | Use case |
|---|---|---|---|
| **Iterative deepening A\*** ([IDA\*](/wiki/iterative_deepening_a_star)) | 1985, Korf | Uses depth-first search bounded by an *f*-cost threshold that grows between iterations. | Memory-constrained problems such as the 15-puzzle and Rubik's cube, where A\*'s open list would not fit in RAM. |
| **Simplified Memory-bounded A\*** (SMA\*) | 1992, Russell | Like A\* but discards the highest-*f* leaves when memory is full, backing up their *f* values to ancestors. | Real-time and embedded systems with hard memory limits. |
| **Weighted A\*** | 1970, Pohl | Replaces *f = g + h* with *f = g + w \* h* for *w > 1*, sacrificing optimality for speed. | Time-bounded search where a near-optimal answer (within factor *w*) is acceptable. |
| **Anytime A\* / ARA\*** | 2003, Likhachev et al. | Runs weighted A\* with decreasing weight, returning successively better solutions until time runs out. | Robotics and planning problems with deadlines. |
| **D\* (Dynamic A\*)** | 1994, Stentz | Repairs an existing plan when edge costs change, instead of replanning from scratch. | Robot navigation with partially known or changing terrain. |
| **D\* Lite** | 2002, Koenig and Likhachev | Re-derives D\*'s functionality from Lifelong Planning A\* with simpler bookkeeping. | Same as D\*, used in the Mars Exploration Rovers and many subsequent robots. |
| **Lifelong Planning A\*** (LPA\*) | 2001, Koenig et al. | Reuses information from previous searches when the graph changes between queries. | Repeated planning in slowly changing environments. |
| **Theta\* / Lazy Theta\*** | 2007, Daniel et al. | Allows the parent of a node to be any visible ancestor, producing any-angle paths instead of grid-aligned paths. | 3D and continuous-space pathfinding for games and robotics. |
| **Jump Point Search** (JPS) | 2011, Harabor and Grastien | Skips symmetric paths on uniform-cost grids by jumping over forced and natural neighbors. | Real-time game pathfinding, where speedups of an order of magnitude over plain A\* are common. |
| **Hierarchical Pathfinding A\*** (HPA\*) | 2004, Botea et al. | Pre-computes an abstract graph over clusters and searches the abstract graph before refining within clusters. | Very large grid maps in strategy games. |
| **Bidirectional A\*** | 1971, Pohl | Runs two A\* searches at once, one forward from the start and one backward from the goal, meeting in the middle. | Long-distance road routing and other large graphs. |
| **Field D\*** | 2007, Ferguson and Stentz | An any-angle, dynamic variant of D\* that interpolates costs across grid faces. | Mars rovers and outdoor mobile robots. |
| **Real-Time A\*** (RTA\*) and Learning Real-Time A\* (LRTA\*) | 1990, Korf | Commits to actions within a fixed time bound and learns improved heuristic estimates between trials. | Agents that must act faster than full A\* search would allow. |

## Related algorithms

A\* sits inside a small family of best-first search procedures that differ only in how they rank nodes. Setting the *g* term, the *h* term, or both to a constant produces several other classical algorithms:

| Algorithm | Evaluation function | Notes |
|---|---|---|
| Dijkstra's algorithm | *f(n) = g(n)* | Equivalent to A\* with *h(n) = 0*. Optimal but expands many irrelevant nodes. |
| Uniform-cost search | *f(n) = g(n)* | The AI-textbook framing of Dijkstra; same algorithm. |
| Greedy best-first search | *f(n) = h(n)* | Fast, but neither complete on infinite graphs nor optimal. |
| [Breadth-first search](/wiki/ai_search) | All edge costs treated equal | A\* with *g(n)* = path length and *h(n) = 0*. |
| Depth-first search | LIFO ordering | Not best-first; included for contrast. |
| Best-first beam search | *f(n) = h(n)*, but the open set is truncated to size *k* | Sacrifices completeness for bounded memory. |

The relationship to Dijkstra's algorithm is the most useful one to remember: A\* is Dijkstra plus a heuristic, and Dijkstra is A\* with the trivial heuristic *h = 0*. Any correctness or complexity intuition that holds for one transfers, with adjustments for *h*, to the other.

## Applications

### Video games

A\* is the default pathfinding algorithm in the games industry. Real-time strategy titles such as *StarCraft*, *Age of Empires*, and the *Total War* series use A\* (or HPA\* or Jump Point Search variants) to move units across maps with thousands of tiles. Role-playing games use it for non-player character navigation and for click-to-move player movement. The algorithm is popular because it is straightforward to implement on top of a navigation mesh or grid, scales to maps of practical size, and produces plausibly direct paths.

### Robotics

Mobile robots use A\* and its dynamic descendants (D\*, D\* Lite, Field D\*) for global path planning over occupancy grids. Notable deployments include the Mars Exploration Rovers Spirit and Opportunity, which used a variant of D\* developed at Carnegie Mellon. Manipulation planners and motion planners also use A\* over discretized configuration spaces for low-dimensional problems, though sampling-based planners such as RRT and PRM dominate at higher dimensions.

### Route planning

Early automotive GPS navigation devices used A\* with great-circle or Euclidean heuristics on road graphs. Modern web-scale route planners (Google Maps, Bing Maps, OpenStreetMap routers) generally rely on speedup techniques such as contraction hierarchies, transit-node routing, and customizable contraction hierarchies, but A\* with sophisticated heuristics (notably ALT, the landmark-based heuristic from Goldberg and Harrelson, 2005) remains a strong baseline and is still used in research and in some production systems.

### Parsing in natural language processing

A\* parsing applies the algorithm to chart parsing for probabilistic context-free grammars (PCFGs) and other weighted grammars. Each chart edge is a node in the search graph, and the heuristic estimates the negative log probability of completing a parse from that edge. Klein and Manning's 2003 paper "A\* Parsing: Fast Exact Viterbi Parse Selection" showed that admissible heuristics can give large speedups over standard chart parsing while still returning the most probable parse, a result that has influenced subsequent work on dependency parsing and semantic parsing in [natural language processing](/wiki/natural_language_processing).

### Other domains

A\* and its variants appear in puzzle solvers (15-puzzle, Rubik's cube via IDA\*), automated theorem proving, protein structure prediction, VLSI routing, multiple sequence alignment, and as the inner planner in many [reinforcement learning](/wiki/reinforcement_learning) systems that combine search with learned value estimates. The 2017 AlphaZero paper, while best known for [minimax](/wiki/minimax) and Monte Carlo tree search, popularized neural-network-guided search techniques that generalize the A\* idea of combining a learned heuristic with explicit lookahead.

## Limitations and pitfalls

A\*'s memory consumption is the most common production headache. Maintaining the entire open set in a priority queue, plus a closed set large enough to deduplicate revisits, becomes infeasible on graphs with billions of nodes (continental road networks, high-resolution 3D voxel grids). IDA\*, SMA\*, and external-memory variants are the standard mitigations, along with hierarchical decompositions that shrink the problem before A\* sees it.

A second pitfall is heuristic design. An inadmissible heuristic invalidates the optimality proof, and an inconsistent admissible heuristic invalidates the simple closed-list optimization. Many published implementations on the web silently assume consistency and quietly return suboptimal paths when the heuristic is only admissible. Designers writing custom heuristics should test for consistency by checking the triangle inequality on small graphs, and should be explicit about which variant of A\* they are running.

A\* is also a single-source single-target algorithm. For one-to-many or many-to-many shortest paths it is often more efficient to run Dijkstra from each source, or to use specialized algorithms such as contraction hierarchies. Heuristics that are tight for one goal may be loose for another, eroding A\*'s speed advantage when the goal changes.

Finally, A\* assumes the graph is fixed during the search. If edge costs can change while the algorithm runs (a moving obstacle, a closing road), plain A\* will return a plan that may already be obsolete. Dynamic variants such as D\* Lite and LPA\* exist precisely to handle this case.

## See also

- [Heuristic](/wiki/heuristic)
- [Graph](/wiki/graph)
- [Search](/wiki/ai_search) algorithms
- [Artificial intelligence](/wiki/artificial_intelligence)
- [Minimax](/wiki/minimax) and game-tree search
- [Reinforcement learning](/wiki/reinforcement_learning)
- [Natural language processing](/wiki/natural_language_processing)
- [Iterative Deepening A\*](/wiki/iterative_deepening_a_star)
- [Shakey the robot](/wiki/shakey_the_robot)

## References

1. Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). "A Formal Basis for the Heuristic Determination of Minimum Cost Paths." *IEEE Transactions on Systems Science and Cybernetics*, SSC-4(2), 100-107.
2. Hart, P. E., Nilsson, N. J., & Raphael, B. (1972). "Correction to 'A Formal Basis for the Heuristic Determination of Minimum Cost Paths.'" *SIGART Newsletter*, 37, 28-29.
3. Russell, S., & Norvig, P. (2021). *Artificial Intelligence: A Modern Approach* (4th ed.). Pearson. Chapter 3, Solving Problems by Searching.
4. Pearl, J. (1984). *Heuristics: Intelligent Search Strategies for Computer Problem Solving*. Addison-Wesley.
5. Nilsson, N. J. (1984, revised). *Shakey the Robot*. SRI Technical Note 323. https://ai.stanford.edu/~nilsson/OnlinePubs-Nils/shakey-the-robot.pdf
6. Korf, R. E. (1985). "Depth-first iterative-deepening: An optimal admissible tree search." *Artificial Intelligence*, 27(1), 97-109.
7. Pohl, I. (1970). "Heuristic search viewed as path finding in a graph." *Artificial Intelligence*, 1(3-4), 193-204.
8. Pohl, I. (1971). "Bi-directional search." In *Machine Intelligence 6*, Edinburgh University Press, 127-140.
9. Stentz, A. (1994). "Optimal and Efficient Path Planning for Partially-Known Environments." *Proceedings of the IEEE International Conference on Robotics and Automation*, 3310-3317.
10. Koenig, S., & Likhachev, M. (2002). "D\* Lite." *Proceedings of the AAAI Conference on Artificial Intelligence*.
11. Likhachev, M., Gordon, G., & Thrun, S. (2003). "ARA\*: Anytime A\* with Provable Bounds on Sub-Optimality." *Advances in Neural Information Processing Systems* 16.
12. Daniel, K., Nash, A., Koenig, S., & Felner, A. (2010). "Theta\*: Any-Angle Path Planning on Grids." *Journal of Artificial Intelligence Research*, 39, 533-579.
13. Harabor, D., & Grastien, A. (2011). "Online Graph Pruning for Pathfinding on Grid Maps." *Proceedings of the AAAI Conference on Artificial Intelligence*.
14. Botea, A., Muller, M., & Schaeffer, J. (2004). "Near Optimal Hierarchical Path-Finding." *Journal of Game Development*, 1(1), 7-28.
15. Klein, D., & Manning, C. D. (2003). "A\* Parsing: Fast Exact Viterbi Parse Selection." *Proceedings of HLT-NAACL 2003*, 119-126.
16. Goldberg, A. V., & Harrelson, C. (2005). "Computing the Shortest Path: A\* Search Meets Graph Theory." *Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA)*, 156-165.
17. "A\* search algorithm." *Wikipedia*. https://en.wikipedia.org/wiki/A*_search_algorithm
18. "Consistent heuristic." *Wikipedia*. https://en.wikipedia.org/wiki/Consistent_heuristic
19. "Shakey the robot." *Wikipedia*. https://en.wikipedia.org/wiki/Shakey_the_robot