M3-T3 — A*: Search with a Heuristic

Learning objectives

After this lesson, you should be able to:

• Write the A* priority f = g + h and trace the algorithm on a small grid.
• Define an admissible and a consistent heuristic and say what each guarantees.
• Explain why A* with an admissible heuristic returns an optimal path.
• Describe which nodes A* expands and compare its work with Dijkstra and greedy search.

The intuition

Imagine walking to the pharmacy with a compass in your pocket. Dijkstra is the walker who explores every corridor to the same radius before committing. Greedy best-first search is the walker who always takes the step that gets closest to the pharmacy by compass, and who walks straight into a dead end because a wall is in the way. A* is the sensible walker: she weighs the cost of the way she has already walked against the compass distance still to go, and so she heads for the goal while still noticing when the way ahead is much more expensive than the way back.

The compass distance is the heuristic. It must be honest in one direction: it may say the goal is closer than it really is, never farther. An optimistic compass costs a little extra searching and never costs the right answer. A pessimistic one makes the search faster and the answer wrong.

The mathematics

The A* priority

For every node n, A* tracks g(n), the cost of the cheapest route found so far from the start to n, and uses a heuristic h(n), an estimate of the cheapest cost from n to the goal. It always expands the open node with the smallest f(n) = g(n) + h(n).

f(n) = g(n) + h(n)

A*(start, goal):
  g[start] ← 0;  open ← {(h(start), start)};  closed ← ∅
  while open not empty:
    n ← open node with the smallest f;  if n is in closed: continue
    add n to closed
    if n is the goal: return the route from parent pointers
    for each neighbour m of n with step cost c:
      if g[n] + c < g[m]:  g[m] ← g[n] + c;  parent[m] ← n;  push (g[m] + h(m), m)

With h = 0 for every node this is exactly Dijkstra. With g left out of the priority it is greedy best-first search.

Admissible and consistent

admissible

h(n) ≤ h*(n) for every n, where h*(n) is the true cheapest cost from n to the goal: the heuristic never overestimates.

consistent

h(n) ≤ c(n, m) + h(m) for every edge (n, m) (the triangle inequality), and h(goal) = 0. Every consistent heuristic is admissible.

Admissibility makes A* return an optimal route. Consistency makes it do so efficiently: f never decreases along a path, so a node is expanded once, with its final g, and a closed set is safe.

Why admissible gives optimal

Let C* be the cost of the cheapest route. Suppose A* is about to pop the goal with g(goal) > C*. At that moment some node n on a cheapest route is still open, with its cheapest g, so f(n) = g(n) + h(n) ≤ g(n) + h*(n) = C*. That is smaller than the f of the goal, which is g(goal) > C*, so n would have been popped first. The contradiction shows the goal is only popped with g = C*.

What gets expanded

With a consistent heuristic A* expands every node with f(n) < C*, possibly some with f(n) = C* (which ones depends on how ties are broken), and none with f(n) > C*. A better heuristic (closer to h*, still admissible) raises f of more nodes above C* and shrinks the search. In a precise sense A* is optimally efficient: no algorithm that is guaranteed to return an optimal route with the same heuristic knowledge expands fewer nodes apart from ties (Dechter and Pearl, 1985).

A* as Dijkstra with new costs

Define a reduced cost c′(n, m) = c(n, m) + h(m) − h(n). If h is consistent, c′ is not negative, and A* is Dijkstra run with the costs c′: the heuristic only changes which of the equal-looking routes is cheaper, by making routes towards the goal cheaper and routes away from it dearer.

A worked example

A trace on a small grid. The grid of the figure has five rows and six columns. The cells (1,3), (2,3) and (3,3) are wall. Scout starts at (2,0) and the goal is (2,5). Moves are up, down, left and right with cost 1. The heuristic is the Manhattan distance, which is exact in an open 4-connected grid and therefore admissible.

