Search as Structured Exploration

Part oneThe frontier is the algorithm

Imagine pausing search after five expansions. Some states have never been encountered. Some have been expanded, so every permitted outgoing action has been considered. Between them sits a set of reached but unfinished paths. That middle set is where choice remains. Steven LaValle’s general forward-search formulation calls these states alive and stores them in a queue whose sorting rule distinguishes search methods.^[1] His treatment makes the unification explicit: classical methods are special cases of one template obtained by changing the ordering of that queue.^[2]

The word queue can mislead because it sounds like FIFO only. Think instead of an abstract frontier with three operations: insert a path, select the next path and report whether any path remains. A FIFO deque, a LIFO stack and a minimum heap all implement that interface. They answer the selection question differently.

One loop, three disciplines

A search state describes a possible situation in the problem. An action transforms one state into a successor. A search node represents a path that ends in a state, so two nodes can end in the same state through different histories. This distinction matters because the frontier contains paths, while duplicate control usually compares states.

The generic loop is short:

1. Put the initial path on the frontier.
2. Select and remove one frontier path according to the discipline.
3. If its final state satisfies the goal test, return the path.
4. Otherwise expand the state, construct child paths and admit eligible children.
5. Stop with failure only when the frontier is empty.

The simplicity hides four contracts. The ordering contract says which path is selected. The identity contract says when two reached situations count as the same state. The duplicate contract says whether a later path may replace an earlier one. The termination contract says when a goal or exhausted frontier is sufficient evidence to stop.

For BFS, the frontier is FIFO. Paths leave in the order they entered, so every depth-4 path leaves before any depth-5 path. For DFS, the frontier is LIFO. The last child inserted leaves first, so the search extends one branch before returning to waiting siblings. For UCS, the frontier is a minimum-priority queue keyed by accumulated path cost. Python’s standard library mirrors these mechanisms: collections.deque supports operations at both ends, while heapq maintains a min-heap whose root is the smallest entry.^[12][13]

Tie-breaking often surprises beginners. Two paths can have the same depth or cost. Their relative order then depends on successor ordering or an explicit secondary key. BFS’s shortest-path guarantee survives ties under unit costs, and UCS’s cost guarantee survives equal-cost ties under its usual assumptions. The exact path and expansion trace may still change. Reproducible experiments therefore record successor order and tie policy.

Part twoThe guarantees and their price

A frontier discipline does more than produce a recognisable animation. It maintains an invariant, a statement that remains true whenever the next path is selected. Guarantees follow from that invariant together with assumptions about branching, costs, duplicate handling and state representation. Remove an assumption and the familiar algorithm name no longer carries the familiar promise.

Breadth-first search: fewest actions first

BFS selects a path of minimum depth, where depth d(n) is the number of actions from the initial state to node n. Its invariant is simple: no path at depth k + 1 is selected while a path at depth k remains on the frontier. Edward F. Moore’s 1959 maze work is an early published formulation of layerwise shortest-path exploration.^[3] Korf later described the same level-by-level property when comparing brute-force tree searches.^[6]

If a goal first leaves a FIFO frontier at depth d, every shallower reachable path has already been considered. The returned path therefore uses the fewest actions. This is an optimality statement only because the objective is action count. If one move costs one second and another costs a minute, BFS treats them as equal.

Completeness needs conditions. With finite branching and a goal at finite depth, BFS eventually reaches the goal if successor generation itself terminates. Duplicate control makes a finite graph practical and prevents cycles from creating repeated paths. An infinite number of successors at one state, or a generator that silently omits legal actions, breaks the familiar layer argument.

Depth-first search: latest commitment first

DFS selects the most recently admitted path. Its working invariant is local rather than global: keep extending the current branch until it ends, repeats a blocked state or reaches a configured limit, then backtrack to the latest waiting sibling. The reward is modest live memory. A recursive implementation that generates successors lazily can retain mainly the current path; an explicit stack commonly retains the path plus waiting siblings, often expressed as O(bm) for branching factor b and maximum search depth m.

