Uninformed Search

A reflex agent maps the current percept straight to an action, and for many environments that is not enough: no single action reaches the goal, and the agent has to string together a whole sequence of them, choosing the first only after reasoning about where the later ones lead. An agent standing in Arad with a non-refundable ticket out of Bucharest gains nothing from any one move — every road out of Arad leads to a town that is not Bucharest — yet with a map it can plan a route, examining future actions that eventually reach a state of known value before committing to the first one.¹ That is the whole idea of a problem-solving agent: adopt a goal, formulate the problem as a state space, search for a solution offline, then execute it.

This lesson does three things. It defines what a problem is — the five components any search algorithm takes as input. It gives the one search skeleton, Tree-Search and its repeated-state-safe cousin Graph-Search, that every strategy specializes. And it works through the first two uninformed strategies — breadth-first and uniform-cost search — which differ in precisely one design choice: the order in which the frontier hands back nodes. The remaining strategies (depth-first, iterative deepening, bidirectional) and the head-to-head comparison of all of them are the subject of the companion lesson, Search Strategies Compared.

Formulating a problem

Between goal and solution sits problem formulation: deciding which actions and states to consider. Consider the level of turn the steering wheel one degree and the agent never leaves the parking lot; consider driving from one town to the next and the problem becomes a graph of two dozen cities. Choosing the right level of abstraction — dropping every detail irrelevant to reaching the goal — is what makes a real-world task tractable at all.² Formally, a problem has five components.

The initial state, actions, and transition model together define the state space implicitly: the set of all states reachable from $s_0$ by any sequence of actions. The state space is a directed graph whose nodes are states and whose edges are actions; a path is a sequence of states connected by actions. A solution is a path from $s_0$ to a goal state, and an optimal solution is one of least path cost. Notice the state space is defined implicitly — by the three functions, not by an enumerated list, and so it can be enormous or even infinite while the description stays small.

Route-finding on a map

The running example is route-finding in Romania. The agent is in Arad and must reach Bucharest. The abstraction is deliberate: a state is just which city the agent is in, ignoring the companions, the radio, the weather — everything irrelevant to finding a route.

• States: the agent's current city, e.g. $\text{In}(\text{Arad})$.
• Initial state: $\text{In}(\text{Arad})$.
• Actions: from a city, drive to an adjacent city; $\text{Actions}(\text{In}(\text{Arad}))=\{\text{Go}(\text{Sibiu}),\text{Go}(\text{Timisoara}),\text{Go}(\text{Zerind})\}$.
• Transition model: $\text{Result}(\text{In}(\text{Arad}),\text{Go}(\text{Zerind}))=\text{In}(\text{Zerind})$.
• Goal test: is the state $\text{In}(\text{Bucharest})$?
• Step cost: the road distance in kilometers; the path cost is the total distance.

The 8-puzzle

Route-finding has an obvious geography; the point of a toy problem is that it strips that away and leaves a clean state space to test algorithms on. The 8-puzzle is a $3\times 3$ board with eight numbered tiles and one blank; a tile adjacent to the blank slides into it, and the object is to reach a specified goal configuration.

• States: the location of each of the eight tiles and the blank in the nine squares.
• Initial state: any configuration.
• Actions: move the blank $\text{Left}$, $\text{Right}$, $\text{Up}$, or $\text{Down}$ (whichever are legal, given where the blank is).
• Transition model: given a state and a move, return the board with the blank and the neighboring tile swapped.
• Goal test: does the board match the goal configuration?
• Step cost: each move costs $1$, so the path cost is the number of moves.

The 8-puzzle has $9!/2=181,440$ reachable states and is easily solved; the $15$-puzzle on a $4\times 4$ board has about $1.3$ trillion, and the $24$-puzzle around $10^{25}$. This blow-up is why the abstraction matters, and why a good search strategy matters more.

Searching for solutions

A solution is a sequence of actions, so a search algorithm builds a search tree: the root is the initial state, the branches are actions, and each node corresponds to a state reached by some action sequence. Expanding a node applies each legal action to its state, generating a new set of child nodes. The leaf nodes available for expansion at any moment — the boundary between what has been explored and what has not — form the frontier.³

