Search-Based Planning (BFS, DFS, A*)

A delivery robot sits in the lobby of an office floor. It needs to reach the server room. Its first attempt at navigation is the obvious one: face roughly towards the goal and drive.

It drives into a wall. The server room is behind the stairwell, and the direct line passes through 30 centimetres of reinforced concrete.

The second attempt adds a rule: when blocked, turn right and follow the wall. This gets it to the kitchen, the lab, and eventually — after four minutes and 40 metres of travel — the server room. The direct route through the stairwell is 12 metres.

Both attempts fail for the same reason. The robot decides where to go next using only what it can see right now. It never considers the sequence of moves as a whole. To do that, it needs to lay out every place it could go, every way of getting between them, and find the cheapest chain from where it is to where it wants to be. That is search, and it is the oldest working idea in planning.

Search, stated precisely

Search treats planning as a question about a graph. You need five things, and once you have them the problem is solved by machinery rather than cleverness:

The states and actions together define a state-space graph: nodes are states, edges are actions. Crucially, you almost never build this graph — it is far too large. You generate it lazily, expanding a node only when the search reaches it. A chess position has around 35 legal moves and the game has roughly $10^{44}$ legal positions; nobody stores that. You expand what you need.

Search does not find the goal. It finds a path to the goal. The distinction matters: the answer to a planning problem is the sequence of actions, not the destination.

The office floor as a graph

        Lobby        /   \   Corridor  Stairs     /  \        \Kitchen  MeetingA  Server   |        |       /  Lab ------|------/             MeetingB ----/

1FLOOR = {2    "Lobby":    ["Corridor", "Stairs"],3    "Corridor": ["Kitchen", "MeetingA"],4    "Stairs":   ["Server"],5    "Kitchen":  ["Lab"],6    "MeetingA": ["MeetingB"],7    "MeetingB": ["Server"],8    "Lab":      ["Server"],9    "Server":   [],10}

Three paths exist from Lobby to Server: via Stairs (2 moves), via Corridor–MeetingA–MeetingB (4 moves), via Corridor–Kitchen–Lab (4 moves). Which one an algorithm finds depends entirely on the order in which it pulls nodes off its list of things to try. That single design choice is the difference between every algorithm below.

Breadth-first search

BFS keeps a queue — first in, first out. It expands every node at distance 1 before any node at distance 2, every node at distance 2 before any at distance 3, and so on. It sweeps outward in shells.

frontier = queue([start])visited  = {start}while frontier not empty:    node = frontier.pop_front()    if goal(node): return path_to(node)    for nb in neighbours(node):        if nb not in visited:            visited.add(nb)            parent[nb] = node            frontier.push_back(nb)return failure

Trace on the office floor

frontier                              dequeue    discovered[Lobby]                               Lobby      Corridor, Stairs[Corridor, Stairs]                    Corridor   Kitchen, MeetingA[Stairs, Kitchen, MeetingA]           Stairs     Server[Kitchen, MeetingA, Server]           Kitchen    Lab[MeetingA, Server, Lab]               MeetingA   MeetingB[Server, Lab, MeetingB]               Server     GOALPath: Lobby -> Stairs -> Server        (2 moves)Nodes expanded: 6

BFS found the shortest path, and this is guaranteed rather than lucky. Since it never touches depth k+1 until depth k is exhausted, the first time it meets the goal it has met it at minimum depth.

Notice the six expansions. It looked at Kitchen and MeetingA — rooms in completely the wrong direction — before finishing. That is BFS's price. You can shave it by testing the goal when a node is discovered rather than when it is dequeued, which finds Server while expanding Stairs and cuts expansions from 6 to 3. This early goal test is safe for unit-cost edges only; with varying costs it can return a suboptimal path.

1from collections import deque23def bfs(graph, start, goal):4    frontier = deque([start])5    parent = {start: None}6    expanded = 07    while frontier:8        node = frontier.popleft()9        expanded += 110        if node == goal:11            path, cur = [], node12            while cur is not None:13                path.append(cur)14                cur = parent[cur]15            return list(reversed(path)), expanded16        for nb in graph[node]:17            if nb not in parent:18                parent[nb] = node19                frontier.append(nb)20    return None, expanded

