Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Classical Planning and Optimal Control › State-Space Search

Michael BrenndoerferJune 10, 20268 min read

World Models HandbookAll chapters

Part 2 of 12Inference, Decisions, and Control

Chapter 10Classical Planning and Optimal Control › State-Space Search

Reading section 3 of 10 · State-Space Search · 8 minSection 3 of 10 · 8 min

Section 3 of 10 · 8 min read

Classical Planning and Optimal Control › State-Space SearchOne section · Sections in this chapter3 / 10 ↓

Sections in this chapter10

Reading tools Definitions & inline links

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

When the world is deterministic and fully observable and the reachable state-action space is represented as a discrete graph, planning can be posed as graph search. States become nodes, actions become edges, and action costs become edge weights. The planner's job is to find a minimum-cost path from the current state to a goal state.

This is a transparent relationship between model and decision: the model is the graph itself, and a rollout is a walk along edges. There is no expectation to average over, no discounting to tune, and no value function to estimate. The planning problem is combinatorial: which of the potentially exponentially many simple paths from start to goal is cheapest?

This abstraction covers route planning, puzzles, symbolic task planning, and motion planning on discretized configuration spaces. Other tasks can be approximated as search when a finite state representation and known transitions are available. Exact search is then a useful baseline when the graph size, costs, and query structure make it tractable.

Dijkstra's algorithm and uniform-cost searchLink Copied

If all we know is the cost of each action, the right baseline is Dijkstra's algorithm. It maintains a priority queue of frontier states ordered by the cheapest known cost to reach them, and repeatedly expands the cheapest frontier state. When a state is expanded, we can be certain that no cheaper route to it exists, because any other route would have to pass through the frontier, and everything on the frontier is already at least as expensive. When the goal is expanded, the path is therefore guaranteed optimal, provided all costs are nonnegative.

The price is that Dijkstra is uninformed about where the goal lies. On the uniform grid used below, its shortest-distance sublevel set grows like a blob around the start until it reaches the goal. On an irregular weighted graph that set need not resemble a disk, and the same work may be reusable for other queries.

A* and the value of a heuristicLink Copied

A* fixes this by adding heuristic knowledge. Each frontier state is ranked not by cost-so-far $g(s)$ alone, but by

f(s) = g(s) + h(s),

where:

$g(s)$ : the cheapest known cost to reach $s$ from the start, accumulated along the best path found so far
$h(s)$ : an estimate of the remaining cost from $s$ to the goal
$f(s)$ : the estimated total cost of a solution path passing through $s$ , the priority used to rank frontier states

If $h$ were the true remaining cost, A* would avoid nodes that cannot belong to an optimal solution, although ties among equally optimal alternatives can still cause extra expansions. In practice $h$ is a cheap lower bound, such as straight-line distance for a robot or Manhattan distance on a grid. These estimates ignore walls, detours, and dynamics, which makes them optimistic.

Admissible and consistent heuristics

A heuristic is admissible if it never overestimates the true remaining cost: $h(s) \le h^*(s)$ for every state $s$ . It is consistent (or monotone) if $h(s) \le c(s, s') + h(s')$ for every edge. Admissibility is enough for A* tree search, while graph-search implementations with a permanent closed set require consistency or must reopen nodes when a cheaper path appears. Manhattan distance on this unit-step grid is both admissible and consistent.

Why does optimism translate into optimality? Let $C^*$ be the optimal solution cost. Before the optimal goal is popped, at least one frontier entry $n$ on an optimal path has $g(n)=g^*(n)$ ; admissibility then gives $f(n)=g^*(n)+h(n)\le C^*$ . A suboptimal goal has $h=0$ and therefore $f=C>C^*$ . A* cannot pop that goal while the optimal-prefix entry remains. For graph search, consistency or node reopening preserves this invariant when paths merge.

The heuristic is encoded task knowledge that accelerates planning. It approximates remaining cost without simulating the full dynamics. Manhattan distance knows nothing about the walls in our grid, yet it reduces search effort because cost tends to grow with distance. The same pattern, an exact method guided by an approximation of cost-to-go, reappears in learned latent-space planning.

Let's build a small grid world with two walls, each with a gap, and compare A* against Dijkstra.

In[5]:

Code

from heapq import heappop, heappush

import numpy as np

