Search is controlled expansion

Suppose a problem is represented as a graph. A state is a vertex. A permitted action is an edge. Each edge carries a non-negative cost. The search begins with one known state and a frontier of discovered states whose consequences have not yet been expanded. Every search policy answers the same operational question: which frontier state receives the next unit of computation?

Breadth-first search answers with depth. Uniform-cost search answers with cost already paid. Depth-first search answers with the most recently opened branch. A heuristic search adds a domain-informed estimate of what remains. The algorithms differ less in their ability to generate possibilities than in the discipline used to order those possibilities.

Dijkstra's shortest-path method settles states in increasing cost from the start.[1] If all edge costs are non-negative and the graph is handled correctly, the first settled route to the goal is cheapest. The method is admirably honest. It refuses to guess where the goal lies. That honesty can also be expensive, because it explores every state whose known cost competes with the best route.

The sum that defines A*

Hart, Nilsson and Raphael formalised A* by combining domain heuristic information with graph search.[2] For a frontier state n, the familiar evaluation is:

The equation earns its value from the tension between its terms. A low g state is cheap to reach but may point away from the goal. A low h state looks close to the goal but may have required an expensive route. A* gives priority to states that are competitive on the total estimated path cost.

Set h to zero everywhere and A* becomes Dijkstra's cost-ordered search. Set g aside and the policy becomes greedy best-first search, which pursues apparent closeness without protecting the price already paid. Between them lies a family of policies that decide how strongly to trust the estimate. Pohl's early analysis explicitly related search efficiency to heuristic accuracy and to the weight placed on the heuristic.[3]

The heuristic is therefore an ordering instrument. It is evaluated before the future route is known. A useful estimate must be cheaper to obtain than the search work it avoids. An oracle that computes the exact remaining cost by solving a second shortest-path problem is perfectly informative and usually pointless, unless that work can be precomputed and reused.

Minimal worked example: three versions of the same frontier

Consider a graph with two complete routes. The upper route is S → A → C → G with total cost 5. The lower route is S → B → G with total cost 10. After expanding S, the frontier contains A with g=3 and B with g=1.

With h=0, uniform-cost search expands B first because one unit has been paid, then later corrects towards the upper route. With admissible estimates h(A)=2 and h(B)=9, both complete-route estimates become 5 and 10, so A* commits useful work to A. With a false estimate h(A)=100 and h(B)=0, the goal through B can be removed from the frontier at cost 10 before the optimal branch is examined.

This small graph also reveals why a benchmark that reports only successful completion is weak. All three policies may reach the goal. The measured difference lies in route cost, expansion order and the conditions under which the first goal can be accepted. A search evaluation must record these separately.

Why a modest heuristic improvement can matter enormously

Search cost grows through branching. If each expanded state produces roughly b useful successors and the cheapest solution lies at depth d, an unguided tree can contain a number of states on the order of b^d. The exact count depends on duplicate structure, edge costs and pruning, but the exponential pressure is real. A heuristic earns leverage by reducing the effective branching factor: fewer successors remain competitive at each layer.

A common descriptive measure chooses b* so that the observed number of expanded states N satisfies N+1 = 1+b*+(b*)²+…+(b*)^d. This does not explain why the heuristic worked, and different problem families can share the same value. It does show why a small reduction can compound across a long route. Moving from an effective branching factor of 2.0 to 1.6 has little drama in one layer and a large consequence after twenty.

The same compounding creates a trap for averages. A heuristic may be excellent for nineteen layers and fail near one bottleneck, causing the frontier to spread precisely where the remaining search is largest. Report expansion distributions by depth and topology, not only one final ratio. The goal is to learn which structural feature was pruned, which was delayed and whether that delay was licensed by a lower bound.

flowchart LR
  A["The route that looks shorter"] --> B["Search is controlled expansion"]
  B --> C["Where the guarantee lives"]
  C --> D["The price of guidance"]
  D -. "re-test" .-> A
  classDef first fill:#0a1424,stroke:#087A98,stroke-width:2px,color:#e6f3ff
  classDef step fill:#0a1424,stroke:#3f7da0,stroke-width:1px,color:#e6f3ff
  class A first
  class B,C,D step

Where the guarantee lives

Let h*(n) denote the true cheapest remaining cost from state n to a goal. A heuristic is admissible when it never claims more remaining cost than reality:

