I4 · Problem Solving and Reasoning: Classical AI

Problem Formulation and State Space

Problem formulation turns a task into a form a search algorithm can solve. It specifies the initial state, the actions available in each state, a transition model describing the result of each action, a goal test, and a path cost. Together these define the state space: the set of all states reachable from the initial state, connected by actions, which can be pictured as a graph.

10 min Intermediate · Sublevel Intermediate Jump to the activity

What you need: The earlier topics of this module.

Definition

How does a computer solve a puzzle it has never seen, such as getting a farmer, a goat, a tiger and a bundle of grass across a river in a tiny boat? First it must describe the puzzle precisely, as states and moves.

Problem formulation turns a task into a form a search algorithm can solve. It specifies the initial state, the actions available in each state, a transition model describing the result of each action, a goal test, and a path cost. Together these define the state space: the set of all states reachable from the initial state, connected by actions, which can be pictured as a graph.

In simple words

Planning a trip on a metro map is search. Each station is a state, each line between stations is an action, your starting station is the initial state, your destination is the goal, and the number of stops or minutes is the path cost.

Overview

  • Before an agent can search, the problem must be stated precisely.
  • A problem has an initial state, actions, a transition model, a goal test and a path cost.
  • The state space is the set of all states reachable from the initial state.
  • A solution is a sequence of actions leading from the initial state to a goal state; an optimal one has the lowest cost.
  • Abstraction removes irrelevant details, such as the colour of the car on a route-finding map.
  • State spaces can be astronomically large: chess has more possible games than atoms in the observable universe.

Why it matters

A good formulation makes a problem easy; a poor one can make it impossible. Route planning, puzzle solving, scheduling and robot motion all start by choosing what a state is and which details to leave out.

Key terms

State
A description of the situation that contains everything relevant to the problem.
Initial state
Where the agent starts.
Action and transition model
The available moves and the state each move leads to.
Goal test
A check of whether a state solves the problem.
Path cost
The total cost of a sequence of actions, such as distance or time.
Branching factor
The average number of actions available from a state.

Types

Problems are formulated in a few standard ways. These types of problem and representation appear throughout classical AI.

1. Toy (puzzle) problems

Small, exactly defined problems used to compare algorithms.

  • How it works: States, actions and goals are simple to write down, so results are easy to check.
  • Example: The 8-puzzle (sliding tiles, 181,440 reachable states), the water-jug problem and the missionaries-and-cannibals puzzle.
  • When to use it: Use them to learn and test search algorithms before moving to real problems.

2. Real-world problems

Practical problems whose formulation needs careful abstraction.

  • How it works: States must capture what matters (location, time, fuel) and ignore the rest; costs often combine distance, time and money.
  • Example: Route finding for delivery vans, airline scheduling, chip layout and robot navigation.
  • When to use it: Use them as the real target; formulation choices here matter as much as the algorithm.

3. State-space graphs and trees

Representing states as nodes and actions as edges.

  • How it works: A search tree unrolls the graph from the start state; the same state can appear many times in the tree, so algorithms keep an explored set.
  • Example: A road map of cities with distances on the edges.
  • When to use it: Use graphs to reason about the problem and trees to understand how search explores it.

4. Incremental versus complete-state formulation

Incremental formulations build a solution step by step; complete-state formulations start with a full candidate and modify it.

  • How it works: Incremental suits path-finding by search; complete-state suits local search and genetic algorithms, which only need a way to score candidates.
  • Example: N-queens placed one queen at a time (incremental) versus all eight placed and then moved (complete-state).
  • When to use it: Choose complete-state formulations when the path does not matter, only the final arrangement.

Explained in detail

Formulating the river-crossing puzzle

ComponentFor the farmer, goat, tiger and grass
StateWhich bank each of the four is on, for example (L, L, L, L)
Initial stateEveryone on the left bank
ActionsThe farmer crosses alone or with one item
ConstraintNever leave the goat with the tiger or the goat with the grass without the farmer
Goal testEveryone on the right bank
Path costNumber of crossings