The price is that recency says nothing about route quality. The first branch may contain a deep goal while a sibling contains a shallow one. It may contain an endless sequence of distinct states. It may contain a cycle if duplicate detection is absent or state identity is wrong. Korf’s analysis emphasised both the low-space appeal and the possibility of excessive time, non-termination and non-optimal first solutions.^[6]

DFS is nevertheless more than a weak route finder. Its disciplined nesting exposes structural facts about graphs. Tarjan’s classic algorithms use depth-first traversal to find strongly connected and biconnected components in linear time.^[5] That success does not contradict the pathfinding limitations. It shows that a traversal order can be exactly right for one derived property and poorly aligned with another objective.

Uniform-cost search: cheapest accumulated path first

UCS replaces depth with accumulated path cost. If a path contains transitions with costs c₀, c₁, …, cₖ₋₁, its cost-to-come is:

The frontier is ordered by g. A path can use more actions and still leave first if its accumulated cost is lower. Dijkstra’s 1959 formulation constructs minimum paths in increasing order of length, and modern UCS is the goal-directed state-space version of the same label-setting idea.^[4] LaValle states the key condition explicitly: edge costs are non-negative, tentative costs can be lowered while states remain on the priority queue, and a state’s cost becomes final when it is removed as the least-cost entry.^[14]

This explains a subtle implementation rule. For UCS, discovering a goal is not enough; the goal must be selected from the frontier at minimum accumulated cost. A costly one-edge path can generate the goal before a cheaper three-edge path has been completed. Testing on insertion would stop too early. Testing on removal lets the priority invariant do its work.

When every transition has the same positive cost k, UCS collapses to BFS:

This equivalence is a useful negative check. If BFS and UCS return different objective values on a unit-cost graph, inspect duplicate handling, goal timing, tie-breaking or implementation defects before inventing a theoretical explanation.

Worked example: one graph, three defensible answers

Consider the synthetic graph below. The goal G can be reached in two actions through B, at total cost 10. It can also be reached in three actions through A and C, at total cost 3. Successors are listed left to right. DFS is configured to visit the first listed child first.

BFS expands S, then the depth-one states A and B. The goal enters the frontier from B at depth two and eventually leaves before the depth-three alternative. It returns S → B → G, cost 10. That answer is correct for minimum action count.

DFS takes A first, then C, then G. It returns S → A → C → G, cost 3. Reverse the successor order at S and it returns the expensive route instead. The outcome is evidence about ordering, not a general cheapest-path capability.

UCS expands paths in non-decreasing accumulated cost. It reaches B with cost 1 and C with cost 2, but the goal through B has cost 10. The path through C generates the goal at cost 3, which leaves first. It returns the least-cost route.

The first serious compromise: iterative deepening

Suppose unit costs make shallowest depth the right objective, but BFS’s frontier will not fit in memory. Depth-first iterative deepening runs a depth-limited DFS at limit zero, then one, then two, continuing until a goal appears. It repeats shallow work, yet in an exponential tree most nodes sit near the deepest layer, so the repeated upper layers can be a bounded multiplicative overhead. Korf proved asymptotic time, space and solution-length results for the stated brute-force tree model.^[6]

The boundary matters. On a graph with many paths to the same states, repeated depth-limited tree exploration can revisit combinatorially many paths. A transposition table reduces repetition but spends memory and changes the clean tree analysis. Iterative deepening is therefore a resource trade, not a promise that combines every virtue of BFS and DFS under every topology.

Part threeWhat frontier order cannot repair

It is tempting to treat BFS, DFS and UCS as interchangeable engines whose only difference is speed. The more important failures occur before the frontier is consulted. A search can order paths perfectly and still solve the wrong graph, merge different situations, retain irrelevant histories or assign a convenient number to a prohibition.

