Frontier An interactive monograph on pathfinding

Frontier

How a machine finds its way from one place to another when it cannot see the whole map, and how it knows the route it found is the best one.

An interactive monograph in nine sections, with five live figures. Reading time roughly forty minutes. The figures are operable by mouse, touch and keyboard, and the document conforms to WCAG 2.2 AA. Built as a single static page in vanilla HTML, CSS and JavaScript, with no framework and no build step.

Abstract

Pathfinding is the problem of finding a route between two points in a space that a machine can examine only locally, one position and its neighbours at a time. This document develops the subject from its foundations. It begins with the abstraction every method shares, the graph, and the data structure at the centre of every search, the frontier. It reviews the historical development of the field, in which each algorithm was introduced to remove a definite limitation of the one before it. It then treats the three classical search algorithms in turn: breadth-first search and its guarantee on unweighted graphs, Dijkstra's algorithm and the generalisation to weighted graphs, and A* and the use of a heuristic estimate to direct the search toward its goal. A section on the theory establishes the conditions under which these algorithms return an optimal route. A final section leaves the grid for the structures that real systems search instead.

Every figure is interactive and runs on an editable grid. The grid is a deliberate simplification: it lets the behaviour under discussion, the order in which positions are examined and the route finally recovered, be watched directly and computed exactly.

1Search without a map

A delivery robot crossing a warehouse, a character moving across a game level, and a packet traversing a network all face one problem in common. Each must travel from a starting position to a goal position through a space that contains obstacles, and each must do so without the overview that a person glancing at a map enjoys. A machine in this situation has access only to local information: it can determine, for a position it currently holds, which neighbouring positions are reachable, and little more. It cannot take in the whole space at once.

Because of that restriction the machine cannot simply see the route. It must construct one, and it must do so by a process of search: starting from the known position, it examines reachable neighbours, then their neighbours, accumulating knowledge of which positions connect to which until the goal is among the positions reached. The subject of this document is how that search should be conducted. Three questions organise it. In what order should positions be examined? How is the route reconstructed once the goal is found? And how can the search guarantee that the route it returns is the shortest, or the cheapest, rather than merely a route that happens to work?

These questions have precise answers, and the answers are short algorithms. What makes the subject worth a careful treatment is not the length of the algorithms but the reasoning that establishes their correctness, and the way each one was devised to repair a specific shortcoming of its predecessor. That reasoning is the thread the document follows.

2Graphs, grids and the frontier

To reason about movement a machine first replaces the physical space with an abstraction. The abstraction is the graph: a set of positions, called nodes, together with a set of connections between them, called edges. A node is a place the traveller may occupy; an edge records that one place can be reached directly from another. Every algorithm in this document operates on a graph and on nothing else, which is why the same three algorithms serve the warehouse robot, the game character and the network packet without modification.

The graph used throughout the figures here is the grid: a lattice of square cells in which each cell is connected to its four orthogonal neighbours, and a cell may be marked as a wall, which removes its edges. The grid is the friendliest graph to draw and the easiest to edit, and the figure below presents one. Cells can be added and removed as walls, the start and goal can be moved, and a search can be run. The grid is a particular graph, not a special case; the algorithms never refer to its geometry.

One data structure recurs in every search and deserves to be named at the outset. As a search proceeds, the positions it has encountered fall into three groups. Some have been fully examined, meaning the search has inspected all of their neighbours; these are the visited positions. Some have not yet been encountered at all. Between the two lies the frontier: the positions that have been discovered but not yet examined. The frontier is where every search does its work, and the differences among the algorithms that follow reduce almost entirely to one decision, namely which position to remove from the frontier next. This document takes its name from that structure.

3A history of pathfinding: a literature review

The three classical algorithms, and the refinements that followed them, form a sequence in which each member answers a documented limitation of the one before. This section traces that sequence. As in any literature review the emphasis is causal: the concern is not only what each method did, but which earlier failure it was introduced to repair.

