State-Space Representation and Problem Solving

Every classical search problem is defined by five ingredients: a state space (the set of all configurations the world could be in), an initial state, a set of actions available in each state, a transition model that says what state results from taking an action in a given state, and a goal test that decides whether a state counts as done. The canonical illustration is the two-square vacuum world: a robot occupies square A or B, and each square is either dirty or clean, so the entire state space has exactly eight states (2 locations × 2×2 dirt configurations). Actions are Left, Right, and Suck; the transition model says, for instance, that Suck in a dirty square yields the same square now clean; and the goal test asks whether both squares are clean. Small as it is, this toy problem already forces the precision that search demands: "clean" must be a property of a specific state, not a vague sense of tidiness, and every action's effect must be spelled out for every state it could apply to, with no exceptions left implicit.

A second classic example is route-finding on a map, where states are named locations and actions are the roads connecting them. Consider a five-town network — Home, Market, River, Hill, and Park — where Home connects to Market and River, Market connects to Hill, River connects to Hill and Park, and Hill connects to Park. Formulating this as a search problem means: the state space is {Home, Market, River, Hill, Park}; the initial state is Home; the actions available at each town are "drive to" whichever towns it directly connects to; the transition model is exactly the adjacency list just given; and the goal test checks whether the current town equals Park. Nothing about distances, traffic, or scenery belongs in this formulation unless the task explicitly needs it — a well-posed state space includes only what the search actually needs to reason about, and every extra attribute enlarges the space and slows every algorithm that searches it.

This last point is the abstraction principle: a "world state" may contain enormous incidental detail (weather, the driver's mood, tire pressure), but a "search state" should retain only what is relevant to reaching the goal. Choosing the right abstraction is itself part of problem formulation, not a separate step — a route-finding problem that tracked fuel level, radio station, and passenger count would have a needlessly larger state space than one that tracks location alone, unless the task genuinely depends on those details (for example, a problem that requires refueling before running out of gas would need fuel level in the state). The path cost function, typically a sum of nonnegative step costs along the sequence of actions taken, completes the formulation and is what later distinguishes a solution from an optimal solution — the subject of the next lesson. Two different people can legitimately formulate the same underlying task as two different state spaces, and neither formulation is automatically "wrong"; what matters is whether the chosen state space contains enough information to compute the transition model and goal test correctly, and no more than that.

Given a problem formulation, a search algorithm builds a search tree by repeatedly expanding nodes: starting from a root node holding the initial state, expansion applies every available action to generate child nodes representing the resulting states, and this process continues until a node satisfying the goal test is generated. The nodes awaiting expansion form the frontier (sometimes called the "open list"), while nodes already expanded form the explored set. Two numbers characterize the resulting tree's size: the branching factor b, the maximum number of successors any state has, and the depth d of the shallowest goal node — a tree with uniform branching factor b and depth d can have on the order of b^d nodes at the deepest level, a quantity that later lessons on uninformed and informed search use directly to compare algorithms' time and space requirements. A node itself is not the same thing as a state: a node is a bookkeeping structure holding a state together with a pointer to its parent, the action that generated it, and its accumulated path cost, so that once a goal node is found the sequence of actions forming the solution can be recovered by walking back up the pointers to the root.

In the five-town example from the previous lesson, expanding Home generates two children, Market and River; expanding Market generates Hill; expanding River generates Hill and Park. Notice that Hill is reachable both from Market and from River — it would appear twice in the search tree as two distinct nodes, even though it is the same state. This is the repeated-states problem: a search tree can be exponentially larger than the underlying search graph because it re-derives the same state along every path that leads to it. Algorithms that track an explored set and skip re-adding states already visited convert the tree search into a graph search, trading a bookkeeping cost (remembering which states have been seen) for a potentially large reduction in wasted work — a trade-off that matters enormously once state spaces grow beyond toy examples like this one. In grid-shaped or highly connected state spaces this effect compounds quickly: a state reachable by many alternate routes can otherwise be re-derived an enormous number of times, so in practice almost every serious implementation of tree-search algorithms is really a graph-search implementation underneath.

A solution is any sequence of actions leading from the initial state to a state that passes the goal test; an optimal solution is one with the lowest path cost among all solutions. Classical AI distinguishes toy problems, built to illustrate or test a method cleanly — the 8-puzzle, vacuum world, and small route-finding maps among them — from real-world problems such as robot navigation, VLSI circuit layout, and airline crew scheduling, where the same five-part formulation applies but state spaces routinely reach billions of states or more. The algorithms introduced in the next two modules — uninformed and informed search — are general-purpose procedures for finding solutions, and in some cases optimal ones, within exactly this state-space formalism, regardless of which domain the states happen to describe. That generality is the whole point of formalizing problems this way in the first place: a single BFS or A* implementation, written once against the five-part interface of initial state, actions, transition model, goal test, and path cost, can be handed a vacuum-world problem on Monday and a route-finding problem on Tuesday without changing a line of the search algorithm itself.