Thought experiment one: the endless corridor

At state 0, one action enters a side room containing the goal after two steps. Another action advances to corridor state 1. Every corridor state has a successor with the next integer label. Change only the frontier discipline. BFS completes depth one, then depth two, and reaches the goal. DFS that always chooses “forward” creates 1, 2, 3 and so on without returning. Every state is new, so a visited set does not help.

The causal variable is not graph size alone. It is whether one live branch can remain perpetually preferred. Add a depth limit and DFS eventually backtracks. Use iterative deepening and the shallow goal is found under finite branching. The termination guarantee changed because the resource and selection contract changed.

Thought experiment two: the room that is not one state

A robot enters Room 7 without a keycard, explores its exits and leaves. Later it collects the keycard and returns. If the state key is only “Room 7”, graph search prunes the second visit as a duplicate. Yet the legal successors changed: the locked exit is now available. Change only the state representation from room to (room, has_keycard). The path reappears.

Two situations are the same search state only when every future-relevant consequence is equivalent for the problem being solved. Location can be enough for a static maze. It is not enough when inventory, remaining energy, time window, permissions or commitments change what can happen next. Equality is a modelling claim, not a data-structure detail.

The opposite error matters too. If state identity includes irrelevant history, equivalent situations fail to merge. A route finder that stores the entire travelled path as part of state identity can turn a small cyclic map into a vast tree of path copies. The right abstraction preserves future-relevant distinctions and discards the rest.

Tree search and graph search answer different questions

A tree-search implementation stores paths and may treat two paths ending in the same world state as different live possibilities. That is sometimes intentional. History itself may affect future cost, a resource budget or a path-dependent constraint. More often, repeated paths are accidental copies created by cycles or converging routes. Graph search tries to merge them through a state record.

In a diamond-shaped graph, two parents may reach the same child. Expanding both copies adds no new world state when the child’s future is independent of the route. In a cyclic graph, failing to merge can create an unbounded search tree even though the reachable graph is finite. LaValle notes that permitting repeated states can make computation grow far beyond the graph and can prevent termination.^[1] Duplicate detection is therefore not merely a speed optimisation. It states when two histories are interchangeable.

A useful property test constructs pairs of paths that collide under the proposed state key. For each permitted action, compare successor availability, step cost, goal status and constraint-relevant resources. If one differs, the key merged states that the problem treats differently. If none differs across the tested boundary, merging has earned local evidence, though not a proof for untested transitions. Graph search is correct only relative to a behavioural equivalence relation, not merely a convenient hash function.

Duplicate rules are objective-dependent

BFS on an unweighted graph can usually accept the first generated path to a state because FIFO layering ensures it is a shallowest path. DFS can accept first arrival when the task is merely reachability, but doing so makes no shortest-path claim. UCS cannot freeze first arrival. A state discovered at cost 12 may later be reached at cost 7, so the tentative label and frontier priority must be updated. The artefact uses a best-known-cost map and ignores stale heap entries after a cheaper path is inserted.

These rules reveal why copying one “visited set” pattern across algorithms is dangerous. A boolean answers “have I ever seen this state?” UCS needs “what is the cheapest path seen so far, and has that cost become final?” Search correctness lives in the meaning of the record, not the variable name.

Costs can invalidate the ordering proof

UCS’s label-setting proof depends on non-negative transition costs. A negative edge can make a path cheaper after it has passed through a state with a larger apparent prefix cost. The minimum frontier path is no longer guaranteed to be final. Zero-cost edges do not violate non-negativity, but an infinite family of distinct zero-cost states can prevent progress to a positive-cost goal. A common completeness condition therefore includes finite branching, a finite optimal cost and a positive lower bound on step cost.

Cost must also represent the decision. If a move costs seconds, summing seconds is coherent for a fixed route. If it carries a probability of injury, a regulatory prohibition or a hard battery reserve, one scalar sum may be an unacceptable compression. A forbidden edge should often be removed by the transition model rather than assigned a merely large number. Multi-objective or constrained search requires a richer mechanism.