The earliest of the three to be published in its modern form was breadth-first search, set out by Edward Moore in 1959 in a paper explicitly about finding the shortest path through a maze [1]. Moore's procedure explored a maze outward from its entrance in layers, and it was guaranteed to reach the exit by a path of the fewest possible cells. Its limitation was structural: it counted cells, and so it was correct only when every step was equally costly. A maze in which some ground is slow to cross and other ground is fast lies outside what breadth-first search can solve.

That limitation was removed, in the same year, by Edsger Dijkstra [2]. Dijkstra's algorithm attached a cost to each edge and examined positions in order of their cheapest known cost from the start rather than in order of their discovery. This generalised breadth-first search exactly: when every edge has the same cost the two algorithms behave identically, and when costs differ Dijkstra's algorithm remains correct where breadth-first search does not. It carried, however, a limitation of its own. Like breadth-first search it had no notion of where the goal lay, and so it expanded outward in all directions equally, including directly away from the target, examining far more of the graph than a route to the goal required.

The repair of that inefficiency is the principal advance in the history of the field. In 1968 Peter Hart, Nils Nilsson and Bertram Raphael introduced A* [3], which added to Dijkstra's cost-so-far a second quantity: a heuristic estimate of the cost still remaining to the goal. By examining positions in order of the sum of the two, A* directed its search toward the goal and examined dramatically fewer positions while still, under a condition the paper made precise, returning an optimal route. A short correction the following year [4] tightened the statement of that condition. A* remains the algorithm in ordinary use, and sections six and seven are devoted to it.

The refinements that followed each relaxed an assumption that A* had taken for granted. A* assumes that an optimal route is required; where a merely good route found quickly is acceptable, the weighted and bidirectional variants studied by Ira Pohl in 1970 [5] inflate the heuristic or search from both ends, trading the guarantee of optimality for speed. A* assumes that the graph is known and fixed; a robot discovering obstacles as it moves needs to repair its route without searching afresh, which is the problem Anthony Stentz addressed with D* in 1994 [6] and Sven Koenig and Maxim Likhachev refined as D* Lite in 2002 [7]. A* assumes that searching the full graph is affordable; on a very large map it is not, and the hierarchical method of Adi Botea and colleagues in 2004 [8] searched an abstract graph of regions first and the detailed grid only within the regions the route crossed. A* assumes nothing about the regularity of the graph, and so on a uniform grid it repeats work across symmetric paths that lead to the same place; the jump point search of Daniel Harabor and Alban Grastien in 2011 [9] exploited that regularity to skip the repetition.

Two further situations fall outside the single-traveller, grid-graph assumption entirely, and section eight returns to them. When many travellers share one destination, the continuum approach of Adrien Treuille and colleagues [10] computes one field of directions rather than many separate routes. When the space is open rather than maze-like, the grid is a poor model of it, and the navigation mesh, described by Greg Snook [11], replaces the grid with a small set of convex regions. The pattern across the whole history is consistent: a fixed assumption, identified as a limitation, is relaxed, and the search that the reader is about to study carries over unchanged to the new graph.

Return to contents

4Breadth-first search

Breadth-first search keeps its frontier in a queue, a structure from which positions are removed in the order they were added. The search begins by placing the start position in the queue. It then repeats one step until the queue is empty: remove the position at the front of the queue, mark it visited, and add to the back of the queue every neighbour not already discovered.

Because the queue removes positions in the order they entered, the search examines the start first, then every position one step from the start, then every position two steps away, and so on. The frontier is at every moment a set of positions all at the same distance from the start, and that set grows outward by one layer at a time. The figure shows the layers forming.

The guarantee follows directly. Breadth-first search examines positions in order of increasing distance from the start, so the first time it reaches the goal it has reached the goal by a path of the fewest possible steps; a shorter path would have a smaller distance, and the search would have found it on an earlier layer. The route itself is recovered by a device used by all three algorithms: each position, when discovered, records the neighbour that discovered it, its parent. Following parents back from the goal to the start and reversing the chain yields the path, at no extra cost.

The limitation noted in the literature review is visible in the figure. Breadth-first search counts steps and treats them all alike, so it finds the path of fewest cells. That is the best path only when every cell costs the same to enter. As soon as some terrain is slower than other terrain, fewest cells and lowest cost cease to be the same quantity, and a different algorithm is required.

