Skip to content

NavigationMaps and Paths

A* Search

A* adds a guess of the distance left, f = g + h, so it looks toward the goal first and still finds the shortest path.

Not started Jump to practice

BFS searches in every direction. A* searches toward the goal first, and still finds the shortest path.

Key idea

A* scores each waiting cell by $f = g + h$: $g$ is the cost so far and $h$ is a guess of the cost left. It always opens the cell with the smallest $f$. If $h$ never overestimates (it is admissible), A* finds a shortest path. On a 4-connected grid, the Manhattan distance $|\Delta x| + |\Delta y|$ works.
Compare A* with breadth-first search on the same walls. A* opens far fewer cells.

Why it works

The guess pulls the search toward the goal. Because the guess is never too big, A* cannot be fooled into stopping on a longer path: any cell on a shorter path would have a smaller $f$ and be opened first. Peter Hart, Nils Nilsson and Bertram Raphael published it in 1968 for Shakey, one of the first mobile robots.

Worked example: Score a cell

Goal at (9, 6). Cell (4, 2) reached with $g = 5$.
  1. $h = 5 + 4 = 9$.
  2. $f = 5 + 9 = 14$.

Answer: 14.

Common mistake

Using a guess that can overestimate. A* may then find a path quickly, but not the shortest one.

Practice

Pass with 3 right answers, the last 2 in a row. Each right answer earns 3 XP.

Loading practice…

Builds on

Leads to

This is one of the top rungs of Mobile Robots and Navigation.

Sources and further reading

  • Peter E. Hart, Nils J. Nilsson and Bertram Raphael, A Formal Basis for the Heuristic Determination of Minimum Cost Paths, IEEE Transactions on Systems Science and Cybernetics (1968)
  • Roland Siegwart, Illah R. Nourbakhsh and Davide Scaramuzza, Introduction to Autonomous Mobile Robots, 2nd ed. (MIT Press, 2011)