The parent dictionary does double duty: it records the tree so a path can be reconstructed, and membership in it serves as the visited set. Forgetting the visited check is the classic BFS bug — on a graph with cycles the queue grows without bound and the process dies of memory exhaustion.

The memory problem

BFS holds the entire frontier in memory, and the frontier at depth d has roughly b^d nodes for branching factor b. Put numbers on it: with b = 10 and 100 bytes per node,

BFS does not fail slowly on deep problems. It fails abruptly, by running out of RAM, usually two levels after it was working perfectly.

Depth-first search

DFS keeps a stack — last in, first out. It follows one branch as deep as it goes, and only when that branch is exhausted does it back up and try an alternative.

1def dfs(graph, start, goal, depth_limit=50):2    stack = [(start, [start])]3    seen = set()4    expanded = 05    while stack:6        node, path = stack.pop()7        expanded += 18        if node == goal:9            return path, expanded10        if node in seen or len(path) > depth_limit:11            continue12        seen.add(node)13        for nb in reversed(graph[node]):     # so the first listed14            if nb not in seen:               # neighbour is explored first15                stack.append((nb, path + [nb]))16    return None, expanded

Trace on the same floor

pop Lobby     -> push Stairs, Corridor  (Corridor on top)pop Corridor  -> push MeetingA, Kitchen (Kitchen on top)pop Kitchen   -> push Labpop Lab       -> push Serverpop Server    -> GOALPath: Lobby -> Corridor -> Kitchen -> Lab -> Server   (4 moves)Nodes expanded: 5

Read those two results side by side. DFS expanded 5 nodes to BFS's 6 — slightly cheaper. And it returned a path twice as long, 4 moves against 2. For a robot that is 40 metres against 12.

DFS commits early and never reconsiders. It went into the Corridor first because that neighbour happened to be listed first, and once committed it drove all the way to the end of that branch. Nothing in the algorithm asks whether the branch is a good idea.

What DFS buys is memory. It stores only the current path plus the unexplored siblings along it: O(b·m) rather than O(b^d). With b = 10 and depth 10, that is roughly 100 nodes instead of ten billion. This is why DFS is the default for constraint problems with deep solution trees — Sudoku, SAT, dependency resolution — where the answer is at a known depth and any valid solution will do.

Two dangers. Without a visited set, a cycle makes DFS loop forever. Without a depth limit, an infinite branch swallows it even on an acyclic graph. Both are in the code above and both are non-optional.

BFS runs out of memory. DFS runs out of patience, and returns a bad answer while doing it. Neither has any idea which direction the goal is in.

A* search

Every algorithm so far is uninformed — it uses no knowledge of where the goal actually is. A* fixes this by adding an estimate.

A* orders its frontier by

where g(n) is the known cost of the best path found so far from the start to n, and h(n) is a heuristic: a guess at the remaining cost from n to the goal. It always expands the node with the lowest f — the one that looks most promising as part of a complete cheap path.

Set h = 0 everywhere and A degrades into Dijkstra's algorithm: pure cost-so-far, no foresight. Make h exact and A walks straight down the optimal path expanding nothing else. Real heuristics sit between.

A weighted worked example

Six locations. Edge labels are real travel costs in kilometres. Each node also carries a straight-line distance to the goal G, which is our heuristic — a road can never be shorter than the crow-flight distance, so this estimate never overshoots.

Edges (km):   S-A 4   S-B 3   A-C 5   A-D 12              B-C 10  B-D 7   C-G 6   D-G 2Heuristic h (straight line to G):      S = 9    A = 8    B = 7    C = 5    D = 2    G = 0

EXPAND S     g=0   h=9   f=9  A: g=0+4=4    h=8  f=12  B: g=0+3=3    h=7  f=10  open = { B:10, A:12 }EXPAND B     g=3   h=7   f=10          (lowest f)  D: g=3+7=10   h=2  f=12  C: g=3+10=13  h=5  f=18  open = { A:12, D:12, C:18 }EXPAND D     g=10  h=2   f=12          (tie with A, lower h wins)  G: g=10+2=12  h=0  f=12  open = { A:12, G:12, C:18 }EXPAND G     g=12  h=0   f=12          GOALPath: S -> B -> D -> G      Cost: 3 + 7 + 2 = 12 kmNodes expanded: 4