5Weighted terrain and Dijkstra's algorithm

Suppose each position carries a cost to enter, so that crossing mud is dearer than crossing pavement. In the figure below the plain cells cost one unit and the hatched cells, representing heavy terrain, cost five. The cost of a route is the sum of the costs of the cells it enters, and the goal is no longer the route of fewest cells but the route of lowest total cost. A detour across three cheap cells is now preferable to a shortcut through one expensive one.

Breadth-first search cannot find that route, because its queue assumes every step is worth the same. Dijkstra's algorithm makes one change. The frontier is kept not in a plain queue but in a priority queue, a structure that always yields the position of smallest cost first. Each position records the cheapest total cost by which the search has so far reached it. The search repeatedly removes the position of least cost, marks it settled, and for each neighbour checks whether reaching it through the current position is cheaper than any route found before; if so, the neighbour's recorded cost is lowered and its parent updated.

Because positions are settled in order of increasing cost, the first time the algorithm settles the goal it has the cheapest route to it, which is the same argument that made breadth-first search optimal, now stated in cost rather than in steps. The relationship between the two algorithms is exact: breadth-first search is Dijkstra's algorithm for the particular case in which every cell costs one, and in that case the priority queue, always yielding the smallest cost, reduces to a plain queue yielding the earliest arrival. The figure makes the difference visible. Without weights the frontier is a roughly circular ring; place a band of heavy terrain across it and the ring deforms, racing over the cheap ground and stalling against the costly band, because the frontier is a contour of equal cost and no longer a contour of equal distance.

6Heuristics and A* search

Dijkstra's algorithm shares one weakness with breadth-first search. It has no information about the position of the goal, and so it expands the cheapest position anywhere on the frontier, including positions that lie in the opposite direction from the target. A* removes that weakness by supplying the missing information.

A* retains the cost-so-far of Dijkstra's algorithm, written g, the cheapest known cost from the start to a position. It adds a second quantity, written h, an estimate of the cost that remains from that position to the goal. It then orders the frontier not by g alone but by the sum f = g + h, which is an estimate of the total cost of the best route passing through that position. The search always works on the position that looks most promising overall, weighing cost already incurred against cost expected to come.

On a grid whose moves are the four orthogonal directions, the natural estimate is the Manhattan distance, the number of horizontal and vertical steps between a position and the goal counted as though no walls existed. It is cheap to compute and, because walls can only lengthen a route and never shorten it, it never exceeds the true remaining cost. The figure shows the consequence. Where Dijkstra's algorithm expanded a roughly circular region around the start, A* expands a region stretched toward the goal, and positions lying behind the start or far to the side are never examined at all, because their f is too large to reach the front of the queue. The route returned is the same optimal route; the quantity that changes is the count of positions examined to find it, and on a graph of millions of positions that count is the difference between a smooth response and a visible delay.

7Admissibility, consistency and optimality

A* returns an optimal route only when its heuristic satisfies a condition, and the condition is worth stating carefully, because it is the point at which the algorithm's speed and its correctness are reconciled. A heuristic is called admissible when it never overestimates the true remaining cost to the goal. The Manhattan distance of the previous section is admissible, since the true route can only be longer than the obstacle-free estimate. When the heuristic is admissible, A* is guaranteed to return a route of minimum cost.

The reason is that an admissible heuristic can never cause A* to settle the goal by a route that is not the cheapest. Were the goal about to be settled by an over-long route, some position on a genuinely cheaper route would still be on the frontier, and because the heuristic does not overestimate, that position's f would be no greater than the true optimal cost, which is less than the cost of the over-long route. The cheaper position would therefore be settled first. The goal is settled only when no cheaper possibility remains.

A slightly stronger condition, consistency, requires that the heuristic's estimate never falls by more than the cost of a step when the search moves one step closer to the goal. A consistent heuristic is always admissible, and it brings a practical convenience: under it, the first time A* settles any position it has already found the cheapest route to that position, and no position need ever be re-examined. The Manhattan distance is consistent, which is why the implementation in the figures need not reopen settled cells.