Admissibility makes f(n) a lower bound on completions of the particular path record represented by n. It is not automatically a lower bound on every route through the same state when a cheaper path to that state may still be undiscovered. When a goal is selected with cost C, and every path record that could lead to a cheaper completion remains represented by a frontier lower bound of at least C, the search has a certificate. An unseen cheaper route cannot have been discarded by invalid duplicate handling.

Optimality belongs to the bound, duplicate policy and stopping rule together. Merely calculating g+h does not create it. The proof depends on retaining the cheapest discovered path record, reopening a state when an improved path can invalidate closure, requiring the declared edge-cost domain, and applying the goal test only at the certified stopping point.

Consistency is a local condition with operational consequences

A heuristic is consistent when each edge preserves a triangle-like inequality:

With a consistent heuristic, the first expansion of a state under ordinary graph-search A* carries its cheapest g value. A closed state need not be reopened. Admissibility alone is enough for several forms of tree search, but a graph implementation that closes states permanently needs the stronger local condition or another mechanism that repairs cheaper discoveries.

The common teaching shortcut, “admissible is good and inconsistent is bad”, is too crude. Felner and colleagues showed that inconsistent heuristics can increase value diversity and reduce work in some domains, especially when paired with propagation methods such as bidirectional pathmax. They can also trigger many reopenings in A* pathfinding.[8] The engineering question is therefore not whether inconsistency exists in the abstract. It is whether the implementation detects improved paths, supports the required repair and measures the resulting cost.

Thought experiment one: the honest compass and the hidden wall

Imagine two maps that are identical in every visible coordinate. In Map A, the direct corridor to the goal is open. In Map B, a wall blocks it near the end and the only doorway lies far to the south. Manhattan distance assigns the same heuristic value to corresponding states in both maps.

Change only the wall. The estimate remains admissible because it still understates actual travel cost. In Map A it is highly informative; in Map B it creates a dense search basin near the blocked corridor. Ordinary A* eventually recovers and remains optimal, but the expansion saving collapses. A greedy or heavily weighted variant may spend its budget at the wall or accept a more expensive alternative.

The thought experiment isolates one causal feature: heuristic accuracy is conditional on environment structure. A low average error over open maps says little about maps whose decisive feature is a remote bottleneck. The relevant failure may sit in a narrow subset of states along plausible optimal routes, not in the global mean.

Making a lower bound stronger without making it false

A zero heuristic is safe and usually weak. The craft lies in constructing estimates that approach h* from below. Several enduring methods do this by solving an abstraction or exploiting a metric relation.

Pattern databases precompute exact costs for abstract subproblems, then use those values as lower bounds for full states. Culberson and Schaeffer demonstrated how such stored abstractions can dramatically reduce search in sliding-tile puzzles.[6] The cost is moved into preprocessing time and memory. Additive pattern databases can combine disjoint contributions when their cost partition is valid; taking a maximum over admissible estimates is safe because no member exceeds the true cost.

Landmark methods choose reference vertices and use triangle inequalities to derive lower bounds between a query state and goal. Goldberg and Harrelson combined A* with landmark preprocessing and bidirectional variants for directed shortest paths, reporting large practical gains on road networks while preserving optimal paths.[7] Again, the speed is purchased through stored structure and query-time lookups.

Korf's iterative-deepening A* offers another trade when memory, rather than arithmetic, is the binding constraint. IDA* repeatedly performs depth-first searches under rising f thresholds, retaining linear path memory at the price of regenerated work.[5] There is no universally best search discipline. The right choice depends on branching, solution depth, duplicate structure, heuristic cost and memory pressure.

A stronger lower bound is useful only after its own cost is counted. A neural network may reduce node expansions while losing wall-clock time to batching, device transfer or per-state inference. Research on neural heuristics for optimal search explicitly reports this tension between smaller search trees and overhead against efficient conventional implementations.[13]

The price of guidance

Heuristic quality is often compressed into one number, such as mean absolute error against true cost-to-go. That number is convenient and incomplete. Search performance depends on where errors occur, how they correlate along paths, how they reshape plateaus and whether they violate the conditions used by the stopping proof.

An underestimate far from every competitive path may be harmless. A small overestimate on the only cheap corridor can hide the optimum. A locally inconsistent sequence can cause repeated reopening. An expensive but accurate estimate may lose to a weaker constant-time one. A learned estimate can pass a held-out test while failing on a new map family whose bottlenecks were absent from training.

