The Block World Problem: Planning with STRIPS

A robot arm stacking blocks — the problem that gave us predicate representation, the STRIPS planner, goal stacks, and the Sussman anomaly that broke naive planning for a decade.

A table. Some cubes. A robot arm that can pick up one block at a time. Get the blocks into a target arrangement.

Block world looks even simpler than the 8-puzzle, and in one sense it is. But it’s on this problem that AI learned something the sliding-tile puzzles never taught: that sub-goals interfere with each other, and that a planner which treats them independently will confidently produce a plan that doesn’t work.

That discovery — the Sussman anomaly — is the reason planning is its own field.

The problem

Rules.

The arm holds at most one block.
You can only pick up a block that has nothing on top of it.
You can put a block on the table, or on top of another clear block.
The table is infinitely large — there’s always room to put something down.

State representation: predicates, not grids

Here’s where block world departs from the 8-puzzle. Instead of a fixed array of cells, describe the world by what is true:

Predicate	Meaning
`ON(x, y)`	Block `x` is directly on top of block `y`
`ONTABLE(x)`	Block `x` rests on the table
`CLEAR(x)`	Nothing is on top of `x`
`HOLDING(x)`	The arm is holding `x`
`HANDEMPTY`	The arm holds nothing

Our initial state is the set:

{ ON(C, A), ONTABLE(A), ONTABLE(B), CLEAR(C), CLEAR(B), HANDEMPTY }

And the goal:

{ ON(A, B), ON(B, C) }

Two things to notice, and both matter enormously:

1. The goal is partial. It says nothing about ONTABLE(C), CLEAR(A), or where the arm is. Any state satisfying those two facts counts as a goal. This is very different from the 8-puzzle, where the goal is one exact board.

2. Facts must stay consistent. If you assert ON(C, A), you had better not also have CLEAR(A). Bugs in block-world code are almost always a forgotten delete: you added ON(A, B) but never removed CLEAR(B).

In Python, use a frozenset of tuples so states stay hashable:

initial = frozenset({
    ('ON', 'C', 'A'), ('ONTABLE', 'A'), ('ONTABLE', 'B'),
    ('CLEAR', 'C'), ('CLEAR', 'B'), ('HANDEMPTY',),
})

goal = frozenset({('ON', 'A', 'B'), ('ON', 'B', 'C')})

The four operators, STRIPS-style

STRIPS (STanford Research Institute Problem Solver, 1971) introduced a format that every planner since has used. Each operator has three lists:

Preconditions — what must be true to apply it
Add list — facts that become true
Delete list — facts that stop being true

Look at the symmetry: PUTDOWN is exactly PICKUP with add and delete swapped, and UNSTACK is exactly STACK reversed. Every block-world action is reversible, which means the state space is an undirected graph — and cycles are everywhere, so you must track visited states.

Applying an operator is one line:

def apply(state, op):
    return (state - op.delete) | op.add

The state space

For $n$ blocks the number of arrangements grows fast:

Blocks	Distinct configurations
1	1
2	3
3	13
4	73
5	501
6	4,051
10	58,941,091

The counting sequence is $a_n = n \cdot a_{n-1} + \dots$ — it’s the number of ways to partition $n$ blocks into ordered stacks, and it grows faster than $n!$ . Three blocks give you 13 states, which is small enough to draw the whole graph. Ten blocks and you’re already in the tens of millions.

Include the arm’s state (empty, or holding one of $n$ blocks) and multiply further.

The Sussman anomaly

This is the famous part. Our problem — ON(C,A), B on the table, goal ON(A,B) ∧ ON(B,C) — is the Sussman anomaly, and it defeats the obvious planning strategy.

The obvious strategy is: solve the sub-goals one at a time.

Neither order works. Achieving one sub-goal destroys the conditions the other needs. Early planners (which committed to a linear ordering of sub-goals) either produced a wrong plan or a needlessly long one.

The correct plan requires interleaving the sub-goals:

#	Action	Why
1	`UNSTACK(C, A)`	C is in the way; A must be clear
2	`PUTDOWN(C)`	Park C on the table
3	`PICKUP(B)`	B is clear and on the table
4	`STACK(B, C)`	✅ achieves `ON(B, C)`
5	`PICKUP(A)`	A is now clear and on the table
6	`STACK(A, B)`	✅ achieves `ON(A, B)`

Six actions. Notice that step 4 achieves one sub-goal and step 6 the other, but steps 1–3 serve both — they’re the shared preparation neither sub-goal would have planned for on its own.

The lesson generalises far beyond blocks: you cannot plan sub-goals in isolation when they share resources. The fix, developed through the 1970s and 80s, was partial-order planning — build a plan as a set of actions with ordering constraints only where they’re genuinely needed, and commit to a total order at the very end.

Solving it as ordinary search

You don’t strictly need a planner. Block world is a state space like any other, so BFS finds the optimal plan directly:

from collections import deque
from itertools import permutations

BLOCKS = ['A', 'B', 'C']