The two endpoints of the heuristic are instructive. A heuristic that estimates zero everywhere is trivially admissible, and with it f = g and A* becomes Dijkstra's algorithm exactly. A heuristic equal to the true remaining cost would lead A* straight to the goal with no wasted work. Every practical heuristic lies between the two, and the closer it approaches the true cost without exceeding it, the narrower the search.

8Beyond the grid

A* on a grid is the standard tool of pathfinding, but the grid was a modelling choice, and three situations identified in the literature review call for a different graph. The figure below runs A* on a maze of narrow corridors, a harder grid than the earlier ones, as a point of comparison before those situations are described.

The first situation is many travellers sharing one destination. Running A* once for each traveller repeats almost identical work, and a single search already computes something better. One run of Dijkstra's algorithm outward from the goal assigns every position its cheapest cost to that goal; recording at each position the direction of its cheapest neighbour yields a flow field, a map of directions covering the whole graph. Every traveller, wherever it stands, follows the direction recorded beneath it. The continuum approach of Treuille and colleagues [10] is the developed form of this idea.

The second situation is open space. A grid spends its detail uniformly, so an empty plaza costs as many cells as a cluttered corridor, and its four-directional moves can only approximate a straight line across open ground. A navigation mesh [11] covers the walkable area with a small number of convex polygons; movement within a polygon is a straight line, so the search runs over a few hundred polygons rather than a few million cells, and the route may run at any angle.

The third situation is sheer scale. On a very large map even A* is too slow, and the remedy mirrors how a person plans a long journey, by choosing a sequence of cities first and the streets within each city only afterwards. Hierarchical pathfinding [8] divides the map into regions, precomputes the costs between region gateways, and searches the small graph of regions before searching the detailed grid inside the few regions the route actually crosses. In every one of these cases the search itself is unchanged. What changes is the graph it is given.

9Conclusion

Pathfinding rests on a small and stable core. A graph abstracts the space. A frontier holds the positions discovered but not yet examined. Parent pointers, accumulated for free during the search, recover the route once the goal is reached. The three classical algorithms differ only in the order in which they take positions from the frontier: breadth-first search by distance in steps, Dijkstra's algorithm by cost, and A* by cost plus a heuristic estimate of the cost remaining. The theory of section seven identifies the single condition, admissibility, under which the heuristic accelerates the search without compromising the optimality of its result.

The literature review placed this core in a sequence of repairs, and the structures of section eight continue it: a flow field for many travellers, a navigation mesh for open space, a hierarchy for vast maps. Each is a different graph handed to the same search. A reader who has followed the argument here is equipped to read further into that history, because its questions are the questions this document has posed throughout: in what order to examine positions, how to recover the route, and how to be certain the route is the best one.

Return to contents

RReferences

  1. Moore, E. (1959). The shortest path through a maze. Proceedings of an International Symposium on the Theory of Switching. Harvard University Press.
  2. Dijkstra, E. (1959). A note on two problems in connexion with graphs. Numerische Mathematik, 1(1).
  3. Hart, P., Nilsson, N. and Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2).
  4. Hart, P., Nilsson, N. and Raphael, B. (1972). Correction to "A formal basis for the heuristic determination of minimum cost paths". SIGART Newsletter, 37.
  5. Pohl, I. (1970). Heuristic search viewed as path finding in a graph. Artificial Intelligence, 1(3-4).
  6. Stentz, A. (1994). Optimal and efficient path planning for partially-known environments. Proceedings of the IEEE International Conference on Robotics and Automation.
  7. Koenig, S. and Likhachev, M. (2002). D* Lite. Proceedings of the AAAI Conference on Artificial Intelligence.
  8. Botea, A., Müller, M. and Schaeffer, J. (2004). Near optimal hierarchical path-finding. Journal of Game Development, 1(1).
  9. Harabor, D. and Grastien, A. (2011). Online graph pruning for pathfinding on grid maps. Proceedings of the AAAI Conference on Artificial Intelligence.
  10. Treuille, A., Cooper, S. and Popović, Z. (2006). Continuum crowds. ACM Transactions on Graphics, 25(3).
  11. Snook, G. (2000). Simplified 3D movement and pathfinding using navigation meshes. In Game Programming Gems. Charles River Media.