The route that changed when nothing moved

A maintenance robot must reach a coolant isolator inside a warehouse. The map, start and goal remain fixed. Only the rule for choosing the next unfinished route changes.

One route reaches the isolator through two powered doors. It has only two actions, but each door takes seven minutes to cycle. A second route crosses four open aisles at one minute each. A third branch begins with an inviting open aisle, then runs deep into an inspection gallery before returning to the useful part of the map.

A breadth-first search returns the two-door route because two actions are fewer than four. A uniform-cost search returns the four-aisle route because four minutes are cheaper than fourteen. A depth-first search follows whichever successor was placed last on its stack, so it may inspect the gallery before either useful route. The world did not change. The meaning of “next” changed.

This is easy to describe as three data structures: queue, priority queue and stack. That account is memorable, but incomplete. Put the same records into those containers while testing the goal at the wrong time, collapsing distinct states, or refusing to replace an expensive pending path with a cheaper one. The familiar guarantee disappears even though the container still has the expected name.

The frontier is the algorithm’s moving present

A discrete search problem begins with less machinery than its names suggest. There is a set of states, an initial state, a way to generate legal successors, a goal predicate and, when routes differ in value, a rule for extending path cost. The complete transition graph need not exist in memory. Search reveals a reachable subgraph only where expansion demands it.

LaValle’s general forward-search template divides states into unvisited, alive and dead. Alive states have been encountered but may still contribute new successors. They inhabit a priority queue whose sorting function distinguishes one method from another.⁶ His later unified view makes the common structure explicit: initialise a partial search graph, select a vertex, apply an action and conditionally insert the resulting state and edge.⁷

The word frontier is useful because a queue is only one implementation. Conceptually, the frontier is the set of path records that have been generated but not yet expanded. It separates an explored interior from an ungenerated exterior. Every record is a claim: “This path could still lead to a result that matters.” Selection grants one such claim the next unit of computation.

A node is a path record, not a state

Suppose two routes both reach aisle 4. The world state may be identical, but the path records can differ in parent, action history, depth and accumulated cost. Breadth-first search can usually discard a later route to the same state because the first discovery is already shallowest when every action has equal cost. Uniform-cost search cannot apply that rule blindly. A later route may be cheaper and must replace or supersede the earlier record.

A useful minimal record is:

Here g is the accumulated path cost. Parent pointers recover the chosen route after the goal is accepted. The state key controls duplicate detection. The remaining fields support ordering, comparison and explanation.

The problem contract precedes the frontier contract

A useful formal boundary is a problem tuple P = (S, s₀, A, T, G, c). S is the state space; s₀ the initial state; A(s) the actions legal in state s; T(s,a) the successor relation; G(s) the goal predicate; and c(s,a,s′) the incremental path cost. Search does not repair ambiguity in these elements. It operationalises them.

This distinction matters because an algorithm can be internally correct and externally useless. If G recognises “a document exists” when the real requirement is “an approved document exists”, the search may optimally reach the wrong terminal condition. If T omits a legal recovery action, no frontier discipline can discover it. If c encodes elapsed time while the decision is governed by irreversible risk, UCS may faithfully optimise the wrong quantity.

The problem contract therefore answers what counts as a possible world and a successful route. The frontier contract answers how pending routes compete for computation. The first is semantic; the second is procedural. Combining them too early encourages a familiar mistake: treating the path returned by a correct algorithm as evidence that the problem was correctly specified.

Tree search and graph search are different evidence policies

Tree search keeps every generated path as a distinct possibility. It is appropriate when the underlying state space is genuinely a tree or when different histories must remain distinct. On a graph, however, cycles and converging paths can generate the same state repeatedly. A tree-search DFS may follow a cycle indefinitely. A tree-search UCS may create an unbounded number of increasingly redundant records.

Graph search adds a reached or explored structure. That structure is not merely a speed cache. It asserts that a stored representative is sufficient for all future reasoning about a state. AIMA’s reference code makes this contrast visible: its tree-search version drops explored-state and frontier-replacement bookkeeping and warns that cyclic graphs may not terminate, while graph search retains those controls.⁸

Seen this way, duplicate detection is a form of proof compression. Instead of preserving every history, the algorithm keeps one record or a small nondominated set and claims that discarded histories cannot improve the result. The memory saving is earned only when that claim is true.

Recent learned planning makes the risk concrete. Distincter uses a graph representation to guide search and identify symmetries, then applies action or state pruning inside Fast Downward. It improved coverage on the 2023 planning competition’s learning track, but the boundary is as important as the gain: ordinary graph networks can fail to distinguish non-isomorphic states, state pruning can threaten completeness, and the extra symmetry test can cost more than it saves. Learning can propose equivalence. The search engine still needs a defensible rule for when equivalence is safe to act on.

