astar-grid

Instrumented single-agent A* on 2D grids. Foundation layer of the femi-mapf series.

---

Why this repository exists

Conflict-Based Search is often described as a two-level algorithm: a high-level constraint tree and a low-level single-agent planner. The low level is this search — A* over a time-extended graph, replanning a single agent subject to a set of vertex and edge constraints. CBS calls it thousands of times per instance. Its correctness is CBS's correctness, and its expansion count is CBS's runtime.

So this repository does not treat A* as a solved exercise to be got out of the way. It builds the search properly, verifies it against an independent oracle, and instruments every expansion so that search behaviour — not just search output — is observable. The subsequent repositories in the series (cbs-from-scratch, eecbs-benchmark, lacam-python, inspection-mapf) inherit that domain model and that instrumentation directly.

The heuristic comparison below is the deliverable. Every heuristic returns the same optimal cost. What separates them is how much of the map they had to look at to prove it.

---

Results

All figures and numbers are regenerated by astar-grid experiment. Nothing here is hand-copied.

32×32, 30% obstacles, 4-connected, seed 13

Obstacles are dark grey. Free cells the search never touched are white. Expanded cells are shaded by expansion order, pale (early) to bright (late). The optimal path is red.

heuristic	cost	expanded	generated	ms
zero	70.000	694	695	3.20
manhattan	70.000	225	296	1.93
euclidean	70.000	487	517	2.60
octile	70.000	458	501	2.72
chebyshev	70.000	514	557	3.11

Three things in that table are worth stating explicitly, because each one is a claim this repository is making and testing.

Every heuristic returns cost 70.000. That is admissibility doing its job. It is asserted, not hoped for: test_astar_matches_the_dijkstra_oracle_everywhere checks A* against an independently implemented Dijkstra, for every admissible heuristic, to every reachable cell, on eight seeded grids, under both movement models.

Manhattan expands 225 nodes; the null heuristic expands 694. A 3.1× reduction for the identical answer. That gap is the entire economic argument for informed search, and in CBS it is multiplied by the number of low-level replans in the constraint tree.

Euclidean expands 487 — more than twice Manhattan's 225 — despite both being admissible. This is the point most implementations miss. Correctness is a floor, not a target. On a 4-connected grid Manhattan dominates Euclidean (it is uniformly the tighter bound, tested in test_manhattan_dominates_euclidean_on_four_connected_grids), and dominance translates directly into fewer expansions. Choosing an admissible-but-weak heuristic costs you real time while telling you nothing is wrong.

Scaling across grid sizes (4-connected)

grid	zero	manhattan	reduction
8×8	49	33	1.5×
16×16	183	43	4.3×
32×32	694	225	3.1×

The advantage of the heuristic grows with the search space, which is the expected behaviour and the reason heuristic strength matters more, not less, as instances scale toward MAPF sizes.

The 8×8 instance (seed 23) is deliberately not a trivial one: optimal cost is 16 against a free-space lower bound of 14, so the path must bend around an obstacle rather than walk a monotone staircase.

8-connected results

With diagonal moves priced at √2, Manhattan becomes inadmissible and the library refuses to run it (see below). Octile — the exact free-space distance under that cost model — becomes the strongest heuristic:

grid	zero	euclidean	octile	chebyshev
8×8	48	39	34	40
16×16	170	59	55	76
32×32	692	399	355	462

All return identical optimal costs (14.828 / 24.728 / 62.627 respectively).

---

The inadmissibility guard

The most common silent bug in grid pathfinding is Manhattan distance on an 8-connected grid. A diagonal move spans two Manhattan units but costs only √2 ≈ 1.414, so Manhattan overestimates by up to 41%. A* then returns paths that are suboptimal but entirely plausible-looking — no crash, no warning, just quietly wrong costs propagating into whatever consumes them.

This library will not let that happen:

>>> from astar_grid import for_movement, Movement
>>> for_movement("manhattan", Movement.EIGHT_CONNECTED)
InadmissibleHeuristicError: 'manhattan' is not admissible on a 8-connected grid
(a diagonal move costs sqrt(2) but spans two manhattan units); use 'octile' or
'euclidean' instead

heuristics.by_name gives you the raw function if you deliberately want an inadmissible heuristic (weighted A* has legitimate uses for exactly this). heuristics.for_movement is the safe path and is what the CLI uses.

---

Install

Requires Python 3.10+. Instructions are for Git Bash on Windows.

git clone https://github.com/femi-mapf/astar-grid.git
cd astar-grid

python -m venv .venv
source .venv/Scripts/activate      # Git Bash on Windows

pip install -e ".[dev]"

On macOS or Linux the activation line is source .venv/bin/activate; everything else is identical.

---

Usage

Command line

# Solve one instance and print the map with the path marked
astar-grid solve --size 16 --density 0.25 --seed 11 --ascii

