A* search with admissible heuristics

A* search finds a cheapest route from a start to one known goal, as Dijkstra’s algorithm does, but it orders its queue by the cost so far plus an estimate of the cost still to come. With an admissible heuristic, an estimate that never overestimates the remaining cost, the moment A* takes the goal from its queue it has a cheapest route. On grids the usual estimate is the Manhattan distance to the goal. A good estimate steers the search towards the goal, so it settles fewer cells than Dijkstra for the same answer.

The problem: a robot on a warehouse floor

A warehouse floor is a grid of up to 300 × 300 cells. # is a shelf the robot cannot enter, . a tile that takes 1 second to enter and ~ a wet tile that takes 3. The robot at S moves one cell up, down, left or right per step, and entering S or the packing desk T takes 1 second. Return the fewest seconds from S to T, or −1 if T cannot be reached. The control computer plans 5,000 trips a minute, so a trip should settle as few cells as it can.

• The 6 × 9 floor in the diagram takes 15 seconds; its route crosses one wet tile because going round costs more.
• S.#T above ..#. cannot be done: −1.
• S~T takes 4 seconds: 3 for the wet tile and 1 for the desk.

The brute force, and why it fails at 5,000 trips a minute

Listing routes is hopeless, and Dijkstra’s algorithm, though right, searches nearly the whole floor:

"""Two baselines for the robot's route: listing routes, which explodes, and Dijkstra's algorithm, which is right but
settles almost every cell that the robot could reach sooner than the desk."""

import heapq
import time
from math import comb

COST = {".": 1, "~": 3, "S": 1, "T": 1}


def dijkstra(floor):
    """(seconds to the desk, cells settled), or (-1, cells settled) when the desk cannot be reached."""
    rows, cols = len(floor), len(floor[0])
    start = next((r, row.index("S")) for r, row in enumerate(floor) if "S" in row)
    desk = next((r, row.index("T")) for r, row in enumerate(floor) if "T" in row)
    best, heap, settled = {start: 0}, [(0, start)], 0
    while heap:
        g, (r, c) = heapq.heappop(heap)
        if g > best[(r, c)]:
            continue
        settled += 1
        if (r, c) == desk:
            return g, settled
        for nr, nc in ((r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)):
            if 0 <= nr < rows and 0 <= nc < cols and floor[nr][nc] != "#":
                ng = g + COST[floor[nr][nc]]
                if ng < best.get((nr, nc), float("inf")):
                    best[(nr, nc)] = ng
                    heapq.heappush(heap, (ng, (nr, nc)))
    return -1, settled


def floor_of(rows, cols, seed, shelves=20, wet=15):
    state, out = seed, []
    for _ in range(rows):
        row = []
        for _ in range(cols):
            state = state * 48271 % 2147483647
            v = state % 100
            row.append("#" if v < shelves else "~" if v < shelves + wet else ".")
        out.append(row)
    out[0][0], out[-1][-1] = "S", "T"
    return ["".join(row) for row in out]


def open_cells(floor):
    return sum(row.count(".") + row.count("~") + row.count("S") + row.count("T") for row in floor)


SMALL = ["S..#.....",
         ".#.#.~~..",
         ".#...~##.",
         ".###.~...",
         "...#.#.#.",
         "~~...#.#T"]
for name, floor in [("small floor", SMALL), ("walled-off desk", ["S.#T", "..#."]), ("one wet tile", ["S~T"])]:
    seconds, settled = dijkstra(floor)
    print(f"{name}: {seconds} s; Dijkstra settled {settled} of {open_cells(floor)} open cells")

print(f"routes of 38 steps across an open 20 x 20 floor, corner to corner: {comb(38, 19):,}")

big = floor_of(300, 300, 1)
start = time.process_time()
seconds, settled = dijkstra(big)
used = time.process_time() - start
print(f"300 x 300 floor: {seconds} s; Dijkstra settled {settled:,} of {open_cells(big):,} open cells in {used:.2f} s of CPU")
print(f"at that speed, 5,000 trips a minute need {5000 * used / 60:.0f} CPU cores")

small floor: 15 s; Dijkstra settled 40 of 40 open cells
walled-off desk: -1 s; Dijkstra settled 4 of 6 open cells
one wet tile: 4 s; Dijkstra settled 3 of 3 open cells
routes of 38 steps across an open 20 x 20 floor, corner to corner: 35,345,263,800
300 x 300 floor: 620 s; Dijkstra settled 71,927 of 72,081 open cells in 0.13 s of CPU
at that speed, 5,000 trips a minute need 11 CPU cores

An open 20 × 20 floor alone has 35,345,263,800 shortest routes from corner to corner. Dijkstra settles all 40 open cells of the small floor, and 71,927 of the 72,081 open cells of the 300 × 300 floor, because the desk is in the far corner. In the recorded run a single trip took over a tenth of a second of CPU in CPython, so 5,000 trips a minute would need more than ten processor cores.

What to notice

• The desk is known. Dijkstra spreads out evenly in every direction and never uses where the desk is.
• A cheap lower bound exists. Every step takes at least 1 second, so the time still needed is at least the Manhattan distance to the desk.
• Bounds add up. Time so far plus that bound is a lower bound for every route through a cell, so cells can be ordered by it.

Five ideas follow:

• A* orders cells by g + h, the seconds so far plus the Manhattan distance to the desk.
• An admissible estimate never exceeds the true remaining time.
• A consistent estimate drops by at most the cost of each step, so a step never lowers g + h.
• A tie rule decides which of two cells with equal g + h comes out of the queue first.
• A weighted estimate multiplies h by a number above 1 and gives up the guarantee of a fastest route.

A* step by step Pro: opens with a Pro, Premium or Ultimate pass