TL;DR:
A* searches a grid by always expanding the cell with the lowest f = g + h, where g is the cost so far and h is a guess of the cost still to go.
The open list holds cells waiting to be expanded, and the closed list holds cells already finished.
With an admissible heuristic (one that never overestimates), A* returns a shortest path.
A robot sits at the top left of a room divided into a grid. It needs to reach the bottom right, and a couple of cells are blocked. Which way should it go? You could try every route, but a smarter search finds the shortest one while looking at only a few cells. That search is A* (pronounced "A-star"), and you can trace it by hand on a small grid.
What it does on a robot
Many robots plan on a grid: the map is cut into square cells, each either free or blocked. A planner finds a sequence of free cells from start to goal. A* is the standard choice because it finds the shortest path and avoids searching in directions that cannot help.
The idea: cost so far plus a guess
For each cell n, A* tracks two numbers:
g(n): the cost of the best path found so far from the start to n. Here each step costs 1.
h(n): the heuristic, an estimate of the remaining cost from n to the goal. On a grid with 4-direction moves, the standard choice is the Manhattan distance:
h = |row difference| + |column difference|, because you must travel at least that many steps.
The score is f(n) = g(n) + h(n). A* repeatedly takes the cell with the lowest f from the open list (cells discovered but not yet expanded), moves it to the closed list (cells finished), and adds its free neighbours to the open list with updated g values. It stops when the goal is taken from the open list.
If h never overestimates the real remaining cost (it is admissible), the first time the goal is expanded the path is a shortest one. Manhattan distance never overestimates on a 4-connected grid, since you cannot reach the goal in fewer moves than the distance.
Worked example: a five by five grid with walls
Rows are numbered 0 to 4 from the top, columns 0 to 4 from the left. S is the start at (0,0), G the goal at (4,4), and # a wall.
S . . . .
. # . . .
. . . . .
. . . # .
. . . . GWalls are at (1,1) and (3,3). Moves are up, down, left, right, each costing 1. The Manhattan distance from (0,0) to (4,4) is 8.
Expand (0,0): g = 0, h = 8, f = 8. Neighbours: (1,0) with g = 1, h = 7, f = 8, and (0,1) with g = 1, h = 7, f = 8.
Tie. Both open cells have f = 8. We break ties by choosing the lower h (closer to the goal), and then the one added first. Take (1,0).
Expand (1,0): neighbour (2,0), g = 2, h = 6, f = 8. (The cell (1,1) is a wall.) Open: (0,1) f = 8 (h 7), (2,0) f = 8 (h 6).
Expand (2,0) (lower h): neighbour (3,0), g = 3, h = 5, f = 8. Also (2,1), g = 3, h = 5, f = 8.
Expand (3,0): neighbour (4,0), g = 4, h = 4, f = 8 (and (3,1) with g = 4, h = 4, f = 8).
Expand (4,0): neighbour (4,1), g = 5, h = 3, f = 8.
Expand (4,1): neighbour (4,2), g = 6, h = 2, f = 8.
Expand (4,2): neighbour (4,3), g = 7, h = 1, f = 8.
Expand (4,3): neighbour (4,4), g = 8, h = 0, f = 8.
Expand (4,4): the goal. Stop.
Every expanded cell had f = 8, because the heuristic was exact along the route: the wall did not force a detour. A* expanded 9 cells before reaching the goal, which is the path itself: (0,0), (1,0), (2,0), (3,0), (4,0), (4,1), (4,2), (4,3), (4,4), a length of 8 moves.
To trace the path, each cell remembers its parent, the cell it was reached from. From the goal, follow parents back to the start and reverse the list. Check: 8 moves, and the cost equals g at the goal, 8.
For comparison, a search that ignores h (Dijkstra's algorithm, covered in Dijkstra and A*: what the heuristic buys you) expands all 23 free cells on this map before it takes the goal. A* did the same job by expanding 9.
Where it goes wrong
Overestimating h. If the heuristic is too big, for instance if you double the Manhattan distance, A* is faster but may return a longer path than necessary.
Using the wrong heuristic for the moves. Manhattan distance is right for 4-direction moves. If diagonal moves are allowed, it overestimates, and you need a different one (such as the octile distance).
Tie-breaking. The order of expansion among equal f values changes which path you get, though not its length.
Resolution. A coarse grid misses narrow gaps, and a fine grid has many cells and is slow.
Robot size. A path through a one-cell gap is useless if the robot is wider. Grow the walls by the robot's radius before planning.
Grid paths are jagged. The robot may need to smooth the path and obey its turning limits.
Safety: A path that looks collision-free on the map can still cross something the map missed. Before a real robot follows a planned route, check it in simulation, run at low speed with an emergency stop within reach, and keep obstacles and people clear of the planned path. Do not rely on the plan alone: keep a distance sensor active for the last-moment stop.
How real robots use it
Robot vacuums, warehouse vehicles and game characters all use A* or variants on grids and graphs. Larger systems use A* over a road network or a lattice of precomputed motions. When the space is too large for a grid (an arm with many joints), planners such as sampling-based methods take over.
Try it yourself
Draw the 5 by 5 grid above on paper. Add one more wall at (2,2) and trace A* again, writing g, h and f for each cell as you expand it. Keep the open and closed lists as columns. When you finish, count how many cells you expanded, and check that the path length matches what you can find by eye.
Frequently asked questions
What does f = g + h mean?
g is the cost already paid to reach the cell and h is the guess of what remains. Their sum is the estimated total length of the best path that goes through that cell.
Does A* always find the shortest path?
Yes, if the heuristic never overestimates the true remaining cost. Manhattan distance on a 4-connected grid with unit steps meets that condition.
Get started