The search goes straight for the goal while f = 5. At (2,2) the wall is in the way and every continuation has f of at least 7, so the other cells with f = 7 are tried: the cells around the start, all of which are cheaper to explore than f = 9. When f reaches 9 the search follows the route over the top of the wall and pops the goal with g = 9, which is the cheapest cost. In total 15 cells are expanded. Dijkstra, with h = 0, expands every cell whose g is at most 9, which is all 27 free cells: 12 more than A*, 80% more work.

The 12 cells that were never expanded include the entire bottom row and cells such as (0,0) and (0,1), which have f = 9 as well. Whether tied cells are expanded before the goal depends on how ties are broken; here cells with a larger g were preferred (lesson M3-T4).

Greedy search on the same grid. Ordered by h alone, the search would run to (2,2), try the cells next to it in order of their distance to the goal, and go round the wall by whichever side it reaches first. On this small grid it still finds the cost-9 route. With a longer wall or a pocket it can return a route much longer than the cheapest, which is the failure shown by the starter code in lab M3-L2.

Engineering implications and limitations

The open list is a heap, the closed list is a set

Store open nodes in a binary heap keyed on f, and keep a set of expanded nodes (or a per-cell flag). Skip popped entries that are already closed, as in Dijkstra's lazy deletion. Memory, not time, is usually the limit: A* stores every node it generates.

When the heuristic is only admissible

If h is admissible but not consistent, a node can be reached again with a smaller g after it has been expanded. A correct A* must then reopen it. Grid distance heuristics (Manhattan for 4-connected grids, octile for 8-connected) are consistent, so a simple closed set is fine; heuristics that come from learned models or from a coarser map need checking.

The cost function and the heuristic must match

If the step cost is scaled, as when costmap values are added to the distance (lesson M3-T7), the heuristic must be at most the cheapest possible cost per unit of distance. A distance heuristic in metres is admissible against a cost that is at least one per metre; it is not against a cost that can be lower.

Where it is used

Grid planners in navigation stacks are mostly A* with a distance heuristic or Dijkstra. The Nav2 NavFn planner offers both and has a parameter that selects A* instead of Dijkstra; the Smac planners are A* variants on grids and on lattices of motion primitives (module M4). Check the planner's documentation for the exact heuristic it uses.

Debug by replay

The easiest way to see a heuristic bug is to draw which cells the search expanded, in order. A thin line towards the goal that then floods a pocket is greedy behaviour; a round blob around the start is Dijkstra behaviour. Lab M3-L2 gives you a slider to scrub through the expansions.

Common misconceptions

Engineering takeaways

1. A* expands the open node with the smallest f = g + h, where g is the cost so far and h an estimate of the cost to go.
2. An admissible heuristic (never above the true cost) guarantees an optimal route; a consistent one also makes every node expand once.
3. A* expands all nodes with f below the optimal cost and none above it; a better heuristic shrinks the search.
4. With h = 0 A* is Dijkstra, and with g left out it is greedy best-first search, which is fast and not optimal.
5. Draw the expansions: the shape of the searched region tells you which algorithm you really ran.

References and further reading

The paper that introduced A*, and the analyses of its optimality and efficiency.

• P. E. Hart, N. J. Nilsson and B. Raphael, “A Formal Basis for the Heuristic Determination of Minimum Cost Paths”, IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107, 1968.
• R. Dechter and J. Pearl, “Generalized Best-First Search Strategies and the Optimality of A*”, Journal of the ACM, 32(3), 505-536, 1985.
• J. Pearl, Heuristics: Intelligent Search Strategies for Computer Problem Solving, Addison-Wesley, 1984.

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Next: how to choose a heuristic for grids, what consistency buys, how ties are broken, and how weighted A* trades optimality for speed.

Related content

Nothing below is required to finish this lesson.

• Before
  M3-T2: Breadth-First Search and Dijkstra

  Trace Dijkstra with a priority queue and explain why it returns shortest paths on non-negative costs.

• Lab
  M3-L2: Implement A* with Search Replay

  Make the same route faster: implement A*, then scrub through the search to see what it skipped.

• Lab
  M10-L1: The Shift Simulator

  Run a full compressed shift with your own planner, controller and recovery logic, scored on hidden shifts.