Skip to content
learn
  1. Learn
  2. Artificial Intelligence
  3. Intelligent Agents and Problem Solving by Search

AI AI-01.02

Problem formulation and state spaces

Turn a problem into search: states, actions, a transition model, a goal test and path costs, with route finding and the 8-puzzle as examples.

Beginner 10 min Last reviewed

The big idea

A goal-based agent needs to find a sequence of actions that gets it from where it is to where it wants to be. Before any clever algorithm can help, the problem has to be written down in a precise form: what situations can exist, what moves are possible, what each move does, how we know we have arrived, and what each move costs. This step is called problem formulationWriting a problem as an initial state, actions, a transition model, a goal test and a step cost, so that a search algorithm can solve it., and it is where most of the intelligence in classical AI really lives.

Once a problem is formulated, every possible situation becomes a point, and every move becomes a line between points. Solving the problem means finding a path through that graph. The same search algorithms then work for road trips, sliding puzzles, robot arms and delivery schedules.

Think of planning a trip with a paper map. The towns are the states, the roads are the actions, the distances are the costs, and "am I in Kingsport?" is the goal test. You have formulated the problem the moment you unfold the map.

How it works

Step 1: The five ingredients

A search problem is defined by:

  1. Initial state: where the agent starts. In Ashford.
  2. Actions: what can be done in a given state. From Ashford: drive to Bexley, Crane or Dunmore.
  3. Transition model: the state each action leads to. Driving to Crane from Ashford results in being in Crane.
  4. Goal test: whether a state is a goal. Is this Kingsport?
  5. Path cost: a number for each step, summed along a path. Kilometres driven.

A solutionA sequence of actions leading from the initial state to a state that passes the goal test. is a sequence of actions from the initial state to a goal; an optimal solutionA solution with the lowest path cost among all solutions. has the lowest total cost.

Step 2: The state space is a graph

The initial state, actions and transition model together define the state spaceThe set of all states reachable from the initial state, connected by the actions between them. Usually drawn as a graph.: every reachable state and how they connect. For route finding it is literally the road map:

A road map as a state space, from Ashford to Kingsport Eleven towns connected by roads labelled with distances in kilometres. Ashford, the start, glows green on the left; Kingsport, the goal, glows red on the right. Roads include Ashford to Crane 140, Crane to Glenn 80, Glenn to Juniper 97 and Juniper to Kingsport 101. 75 140 118 71 151 99 80 111 160 146 97 138 211 101 Ashford Bexley Elmwood Dunmore Hollis Crane Fairview Glenn Ivy Juniper Kingsport Figure 1. Each town is a state and each road an action with a cost in km. Solving the problem means finding a path from Ashford (green) to Kingsport (red). The next lesson searches this exact map.

The search algorithm never needs the whole map drawn in advance. It only needs to ask "what are the actions here, and where do they lead?" and it builds the part of the graph it explores as it goes. That matters because many state spaces are far too large to list.

Step 3: The same recipe, a puzzle

The 8-puzzle is a 3 by 3 board with eight numbered tiles and one gap. A state is an arrangement of the tiles. The actions slide a tile into the gap (or, equivalently, move the gap up, down, left or right). Each move costs 1, and the goal test checks for the solved order.

The first moves of an 8-puzzle search The start state has the gap in the centre. Four moves lead to four new states: gap up, down, left and right. Moving the gap down and then right reaches the solved state 1 2 3, 4 5 6, 7 8, gap. 1 _ 3 / 4 2 6 / 7 5 8 gap up 1 2 3 / 4 5 6 / 7 8 _ gap right: goal 1 2 3 / 4 5 6 / 7 _ 8 gap down 1 2 3 / _ 4 6 / 7 5 8 gap left 1 2 3 / 4 6 _ / 7 5 8 gap right 1 2 3 / 4 _ 6 / 7 5 8 gap in the middle Figure 2. Rows are separated by slashes and _ is the gap. From the start, four moves are possible; moving the gap down and then right solves this puzzle in two moves.

The 8-puzzle has 181,440 reachable states, which a computer can search completely. The 15-puzzle (4 by 4) has over 10 trillion, and the 24-puzzle far more, which is why the choice of search algorithm and of a good heuristic matters so much in the coming lessons.

Step 4: Choosing the right abstraction

A good formulation leaves out everything that does not affect the decision. A route planner does not track the radio station, the weather inside the car or each turn of the steering wheel; it abstracts the trip into towns and roads. Too little detail and the solution cannot be carried out; too much and the state space explodes. Picking that level is a design skill, much like choosing the right components in system design.

Going deeper

Following actions blindly can revisit the same state through different paths, or go round in circles: Ashford to Bexley and back to Ashford. Tree search ignores this and may waste enormous effort. Graph search remembers which states it has already explored, an explored setThe set of states a graph search has already expanded, so it never expands them again., at the cost of memory. You will see both in Uninformed search: BFS, DFS, uniform cost .

Many real problems fit

Delivery route planning, airline crew scheduling, robot motion, theorem proving, chip layout and even planning the steps of an AI agent's task can be framed as states, actions, transitions, goals and costs. When the state space is enormous, the same framing is used with smarter algorithms, from A* to local search to constraint solvers later in this module.

Trade-offs

OptionWins whenLoses when
Coarse abstraction (towns and roads) Planning over large areas quickly with few states Details needed to actually carry out the plan, such as lanes and turns
Fine abstraction (every street and turn) Plans that can be executed directly Search time: the state space becomes huge
Hierarchical (coarse first, then refine) Real navigation systems: plan highways, then streets Simplicity, and sometimes optimality across levels

Common mistakes

  • Leaving costs out. Without a path cost you can find a solution but not the best one.
  • Including irrelevant detail in the state, which multiplies the number of states for no benefit.
  • Forgetting that actions depend on the state. Not every move is legal everywhere.
  • Writing a goal test that is too loose or too strict, so the search stops early or never stops.

Check yourself

  1. Which is NOT one of the parts of a search problem?

    Show answer

    D. Learning rate A search problem needs an initial state, actions, a transition model, a goal test and a path cost. Learning rates belong to training models.

  2. In route finding, what is a state?

    Show answer

    B. Being in a particular town The state is the agent's situation: which town it is in. Roads are actions.

  3. What makes a solution optimal?

    Show answer

    B. It has the lowest path cost of all solutions Optimal means cheapest according to the path cost.

  4. Why does graph search keep an explored set?

    Show answer

    B. To avoid expanding the same state twice Remembering explored states prevents loops and repeated work, at the cost of memory.

Recap

  • A search problem has an initial state, actions, a transition model, a goal test and path costs.
  • Together they define a state space: a graph of states connected by actions.
  • A solution is a path to a goal; an optimal solution is the cheapest one.
  • The same framing fits route finding, puzzles, scheduling and planning.
  • Choose the abstraction carefully: enough detail to act, little enough to search.

Get new lessons by email

Get new posts on backend and AI internals. No spam, unsubscribe anytime.

Your email is only used to send new posts. Privacy