State Space Representation in Artificial Intelligence

In the previous post, we explored how intelligent agents solve problems by searching through a series of actions to reach a desired goal. We learned how a problem-solving agent works by formulating a goal, creating a problem definition, searching for a solution, and executing the necessary steps. Building on that, this post will dive deeper into one of the foundational models used in AI problem solving — State Space Representation.

What is State Space Representation?

State space representation is a fundamental concept in Artificial Intelligence, particularly in problem-solving and search techniques.

• The state space of a problem is the set of all possible states that can be reached from the initial state by applying a sequence of actions.
• It forms a directed graph, where:
  • Nodes represent the states.
  • Edges represent the actions taken to move from one state to another.
• A solution is a path from the initial state to a goal state, passing through a series of valid intermediate states.

Why Use State Space Representation?

Using this approach helps us formally define and visualize the problem-solving process. It simplifies the tracking of how an agent moves through the environment, what actions are available, and how success is determined.

It includes four key components:

1. Initial State – Where the agent begins.
2. Successor Function – Defines the legal actions and resulting states.
3. Goal Test – Checks if the goal has been achieved.
4. Path Cost – The total cost incurred to reach the goal from the initial state.

Example 1: Vacuum World Problem (with Solution)

Problem: A vacuum cleaner is in a two-room world (Left and Right), and each room may be clean or dirty. The goal is to clean both rooms.

🔸 State Space Representation:

Each state can be represented as a combination of:

• The location of the vacuum: L (Left) or R (Right)
• The status of Left room: Clean or Dirty
• The status of Right room: Clean or Dirty

For example: (L, Dirty, Clean) means the vacuum is in the left room, the left room is dirty, and the right room is clean.

🔸 Initial State:

Let’s assume: (L, Dirty, Dirty)

🔸 Actions:

• Clear – cleans the current room
• Move Right or Move Left – moves the vacuum

🔸 Goal State:

All rooms are clean: e.g., (R, Clean, Clean) or (L, Clean, Clean)

🔸 Solution Path:

1. Start at (L, Dirty, Dirty)
2. Action: Clear → (L, Clean, Dirty)
3. Action: Move Right → (R, Clean, Dirty)
4. Action: Clear → (R, Clean, Clean)

✔ Goal achieved in 3 steps.

Example 3: Water Jug Problem

Problem: You are given:

• A 4-liter jug (Jug A)
• A 3-liter jug (Jug B)

Goal: Measure exactly 2 liters in Jug A.

🔸 State Representation:

Each state is a pair (A, B) representing the water in each jug.

🔸 Initial State:

(0, 0) — both jugs are empty

🔸 Goal State:

(2, _) — Jug A contains 2 liters

🔸 Actions (Successor Function):

• Fill a jug: Fill A or B
• Empty a jug: Empty A or B
• Pour water from one jug to another

🔸 Solution Path (Optimal Steps):

1. Fill Jug B → (0, 3)
2. Pour B → A → (3, 0)
3. Fill Jug B again → (3, 3)
4. Pour B → A → (4, 2) → Jug A is full, B has 2 liters
5. Empty Jug A → (0, 2)
6. Pour B → A → (2, 0)

✔ Goal achieved: Jug A has exactly 2 liters in 6 steps

In this post, we explored State Space Representation — a formal way to model AI problems and solve them using search. By breaking down problems into states, actions, and goals, we can clearly define paths and evaluate performance.

We demonstrated this using three classic AI problems:

• The Vacuum World (cleaning rooms)
• The 8-Tile Puzzle (number arrangement)
• The Water Jug Problem (measuring quantities)

These models are the foundation for designing AI agents that can plan and make decisions effectively.