With four items, each on one of two banks, there are only 2⁴ = 16 possible states, and some are forbidden by the constraint. A computer can explore them all in an instant and find the seven-crossing solution: take the goat across, return, take the tiger, bring the goat back, take the grass, return, take the goat. The cleverness was in the formulation, not the search.

The right level of abstraction

Choosing what to include in a state is an act of abstraction. For route planning between cities, a state can be just "which city am I in"; the colour of the car, the radio station and the exact lane are irrelevant. Including them would multiply the state space enormously for no benefit. Leaving out something relevant, such as fuel level on a long trip through remote areas, can make solutions useless. Good formulation keeps exactly the details that affect which actions are possible, what they cost and whether the goal is reached.

How big state spaces get

  • The 8-puzzle, a 3 × 3 grid of sliding tiles, has 181,440 reachable states: easy for a computer.
  • The 15-puzzle (4 × 4) has about 10 trillion: hard without good heuristics.
  • Chess has an estimated 10⁴³ or more legal positions: far too many to enumerate.
  • The branching factor drives this growth: with b actions per state, looking d steps ahead means about bᵈ paths.

Because state spaces can be astronomically large, search algorithms do not build the whole graph in advance. They generate states only as they explore, keeping a frontier of states waiting to be expanded and, usually, a set of states already visited so they are not explored twice.

How it works

  1. Decide what a state must contain, and nothing more.
  2. Define the initial state and the goal test.
  3. List the actions and their results, including constraints.
  4. Choose a path cost that matches what you want to minimise.
  5. Estimate the size of the state space and branching factor.

In code

river_crossing.py
from collections import deque

ITEMS = ("farmer", "goat", "tiger", "grass")

def safe(state):
    farmer, goat, tiger, grass = state
    if goat == tiger and farmer != goat:
        return False
    if goat == grass and farmer != goat:
        return False
    return True

def actions(state):
    farmer = state[0]
    for i in range(4):  # 0 = farmer alone, otherwise farmer takes item i
        if state[i] != farmer:
            continue
        new = list(state)
        new[0] = "R" if farmer == "L" else "L"
        if i:
            new[i] = new[0]
        new = tuple(new)
        if safe(new):
            yield ("alone" if i == 0 else ITEMS[i]), new

start, goal = ("L",) * 4, ("R",) * 4
frontier, seen = deque([(start, [])]), {start}
while frontier:
    state, path = frontier.popleft()
    if state == goal:
        print(len(path), "crossings:", path)
        break
    for move, nxt in actions(state):
        if nxt not in seen:
            seen.add(nxt)
            frontier.append((nxt, path + [move]))
print("States explored:", len(seen))

Output

7 crossings: ['goat', 'alone', 'tiger', 'goat', 'grass', 'alone', 'goat']
States explored: 10

Try it yourself

Across the river

A farmer must ferry a goat, a tiger and a bundle of grass across a river; the boat carries the farmer and one item.

Formulate a problem

Put the formulation steps in order.

  1. 1List actions and their results
  2. 2Write the goal test
  3. 3Set the initial state
  4. 4Define what a state contains
  5. 5Choose the path cost

Common mistakes

  • Putting irrelevant details into the state.
  • Forgetting constraints, so the search finds illegal solutions.
  • Choosing a path cost that does not match the real goal.

Check yourself

Question 1

1. Which is NOT part of a problem formulation?

Question 2

2. What is the branching factor?

Question 3

3. Why do search algorithms generate states as they go?

Summary

  • Formulation specifies initial state, actions, transitions, goal test and path cost.
  • The state space is the graph of reachable states; good abstraction keeps it small.
  • Branching factor and depth determine how hard search will be.

Finished reading?

Sources: Russell and Norvig, Artificial Intelligence: A Modern Approach (4th edition) · UC Berkeley CS188: Introduction to Artificial Intelligence