grid = np.zeros((8, 12), dtype=int)
grid[0:6, 4] = 1  # first wall, gap along the bottom two rows
grid[2:, 8] = 1  # second wall, gap along the top two rows
start, goal = (6, 0), (1, 11)


def astar(grid, start, goal, heuristic):
    """4-connected grid search. heuristic=None reduces A* to Dijkstra."""
    rows, cols = grid.shape
    h = heuristic if heuristic is not None else (lambda s: 0)
    frontier = [(h(start), 0, start)]
    came_from = {start: None}
    cost_so_far = {start: 0}
    expanded = set()
    while frontier:
        _, g, current = heappop(frontier)
        if current == goal:
            break
        if current in expanded:
            continue
        expanded.add(current)
        for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            r, c = current[0] + dr, current[1] + dc
            if 0 <= r < rows and 0 <= c < cols and grid[r, c] == 0:
                nxt = (r, c)
                new_cost = g + 1
                if nxt not in cost_so_far or new_cost < cost_so_far[nxt]:
                    cost_so_far[nxt] = new_cost
                    came_from[nxt] = current
                    heappush(frontier, (new_cost + h(nxt), new_cost, nxt))
    path, node = [], goal
    while node is not None:
        path.append(node)
        node = came_from[node]
    return path[::-1], expanded

The key data structures are the priority queue over frontier states and the came_from map, which lets us reconstruct the optimal path once the goal is popped. States land in expanded only after being popped with their best cost, so the set records where the search spent its effort. Passing heuristic=None reduces A* to Dijkstra with no other change, because a heuristic of zero is the uninformed special case. This keeps the encoded heuristic as the only difference in the comparison.

Now run both variants and compare how much work each does.

In[6]:

Code

manhattan = lambda s: abs(s[0] - goal[0]) + abs(s[1] - goal[1])
path_a, expanded_a = astar(grid, start, goal, manhattan)
path_d, expanded_d = astar(grid, start, goal, None)

Out[7]:

Console

A*       : 16 steps, 46 states expanded
Dijkstra : 16 steps, 65 states expanded
Heuristic saved 19 expansions for the same optimal path

Both searches find a path of identical length because Manhattan distance is admissible and consistent on this grid. Excluding the goal pop, A* expands substantially fewer states than Dijkstra for the same optimal path, as the printed counts above show. In problems where expanding a state requires an expensive simulation or collision check, reducing that count can materially extend the planning horizon, although queue work, memory, and other costs may also dominate.

Out[8]:

Visualization

Grid map showing A* expansions across much of the region left of the first wall and an amber path threading both gaps from bottom left to top right. — A* on an 8 by 12 grid with two walled gaps. Faint dots mark the non-goal states expanded by A*, fewer than for Dijkstra; the amber line is an optimal path.

The picture also shows the heuristic's limits. Many states tie on the same $f$ value, so A* still expands a broad region to the left of the first wall. A wall-aware cost-to-go estimate could reduce that extra work, but tie-breaking and multiple optimal routes still matter.

What search assumes, and what it costsLink Copied

The finite deterministic shortest-path methods used here are exact under their cost and heuristic conditions. Their basic formulations also make several simplifying assumptions:

Determinism. Each action has exactly one outcome. Stochasticity does not remove the state graph, but it breaks the single-successor shortest-path formulation and requires expectations or contingent policies over transition distributions.
Full observability. The planner knows the current node. With partial observability we search over belief states instead, exactly the objects Chapter 2 of this part built for us. Note that the belief space is continuous even when the underlying state space is discrete, so partial observability quietly destroys the discreteness assumption as well.
Discreteness. Exact Dijkstra or A* needs an explicitly enumerable or lazily generated discrete graph whose successors can be enumerated at each expansion. Sampling-based continuous planners use different constructions and may offer probabilistic-completeness or asymptotic-optimality guarantees; the exact guarantee depends on the algorithm.
Query scope. The A* run here answers one start-goal query. Dijkstra can compute single-source distances to all reachable nodes, and roadmap methods can amortize preprocessing across queries. Tabular DP goes further by computing a policy for every represented state under stochastic dynamics.

For this example, A* is a one-shot calculation and tabular DP is an amortized investment: it spends more work up front, then supplies an action at every represented state. Neither dominates the other. The right choice depends on query volume, stochasticity, graph size, and whether the model stays fixed.