A* search

g, h and f, open and closed lists, admissible heuristics, tracing A*, and A* against Dijkstra on the mat's grid.

A5.8Algorithms and complexityA level30 min

Dijkstra's algorithm spreads out from the start in every direction, like a ripple on a pond, until the ripple reaches the destination. It has no idea where the destination is, so it wastes effort on vertices that lead the wrong way. A* (said "A star") finds a shortest route to one destination using a hint about which way to go. It is the standard path-finding algorithm in games and robot navigation.

g, h and f

For every vertex n it considers, A* uses three numbers:

• g(n): the cost of the best route found so far from the start to n. This is exactly Dijkstra's distance.
• h(n): a heuristic, an estimate of the cost still to go from n to the destination. It is worked out from where n is, not by searching.
• f(n) = g(n) + h(n): the estimated cost of the whole route from start to destination through n.

Dijkstra's algorithm always takes the vertex with the smallest g. A* always takes the vertex with the smallest f. A vertex that is cheap to reach but leads away from the goal has a large h, so A* leaves it until later, and may never need it at all.

On the mat, a good heuristic is the straight-line distance to the destination. On a grid where the robot moves only up, down, left and right, it is the Manhattan distance: the difference in rows plus the difference in columns.

The algorithm

A* keeps two lists. The open list holds vertices that have been found but not yet expanded. The closed list holds vertices that have been expanded, whose best route is settled.

1. Put the start on the open list with g = 0 and f = h(start).
2. Take the vertex with the smallest f off the open list and put it on the closed list. If it is the destination, stop.
3. For each neighbour not on the closed list: work out g through this vertex (this vertex's g plus the edge weight). If the neighbour is not on the open list, or this g is smaller than its current g, set its g, set f = g + h, record this vertex as its previous vertex, and put it on the open list.
4. Repeat from step 2. If the open list becomes empty, there is no route.

Then read the route back through the previous vertices, as with Dijkstra.

A trace

Find the shortest route from S to G. The number above or below each vertex is its heuristic h, the straight-line distance to G rounded down.

In step 4, A and G are tied on f = 11. The tie is broken by the smaller h, which picks G: nearer the goal by the estimate. The route read back from G is S, B, D, G with cost 11.

A* expanded 4 vertices and never touched A or C. Dijkstra's algorithm on the same graph would expand all six, because A (distance 4) and C (distance 8) are both closer to S than G is (11).

When is the answer guaranteed shortest?

The heuristic decides. A heuristic is admissible if it never overestimates the real remaining cost.

• Admissible heuristic: A* always finds a shortest route. Straight-line distance is admissible on the mat, because no road can be shorter than a straight line. (In the trace, the heuristics were rounded down to keep them admissible.)
• h = 0 everywhere: f is just g, and A* is exactly Dijkstra's algorithm.
• Heuristic that overestimates: A* rushes towards the goal and usually expands fewer vertices, but it can return a route that is not the shortest.

The closer an admissible heuristic is to the true remaining cost, the fewer vertices A* expands. (Straight-line and Manhattan distances also have a stronger property, called being consistent, which guarantees that a vertex's g never improves after it is closed. The lesson's algorithm relies on that.)

A* on the mat's grid

Split the mat into squares, some of them walls (#). The robot moves one square at a time up, down, left or right, each move costing 1. This runs A* with the Manhattan distance, and then runs the same code with h = 0, which is Dijkstra's algorithm, and draws each route with *:

import heapq

mat = [
    "..........",
    "......#...",
    "......#...",
    ".S....#.G.",
    "......#...",
    "....###...",
    "..........",
]

def find(ch):
    for r, row in enumerate(mat):
        if ch in row:
            return (r, row.index(ch))

def a_star(start, goal, use_heuristic=True):
    def h(cell):
        if not use_heuristic:
            return 0
        return abs(cell[0] - goal[0]) + abs(cell[1] - goal[1])    # Manhattan distance
    g = {start: 0}
    previous = {start: None}
    open_list = [(h(start), h(start), start)]                     # (f, h, cell)
    closed = set()
    while open_list:
        f, _, cell = heapq.heappop(open_list)
        if cell in closed:
            continue
        closed.add(cell)
        if cell == goal:
            break
        r, c = cell
        for nxt in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]:
            nr, nc = nxt
            if 0 <= nr < len(mat) and 0 <= nc < len(mat[0]) and mat[nr][nc] != "#" and nxt not in closed:
                if g[cell] + 1 < g.get(nxt, float("inf")):
                    g[nxt] = g[cell] + 1
                    previous[nxt] = cell
                    heapq.heappush(open_list, (g[nxt] + h(nxt), h(nxt), nxt))
    path, cell = [], goal
    while cell is not None:
        path.append(cell)
        cell = previous[cell]
    return path[::-1], len(closed)

start, goal = find("S"), find("G")
for name, flag in [("A*", True), ("Dijkstra", False)]:
    path, expanded = a_star(start, goal, flag)
    print(name, "route of", len(path) - 1, "moves, expanded", expanded, "cells")
    rows = [list(row) for row in mat]
    for r, c in path[1:-1]:
        rows[r][c] = "*"
    print("\n".join("".join(row) for row in rows))

Run this in the simulator

Both find a route of 13 moves (they may draw different routes of the same length), but A* expands 33 cells and Dijkstra's algorithm 61. On a bigger, more open mat the difference is far larger.

Efficiency

A*'s performance depends on its heuristic. With h = 0 it does all of Dijkstra's work, plus a little for the heuristic. With a good admissible heuristic it expands a small fraction of the graph. In the worst case, with a poor heuristic on a hard map, it can expand nearly everything, and it must hold the whole open list in memory, which can be the real limit on a large map.

So when the robot needs routes to many places at once (a table of distances to every charging point), Dijkstra's algorithm is the right tool. When it needs one route to one place, quickly, A* is.

Task: round the rough ground

The mat in the starter has rough squares (~) as well as walls (#). Entering a normal square (., S or G) costs 1 and entering a rough square costs 3. Moves are up, down, left and right only.

Write a_star(grid, use_heuristic) that returns a tuple (cost, expanded): the cost of the cheapest route from S to G, and the number of squares expanded. Use the Manhattan distance as the heuristic when use_heuristic is True and 0 when it is False (which makes it Dijkstra's algorithm). To make the count exact:

• always expand the open square with the smallest f; break a tie by the smaller h, and then by the smaller row and then column, which is what a heap of (f, h, row, col) tuples does;
• a square is expanded when it is taken off the open list and closed. Skip (and do not count) a square that is already closed. Stop as soon as G is expanded, and count it.

Print exactly three lines:

• cost: <n>
• A* expanded: <n>
• Dijkstra expanded: <n>

# the two lines every program starts with: the commands, then the robot
from bugbot import *
connect()

import heapq

grid = [
    "............",
    "............",
    "....~~~~....",
    ".S..~~~~..G.",
    "....~~~~....",
    "....#####...",
    "............",
    "............",
]

Challenges

1. Is the Manhattan distance still admissible if moving onto a normal square cost 0.5? What would you change?
2. Multiply the heuristic by 3 and run again. Does A* still find the cheapest route? How many squares does it expand?
3. Allow diagonal moves costing 1.4. Why is the Manhattan distance no longer admissible, and what heuristic could you use instead?