The whole family of algorithms shares one skeleton. Initialize the frontier with the start node; then repeat: if the frontier is empty, fail; otherwise remove a leaf, test it for the goal, and if it is not a goal, expand it and add its children to the frontier. The strategies differ only in which leaf gets removed.

There is a hazard in Tree-Search. On the Romania map the path Arad-Sibiu-Arad revisits Arad, and nothing stops it revisiting again: the search tree is infinite even though the state space has only twenty states. Such loopy paths are a special case of redundant paths — more than one way to reach the same state — and because step costs are nonnegative, a looping or roundabout path to a state is never better than the direct one. There is no reason to keep it.

The cure is to remember where the search has been. Augment the skeleton with an explored set (also called the closed list) holding every expanded state; when a newly generated node's state is already in the explored set or on the frontier, discard it. The result is Graph-Search.

Graph-Search keeps at most one copy of each state, so it grows a tree directly on the state-space graph. It also has a clean geometric property: the frontier separates the explored region from the unexplored one, so every path from the initial state to an unexplored state must pass through a frontier node. The search sweeps outward through the state space, one state at a time.

The node data structure

It pays to keep nodes and states distinct. A state is a configuration of the world; a node is a bookkeeping record on a particular search path. Two different nodes can hold the same state if it was reached two ways. Each node $n$ carries four fields:

• $n.\text{State}$ — the state it corresponds to;
• $n.\text{Parent}$ — the node that generated it;
• $n.\text{Action}$ — the action applied to the parent to produce it;
• $n.\text{Path-Cost}$ — the cost $g(n)$ of the path from the root to $n$.

The parent pointers thread the nodes into a tree and let the solution be read off by walking from a goal node back to the root. A child's cost extends its parent's: $g(\text{child})=g(n)+c(n.\text{State},a,\text{child}.\text{State})$.

The frontier holds nodes waiting to be expanded, and the strategy is entirely a choice of which node comes out next. That choice is the frontier's queue discipline, and it is the one axis along which every uninformed strategy varies:

• a FIFO queue pops the oldest node — the shallowest — giving breadth-first search;
• a priority queue pops the node of lowest $g(n)$, giving uniform-cost search;
• a LIFO queue (a stack) pops the newest node — the deepest — giving depth-first search.

Three queue types, three strategies — the through-line of this lesson and the next.

Measuring search

Before choosing among strategies, fix how they are judged. Four criteria matter.

In classical algorithms, complexity is measured against the graph size $|V|+|E|$. In AI the graph is usually implicit and often infinite, so complexity is expressed in three quantities of the problem itself:

• $b$, the branching factor — the maximum number of successors of any node;
• $d$, the depth of the shallowest goal (the fewest steps to a solution);
• $m$, the maximum depth of any path in the state space (possibly infinite).

Time is counted as nodes generated, space as the peak number of nodes stored. With these three numbers the strategies can be compared directly, without reference to any particular map or puzzle.

Breadth-first search

Breadth-first search (BFS) expands the root, then all its successors, then all their successors — every node at one depth before any at the next. It is Graph-Search with a FIFO queue for the frontier: new (deeper) nodes go to the back, so shallow nodes come out first. One tweak pays off — apply the goal test when a node is generated, not when it is expanded, so the search can stop the instant it makes the goal rather than a full level later.

How does BFS score? It is complete whenever $b$ is finite: a goal at depth $d$ is found after all shallower nodes are generated. It is optimal only when the path cost is a nondecreasing function of depth — most commonly when every step costs the same — since it returns the shallowest goal, which need not be the cheapest. The cost is where the news turns bad. A uniform tree generates $b+b^2+\cdots +b^d=O(b^d)$ nodes, and every generated node stays in memory, so both time and space are $O(b^d)$. Space is the binding constraint.

At $b=10$ the memory bill dwarfs the time bill: a depth-$12$ solution takes thirteen days but a petabyte of storage no machine has. Exponential-complexity problems cannot be solved by uninformed search for any but the smallest instances, and among the reasons, the frontier's appetite for memory is the worst.

A traced run