The loop beneath the names

The shared loop is compact. Put the initial path record on the frontier. Remove the eligible record. If it certifies a goal, return its parent chain. Otherwise, generate successors, create child records, compare each child with the current representative for its state, and keep only records that remain entitled to compete. Repeat until a result is certified, the frontier empties, or a resource boundary stops the run.

Search is not “trying everything”. It is a disciplined schedule for postponing most possibilities while preserving enough of them to support a chosen guarantee.

The strongest competing explanation

The simplest rival thesis says that the algorithm is exhausted by its container: queue means BFS, stack means DFS, heap means UCS. That explanation is attractive because it predicts the expansion order in clean finite trees. It is also the right teaching compression for a first implementation.

It becomes insufficient when a guarantee depends on information outside the container. Hold the min-heap fixed and test a UCS goal on generation rather than removal: optimality can fail. Hold the FIFO queue fixed and key states only by location rather than location plus carried key: completeness can fail. Hold the stack fixed and remove cycle detection: termination can fail. These interventions change the result without changing the named container. The broader frontier contract earns its place by explaining those controlled failures.

flowchart TD
  A["The route that changed when<br/>nothing moved"] --> B["The frontier is the<br/>algorithm’s moving present"]
  B --> C["One engine, three eligibility<br/>disciplines"]
  C --> D["The guarantee lives in four<br/>places at once"]
  D -. "re-test" .-> A
  classDef first fill:#0a1424,stroke:#D95545,stroke-width:2px,color:#e6f3ff
  classDef step fill:#0a1424,stroke:#3f7da0,stroke-width:1px,color:#e6f3ff
  class A first
  class B,C,D step

One engine, three eligibility disciplines

Let F be the frontier and let K(n) be the eligibility key for node n. A generic best-first view removes a node with the smallest key. Breadth-first and uniform-cost search fit directly. Depth-first search can be expressed by favouring greater depth and newer insertion order, or implemented more naturally as a LIFO stack.

A tie-breaker matters because keys are often equal. Python’s heapq documentation recommends a monotonically increasing entry count to preserve insertion order and avoid comparing non-comparable task objects when priorities tie.¹¹ This is an implementation detail with visible behavioural consequences. Change the tie-break and DFS may enter a different branch; UCS may return a different member of several equally cheap solutions.

Breadth-first search: pay by transition count

Breadth-first search expands shallow nodes before deeper ones. Edward Moore’s maze work and C. Y. Lee’s path-connection algorithm are early landmarks in wavefront search for shortest unweighted paths and wiring routes.^{1, 2} In a graph with unit action costs, depth equals path cost. A FIFO queue therefore implements a special case of uniform-cost ordering without a heap.

The guarantee is precise: when every action has the same cost and the state key is sound, the first discovered path to a state is shallowest. With finite branching and a reachable shallow goal, breadth-first search is complete. The price is the wavefront. A branching factor of three produces 3, 9, 27 and 81 nodes at successive depths. Most memory is spent on paths that have been generated but not yet expanded.

Why the shallowest guarantee follows

The proof is an ordering invariant. Initially, the frontier contains only depth zero. Assume every record removed so far has depth at most k, and the queue is processing depth k. Every child it appends has depth k+1 and is placed behind all already-pending records of depth k. Therefore no depth k+1 record can be removed while a depth k record remains. By induction, removal depth never decreases.

If all actions cost the same positive amount, lower depth is lower total cost. If costs differ, the induction still proves nondecreasing depth, but depth no longer proves lower cost. This is why saying that BFS finds “the shortest path” is incomplete unless shortest means fewest edges or every edge has equal cost.

Depth-first search: pay with commitment

Depth-first search expands a child before the current node’s unexpanded siblings. It can be implemented recursively or with a stack. NIST’s definition captures the structural rule: outgoing edges of a vertex are considered before siblings, so the extremes are searched first.⁹ Tarjan showed the deeper algorithmic value of this traversal order by deriving linear graph algorithms for strongly connected and biconnected components.⁴

For path finding, DFS trades breadth of coverage for a small active working set. It remembers a branch, enough siblings to backtrack, and a visited structure when cycles matter. It can reach a deep solution without storing every shallower alternative. Yet successor order becomes destiny. In an infinite branch, an unrestricted DFS may never return to a sibling that contains a shallow goal. On cyclic graphs, tree-search DFS can loop forever.