The price of guidance has at least five currencies: solution-cost error, node expansions, heuristic evaluation time, memory or preprocessing, and fragility under shift. Reporting only one lets another become invisible.

Measured worked example: the warehouse laboratory

The map has 600 cells, 26 blocked shelf cells and a central rectangle of 192 costly cells. Movement is orthogonal. Normal entry costs one; entry into the costly zone costs five. The start and goal are 27 horizontal steps apart. The geometrically direct route costs 91, while a 39-step detour around the zone costs 39.

Manhattan distance multiplied by the minimum step cost is admissible. It never exceeds the cheapest remaining cost because every required horizontal or vertical move costs at least one. It is imperfect because it ignores terrain. The exact oracle is computed by reverse Dijkstra and included only as an explanatory ceiling. The shuffled control permutes exact cost-to-go values across states, preserving a useful-looking value distribution while destroying their relation to place.

Ordinary A* reduces expansions by about 77 per cent relative to Dijkstra on this map and preserves the optimal route. The exact oracle reduces them by about 92 per cent. Fivefold weighting reduces expansions by about 77 per cent relative to ordinary A*, yet increases route cost by 133 per cent. The shuffled control is worse than Dijkstra, despite being made from the same multiset of values as the exact oracle.

This is a serious negative control. If the shuffled signal had retained the claimed benefit, the experiment would have implicated incidental tie-breaking, data ordering or implementation effects rather than meaningful cost-to-go information. Here it expands 583 states and reopens 178, showing that value magnitude alone is not guidance. The relation between value and state carries the information.

Weighted and anytime search make the bargain explicit

Weighted A* replaces f=g+h with f_w=g+w·h. A weight above one favours apparent progress towards the goal. Under the assumptions of a particular weighted-search formulation, an admissible base heuristic can support a bounded-suboptimal claim. The bound must be stated with the algorithm, because reopening policy, stopping condition and bounding function matter.

ARA* turns this bargain into an anytime process. It starts with a loose suboptimality bound to obtain a feasible route, then tightens the bound while reusing prior work, converging to an optimal route when time permits.[9] This is often a more honest operating contract than pretending every request has enough time for exact search. The returned artefact should carry the current bound, incumbent cost and reason for stopping.

A faster first answer is defensible when its residual error is visible. A route labelled “cost 91, certified within the current bound, search continuing” is a different object from an unqualified route. The decision-maker can compare time saved with the consequence of excess cost.

Thought experiment two: a safe secondary guide

Now hold the admissible f=g+h ordering fixed. Many frontier states share the same smallest f. Introduce a learned signal that predicts which tied state will reach a goal sooner. In Experiment A, the signal breaks ties only. In Experiment B, the same signal is allowed to rank a higher-f state ahead of every state on the minimum-f plateau.

Only one causal feature changes: authority. In Experiment A, the learned signal can save work without changing which lower-bound layer must be exhausted before a more expensive goal is accepted. In Experiment B, it can hide the very frontier state that carries the optimality certificate.

Asai and Fukunaga showed that tie-breaking can dominate performance on large f plateaus, especially with zero-cost operators, and that inadmissible auxiliary heuristics can be embedded as tie-breakers inside cost-optimal A*.[10] The result supports a broader design rule: a weak but certified primary key and a strong secondary ranker need not be collapsed into one score.

Learned heuristics inherit a generalisation problem

Neural A* demonstrates that a learned guidance map can be coupled with differentiable search and trained from expert paths, improving the empirical optimality-efficiency trade in its evaluated path-planning settings.[12] That is evidence for useful learned ordering, not a universal lower-bound certificate. A model can overestimate on a rare state, and the rare state may be the only doorway to the optimum.

Recent work has therefore begun treating admissibility as a learning constraint rather than an afterthought. Futuhi and Sturtevant formulate heuristic learning with explicit admissibility penalties and analyse generalisation, while reporting near-admissible learned heuristics in Rubik's Cube experiments.[14] “Near” matters. A tiny global violation rate does not automatically bound the consequence of the violating states.

stateDiagram-v2
  [*] --> Claim
  state "The sum that defines A*" as Claim
  state "Minimal worked example: three<br/>versions of the same frontier" as Test
  state "Why a modest heuristic<br/>improvement can matter<br/>enormously" as Revision
  Claim --> Test: expose mechanism
  Test --> Decision: evidence survives
  Test --> Revision: rival survives
  Revision --> Claim: narrow or rebuild
  Decision --> [*]