Negative control: a frontier with no choice

To test whether frontier discipline causes an observed difference, use a graph that removes frontier choice. Let every non-goal state have exactly one successor. The state space is a chain. BFS, DFS and UCS then hold at most one path, expand the same states in the same order and return the same route. The included artefact runs this control and asserts equality across all three traces.

This control can falsify a lazy explanation. If one implementation remains much slower on the chain, the cause is not exploration order. It may be heap overhead, object allocation, logging, hashing or instrumentation. Conversely, if the algorithms diverge only when branching creates competing live paths, the frontier explanation gains causal support.

A second control assigns every edge the same positive cost. BFS and UCS should then agree on optimal action depth and total cost, subject to tie policy. A third deliberately inserts a negative edge and expects UCS to reject the problem. Controls that merely confirm the happy path are weak. Good controls isolate the mechanism and force invalid assumptions to become visible.

Part fourFrom classroom search to an engineered component

Classroom examples usually provide a neat graph, a single goal and one scalar cost. An engineered search component receives none of those for free. It needs a state constructor, a successor contract, an objective, an equality rule, termination limits and operating evidence. The frontier is only one part of that contract, although it is the part that turns the contract into an exploration order.

The minimal graph from Part two asked only whether to count moves or cost. The production-shaped version adds a more important question: which facts must remain in state because they change the legal future? Cell alone is insufficient because arriving at the same door with and without the keycard produces different successor sets. Every transient log line is excessive because most history does not change what can happen next. A useful key might be (cell, has_keycard, gate_snapshot_id).

Suppose every permitted move takes one unit. BFS is the defensible baseline for a fewest-action route. If aisle times vary but remain known and non-negative, UCS matches the stated objective. DFS remains useful for bounded reachability checks, cycle structure or exhaustive diagnostics where discovery order matters. It is a poor default for route quality because successor ordering can change its answer without changing the graph.

This scenario also separates search from execution. The result is a model proposal over a snapshot. Before movement, an authority layer must verify that the route is permitted, the snapshot remains current and the first action is safe. After each action, the system must observe the new world state. A correct path through an obsolete graph is still an incorrect operational instruction. Dynamic replanning, stochastic control and partial observability belong to later mechanisms, not to a hidden extension of this loop.

Measure the invariant, not only elapsed time

A search benchmark should report at least five quantities: whether the returned path is valid, the objective value of that path, the number of expanded states, the peak frontier and elapsed resource use. Wall-clock time alone confounds exploration discipline with runtime, allocator behaviour, hash cost, logging and heap implementation. The negative-control chain deliberately holds exploration constant so those implementation costs can be seen.

Public grid suites from Moving AI provide fixed maps and start-goal scenarios for comparable pathfinding tests.^[7][8] Graph500 uses breadth-first traversal as a systems workload over large synthetic graphs, while the DIMACS implementation challenges include graph and shortest-path families.^[9][10] These sources support different questions. A grid benchmark studies pathfinding behaviour; Graph500 stresses graph-processing systems; DIMACS supports implementation comparison. None validates a warehouse state model or business cost function by itself.

A useful experiment varies one feature at a time. Hold the graph fixed and change frontier discipline. Hold frontier discipline fixed and change edge costs. Hold both fixed and alter the state key. Then inject a cycle, an unreachable goal, a negative edge and a resource cap. Record exact successor order because DFS is especially sensitive to it. This design turns search from a demonstration into a falsifiable component test.

Resource limits create a third outcome

A practical search almost never receives unlimited time and memory. Expansion count, depth, path cost, elapsed time and frontier size may each have a cap. Hitting a cap is not evidence that no route exists. It is a cutoff: the procedure stopped before exhausting the reachable region under its own rules. Conflating cutoff with failure converts a resource decision into a false statement about the world.