“DFS uses linear memory” also needs a boundary. A recursive traversal of a tree stores the active path and local iteration state, which scales with depth. An explicit stack may additionally hold unexpanded siblings along that path, often described as proportional to branching factor times maximum depth. A graph-search implementation also stores visited states, which can approach the reachable graph size. DFS reduces the frontier wavefront; it does not make graph memory disappear.

Its order sensitivity can be productive. Backtracking solvers deliberately order variables and values so that contradictions appear early. Tarjan’s algorithms exploit discovery and finishing structure, not path optimality.⁴ The right conclusion is not that DFS is inferior, but that depth-first ordering is evidence about structural exploration, not evidence of a cheapest route.

Iterative deepening repairs part of this boundary by running depth-limited DFS with increasing limits. Korf established its strong time and space properties for exponential tree search.⁵ The repeated upper levels look wasteful, but the deepest level dominates when branching is exponential. Iterative deepening is therefore not a compromise invented by averaging BFS and DFS. It is a deliberate schedule that repeatedly changes which depth is eligible.

Uniform-cost search: pay by the path-cost algebra

Uniform-cost search removes the pending node with the smallest accumulated cost g. In finite graphs with nonnegative edge weights, this is the goal-directed form of Dijkstra’s label-setting method. Dijkstra’s original note formalised shortest-path computation, and NIST states the key precondition directly: all weights must be nonnegative.^{3, 10}

The algorithm keeps a best known cost for each state. If a newly generated path is cheaper, it becomes the representative. A practical heap implementation can push the new record and leave the older one in place, then discard the stale record when it is popped. Python’s heap documentation describes this lazy-removal pattern for changed priorities.¹¹

Why the cheapest removed record can be settled

Let n be the valid frontier record with minimum accumulated cost. Suppose there were a cheaper undiscovered route to the same state. Follow that hypothetical route from the start until it first crosses from an expanded state to an unexpanded state. The prefix at that crossing must already have generated a frontier record. With nonnegative edge costs, that prefix cannot cost more than the full hypothetical route, so it would be cheaper than n. This contradicts the choice of n as the cheapest pending record.

The argument explains three implementation rules at once. The frontier must be ordered by accumulated cost. Improved records must replace or supersede worse ones. A state is settled on removal of the cheapest valid record, not on first generation. Dijkstra’s method “flows only once” through settled finite states because nonnegative extension preserves this monotone boundary.⁷

For a single target, UCS may stop when a valid goal record is removed. For all-target shortest paths, it continues until the frontier is empty or all required states are settled. These are different stopping contracts over the same cost-ordered mechanism.

Uniform-cost search does not make cost objective. It makes the declared cost additive and operational. Minutes, money and risk points are not interchangeable merely because each is numeric. If the decision is lexicographic, constrained or path-dependent, the state or cost algebra must represent that structure before the frontier can order it honestly.

Additivity can sometimes be recovered by expanding the state. A route with a maximum of two privileged actions can include “privileged actions used” in the state, making the constraint explicit. A turn penalty can be represented by including the previous direction. This increases the state space because history that once looked irrelevant now changes future cost. The modelling trade is exact: either preserve relevant history in the state or accept that two apparently identical arrivals are not safely mergeable.

Asymptotic labels should also be read through assumptions. BFS is commonly summarised as exponential in shallowest solution depth for a tree with branching factor b. DFS can be exponential in maximum explored depth while keeping a much smaller frontier. UCS expands every state whose best cost lies below the optimal solution cost, plus some ties; its work therefore depends on the density of low-cost states, not merely on edge count. A zero-cost plateau can be more damaging than a visually deep graph.

The guarantee lives in four places at once

“Use a queue for BFS and a heap for UCS” identifies an important mechanism. It does not yet prove that the returned path has the intended property. Four additional choices determine whether the algorithm’s local ordering produces a global guarantee: state identity, dominance, goal-test timing and cost assumptions.

State identity decides which futures are interchangeable

A duplicate test assumes that two records with the same state key have the same relevant future. This is a stronger claim than visual similarity. A robot at aisle 4 while carrying a service key is not interchangeable with the robot at aisle 4 without it, because available actions differ. A recovery workflow at “database restarted” before verification is not the same state as “database restarted and readback passed”.

Dominance decides which path records remain alive

A dominance rule answers: when two records reach the same state, which can be discarded without losing the target guarantee? For BFS with unit costs, lower depth dominates higher depth. For UCS, lower accumulated cost dominates higher cost. For ordinary reachability DFS, first seen may be sufficient on a static graph, but it does not confer path optimality.