A guidance contract for real systems

A route planner is more than a search loop. It receives a map snapshot, cost model and goal; returns a proposed route; and then relies on the world remaining close enough to that snapshot for the route to retain meaning. A* can prove the cheapest path in the represented graph. It cannot prove that a doorway remains open, that a cost estimate reflects current congestion or that the robot executed the intended turn.

Optimal in the model is not optimal in the world. This is the sharpest failure boundary. If the environment changes faster than planning and execution, the system needs observation, bounded release, readback and replanning. Search correctness cannot substitute for state freshness.

Production-shaped worked example: route, release, readback

Consider an autonomous mobile robot moving a tote through a mixed human warehouse. The planner's graph includes one-way aisles, turning radius, floor zones, battery cost and reserved intersections. Its heuristic combines Manhattan distance with admissible lower bounds for required turns. A separate learned ranker uses historical congestion patterns to break ties.

At planning time, the map service issues a versioned snapshot. The cost engine records which terms are exact, forecast or policy-derived. A* computes a route with an admissible primary key. Before release, a deterministic controller checks that the route stays within permitted zones and that reservations remain valid. The robot executes only the next bounded segment. Sensors then confirm position and obstruction state before the next segment is released.

If a pallet blocks the chosen aisle, the old route is not “wrong” as a graph result. Its world-state precondition has expired. The controller marks the remaining route stale, preserves the evidence of what was planned and invokes search on a fresh snapshot. This separation keeps algorithmic optimality from being misreported as operational certainty.

The two-channel guidance contract

The bound channel should state how the lower bound was derived, whether it is admissible, whether consistency is known, which cost model it matches and what repair the implementation performs. The ranking channel should state its training or construction data, evaluation cost, shift tests, allowed authority and fallback behaviour.

This design does not require two separate functions. One function may serve both roles when its properties are proved. The value lies in preserving two obligations. A learned signal can be operationally useful even when it cannot satisfy the bound obligation. A conservative geometric estimate can protect the certificate even when it is too weak to rank a large plateau efficiently.

A decision instrument for heuristic selection

Before adopting a heuristic, complete a guidance assurance card. It is deliberately stricter than “accuracy improved on the test set”.

1. Define the objective. Name the exact path cost, resource or risk being minimised. State whether the goal is optimality, bounded suboptimality, first feasible solution or anytime improvement.
2. Type the signal. Mark it as a certified lower bound, consistency-preserving estimate, unproved ranker, tie-breaker or learned proposal. Do not let an implementation cast one type into another silently.
3. Record authority. Specify whether the signal can order equal-bound states, enter a focal set, change the primary key, suppress reopening or trigger termination.
4. Measure the full price. Report route cost, expansions, generated states, reopenings, heuristic calls, evaluation time, peak memory and preprocessing amortisation.
5. Attack the relation. Shuffle, delay or perturb the signal; construct bottlenecks and zero-cost plateaus; shift terrain and goal distribution; compare with h=0 and the strongest affordable conventional baseline.
6. Bind the world model. Version the graph and cost model. Define freshness, readback and replanning conditions so that a valid search proof is not applied to a changed environment.

Executable artefact: re-run the trade

The browser control below runs the same synthetic map with a selected heuristic weight. The static table remains the reviewed result; the control is a compact way to feel the discontinuity. Weight one is the positive case. Weight five is the negative case in which speed improves while route cost worsens.

#!/usr/bin/env python3
"""A small, dependency-free laboratory for heuristic guidance in A*.

The lab searches one synthetic weighted warehouse map with several guidance
policies. It is intentionally small enough to inspect and deterministic enough
to reproduce. Run with:

    python3 a_star_guidance_lab.py

Expected headline result:
- h=0 and admissible Manhattan both return the same optimal route;
- stronger admissible guidance reduces expansions;
- aggressive weighted guidance can expand fewer states yet return a costlier route;
- shuffling a useful signal is a negative control for accidental ordering effects.
"""

from __future__ import annotations

from dataclasses import dataclass
from heapq import heappop, heappush
from itertools import count
import json
import math
import random
from typing import Callable, Dict, Iterable, List, Mapping, Optional, Sequence, Tuple

Cell = Tuple[int, int]
Heuristic = Callable[[Cell], float]