Verify by brute force that 12 is genuinely optimal:

Now run Dijkstra on the same graph — identical code with h forced to zero. It expands S, then B (g=3), then A (g=4), then C (g=9, improved via A from 13), then D (g=10), then G (g=12). Six expansions for the same answer. A* did it in four because the heuristic told it that A and C were pointing away from G, so it never bothered.

1import heapq23def astar(graph, start, goal, h):4    open_heap = [(h[start], h[start], 0, start)]   # (f, h, g, node)5    best_g = {start: 0}6    parent = {start: None}7    closed = set()8    expanded = 0910    while open_heap:11        f, _, g, node = heapq.heappop(open_heap)12        if node in closed:13            continue                        # stale entry, skip14        closed.add(node)15        expanded += 11617        if node == goal:18            path, cur = [], node19            while cur is not None:20                path.append(cur)21                cur = parent[cur]22            return list(reversed(path)), g, expanded2324        for nb, cost in graph[node]:25            new_g = g + cost26            if new_g < best_g.get(nb, float("inf")):27                best_g[nb] = new_g28                parent[nb] = node29                heapq.heappush(open_heap, (new_g + h[nb], h[nb], new_g, nb))3031    return None, float("inf"), expanded

Three implementation points that cause most A bugs. First, Python's heapq has no decrease-key operation, so instead of updating an entry you push a new one and skip stale pops via the closed set — the if node in closed: continue line. Second, the comparison is on new_g, not on f. Comparing f values to decide whether a route is an improvement is wrong, because h is the same for a given node either way and cancels out — but it will silently produce suboptimal paths on graphs where it does not. Third, ties on f are broken by the smaller h — the node nearer the goal — which is why h sits second in the heap tuple. Break ties on g* instead and the weighted example above expands A before D, five nodes instead of four; on the grid below it expands 13 cells instead of 8. Still optimal, just slower.

What makes a heuristic legal

Admissible means h(n) never overestimates: for every node, $h(n) \le h^(n)$ where h^ is the true remaining cost. Check ours: from D the true cost to G is 2 and h(D) = 2 — allowed, equality is fine. From S the true cost is 12 and h(S) = 9 — an underestimate, fine.

Why it matters, concretely. Suppose we had set h(A) = 20 instead of 8, wildly overestimating. Then A gets f = 4 + 20 = 24 and A pushes it to the back of the queue. If the only optimal route ran through A, A would return a worse path and never notice. Overestimating makes A* discard good options unexamined. Underestimating only makes it slower.

Consistent (or monotone) is stronger: for every edge from n to n' with cost c, $h(n) \le c + h(n')$. This says the estimate can never drop by more than the distance you actually travelled. Consistency implies admissibility, and it gives you something practical: with a consistent heuristic, the first time A expands a node it already has that node's optimal g*, so nodes never need re-expanding. Check the S→B edge: h(S) = 9, c = 3, h(B) = 7. Is 9 ≤ 3 + 7 = 10? Yes. Every edge in the example passes.

Between two admissible heuristics, the larger one is better: it is closer to the truth, so it prunes more. This is called dominance. Sum-of-Manhattan dominates misplaced-tiles on the 8-puzzle and typically cuts expansions by an order of magnitude.

Full worked example: a grid maze

      col:  0   1   2   3   4   row 0:   S   .   .   #   .   row 1:   .   #   .   #   .   row 2:   .   #   .   .   .   row 3:   .   .   .   #   G   S = (0,0)    G = (3,4)    # = wall   Moves: up/down/left/right, cost 1   h = Manhattan distance to (3,4)

h(0,0) = |0−3| + |0−4| = 7. A trace, showing the lowest-f* node at each step:

expand (0,0)  g=0 h=7 f=7   ->  (0,1) g=1 h=6 f=7 ; (1,0) g=1 h=6 f=7expand (0,1)  g=1 h=6 f=7   ->  (0,2) g=2 h=5 f=7   [(1,1) is wall]expand (0,2)  g=2 h=5 f=7   ->  (1,2) g=3 h=4 f=7   [(0,3) is wall]expand (1,2)  g=3 h=4 f=7   ->  (2,2) g=4 h=3 f=7expand (2,2)  g=4 h=3 f=7   ->  (2,3) g=5 h=2 f=7 ; (3,2) g=5 h=2 f=7expand (2,3)  g=5 h=2 f=7   ->  (2,4) g=6 h=1 f=7expand (2,4)  g=6 h=1 f=7   ->  (3,4) g=7 h=0 f=7expand (3,4)  GOAL, cost 7Path: (0,0) (0,1) (0,2) (1,2) (2,2) (2,3) (2,4) (3,4)Cells expanded: 8