Trace BFS from Arad on the map fragment above, goal Bucharest. The FIFO frontier starts as [Arad]. Popping Arad expands it to Zerind, Timisoara, and Sibiu, which join the back of the queue. Since none is the goal (the goal test fires at generation), the queue is now [Zerind, Timisoara, Sibiu]. The table below records each expansion, the newly generated states, and the resulting frontier; a state already explored or already queued is dropped rather than re-added.

BFS returns Arad-Sibiu-Fagaras-Bucharest, a path of $140+99+211=450$ km. This is the shallowest goal — three edges — but not the cheapest: the four-edge route Arad-Sibiu-Rimnicu-Pitesti-Bucharest costs only $418$. BFS finds the goal at generation in step $7$, one level before it would have been expanded, exactly the early-termination tweak paying off. Notice too that when Oradea is expanded in step $5$ every successor (Zerind, Sibiu) is already on the frontier or explored, so the explored set does its job and no duplicate is queued.

Uniform-cost search

BFS is optimal only when steps cost the same, because it orders the frontier by depth. Uniform-cost search orders it by cost instead: expand the node $n$ of lowest path cost $g(n)$, using a priority queue keyed on $g$. This is exactly Dijkstra's algorithm cast as a search over an implicit graph.⁴

Two details separate it from BFS. The goal test is applied when a node is selected for expansion, not when generated — because the first goal node generated may sit on a costly path while a cheaper route to the goal is still on the frontier. And when a shorter path to a frontier state turns up, the frontier node is replaced.

Uniform-cost search is optimal in general. Whenever it selects a node $n$, the cheapest path to $n$ has already been found: any cheaper route would run through some other frontier node $n^{\prime }$ of lower $g$, which would have been selected first. Because step costs are nonnegative, paths only grow as they extend, so nodes are expanded in order of optimal path cost, and the first goal selected is the least-cost goal.

Consider Sibiu to Bucharest. Sibiu's successors are Rimnicu ($80$) and Fagaras ($99$). The cheaper, Rimnicu, is expanded first, adding Pitesti at $80+97=177$. Now Fagaras is cheapest, so it expands, adding Bucharest at $99+211=310$. A goal has been generated — but uniform-cost search does not stop, because Pitesti at $177$ is cheaper than that goal. Expanding Pitesti reaches Bucharest at $80+97+101=278$; the better path replaces the old one, and only when Bucharest at $278$ is selected is the solution returned.

Laid out as a priority-queue trace, the run reads as follows. Each row shows the node selected (lowest $g$), the frontier entries it generates with their cumulative costs, and the frontier that results, sorted by $g$. A goal that is merely generated sits in the queue like any other node and is returned only when it reaches the front.

At step $3$ a Bucharest node exists at cost $310$, but uniform-cost search keeps going because Pitesti at $177$ is cheaper. Expanding Pitesti in step $4$ finds Bucharest again at $80+97+101=278$; the cheaper node replaces the costlier one on the frontier, and only when Bucharest at $278$ is selected in step $5$ does the search stop and return Sibiu-Rimnicu-Pitesti-Bucharest. Testing the goal at selection rather than generation is what saves the run from returning the $310$ path.

The price of guaranteed optimality is that complexity is set by cost, not depth. With $C^{\ast }$ the optimal cost and $\epsilon$ a lower bound on step cost, worst-case time and space are $O\left(b^{1+\lfloor C^{\ast }/\epsilon \rfloor }\right)$, which can exceed $b^d$: uniform-cost search may explore large trees of tiny steps before committing to a path of a few large ones. A concrete failure: from a start with a direct edge of cost $2$ to the goal and a chain of unit-cost edges through many intermediate states, uniform-cost search expands the entire cheap chain before it ever selects the single expensive edge, even though the chain is far longer. When every step costs the same it reduces to BFS, doing a little extra work by examining all nodes at the goal's depth to confirm none is cheaper.

Breadth-first and uniform-cost search both grow the frontier outward and pay for it in memory. The remaining uninformed strategies trade that memory away by diving deep instead of wide — depth-first search, its depth-limited and iterative-deepening refinements, and bidirectional search — and then we can line all of them up against the four criteria at once. This continues in Search Strategies Compared.