The distinction matters most when algorithms are compared. Suppose BFS reaches a memory ceiling after retaining a wide layer, while DFS returns a route inside the same memory budget. The result does not show that DFS is complete or that no shorter route exists. It shows that one method produced a candidate under a particular envelope while another did not finish. Conversely, a UCS timeout does not license the cheapest route currently in the frontier as globally optimal, because a lower-cost unfinished path may still exist.

An engineered result therefore needs a status vocabulary such as SOLVED, EXHAUSTED, CUTOFF and INVALID_MODEL. EXHAUSTED means the frontier became empty under a complete successor model. CUTOFF records the breached limit and preserves the best candidate only as a candidate. INVALID_MODEL covers violated assumptions such as a negative UCS edge or an unhashable state representation. The decision receipt should include the graph version, limit values, expansions completed and frontier summary. Resource exhaustion is an unknown outcome with evidence, not a disguised negative answer.

Executable frontier laboratory

The following Python artefact makes the unification literal. One graph_search loop receives a frontier mode. For comparison, AIMA Python exposes conventional named search implementations; this artefact instead isolates policy behind one interface.^[11] FIFO, LIFO and minimum accumulated cost change what leaves the frontier. The duplicate record changes with the objective: a set for BFS and DFS, and a best-known-cost map for UCS. The code tests goals on removal, rejects negative or non-finite UCS edges and records expansion order and peak frontier.

Assumptions: the graph is finite and explicit; states are hashable; equality preserves every future-relevant fact; successor order is deterministic, and UCS costs are finite and non-negative. The positive case separates fewest actions from least cost. The negative control removes all frontier choice. The failure case proves that an invalid cost condition is rejected rather than silently producing a claim.

from __future__ import annotations

from collections import deque
from dataclasses import dataclass
from heapq import heappop, heappush
from itertools import count
from math import isfinite
from typing import Hashable, Iterable, Literal, Mapping, Sequence

Mode = Literal["bfs", "dfs", "ucs"]
State = Hashable
Edge = tuple[State, float]
Graph = Mapping[State, Sequence[Edge]]


@dataclass(frozen=True)
class Node:
    state: State
    parent: "Node | None"
    step_cost: float
    path_cost: float
    depth: int

    def path(self) -> list[State]:
        out: list[State] = []
        node: Node | None = self
        while node is not None:
            out.append(node.state)
            node = node.parent
        return list(reversed(out))


@dataclass(frozen=True)
class SearchResult:
    mode: Mode
    path: list[State]
    cost: float
    expanded_order: list[State]
    peak_frontier: int


class Frontier:
    """One interface, three disciplines: FIFO, LIFO, or minimum path cost."""

    def __init__(self, mode: Mode) -> None:
        self.mode = mode
        self._queue: deque[Node] = deque()
        self._heap: list[tuple[float, int, Node]] = []
        self._tie = count()

    def push(self, node: Node) -> None:
        if self.mode == "ucs":
            heappush(self._heap, (node.path_cost, next(self._tie), node))
        else:
            self._queue.append(node)

    def pop(self) -> Node:
        if self.mode == "bfs":
            return self._queue.popleft()
        if self.mode == "dfs":
            return self._queue.pop()
        return heappop(self._heap)[2]

    def __bool__(self) -> bool:
        return bool(self._heap if self.mode == "ucs" else self._queue)

    def __len__(self) -> int:
        return len(self._heap if self.mode == "ucs" else self._queue)


def successors(graph: Graph, state: State) -> Iterable[Edge]:
    return graph.get(state, ())


