Skip to content
Tutorials Center
My learning

Topics

Lesson 5 of 46 ยท Uninformed Search

Formulating Search Problems

Learn to define a search problem: states, actions, transition model, goal test and path cost. Build a reusable Python Problem class for route finding and the 8-puzzle.

Many AI problems boil down to one question: which sequence of actions leads from where I am to where I want to be? Finding a route, solving a puzzle, planning a robot's moves and even proving a theorem can all be phrased that way. Before an algorithm can attack such a problem, a human has to formulate it: decide what counts as a state, what moves are allowed and how to recognize success.

Getting the formulation right is half the work. A good one makes the problem small and the code short; a careless one can turn an easy task into an impossible one. In this lesson you will learn the five ingredients of a search problem, write a reusable Python Problem class that every later search algorithm in this course will use, and encode two classic problems: route finding and the 8-puzzle.

The five ingredients

A search problem is defined by:

  1. Initial state: where the agent starts.
  2. Actions: actions(s) returns the moves available in state s. Different states may allow different moves.
  3. Transition model: result(s, a) returns the state you reach by doing action a in state s.
  4. Goal test: is_goal(s) says whether s is a goal. A goal may be one state or a whole set of states.
  5. Path cost: a number for each step, step_cost(s, a, s2); the cost of a path is the sum of its steps. A solution is an action sequence from the initial state to a goal, and an optimal solution has the lowest total cost.

Together, the initial state, actions and transition model define the state space: a graph whose nodes are states and whose edges are actions. A solution is a path through that graph.

graph LR
    S0["initial state"] -- "action a1" --> S1["state"]
    S0 -- "action a2" --> S2["state"]
    S1 -- "action a3" --> G["goal state"]
    S2 -- "action a4" --> S3["state"]
    S3 -- "action a5" --> G

A state space is a graph. Searching means finding a path from the initial state to any goal.

Note: A formulation is an abstraction. When planning a drive from one city to another, the state is "which town am I in", not the fuel level, the weather or the song on the radio. Keep exactly the details the decision needs and nothing more, and the search stays small.

A reusable Problem class

Instead of writing a new search function for every puzzle, we put the five ingredients behind one small interface. A search algorithm will call only these methods, so it works for any problem that provides them.

Python The Problem interface and a route-finding problem

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The three routes are all legal solutions. The one with the fewest road segments is not the cheapest in kilometers, which is why we keep two notions apart: number of steps and path cost. If every step costs 1 (the default step_cost), they are the same thing. Later lessons show which algorithms care about the difference.

The 8-puzzle

A 3 by 3 frame holds eight numbered tiles and one empty square. Sliding a tile into the gap is the only move. The goal is the tiles in order with the blank last.

We need to choose a state representation. The simplest is a tuple of nine numbers in reading order, with 0 for the blank. Tuples are immutable and hashable, so states can be stored in sets and dictionaries, which matters in the next lesson. The clearest way to think about actions is that the blank moves: Up, Down, Left or Right, whenever that does not leave the board.

Python Encoding the 8-puzzle

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Notice that result builds a new tuple and never changes the old state. That is essential: a search algorithm keeps many states alive at once, and mutating one would silently corrupt the others.

How big is the state space?

Knowing the size of the state space tells you whether you can afford to explore all of it. The 8-puzzle has nine squares, so there are 9! = 362,880 ways to place the tiles. Exactly half of them cannot be reached from the goal (swapping two tiles is impossible with sliding moves), so only 181,440 states are reachable. That is small for a computer. The 15-puzzle has 16!/2, about 10 trillion reachable states, and the 24-puzzle has about 8 x 10^24.

Another number matters just as much: the branching factor, the typical number of actions per state. A blank in a corner has 2 moves, on an edge 3, in the center 4. Let us verify the count and average by exploring everything reachable from the goal.

Python Counting the 8-puzzle state space

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The average branching factor of about 2.67 is the number that will predict how fast the search algorithms in the next lessons blow up with depth.

Pitfalls of formulation

  • Too much detail makes the state space huge. Leave out whatever does not affect the decision.
  • Too little detail makes the solution impossible to carry out. A route that ignores one-way streets is useless.
  • A wrong goal test gives wrong answers: a goal that cannot be reached, or one that is already satisfied at the start.
  • Hidden randomness: if actions can have several outcomes, plain search is not enough and you need probabilistic methods (see decision making).

Next, you will build the algorithm that works on any Problem: Tree Search and Graph Search.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which set of ingredients defines a search problem?

    These five parts define the state space, the goal and the quality of a solution. PEAS describes agents; the other lists belong to CSPs and Bayesian reasoning.
  2. 2. Why does the 8-puzzle encoding use tuples instead of lists for states?

    Search algorithms need to remember visited states, which requires hashable values; immutability also stops one branch from corrupting another.
  3. 3. How many states of the 8-puzzle are reachable from the goal?

    There are 9! = 362,880 arrangements, but sliding moves preserve a parity property, so only half of them (181,440) can be reached.
  4. 4. A route has the fewest road segments. Is it necessarily the cheapest route?

    Number of steps equals path cost only when every step costs the same; with different road lengths a longer chain of short roads can be cheaper.

Summary

  • A search problem is an initial state, actions, a transition model, a goal test and a path cost.
  • The state space is a graph; a solution is a path from the initial state to a goal, and an optimal one has the lowest total cost.
  • A small Problem class lets every search algorithm work on every problem.
  • Good formulations abstract away irrelevant detail; immutable, hashable states make visited-state tracking easy.
  • The 8-puzzle has 181,440 reachable states and an average branching factor of about 2.67; larger puzzles explode.

Next: Tree Search and Graph Search.