Visualizing A* Search: Pathfinding Through Heuristic Guidance

Pathfinding is a search problem, and it is worth stating precisely before we solve it. We are given a graph, a start vertex, a goal vertex, and a cost on every edge, and we want a route of least total cost. Underneath it lies a second question: how much of the graph must an algorithm examine before it can commit to an answer? Here is an instance. Each cell of this grid is a vertex; each cell is joined to its neighbours above, below, left and right; and the shaded cells are walls, which no route may enter. One step from a cell to a neighbour costs one unit, so the cost of a route is the number of steps in it. This cell is the start. This one is the goal. A search algorithm answers one question repeatedly: of the cells it has reached but not yet examined, which should it examine next? Every algorithm in this lecture answers by attaching a single number to each candidate and taking the smallest. So consider one candidate. Take this cell, and call it n. Two different costs meet at n. One of them lies behind it. From S, the search has traced a route to n, one step at a time, and that route has a cost of five steps. That measured number is g of n. The other lies ahead of it. From n, some cost remains before G is reached, and the search cannot know it, because it has not been there. So it estimates. This dashed figure is the estimate: four cells across, one cell up, five in total. That number is h of n. Keep the distinction. g is known, because those steps have been taken. h is a guess about ground the search has not covered. A star search adds them. f of n is g of n plus h of n: the cost committed, plus the cost estimated. It is the algorithm's estimate of the total cost of the best route through n. Here that is five plus five, which is ten. And the rule of the algorithm is exactly this: always examine the reached cell whose f is smallest. Two numbers and one sum. What follows takes them apart: a search that uses g and nothing else, then the estimate h on its own, and then the two together.

Start with a search that has no information about where the goal is. Dijkstra's algorithm keeps, for every cell it has reached, the cheapest known cost of reaching it, and it always expands the reached cell whose cost is smallest. When every step costs the same, that is the order breadth-first search uses as well. Look at which quantity that rule uses. It uses g, the cost already accumulated, and nothing else. No term in it mentions the goal, so nothing in it can prefer one direction over another. So it grows in every direction at once. Watch the shading: its leading edge is the frontier, the boundary between cells already expanded and cells not yet reached. Stop it here. The outlined cells are the frontier at this instant: expanded cells behind them, unreached cells in front. The frontier is a diamond rather than a circle, because distance is counted in horizontal and vertical steps. And it spreads behind the start as readily as ahead of it. Let the wave run on, and half of that work is going away from G. Keep going. The expansion folds around the walls and continues, filling cells that no shortest route to G could use. The goal is reached last, because it is far from the start and the search had no reason to hurry towards it. The route returned is a shortest one: ten steps. That optimality is not negotiable. Whatever we add to make the search look in the right direction must still return a route of least cost. Now count the work. Before the goal came off the queue, every cell strictly closer to the start than the goal is had already been expanded. That is this many, out of the sixty-seven cells of this grid that are not walls. That is not a defect of the implementation; it follows from the rule. g measures the past, and a search that ranks candidates by the past alone cannot tell a promising direction from a hopeless one. What is missing is a term that looks forward.

The missing term is an estimate of the cost that remains. For every cell we want a number saying, without any searching, roughly how far the goal still is. Here is the estimate this lecture uses. Ignore the walls completely. Count the horizontal separation between the cell and the goal, count the vertical separation, and add the two. That is the Manhattan distance. Take this cell. It is seven columns and two rows from the goal, so the estimate is nine. Move the cell and the number follows. Here it is six. Nearer the goal, it is two. And computing it costs two subtractions and an addition: no search, no queue, no walls consulted. The estimate ignores walls, and that has a consequence worth seeing. Move the cell here. The estimate is six: four columns across and two rows down. But look where the dashed figure runs. It goes straight through this wall, and no route can follow it. The true remaining cost is eight, not six. A route has to come down to this row, pass the barrier, and climb back up to G. So the estimate falls short of the truth, and that is precisely the property we want. An estimate that never exceeds the true remaining cost is called admissible. The Manhattan estimate is admissible on this grid, because any route must make at least the horizontal steps and at least the vertical steps that separate the cell from the goal, and walls can only force it to make more. Admissibility is what will let us keep the optimality that Dijkstra's algorithm gave us. Now put both costs together at this cell. The cheapest route the search can trace from S to it costs six steps, so g is six. The estimate ahead is six as well, so f is twelve. Notice that twelve is not the true cost of the best route through this cell. In green and yellow together, that route is fourteen steps. Twelve is a lower bound on it, and a lower bound is all we need: twelve already exceeds ten, and a ten-step route exists. So this cell can be discarded without ever being expanded. That is the mechanism: g rules out nothing, h rules out nothing, and their sum rules out most of the maze.

Now the two terms together. One change to the rule: instead of expanding the reached cell of least g, A star search expands the reached cell of least f, where f is g plus h. Expand S. Its four neighbours become reached cells, each with g equal to one, and each is given an f. Those four are the queue. The four share the same g, so g cannot separate them. Their estimates differ. The neighbour towards the goal is seven from it by the estimate; the other three are nine, because a step in the wrong direction adds one instead of removing one. Add the columns and f follows: eight for the neighbour in the direction of the goal, ten for the other three. The smallest f wins, so the search steps that way. Repeat the comparison. The next three choices come out the same way, so the search runs straight along this row, and f stays at eight all the way. Then the row runs into the wall. The cell straight ahead is blocked, so there is nowhere to continue, and every reached cell now has an f of ten. The estimate of eight was optimistic, and the search has just discovered why. Many cells now tie at ten, and f alone cannot choose among them. This implementation prefers the smaller estimate, which keeps it moving towards G; a different tie-break would examine a wider band. What no tie-break can do is examine a cell of larger f before one of smaller f. So it turns the corner and carries on: ten, ten, ten. Then G comes off the queue with f equal to ten, which is its g plus nothing, since the estimate at the goal is zero. Eleven cells expanded. The route returned is the same ten-step route, and it is optimal, for the reason we established: the estimate never overshoots, so no unexpanded cell could have hidden anything cheaper. The queue was not empty when it stopped. These cells were reached and given an f, and then never expanded, because their f exceeded ten. Reaching a cell is cheap; expanding it is the work. Put the two searches side by side, on the same maze, with the same walls, both returning a route of cost ten. The counts are on the board. The larger belongs to the search that ranked by g alone; the smaller belongs to the search that added an estimate of what remained. Same route, a fraction of the work. Three points to take away. First, the two terms measure different things: g is a measured cost over ground the search has covered, h is an estimate over ground it has not, and f is the only quantity the algorithm ever compares. Second, the estimate must never exceed the true remaining cost. That is admissibility, and it is what keeps the returned route optimal. An estimate that overshoots can make the search settle for a route that is not shortest. Third, the quality of the estimate is the quality of the search. Set h to zero and f becomes g, and the algorithm is Dijkstra's again, expanding in every direction. Sharpen h towards the true remaining cost and the expanded region contracts towards the route itself. The equation is one addition. What it changes is the set of cells the algorithm never has to look at.