@dataclass(frozen=True)
class Grid:
    width: int
    height: int
    start: Cell
    goal: Cell
    blocked: frozenset[Cell]
    terrain_cost: Mapping[Cell, float]

    def neighbours(self, cell: Cell) -> Iterable[Tuple[Cell, float]]:
        y, x = cell
        for dy, dx in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            nxt = (y + dy, x + dx)
            ny, nx = nxt
            if not (0 <= ny < self.height and 0 <= nx < self.width):
                continue
            if nxt in self.blocked:
                continue
            # Cost is paid when entering the next cell.
            yield nxt, float(self.terrain_cost.get(nxt, 1.0))


@dataclass
class SearchResult:
    name: str
    found: bool
    cost: float
    expansions: int
    generated: int
    reopens: int
    path: List[Cell]

    def to_record(self, optimal_cost: float) -> Dict[str, object]:
        ratio = self.cost / optimal_cost if self.found and optimal_cost > 0 else math.inf
        return {
            "policy": self.name,
            "found": self.found,
            "cost": None if not self.found else round(self.cost, 3),
            "cost_ratio": None if not self.found else round(ratio, 3),
            "expansions": self.expansions,
            "generated": self.generated,
            "reopens": self.reopens,
            "path_length": max(0, len(self.path) - 1),
        }


def reconstruct(parent: Mapping[Cell, Cell], goal: Cell) -> List[Cell]:
    path = [goal]
    while path[-1] in parent:
        path.append(parent[path[-1]])
    path.reverse()
    return path


def a_star(
    grid: Grid,
    heuristic: Heuristic,
    *,
    name: str,
    weight: float = 1.0,
    reopen: bool = True,
) -> SearchResult:
    """Graph-search A* with stale-entry checks and optional node reopening.

    The priority is g(n) + weight * h(n). With weight=1 and a suitable
    admissible lower bound, this is ordinary A*. With weight>1 it is weighted
    A*, which deliberately changes the speed/solution-cost trade.
    """

    serial = count()
    open_heap: List[Tuple[float, float, int, Cell, float]] = []
    best_g: Dict[Cell, float] = {grid.start: 0.0}
    parent: Dict[Cell, Cell] = {}
    closed: Dict[Cell, float] = {}
    expansions = generated = reopens = 0

    start_h = float(heuristic(grid.start))
    start_secondary = start_h if weight > 0 else 0.0
    heappush(open_heap, (weight * start_h, start_secondary, next(serial), grid.start, 0.0))

    while open_heap:
        _, _, _, node, queued_g = heappop(open_heap)
        current_g = best_g.get(node, math.inf)
        if queued_g != current_g:  # stale heap entry
            continue
        if node in closed and closed[node] <= current_g:
            continue
        if node == grid.goal:
            return SearchResult(
                name=name,
                found=True,
                cost=current_g,
                expansions=expansions,
                generated=generated,
                reopens=reopens,
                path=reconstruct(parent, node),
            )

        closed[node] = current_g
        expansions += 1

        for nxt, step_cost in grid.neighbours(node):
            generated += 1
            candidate_g = current_g + step_cost
            if candidate_g >= best_g.get(nxt, math.inf):
                continue

            if nxt in closed:
                if not reopen:
                    continue
                reopens += 1
                del closed[nxt]

            best_g[nxt] = candidate_g
            parent[nxt] = node
            h = float(heuristic(nxt))
            f = candidate_g + weight * h
            # h is the deterministic secondary key whenever guidance is active.
            # At weight=0 we also remove h from tie-breaking, yielding Dijkstra.
            secondary = h if weight > 0 else 0.0
            heappush(open_heap, (f, secondary, next(serial), nxt, candidate_g))

    return SearchResult(
        name=name,
        found=False,
        cost=math.inf,
        expansions=expansions,
        generated=generated,
        reopens=reopens,
        path=[],
    )


def make_warehouse() -> Grid:
    """Create a synthetic 30x20 map with a costly central 'mud' rectangle.

    The geometrically direct route crosses the costly region. The cheapest route
    bends around it. All numbers are synthetic and intended only to expose the
    search mechanism.
    """

    width, height = 30, 20
    start, goal = (10, 1), (10, 28)
    terrain: Dict[Cell, float] = {}

    # A costly storage zone from columns 7..22 and rows 4..15.
    for y in range(4, 16):
        for x in range(7, 23):
            terrain[(y, x)] = 5.0

    # Two blocked shelf spines narrow the cheap upper/lower bypasses, without
    # changing the existence of either route.
    blocked = set()
    for x in range(8, 22):
        blocked.add((2, x))
        blocked.add((17, x))
    # Doorways in each shelf spine.
    blocked.remove((2, 14))
    blocked.remove((17, 16))

    return Grid(
        width=width,
        height=height,
        start=start,
        goal=goal,
        blocked=frozenset(blocked),
        terrain_cost=terrain,
    )