def graph_search(
    graph: Graph,
    start: State,
    goals: set[State],
    mode: Mode,
) -> SearchResult | None:
    """
    Search a finite explicit graph.

    Assumptions:
      * states are hashable and equality captures every future-relevant fact;
      * UCS edge costs are finite and non-negative;
      * successor order is deterministic, so DFS results are reproducible.
    """
    if mode == "ucs":
        for source, edges in graph.items():
            for target, cost in edges:
                if not isfinite(cost):
                    raise ValueError(
                        f"UCS requires finite costs: "
                        f"{source!r}->{target!r} has {cost}"
                    )
                if cost < 0:
                    raise ValueError(
                        f"UCS requires non-negative costs: "
                        f"{source!r}->{target!r} has {cost}"
                    )

    root = Node(start, None, 0.0, 0.0, 0)
    frontier = Frontier(mode)
    frontier.push(root)
    peak_frontier = 1
    expanded_order: list[State] = []

    # BFS and DFS accept the first generated path to a state. UCS must retain
    # the cheapest generated path and may insert a better replacement.
    seen: set[State] = {start}
    best_g: dict[State, float] = {start: 0.0}
    expanded: set[State] = set()

    while frontier:
        node = frontier.pop()

        if mode == "ucs" and node.path_cost != best_g.get(node.state):
            continue  # stale heap entry after a cheaper path was found
        if node.state in expanded:
            continue

        # Testing on removal is essential for UCS: only then is this cost final.
        if node.state in goals:
            return SearchResult(
                mode=mode,
                path=node.path(),
                cost=node.path_cost,
                expanded_order=expanded_order,
                peak_frontier=peak_frontier,
            )

        expanded.add(node.state)
        expanded_order.append(node.state)

        children = list(successors(graph, node.state))
        # Reversing before stack insertion makes DFS visit the first listed
        # successor first, matching the left-to-right diagrams in the article.
        if mode == "dfs":
            children.reverse()

        for child_state, step_cost in children:
            child = Node(
                state=child_state,
                parent=node,
                step_cost=step_cost,
                path_cost=node.path_cost + step_cost,
                depth=node.depth + 1,
            )

            if mode == "ucs":
                if child.path_cost < best_g.get(child_state, float("inf")):
                    best_g[child_state] = child.path_cost
                    frontier.push(child)
            elif child_state not in seen:
                seen.add(child_state)
                frontier.push(child)

        peak_frontier = max(peak_frontier, len(frontier))

    return None


def format_result(result: SearchResult | None) -> str:
    if result is None:
        return "no solution"
    return (
        f"{result.mode.upper():3} path={result.path} cost={result.cost:g} "
        f"expanded={result.expanded_order} "
        f"peak_frontier={result.peak_frontier}"
    )

def demo() -> None:
    # Positive case: equal hop count and monetary cost are different objectives.
    weighted_graph: Graph = {
        "S": (("A", 1), ("B", 1)),
        "A": (("C", 1),),
        "C": (("G", 1),),
        "B": (("G", 9),),
        "G": (),
    }

    print("Weighted choice")
    results: dict[Mode, SearchResult] = {}
    for mode in ("bfs", "dfs", "ucs"):
        result = graph_search(weighted_graph, "S", {"G"}, mode)
        assert result is not None
        results[mode] = result
        print(format_result(result))

    assert results["bfs"].path == ["S", "B", "G"]
    assert results["bfs"].cost == 10
    assert results["dfs"].path == ["S", "A", "C", "G"]
    assert results["dfs"].cost == 3
    assert results["ucs"].path == ["S", "A", "C", "G"]
    assert results["ucs"].cost == 3

    # Negative control: on a chain, frontier discipline has no choice to make.
    chain: Graph = {
        "S": (("A", 2),),
        "A": (("B", 2),),
        "B": (("G", 2),),
        "G": (),
    }

    print("\nNegative control: a single-path chain")
    chain_paths = []
    for mode in ("bfs", "dfs", "ucs"):
        result = graph_search(chain, "S", {"G"}, mode)
        assert result is not None
        chain_paths.append((result.path, result.cost, result.expanded_order))
        print(format_result(result))

    assert chain_paths[0] == chain_paths[1] == chain_paths[2]

    # Failure guard: Dijkstra/UCS invariants do not survive negative edges.
    negative_graph: Graph = {"S": (("G", -1),), "G": ()}
    try:
        graph_search(negative_graph, "S", {"G"}, "ucs")
    except ValueError as exc:
        print(f"\nExpected rejection: {exc}")
    else:
        raise AssertionError("negative edge should have been rejected")

    non_finite_graph: Graph = {"S": (("G", float("inf")),), "G": ()}
    try:
        graph_search(non_finite_graph, "S", {"G"}, "ucs")
    except ValueError as exc:
        print(f"Expected rejection: {exc}")
    else:
        raise AssertionError("non-finite edge should have been rejected")