Dominance can be partial. Suppose paths track both money and elapsed time, and neither can be collapsed into a trusted scalar. A path costing £4 and taking ten minutes does not dominate one costing £6 and taking four minutes. The frontier may need a Pareto set, a constraint or a lexicographic rule. A scalar priority is a modelling decision before it is an implementation convenience.

Replacement policy and heap policy are separate. A min-heap answers which pending record has the smallest key. It does not know whether two records represent the same state, whether one dominates the other, or whether a popped record has become stale. Those judgements live in the reached map. This is why “use a priority queue” is necessary but not sufficient advice for UCS.

Tie handling deserves the same explicitness. Equal-cost routes can differ in length, reversibility or explanatory quality. If those distinctions matter, they belong in a secondary key or in the objective itself. If they do not, a deterministic insertion counter is still useful for repeatability. It does not improve optimality, but it makes traces, tests and incident reconstruction stable.

Goal timing distinguishes notice from certification

A goal can be tested when it is generated or when it is removed from the frontier. In BFS with uniform action costs, generation-time testing can safely return the shallowest goal because all parents at the previous depth are being processed before deeper nodes. In UCS, generation only proves that one route to the goal exists. A cheaper unfinished route may still be pending.

Cost assumptions make the settled frontier monotone

Dijkstra’s logic relies on nonnegative edges. Once the cheapest pending record is removed, extending any other pending path cannot produce a cheaper route back to that settled state. A negative edge destroys that monotonicity. The future can undercut a record that looked final.

Zero-cost edges do not invalidate finite-graph optimality, but they complicate completeness in unbounded state spaces. If infinitely many distinct states are reachable without increasing path cost, the algorithm can spend forever below the goal’s cost. A positive lower bound on step cost, finite reachable sublevel sets, or another progress condition is needed for a useful termination guarantee.

Negative edges expose the exact causal break. Consider S → G with cost 2, S → A with cost 5, and A → G with cost -10. A goal-directed UCS removes G(2) before A(5) and stops, although the later route costs -5. Bellman’s routing formulation belongs to a different relaxation family that can propagate improvements through negative edges when no reachable negative cycle makes the optimum undefined.¹³

Write the frontier contract before choosing the container

In production-shaped problems, search rarely fails because an engineer forgot that BFS uses a queue. It fails because the state left out a permission, the cost mixed incomparable objectives, the world changed during exploration, or a result was treated as authorised action. The remedy is to define a search contract before implementation.

The contract has seven fields: state identity, successor semantics, goal certification, path-cost algebra, eligibility key, dominance and resource boundary. A container then becomes a consequence of the contract. A deque suits FIFO breadth-first traversal; Python documents deque as supporting fast appends and pops from either side.¹² A min-heap suits cost ordering because its smallest element is always at the root.¹¹

Make cutoff, failure and success different outputs

A bounded search can end in at least three states. Success means a result met its certification rule. Failure means the frontier was exhausted under the declared model, so no reachable goal exists within that model. Cutoff means exploration stopped because a depth, cost, memory, expansion or wall-clock boundary was reached. Treating cutoff as failure converts a resource shortage into a false claim about the state space.

The distinction becomes operational in services. A search response should include the stop reason, expansion count, peak frontier size, best pending key, model version and a compact trace of dominance decisions. For UCS, record how many stale entries were skipped and how often a state was improved. For DFS, record maximum depth and cycle-pruning events. For BFS, record the deepest fully completed layer. These signals explain what the algorithm actually established.

Test invariants, not only example routes

A strong test suite contains metamorphic properties. Multiplying every positive edge cost by the same constant must not change a UCS route, though its reported cost scales. Reordering successors may change DFS but should not change BFS depth optimality or UCS cost optimality. Replacing all edge costs with one should make UCS and BFS agree on optimal depth, subject to tie-breaking. Adding a dominated expensive route to an existing state should not change the answer. Introducing a negative edge should trigger rejection or a different algorithm, not silent reuse of a Dijkstra-style guarantee.

Representation tests are equally important. Split one state into two copies with identical successors and costs: the result should remain equivalent. Merge two states whose available actions differ: a sound test should expose the changed reachability. These checks target the contract’s causal assumptions rather than memorising one golden traversal order.

The frontier-contract audit

The audit below is deliberately mechanism-first. It does not begin with “BFS or DFS?” It begins with the facts that make one of those labels meaningful.

Executable artefact: one template, three disciplines