def actions(state):
    """Yield (name, new_state) for every legal action from `state`."""
    holding = next((f[1] for f in state if f[0] == 'HOLDING'), None)

    if holding is None:
        for b in BLOCKS:
            if ('CLEAR', b) not in state:
                continue
            if ('ONTABLE', b) in state:
                # PICKUP(b)
                new = (state - {('CLEAR', b), ('ONTABLE', b), ('HANDEMPTY',)}) \
                      | {('HOLDING', b)}
                yield f'PICKUP({b})', frozenset(new)
            else:
                under = next(f[2] for f in state if f[0] == 'ON' and f[1] == b)
                # UNSTACK(b, under)
                new = (state - {('ON', b, under), ('CLEAR', b), ('HANDEMPTY',)}) \
                      | {('HOLDING', b), ('CLEAR', under)}
                yield f'UNSTACK({b},{under})', frozenset(new)
    else:
        # PUTDOWN(holding)
        new = (state - {('HOLDING', holding)}) \
              | {('CLEAR', holding), ('ONTABLE', holding), ('HANDEMPTY',)}
        yield f'PUTDOWN({holding})', frozenset(new)

        for y in BLOCKS:
            if y != holding and ('CLEAR', y) in state:
                # STACK(holding, y)
                new = (state - {('HOLDING', holding), ('CLEAR', y)}) \
                      | {('ON', holding, y), ('CLEAR', holding), ('HANDEMPTY',)}
                yield f'STACK({holding},{y})', frozenset(new)


def plan(start, goal):
    """BFS for the shortest action sequence reaching a state satisfying `goal`."""
    if goal <= start:
        return []
    frontier = deque([(start, [])])
    seen = {start}
    while frontier:
        state, path = frontier.popleft()
        for name, nxt in actions(state):
            if nxt in seen:
                continue
            if goal <= nxt:                    # subset test — partial goal
                return path + [name]
            seen.add(nxt)
            frontier.append((nxt, path + [name]))
    return None


if __name__ == '__main__':
    initial = frozenset({
        ('ON', 'C', 'A'), ('ONTABLE', 'A'), ('ONTABLE', 'B'),
        ('CLEAR', 'C'), ('CLEAR', 'B'), ('HANDEMPTY',),
    })
    goal = frozenset({('ON', 'A', 'B'), ('ON', 'B', 'C')})

    for i, step in enumerate(plan(initial, goal), 1):
        print(f'{i}. {step}')

Output:

1. UNSTACK(C,A)
2. PUTDOWN(C)
3. PICKUP(B)
4. STACK(B,C)
5. PICKUP(A)
6. STACK(A,B)

The Sussman anomaly, solved in six actions, by a planner that never heard of sub-goals. That’s the point: treating the goal as a subset test over whole states sidesteps the interference problem entirely. The cost is that BFS explores the full space, which is fine for 3 blocks and hopeless for 15.

The one subtle line is if goal <= nxt. Because the goal is partial, you test subset, not equality. Get this wrong — write nxt == goal — and your planner will search forever, because no reachable state ever equals a two-element set.

Goal-stack planning (how STRIPS actually did it)

The historical approach uses a stack:

Push the whole goal onto a stack.
Pop the top item.
- If it’s a compound goal (a set), push each sub-goal, then push the compound back underneath so you re-check it at the end.
- If it’s a single goal already true, discard it.
- If it’s a single goal not yet true, find an operator whose add-list contains it. Push that operator, then push its preconditions.
- If it’s an operator whose preconditions all hold, apply it and record it in the plan.
Repeat until the stack is empty.

Step 2’s “push the compound back underneath” is the anomaly patch: after achieving the sub-goals individually, the planner re-verifies the conjunction, notices one got clobbered, and fixes it. It produces a correct plan, just not always the shortest one — on the Sussman anomaly, naïve goal-stack planning gives a 12-action plan where 6 suffice.

Why block world matters

It’s easy to dismiss as toy — Terry Winograd’s SHRDLU (1970) took natural language commands about a block world and executed them, and for a while it looked like AI was nearly solved. It wasn’t; the approach didn’t generalise past the blocks. That over-promise is part of the story of the first AI winter.

But the representation survived and won:

PDDL (Planning Domain Definition Language), the standard used by every modern automated planner, is STRIPS with better syntax.
NASA’s Remote Agent planned spacecraft operations on Deep Space 1 in 1999 using exactly this precondition/add/delete formalism.
Robot manipulation — a warehouse arm choosing a grasp order is block world with real friction and uncertainty layered on.
Build systems and CI pipelines are planning problems: each task has preconditions (its dependencies), and effects (the artefacts it produces). make is a planner.
LLM agent frameworks are rediscovering this right now: an agent choosing tools has preconditions (“I need the file path before I can read it”) and effects, and hits the Sussman anomaly whenever two sub-tasks share state.

The enduring lesson is the anomaly itself: a plan is not the concatenation of solutions to its parts.

Where to go next

Problem Solving with AI: The State-Space Framework — states, operators, search
Monkey and Banana Problem — the other classic planning problem
The 8-Puzzle — explicit state representation instead of predicates