Vacuum Cleaner World: Agents, Percepts and Rationality

The smallest AI problem there is — eight states, three actions. Used to define what an agent is, what makes one rational, and what happens when it can't see the whole world.

Two rooms. Each is either dirty or clean. A vacuum cleaner sits in one of them. It can move Left, move Right, or Suck.

That’s the entire problem. Eight states. You could solve it on a napkin.

So why does it open the agents chapter of every AI textbook? Because its smallness is the point — with the search made trivial, everything else becomes visible. This is the problem that defines what an agent is, what makes one rational, and what changes when the agent can’t perceive the whole world.

The problem

State representation

Three facts:

$\text{state} = (\text{position},\; \text{dirtyA},\; \text{dirtyB})$

state = ('A', True, True)     # vacuum in A, both rooms dirty
goal  = lambda s: not s[1] and not s[2]

State-space size: $2 \text{ positions} \times 2 \times 2 = 8$ .

Eight. You can draw every single one, and every transition between them:

The longest optimal solution from any state is 3 actions. BFS finds it after looking at a handful of nodes. As a search problem, it’s over before it starts.

What this problem is actually for: defining an agent

An agent is anything that perceives its environment through sensors and acts on it through actuators. The vacuum world makes each part concrete enough to write down.

PEAS: specifying the task

Before you can build an agent, you specify the task environment with four things — Performance measure, Environment, Actuators, Sensors:

	Vacuum world
Performance	+1 per square cleaned per time step; −1 per movement
Environment	Two squares, each dirty or clean
Actuators	Left, Right, Suck
Sensors	Location sensor, dirt sensor (current square only)

Look closely at the performance measure. “+1 per clean square per time step” and “+1 per square cleaned” are different specifications, and they produce different agents. Under the second, an agent that dumps dirt back down and re-cleans it scores infinitely well.

This is the specification-gaming problem, in miniature. Get the performance measure wrong and a perfectly rational agent will optimise exactly what you wrote instead of what you meant. It’s the same failure that shows up in RL reward hacking and in LLM systems that satisfy the letter of a prompt while missing its intent. Vacuum world is where you first meet it, and it’s easier to see here than anywhere else.

Four agent architectures, on one problem

The vacuum world’s real value is that you can implement every classical agent type on it and compare them directly.

1. Simple reflex agent

Look at the current percept. Act. No memory whatsoever.

def reflex_agent(percept):
    location, status = percept
    if status == 'Dirty':
        return 'Suck'
    return 'Right' if location == 'A' else 'Left'

This is optimal for the fully-observable, two-room world. Four lines. It never needs to know anything about the past.

Its failure mode appears the instant you remove a sensor. Take away the location sensor and the agent only knows Dirty or Clean. Now if it perceives Clean it has no basis to choose Left or Right — and a deterministic reflex agent will pick the same one forever, potentially oscillating or getting stuck in a corner of the world it never leaves.

The fix is a randomised reflex agent: when you perceive Clean, move in a random direction. It’s inelegant, but randomisation genuinely rescues an agent that lacks the state to do better — and that’s a real technique, not a hack.

2. Model-based reflex agent

Keep an internal model of the world, updated from percepts.

class ModelAgent:
    def __init__(self):
        self.model = {'A': 'Unknown', 'B': 'Unknown'}

    def act(self, percept):
        location, status = percept
        self.model[location] = status           # update the model

        if status == 'Dirty':
            self.model[location] = 'Clean'
            return 'Suck'
        if all(v == 'Clean' for v in self.model.values()):
            return 'NoOp'                        # done — stop moving, stop
                                                 # losing points to the −1 penalty
        return 'Right' if location == 'A' else 'Left'

The NoOp is the whole point. A reflex agent shuttles between rooms forever, bleeding movement penalties. A model-based agent knows the world is clean and stops. Memory converts an infinite score loss into a finite one.

3. Goal-based agent

Store an explicit goal, and search for a plan to reach it. This is where the state-space machinery from the rest of these pages comes back:

from collections import deque

def plan(state):
    """BFS to a fully-clean state. Returns the action sequence."""
    frontier = deque([(state, [])])
    seen = {state}
    while frontier:
        (pos, a_dirty, b_dirty), path = frontier.popleft()
        if not a_dirty and not b_dirty:
            return path
        options = []
        if pos == 'A':
            options.append((('B', a_dirty, b_dirty), 'Right'))
            if a_dirty: options.append((('A', False, b_dirty), 'Suck'))
        else:
            options.append((('A', a_dirty, b_dirty), 'Left'))
            if b_dirty: options.append((('B', a_dirty, False), 'Suck'))
        for nxt, action in options:
            if nxt not in seen:
                seen.add(nxt)
                frontier.append((nxt, path + [action]))
    return []

Overkill for two rooms. Essential for twenty.

4. Utility-based agent

Goals are binary — clean or not. Utility lets you rank outcomes: this plan scores 8, that one scores 6, take the first. That’s what you need when there are trade-offs — battery life against cleanliness, speed against thoroughness — and it’s the bridge from classical AI to decision theory and reinforcement learning.

Agent type	Memory	Handles unseen dirt?	Optimal here?	Lines of code
Simple reflex	none	❌	✅ (if fully observable)	4
Randomised reflex	none	✅ eventually	❌ inefficient	5
Model-based	world model	✅	✅ + knows when to stop	12
Goal-based	model + goal	✅	✅ + optimal plans	25
Utility-based	model + utility fn	✅	✅ + handles trade-offs	40+

Partial observability: the interesting version

Remove the sensors entirely. The agent knows the rules but perceives nothing. Can it still guarantee a clean world?

Yes — and the technique is worth knowing. When you can’t observe the state, you reason about the set of states you might be in. That set is called a belief state, and searching over belief states is exactly the same algorithm you’ve been using, one level up.

[Suck, Right, Suck] cleans both rooms starting from any of the eight states, with no sensors at all. That’s a conformant plan — a fixed action sequence that succeeds regardless of what you can’t see.

The size numbers are the punchline: 8 world states become $2^8 = 256$ possible belief states. In general, belief-state search is exponentially larger than the underlying problem. This is why partial observability is hard, and why POMDPs (partially observable Markov decision processes) are computationally brutal in anything but toy domains.

Environment properties, illustrated

Vacuum world is the standard vehicle for classifying environments, because you can toggle each property one at a time and watch what breaks:

Property	Vacuum world	If you flip it
Fully observable	✅ (with both sensors)	Belief states; exponential blow-up
Deterministic	✅ Suck always cleans	Suck sometimes fails → contingency plans
Episodic	❌ sequential — actions have lasting effects	Episodic = each decision independent
Static	✅ dirt doesn’t appear mid-decision	Dynamic → must decide under time pressure
Discrete	✅ two rooms, three actions	Continuous → robot with real coordinates
Single agent	✅	Two vacuums → coordination or competition

Now compare against a real robot vacuum: partially observable (it can’t see the whole house), stochastic (wheels slip), sequential, dynamic (the cat moves, someone spills something), continuous (real position and heading), and increasingly multi-agent.

Every one of those flips is a step from the toy to the real thing, and each adds a subfield: SLAM for the observability, probabilistic robotics for the stochasticity, real-time planning for the dynamism. Vacuum world is the fixed point you measure all that distance from.

Full working code

import random
from collections import deque

ACTIONS = ['Left', 'Right', 'Suck']


class Environment:
    def __init__(self, pos='A', dirt=None):
        self.pos = pos
        self.dirt = dirt if dirt is not None else {'A': True, 'B': True}
        self.score = 0
        self.steps = 0

    def percept(self):
        return (self.pos, 'Dirty' if self.dirt[self.pos] else 'Clean')

    def execute(self, action):
        if action == 'Suck':
            self.dirt[self.pos] = False
        elif action == 'Left':
            self.pos = 'A'; self.score -= 1        # movement costs
        elif action == 'Right':
            self.pos = 'B'; self.score -= 1
        # performance measure: +1 per clean square, per time step
        self.score += sum(1 for clean in self.dirt.values() if not clean)
        self.steps += 1

    def is_clean(self):
        return not any(self.dirt.values())