The Python template below exposes the choices that textbook wrappers often hide. A discipline supplies the priority key and the value used for dominance. The loop tests goals only after removal, rejects negative UCS edges, stores parent records and tolerates stale heap entries. The positive case shows BFS choosing fewer steps while UCS chooses lower cost. The negative case verifies that UCS refuses an invalid cost model.

from __future__ import annotations

from dataclasses import dataclass
from heapq import heappop, heappush
from itertools import count
from math import inf
from typing import Callable, Hashable, Iterable, Literal, TypeVar

State = TypeVar("State", bound=Hashable)
Mode = Literal["bfs", "dfs", "ucs"]


@dataclass(frozen=True)
class Edge:
    target: State
    cost: float = 1.0
    action: str = "move"


@dataclass(frozen=True)
class Node:
    state: State
    parent: "Node | None"
    action: str | None
    depth: int
    g: float


def priority(mode: Mode, node: Node, serial: int) -> tuple[float, int]:
    if mode == "bfs":
        return (node.depth, serial)          # shallowest, oldest first
    if mode == "dfs":
        return (-node.depth, -serial)        # deepest, newest first
    return (node.g, serial)                  # cheapest, oldest first


def record_value(mode: Mode, node: Node) -> float:
    return node.g if mode == "ucs" else node.depth


def is_better(mode: Mode, new: float, old: float) -> bool:
    if mode == "ucs":
        return new < old                    # reopen on cheaper path
    return False                             # BFS/DFS keep first discovery


def reconstruct(node: Node) -> tuple[list[State], list[str], float]:
    states: list[State] = []
    actions: list[str] = []
    cursor: Node | None = node
    while cursor is not None:
        states.append(cursor.state)
        if cursor.action is not None:
            actions.append(cursor.action)
        cursor = cursor.parent
    return states[::-1], actions[::-1], node.g


def search(
    start: State,
    is_goal: Callable[[State], bool],
    expand: Callable[[State], Iterable[Edge]],
    mode: Mode,
    *,
    max_expansions: int = 100_000,
) -> tuple[list[State], list[str], float] | None:
    serials = count()
    root = Node(start, None, None, 0, 0.0)
    frontier: list[tuple[float, int, Node]] = []
    first_serial = next(serials)
    heappush(frontier, (*priority(mode, root, first_serial), root))

    best: dict[State, float] = {start: record_value(mode, root)}
    expansions = 0

    while frontier:
        _, _, node = heappop(frontier)
        current = record_value(mode, node)

        # Lazy deletion: ignore a path superseded after it entered the heap.
        if current != best.get(node.state):
            continue

        # Pop-time testing is safe for all three modes used here.
        if is_goal(node.state):
            return reconstruct(node)

        expansions += 1
        if expansions > max_expansions:
            raise RuntimeError("search cutoff: expansion budget exhausted")

        for edge in expand(node.state):
            if mode == "ucs" and edge.cost < 0:
                raise ValueError("UCS requires nonnegative edge costs")

            child = Node(
                state=edge.target,
                parent=node,
                action=edge.action,
                depth=node.depth + 1,
                g=node.g + edge.cost,
            )
            value = record_value(mode, child)
            old = best.get(child.state, inf)

            if child.state not in best or is_better(mode, value, old):
                best[child.state] = value
                serial = next(serials)
                heappush(frontier, (*priority(mode, child, serial), child))

    return None


GRAPH = {
    "S": [Edge("A", 6, "powered door 1"), Edge("B", 1, "aisle 1")],
    "A": [Edge("G", 6, "powered door 2")],
    "B": [Edge("C", 1, "aisle 2")],
    "C": [Edge("G", 1, "aisle 3")],
    "G": [],
}


def expand(state: str) -> Iterable[Edge]:
    return GRAPH[state]


bfs = search("S", lambda s: s == "G", expand, "bfs")
ucs = search("S", lambda s: s == "G", expand, "ucs")

assert bfs == (["S", "A", "G"], ["powered door 1", "powered door 2"], 12.0)
assert ucs == (["S", "B", "C", "G"], ["aisle 1", "aisle 2", "aisle 3"], 3.0)

BAD = {"S": [Edge("G", 10), Edge("A", 1)], "A": [Edge("G", -5)], "G": []}
try:
    search("S", lambda s: s == "G", lambda s: BAD[s], "ucs")
except ValueError as exc:
    assert "nonnegative" in str(exc)
else:
    raise AssertionError("negative UCS edge was not rejected")

print("positive:", bfs, ucs)
print("negative: invalid UCS cost model rejected")

Expected output: BFS returns the two-action path with cost 12; UCS returns the three-action path with cost 3; the negative-edge graph is rejected before it can silently produce an invalid guarantee.