# Save the expansion figure
astar-grid solve --size 32 --density 0.3 --seed 13 --figure examples/run.png

# 8-connected with the octile heuristic
astar-grid --movement 8 solve --size 32 --heuristic octile

# Load a movingai.com benchmark map
astar-grid --movement 8 solve --map benchmarks/den312d.map --heuristic octile

# Regenerate every table and figure in this README
astar-grid experiment --out examples

Exit codes: 0 solved, 1 no path exists, 2 bad arguments (including an inadmissible heuristic).

Library

from astar_grid import Grid, Movement, astar, for_movement

grid = Grid.random_obstacles(size=32, density=0.30, seed=13)
result = astar(grid, (0, 0), (31, 31), for_movement("manhattan", grid.movement))

print(result.summary())
# cost=  70.000  cells=  71  expanded=   225  generated=    296     1.93 ms

result.path        # list[Coord] from start to goal, or None
result.cost        # float, inf when unsolved
result.expanded    # cells in expansion order — the instrumentation
result.generated   # nodes pushed, including lazy-deletion duplicates

An unreachable goal is not an exception. It returns an unsolved SearchResult with path=None and cost=inf, because "no path exists" is a finding to be measured, not an error to be raised. Illegal inputs — a start on an obstacle, a goal off the map — do raise GridError.

movingai.com benchmarks

Grid.from_movingai() parses the standard .map format directly, honouring its terrain convention (. and G traversable; @, O, T, S, W blocked). Drop any map from the Moving AI benchmark set into benchmarks/ and it loads without preprocessing. The same loader is reused by every downstream repository in the series, so CBS, EECBS and LaCAM all consume identical instances — which is what makes their head-to-head comparison honest.

---

Design notes

Coordinates are (row, col), origin top-left. Matches both NumPy indexing and the movingai convention, eliminating an entire class of transposition bug at the plotting boundary.

No corner cutting. Under the 8-connected model a diagonal move is legal only when both adjacent cardinal cells are free. This is the standard MAPF benchmark assumption, and it is also what keeps octile admissible — permit corner cutting and the true cost can drop below the octile estimate.

Tie-breaking by lower h. Among equal-f nodes the search expands the one with the smaller h first. Both are optimal; the low-h node sits deeper along a goal-bound path, which collapses the plateau of equal-f nodes that open terrain generates. Remaining ties break FIFO, keeping runs deterministic — test_search_is_deterministic_across_runs enforces this, because CI regenerates the figures above and a nondeterministic tie-break would make them drift.

Lazy deletion instead of decrease-key. heapq offers no decrease-key. Rather than maintain a heap index, an improved node is re-pushed and stale entries are discarded when popped. The g_score table is the single source of truth. This is why generated exceeds expanded, and the ratio between them is a useful diagnostic.

The domain knows nothing about search. Grid answers three questions: in bounds, passable, and what are the successors and their costs. It has no notion of a path, an agent, or a plan. That is precisely why CBS can replace the search wholesale — swapping in time-indexed states and constraint sets — while keeping this domain untouched.

---

Tests

pytest                      # full suite with coverage gate
pytest -vv --no-cov         # fast, verbose, no coverage
ruff check src tests        # lint
mypy                        # strict type check

132 tests, 99.4% coverage (zero uncovered statements). The build fails below 95%.

The suite is structured around properties rather than examples wherever possible:

• Optimality against an independent oracle. reference.py implements Dijkstra separately, with no heuristic machinery and a different code path. A* is verified against it, never against another configuration of itself — checking astar(manhattan) against astar(zero) would share the very expansion loop most likely to be broken, and prove nothing.
• Admissibility, exhaustively. Every heuristic is checked against exact Dijkstra distances at every free cell of a cluttered grid, in both movement models. Nothing is spot-checked.
• Consistency, on every edge. h(n) ≤ cost(n, n′) + h(n′) is verified across every edge in the graph. Consistency is what licenses closing a node permanently on first expansion, so it underwrites the closed-set logic in astar.py, not merely the optimality claim.
• Heuristic dominance. Stronger heuristics are asserted never to expand more nodes than weaker ones, across multiple seeds — the property the results table above depends on.
• The corner-cutting rule, the inadmissibility guard, unreachable goals, walled-in starts, single-cell paths, and determinism across runs.

---

Roadmap

repository	status	role
astar-grid	complete	single-agent A*, instrumentation, benchmark I/O
cbs-from-scratch	next	constraint tree, vertex/edge conflicts, time-indexed low level
eecbs-benchmark	planned	focal search, bounded suboptimality at w ∈ {1.1, 1.5, 2.0}
lacam-python	planned	configuration-space DFS with PIBT, anytime refinement
inspection-mapf	planned	30-node pipeline benchmark, heterogeneous UAV battery, two-mode inspection

---

Licence

MIT. See LICENSE.