def simple_reflex(percept):
    location, status = percept
    if status == 'Dirty':
        return 'Suck'
    return 'Right' if location == 'A' else 'Left'


class ModelBased:
    def __init__(self):
        self.model = {'A': None, 'B': None}

    def __call__(self, percept):
        location, status = percept
        self.model[location] = (status == 'Clean')
        if status == 'Dirty':
            self.model[location] = True
            return 'Suck'
        if all(self.model.values()):
            return 'NoOp'
        return 'Right' if location == 'A' else 'Left'


def run(agent, steps=8, **env_kwargs):
    env = Environment(**env_kwargs)
    trace = []
    for _ in range(steps):
        action = agent(env.percept())
        trace.append(f'{env.percept()} → {action}')
        if action != 'NoOp':
            env.execute(action)
        else:
            env.steps += 1
            env.score += sum(1 for c in env.dirt.values() if not c)
    return trace, env.score


def conformant_plan():
    """A plan that works from ANY start state, with no sensors at all."""
    belief = {(p, a, b) for p in 'AB' for a in (True, False) for b in (True, False)}
    frontier = deque([(frozenset(belief), [])])
    seen = {frozenset(belief)}

    def step(state, action):
        p, a, b = state
        if action == 'Left':  return ('A', a, b)
        if action == 'Right': return ('B', a, b)
        return (p, False, b) if p == 'A' else (p, a, False)

    while frontier:
        belief, path = frontier.popleft()
        if all(not a and not b for _, a, b in belief):
            return path
        for action in ACTIONS:
            nxt = frozenset(step(s, action) for s in belief)
            if nxt not in seen:
                seen.add(nxt)
                frontier.append((nxt, path + [action]))
    return None


if __name__ == '__main__':
    for name, agent in [('simple reflex', simple_reflex),
                        ('model-based ', ModelBased())]:
        trace, score = run(agent)
        print(f'\n{name}  score after 8 steps: {score}')
        for line in trace:
            print('   ', line)

    print(f'\nConformant plan (no sensors): {conformant_plan()}')

Running it, the model-based agent scores noticeably higher — not because it cleans faster (both finish in the same two Sucks) but because it stops moving once it knows the job is done, while the reflex agent keeps paying the −1 movement cost forever.

Conformant plan (no sensors): ['Suck', 'Right', 'Suck']

Why this problem matters

Vacuum world contributes nothing to search algorithms — the space is eight states. What it contributes is the framework for thinking about agents, and that framework is what the rest of AI is built on:

The agent/environment split is the same abstraction reinforcement learning uses. Swap “percept” for “observation” and “action” for “action” and you have the RL loop exactly; the Gym API is this diagram in code.
The agent hierarchy — reflex → model-based → goal-based → utility-based — is a genuinely useful design ladder. Most engineering failures come from building one rung lower than the problem needs: a reflex agent where the world requires memory.
Belief states are how every robot handles uncertainty, from particle-filter localisation to Kalman filters.
The performance measure is the specification problem, and it’s the hardest part of deploying any autonomous system. Vacuum world shows in eight states what takes millions of dollars to learn in production.

The practical version of that last point: when you build an agent — a robot, a trading system, an LLM tool-user — write the performance measure down first, and then look for how a clever agent could satisfy it while defeating your intent. The vacuum that dumps dirt to re-clean it is a joke at two rooms. At scale it isn’t.

Where to go next

Problem Solving with AI: The State-Space Framework — the shared vocabulary
Monkey and Banana — goal-based reasoning in a slightly bigger world
Water Jug Problem — the other tiny state space
The Agentic Loop — the same agent architecture, applied to LLM tool use