Every node on the path had f = 7 the whole way down. That is the signature of a heuristic that is exact for this instance — the walls happen not to force any detour, so Manhattan distance is the true distance. Other cells, such as (1,0), also score f = 7, but the tie-break on smaller h keeps A* on the path nearest the goal, so it walks the optimal route without a single wasted expansion.

The same maze under the other two algorithms:

DFS's 9-step path — down the left edge, along the bottom, then up and across — costs 29% more than necessary. On a 15-metre office floor that is a few extra metres. On a warehouse route repeated 4,000 times a day it is hours of battery.

Choosing

Where this shows up

GPS routing. Plain A on a continent-scale road graph is still too slow for a phone. Production systems precompute: contraction hierarchies collapse through-roads into shortcut edges, and landmark-based heuristics (ALT) store exact distances to a few hundred reference nodes and use the triangle inequality to get much tighter bounds than crow-flight distance. Both are A with a better h.

Game pathfinding. A* over a navigation mesh rather than a raw grid — far fewer nodes. On uniform grids, Jump Point Search skips over long runs of open cells that cannot contain a better path, often 10× faster with identical results.

Robot motion planning. A real robot's state is continuous — position, orientation, joint angles — so there is no finite graph to search. Sampling planners (RRT, PRM) build a graph by scattering random valid configurations and connecting them, then run a graph search over that. Search, on a graph that search itself constructed.

LLM agent planning. An agent choosing tool calls is searching a state space where actions are tools and cost is tokens or latency. Most agents run greedy depth-first: pick the action that looks best, commit, never reconsider — which is exactly why they get stuck in loops. Tree-of-Thoughts keeps several partial plans alive and scores them, which is beam search. Monte Carlo Tree Search samples rollouts to estimate h when no analytic heuristic exists. Naming the search you are doing tells you which failure to expect.

Where people get this wrong

An inadmissible heuristic that seems reasonable. Someone estimates "remaining API calls × average latency" and pads it by 20% for safety. That padding makes it overestimate, and A starts quietly returning suboptimal plans. The padding felt conservative; for A it is the dangerous direction.

No visited set. It works on the test graph because the test graph is a tree. The first real graph with a cycle turns the search into an infinite loop or a memory fire.

Optimising the algorithm instead of the heuristic. Micro-tuning the priority queue gains a few percent. Replacing Euclidean distance with a landmark heuristic can cut expansions by 90%. The heuristic is nearly always where the win is.

Treating the state as the answer. Returning "the goal is reachable" instead of the path. Reconstructing the path costs one parent pointer per node and is the entire point of running the search.

What this means when you build one

The first thing to do with any planning problem is write down those five elements — initial state, actions, transition model, goal test, cost — explicitly, on paper, before touching code. Most planning bugs are not algorithm bugs. They are a goal test that accepts states you did not intend, or a cost function that quietly ignores the thing you actually care about.

Then pick by constraint rather than by preference. Unit costs and a shallow goal: BFS, and stop. Deep tree, any valid answer, limited memory: DFS with a depth limit. Weighted edges: Dijkstra, unless you can write down an honest lower bound on remaining cost, in which case A*.

If you write a heuristic, prove admissibility before you ship it — take three or four nodes, compute the true remaining cost by hand, and confirm your estimate is below it every time. It takes ten minutes and it catches the failure mode that is otherwise invisible, because an inadmissible heuristic does not crash. It just returns slightly wrong answers forever.

And when you build an LLM agent, notice which search you have accidentally implemented. A loop that picks the single best next tool and commits is DFS with no backtracking — it will find a path and it will sometimes be a long one. If that matters, give it the ability to abandon a line of attack and try another, and give it something to score partial plans with. That is the whole difference between the robot that took 40 metres and the one that took 12.