if __name__ == "__main__":
    demo()

Weighted choice
BFS path=['S', 'B', 'G'] cost=10 expanded=['S', 'A', 'B', 'C'] peak_frontier=2
DFS path=['S', 'A', 'C', 'G'] cost=3 expanded=['S', 'A', 'C'] peak_frontier=2
UCS path=['S', 'A', 'C', 'G'] cost=3 expanded=['S', 'A', 'B', 'C'] peak_frontier=2

Negative control: a single-path chain
BFS path=['S', 'A', 'B', 'G'] cost=6 expanded=['S', 'A', 'B'] peak_frontier=1
DFS path=['S', 'A', 'B', 'G'] cost=6 expanded=['S', 'A', 'B'] peak_frontier=1
UCS path=['S', 'A', 'B', 'G'] cost=6 expanded=['S', 'A', 'B'] peak_frontier=1

Expected rejection: UCS requires non-negative costs: 'S'->'G' has -1
Expected rejection: UCS requires finite costs: 'S'->'G' has inf

The trace contains a useful surprise. UCS expands B before C because both A and B first enter with path cost 1, and the tie counter preserves insertion order. It still returns the cheaper three-cost route. Tie policy can change work and which equal-quality solution appears, but it cannot violate the primary ordering if implemented correctly. Tie-breaking therefore belongs in the frontier contract and reproducibility record.

The frontier contract

The paper’s practical contribution is a compact architecture decision record for uninformed graph search. Complete it before choosing a container. Each field states an assumption that can be tested, reviewed or invalidated.

Used properly, this instrument changes code review. Reviewers no longer ask only whether a deque or heap was used. They ask whether the container preserves the stated invariant, whether equality is behaviourally sound and whether the returned path remains authorised in the current world. The algorithm name becomes the summary of a tested contract, not a substitute for one.

Compact glossary

State: information required to determine relevant future successors, costs and goal status. Path: a sequence from the start to a reached state. Frontier: reached paths eligible for expansion. Expansion: applying the successor function to the selected state. Duplicate detection: deciding whether a newly reached state is equivalent to, worse than or worth replacing a prior record. Complete: guaranteed to find a solution under stated conditions when one exists. Optimal: guaranteed to return a solution minimising the stated objective under stated conditions.

Choose the invariant before the queue

The warehouse puzzle did not contain three algorithms waiting to be memorised. It contained a set of unfinished paths and a decision about which one deserved attention next. FIFO made depth the governing quantity. LIFO made recent extension the governing commitment. A minimum heap made accumulated cost the governing quantity. The rest of each guarantee followed from that ordering and its assumptions.

The durable design decision is to choose the invariant before choosing the data structure. State the objective, define state identity, specify duplicate handling, fix the goal-test point and record the condition that withdraws the claim. Then run the weighted example, the single-path negative control and the failure injections. Only after those tests earn the label should the component be called BFS, DFS or UCS.

This framing also marks the mechanism’s boundary. Search does not repair a false model of the world, authorise an action, observe its outcome or make a changing environment static. It explores the possibilities the representation permits. The next research and architecture step is clear: add guidance only after the unguided frontier is understood. A heuristic can change which promising path becomes visible sooner, but it cannot rescue an objective, state key or cost model that was wrong before guidance began.