Reading 1: Problems as State Spaces

The Challenge of Goal-Directed Behavior

In Topic 6a we described goal-directed behavior as a central capability of AI agents: rather than just reacting to the current situation, a goal-directed agent plans ahead, considering possible actions and choosing the ones most likely to reach a desired outcome.

That description is accurate, but it leaves an important question unanswered: how does an agent actually do that? Before it can plan, it needs a precise description of the problem it is trying to solve. It needs to know where it is starting, where it wants to end up, what actions are available, and how to evaluate which sequence of actions is best.

Computer scientists have developed a standard way of framing goal-directed problems that makes them tractable for a reasoning agent. Every such problem can be described using four ingredients. Get those four ingredients right, and "solve this problem" reduces to a single, general challenge that the same reasoning machinery can tackle again and again.

The Four Ingredients of a Search Problem

1. Start State

The start state is a complete description of the situation at the beginning — before the agent has done anything. "Complete" is important here: the start state must capture everything that matters for the problem, and nothing irrelevant.

2. Goal State

The goal state is what the agent is trying to achieve. Sometimes there is exactly one goal state (a specific destination, a specific arrangement of tiles). Sometimes there are many goal states that all count as success (any arrangement where the puzzle is solved, any route that reaches the destination). The agent's job is to reach one of them.

3. Transitions

A transition is a single action that moves the agent from one state to another. Transitions are also called productions or operators depending on the textbook. Each transition has a precondition — a requirement that must be true of the current state before the transition can be applied. At any given state, some transitions are available and others are not.

The complete picture of all states connected by all transitions is called the state space. Solving the problem means finding a path through the state space from the start state to a goal state.

4. Cost

Not all paths are equally good, even if they both reach the goal. The cost of a path is some measure of how expensive or undesirable it is. Cost might be the number of transitions taken, the total distance traveled, the time elapsed, or the fuel consumed — whatever matters for the problem at hand.

This is the ingredient that separates "find a solution" from "find the best solution." An agent that ignores cost might reach the goal by a roundabout, expensive path. A well-designed agent finds the path with the lowest total cost.

Cost plays out very differently depending on the problem. In some problems every transition costs exactly the same — we call this uniform cost. In others, different transitions have different costs. That distinction turns out to matter a great deal for which search strategies work well, as we will see in Readings 2 and 3.

Example 1 — The 8-Puzzle (Uniform Cost)

The 8-puzzle is a classic AI problem: a three-by-three grid holds eight numbered tiles and one empty space. The tiles are scrambled. Your goal is to slide tiles into the empty space, one at a time, until the tiles are arranged in order.

Here is how the 8-puzzle maps onto the four ingredients:

Because every move costs the same, the best solution is simply the one that uses the fewest moves. A five-move solution is always better than a six-move solution, no matter which tiles were moved. This is uniform cost, and it makes the optimization question straightforward: minimize the number of transitions.

The state space is enormous. There are 181,440 distinct reachable arrangements of the eight tiles (roughly half of all possible arrangements are unreachable from any given start state). Even for this small puzzle, the agent cannot try every possible sequence of moves — it has to search intelligently.

Example 2 — GPS Navigation (Variable Cost)

GPS navigation is a different kind of problem, and the difference shows up most clearly in the cost.

Suppose you want to drive from Cedar Falls, Iowa to Chicago, Illinois. From Cedar Falls, you can immediately reach four neighboring cities: Dike to the west, Hudson to the south, Waverly to the north, and Waterloo to the east. From those cities you can reach others, and so on, until eventually you reach Chicago.

From Waterloo the road network branches further. One path continues east on US Highway 20 through Independence, Manchester, and Dubuque, crossing into Illinois and continuing through Galena, Freeport, and Rockford before reaching Chicago. A second path heads south from Waterloo on I-380 to Cedar Rapids, then east through Iowa City and Davenport before joining I-80 into Chicago.

Notice the tension: the route with fewer stops is actually longer in miles. This is the heart of variable cost. Here is how GPS navigation maps onto the four ingredients:

The cost row is where GPS navigation gets interesting — and complicated. If cost is measured in miles, the US 20 route wins (315 vs. 330). If cost is measured in travel time, the I-380/I-80 route might win because it uses faster interstate highways for more of the journey. If cost is fuel efficiency, the answer might differ again.

Crucially, the cost of each individual transition varies. A five-mile segment on a highway is fast and cheap. A five-mile segment through a city center is slow and expensive in time. Unlike the 8-puzzle, you cannot just count transitions to find the best path — you have to add up the actual costs of the specific road segments traveled.

The same route has different costs depending on what you are optimizing. This is why GPS apps can switch between "fastest route," "shortest route," and "most fuel-efficient route" and give you three different answers for the same trip.

The Key Insight: Every Problem Becomes Path-Finding

The puzzle and the GPS trip look nothing alike on the surface — one involves sliding tiles on a grid, the other involves choosing roads between cities. But once you describe both using the four ingredients, the same structure appears:

• A starting point
• A destination
• A set of moves connecting them
• A way to measure how good a path is

In both cases, solving the problem means finding a path through a state space — a network of states connected by transitions — from start to goal, minimizing cost along the way. That reduction is powerful because it means the same reasoning machinery can be applied to both problems. Build a good path-finding engine and you have a general-purpose problem solver.

The Problem: State Spaces Are Enormous

If solving the problem is just finding a path, why is AI reasoning hard? The answer is scale. The 8-puzzle has 181,440 reachable states. A real GPS road network has millions of intersections. Chess has more possible positions than atoms in the observable universe. You cannot enumerate every possible path and pick the best one — there are too many.

The agent has to search the state space intelligently — exploring promising paths without getting lost in the vast majority of paths that lead nowhere useful. The next three readings introduce the main strategies for doing this: breadth-first search, depth-first search, and heuristic search. Each makes different tradeoffs, and — as you will see — the right choice depends heavily on whether cost is uniform or variable.