def manhattan(goal: Cell) -> Heuristic:
    gy, gx = goal
    return lambda cell: abs(cell[0] - gy) + abs(cell[1] - gx)


def reverse_shortest_costs(grid: Grid) -> Dict[Cell, float]:
    """Compute exact cost-to-go values by reverse Dijkstra.

    Because forward movement pays the cost of entering the destination cell,
    reverse traversal from u to predecessor p pays the forward cost of entering u.
    """

    serial = count()
    dist: Dict[Cell, float] = {grid.goal: 0.0}
    heap: List[Tuple[float, int, Cell]] = [(0.0, next(serial), grid.goal)]

    while heap:
        d, _, u = heappop(heap)
        if d != dist[u]:
            continue
        uy, ux = u
        forward_enter_u = float(grid.terrain_cost.get(u, 1.0))
        for dy, dx in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            p = (uy + dy, ux + dx)
            py, px = p
            if not (0 <= py < grid.height and 0 <= px < grid.width):
                continue
            if p in grid.blocked:
                continue
            nd = d + forward_enter_u
            if nd < dist.get(p, math.inf):
                dist[p] = nd
                heappush(heap, (nd, next(serial), p))
    return dist


def shuffled_signal(grid: Grid, values: Mapping[Cell, float], seed: int = 19) -> Heuristic:
    """Permute exact cost-to-go values across cells as a negative control."""

    cells = [
        (y, x)
        for y in range(grid.height)
        for x in range(grid.width)
        if (y, x) not in grid.blocked
    ]
    vals = [float(values[c]) for c in cells]
    random.Random(seed).shuffle(vals)
    # Preserve the exact multiset while keeping the conventional h(goal)=0.
    goal_index = cells.index(grid.goal)
    zero_index = vals.index(0.0)
    vals[goal_index], vals[zero_index] = vals[zero_index], vals[goal_index]
    table = dict(zip(cells, vals))
    return lambda cell: table[cell]


def run_lab() -> Tuple[Grid, List[SearchResult], Dict[str, object]]:
    grid = make_warehouse()
    h_zero: Heuristic = lambda _: 0.0
    h_manhattan = manhattan(grid.goal)
    exact = reverse_shortest_costs(grid)
    h_exact: Heuristic = lambda cell: exact[cell]
    h_shuffled = shuffled_signal(grid, exact)

    policies = [
        ("Dijkstra / h=0", h_zero, 1.0),
        ("A* / Manhattan lower bound", h_manhattan, 1.0),
        ("A* / exact cost-to-go oracle", h_exact, 1.0),
        ("Weighted A* / 1.5× Manhattan", h_manhattan, 1.5),
        ("Weighted A* / 3× Manhattan", h_manhattan, 3.0),
        ("Weighted A* / 5× Manhattan", h_manhattan, 5.0),
        ("Negative control / shuffled oracle", h_shuffled, 1.0),
    ]

    results = [
        a_star(grid, h, name=name, weight=weight, reopen=True)
        for name, h, weight in policies
    ]

    optimal_cost = results[0].cost
    records = [r.to_record(optimal_cost) for r in results]

    # Weight sweep supports the article's measured guidance frontier.
    sweep = []
    for weight in (0.0, 0.25, 0.5, 0.75, 1.0, 1.25, 1.5, 2.0, 3.0, 4.0, 5.0, 6.0):
        # weight=0 is Dijkstra even though the named heuristic is present.
        r = a_star(
            grid,
            h_manhattan,
            name=f"w={weight:g}",
            weight=weight,
            reopen=True,
        )
        sweep.append(r.to_record(optimal_cost))

    report: Dict[str, object] = {
        "map": {
            "width": grid.width,
            "height": grid.height,
            "start": grid.start,
            "goal": grid.goal,
            "blocked_cells": len(grid.blocked),
            "costly_cells": len(grid.terrain_cost),
            "costly_cell_entry_cost": 5.0,
        },
        "assumptions": [
            "four-neighbour movement",
            "non-negative deterministic cell-entry costs",
            "static map during one search",
            "Manhattan distance multiplied by minimum step cost is admissible",
            "the exact oracle is computed by reverse Dijkstra and is for explanation only",
        ],
        "optimal_cost": optimal_cost,
        "policies": records,
        "weight_sweep": sweep,
    }
    return grid, results, report


