Problem Formulation and State-Space Representation — Beginner-Friendly Notes

1. Why Formulation Is Step Zero

Before you can search for a solution, you must describe the problem precisely so a computer can reason about it. A vague problem ("clean the house") is not searchable; a formulated one is.

2. The Five Parts of a Formulation (memorise)

State: a configuration of the world at one moment (e.g., robot at cell A, dirt in B).
Initial state: where we start.
Actions / Operators: what the agent can do in a given state (e.g., moveLeft, suck).
Transition model / Successor function: Result(state, action) → new_state — what happens after an action.
Goal test: how to recognise when we are done (explicit set or property: "all dirt gone").
Path cost: numeric cost of a path (usually $g(n) = sum of step costs$ ) — needed to pick best solution, not just any.

Some textbooks list 5 (merging transition + actions). Examiners accept either if you mention all ideas.

3. State Space in One Picture

Initial State
    |  --action-->  State 1
    |  --action-->  State 2
                    |  --action--> Goal State (passes goal test)

State space: all states reachable from initial via any action sequence.
Search tree/graph: how search explores that space (Module 2 next topics).
Solution: a path from initial to goal. Optimal solution = lowest path cost.

4. Worked Example — Vacuum (2 rooms)

States: location ∈ {A,B} × dirt_A ∈ {clean,dirty} × dirt_B ∈ {clean,dirty} → $2 \cdot 2 \cdot 2 = 8$ states.
Initial: {A, dirty, dirty}
Actions: Left, Right, Suck (if applicable)
Transition: Suck in dirty room → that room becomes clean; Right from A → at B.
Goal test: dirt_A=clean AND dirt_B=clean
Step cost: 1 per action → path cost = number of actions.

5. Bigger Example — 8-Puzzle

State: arrangement of 8 tiles + blank on 3×3.
Actions: slide blank Up/Down/Left/Right.
Goal test: tiles in order.
Branching factor $b≈3$ , number of states $9! /2 = 181,440$ — small enough to search, large enough to need heuristics (A*).

6. Abstraction — The Hidden Skill

You must abstract away irrelevant detail:

For route-finding, state = intersection, ignore fuel level if not needed.
Real world has infinite detail; good formulation keeps only what affects decision.

7. What Makes a Good Formulation

Complete: goal reachable via actions.
Minimal: no extra state that blows up search.
Measurable: step cost reflects real cost (distance, time, energy).

8. One-Line Summary to Write in Exam

Problem formulation defines states, initial state, actions with transition model, goal test and path cost so the task becomes searching a state space for a lowest-cost path from start to goal.

9. Quick Self-Check

Formulate "water jug" (4L and 3L jugs to get 2L) using the 5 parts.
Why is path cost needed if you already have a goal test?
How many states does a 2-room vacuum with 3 dirt levels per room have?

Problem formulation and state-space representation