How a computer finds the shortest route Image: Wanderingchina (Bob T.) (CC BY-SA 4.0)

How a computer finds the shortest route

A route planner has a map with millions of junctions and no idea where you are going until you type it in. It cannot look at every possible route; there are more routes across a city than there are atoms in the Earth. What it does instead is grow a region of explored junctions outwards from the start, in a carefully chosen order, until the region touches the destination. Which junction to explore next is the entire difference between an algorithm that takes a second and one that takes a day.

A grid, a wall, and the simplest search

Take a 5 by 5 grid of cells. Start in the top left corner, goal in the top right. Moves go up, down, left, or right, each costing 1. A wall fills the middle column from the top row down to the fourth row, leaving a gap only in the bottom row. The shortest route goes down the left side, along the bottom, and back up the right side: 12 moves.

Breadth-first search explores in rings. It looks at every cell one move from the start, then every cell two moves away, then three, and so on, keeping a queue of cells to visit in the order they were discovered. The first time it reaches the goal, it has found a route, and because it explored all shorter distances first, that route is the shortest. On this grid it expands 21 cells before it reaches the goal, which is every reachable cell on the board. It had no idea where the goal was, so it looked everywhere.

That is the guarantee and the cost of breadth-first search in one example. It always finds the shortest path when every move costs the same. On a map with branching factor \(b\) (the number of neighbours of a junction) and a goal at depth \(d\), it explores on the order of \(b^d\) junctions, written \(O(b^d)\). With \(b = 4\) and \(d = 12\) that is up to 16 million, and the whole grid saved us only because the grid is tiny.

A heuristic that points at the goal

A* (said "A star") adds one piece of knowledge: a guess, for each cell, of how far the goal still is. The guess is called a heuristic and written \(h(n)\). On a grid where moves go in four directions, the natural guess is the Manhattan distance, the number of rows plus the number of columns between the cell and the goal, as if the wall were not there. A* orders its exploration by

\[ f(n) = g(n) + h(n), \]

where \(g(n)\) is the cost of the route found so far from the start to \(n\). The cell with the smallest \(f\) is explored next. Cells that are far along a promising line come before cells that are near the start but pointing the wrong way.

Run it on the same grid. The start has \(g = 0\), \(h = 4\), \(f = 4\). Its right neighbour has \(g = 1\), \(h = 3\), \(f = 4\), and its lower neighbour \(g = 1\), \(h = 5\), \(f = 6\), so A* tries the cell to the right first. That cell is next to the wall and leads nowhere, so the algorithm turns down. All the way down the left side, \(f\) stays at 6, 8, 10, 12 as \(g\) grows and \(h\) grows with it, because every step down is a step away from the goal row. Along the bottom and up the right side, \(f\) stays at 12: each step adds 1 to \(g\) and takes 1 from \(h\). The goal is reached with \(f = 12\), and no cell with \(f\) greater than 12 was ever expanded.

On this particular grid, A* also ends up expanding 21 cells, because the wall forces the detour and every reachable cell has \(f \le 12\). The count looks like a tie. Now remove the wall. Breadth-first search still floods outwards in rings and expands around 15 cells before it reaches the goal four moves away. A* walks straight along the top row and expands 5. On a real map, where the destination is 50 kilometres away and the map holds a million junctions, that difference is the difference between the algorithm you can use and the one you cannot.

Why the route is still the shortest

The worry about a heuristic is that it might mislead. A* has a precise answer: if \(h(n)\) never overestimates the true remaining cost, a property called admissibility, then the first route A* finds to the goal is a shortest one. The Manhattan distance is admissible on this grid because no route can be shorter than the straight-line count of rows and columns; walls only make routes longer. The proof is short. Suppose A* returned a route of cost \(C\) when a shorter one of cost \(C^* < C\) existed. Some cell on the shorter route was sitting unexpanded with \(f = g + h \le C^*\), because \(h\) never overestimates. But A* expands cells in order of \(f\), so it would have expanded that cell before any cell with \(f = C\). Contradiction.

A heuristic that overestimates is faster and unsafe. Multiply the Manhattan distance by 5 and A* becomes greedy: it rushes towards the goal, explores very few cells, and on a grid with a wall will often return a route that is longer than necessary. This trade is used deliberately in video games, where a route that is 10 per cent too long and found in a tenth of the time is a good bargain, and avoided in a satellite navigation system, where it is not.

The quality of the heuristic is everything. The straight-line distance is admissible for roads but weak, because roads bend. Modern route planners precompute much better estimates, from landmark distances and from a hierarchy of fast roads, and then run a search that expands a few hundred junctions for a route across a continent. The algorithm is still A* or a close cousin; the heuristic is where the decades of engineering went.

Where it came from and where it went

A* was published in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael at the Stanford Research Institute, for a robot called Shakey that needed to plan its way around a room. Dijkstra's algorithm of 1959 is A* with \(h = 0\), which is to say breadth-first search generalized to roads of different lengths. Both are still inside every satellite navigation system, every game character that walks around an obstacle, and every logistics planner that routes a delivery van.

The same idea, search ordered by a cost plus an estimate, runs through the whole field. A chess program searches a tree of moves and estimates the leaves with an evaluation function. A planner searches a space of actions with a heuristic computed from the structure of the problem. AlphaGo searched the game tree of Go with estimates provided by a neural network. In each case the search is the easy part and the estimate is the hard part, and the history of the field is partly the history of replacing hand-written estimates by learned ones.

Unit 2 of the AI Masterclass works breadth-first search and A* on this grid with every \(f\) value written into its cell, counts the leaves of a minimax tree with alpha-beta pruning, and explains why chess fell to search in 1997 while Go needed something else. The tool of that week, PathFinding.js, lets you draw the wall and watch both algorithms run.

Learn how machines learn, properly

The AI Masterclass: weekly units, quizzes, a final exam, and a certificate.
About the program