def verify(report: Mapping[str, object]) -> None:
    policies = {r["policy"]: r for r in report["policies"]}  # type: ignore[index]
    optimal = report["optimal_cost"]

    assert policies["Dijkstra / h=0"]["cost"] == optimal
    assert policies["A* / Manhattan lower bound"]["cost"] == optimal
    assert policies["A* / exact cost-to-go oracle"]["cost"] == optimal
    assert policies["A* / exact cost-to-go oracle"]["expansions"] <= policies["A* / Manhattan lower bound"]["expansions"]
    assert policies["A* / Manhattan lower bound"]["expansions"] <= policies["Dijkstra / h=0"]["expansions"]
    # At least one aggressive weighting must demonstrate the speed/quality trade.
    aggressive = policies["Weighted A* / 5× Manhattan"]
    assert aggressive["expansions"] < policies["A* / Manhattan lower bound"]["expansions"]
    assert aggressive["cost"] > optimal


def render_ascii(grid: Grid, results: Sequence[SearchResult]) -> str:
    symbols = [["." for _ in range(grid.width)] for _ in range(grid.height)]
    for y, x in grid.blocked:
        symbols[y][x] = "#"
    for y, x in grid.terrain_cost:
        symbols[y][x] = "~"
    # Show the optimal Manhattan-A* route.
    route = next(r.path for r in results if r.name == "A* / Manhattan lower bound")
    for y, x in route:
        if (y, x) not in (grid.start, grid.goal):
            symbols[y][x] = "*"
    sy, sx = grid.start
    gy, gx = grid.goal
    symbols[sy][sx] = "S"
    symbols[gy][gx] = "G"
    return "\n".join("".join(row) for row in symbols)


def main() -> None:
    grid, results, report = run_lab()
    verify(report)

    print("Synthetic warehouse map (# shelf, ~ costly zone, * optimal route):")
    print(render_ascii(grid, results))
    print("\nResults:")
    print(json.dumps(report, indent=2))
    print("\nAll verification checks passed.")


if __name__ == "__main__":
    main()

What to test beyond the toy map

One synthetic case cannot establish general performance. A release evaluation should sample across map topology, obstacle density, weighted terrain, goal distance, disconnected cases, zero-cost actions and dynamic changes. The Moving AI pathfinding corpus provides public grid maps and scenarios suitable for broader comparisons.[11]

Use matched compute budgets and report distributions, not only means. Separate search time from heuristic time. Include Dijkstra, a domain-standard admissible heuristic, an exact or strong offline reference where feasible, and shuffled or goal-permuted controls. Stratify by bottleneck structure because aggregate results can hide precisely the cases where guidance matters.

The release gate should also inject stale costs and map changes after planning. The expected response is not that A* somehow remains correct. The expected response is that the route's applicability expires, action release stops and a fresh search reconstructs the decision from current state.

When A* is no longer the right search discipline

A* keeps an open frontier and usually a closed record of expanded states. On large implicit spaces, memory can fail before the goal is reached. IDA*, memory-bounded best-first methods, hierarchical planning or bidirectional search may then be better placements of the same lower-bound idea. The decision should follow measured memory growth and duplicate structure, not loyalty to an algorithm name.

The formulation also becomes strained when the state is only partially observed, action outcomes are stochastic, several objectives cannot be reduced to one defensible cost, or the environment changes during every planning cycle. Those problems may require belief-state planning, contingent policies, multi-objective search or online control. A* can still solve a deterministic subproblem inside such a system, but its guarantee stays inside that boundary.

No-solution cases deserve separate tests. A powerful heuristic can reach a goal quickly when one exists yet provide little help proving that none exists, because the proof may require exhausting every state whose lower bound remains competitive. Measure disconnected maps and exhausted budgets explicitly. “Failed to return” must distinguish no route, insufficient memory, stale state, timeout and implementation error.

The strongest heuristic is the one whose authority matches its evidence. A weak lower bound with explicit limits can safely govern certification. A powerful learned signal may govern ranking. Confusing those roles turns empirical usefulness into an unsupported guarantee.