AI AI-02.06
Classical planning
STRIPS and PDDL, state-space and plan-space planning, the Sussman anomaly, hierarchical task networks, and what they teach about LLM agents that plan.
The big idea
Search, in Uninformed search: BFS, DFS, uniform cost , treated states as black boxes: a route planner only needed to know which towns connect. Many real tasks have states with internal structure. A warehouse robot's world is a set of facts (this box is on that shelf, the gripper is empty); its actions change a few of those facts and leave the rest alone. Classical planningFinding a sequence of actions that turns an initial state into one satisfying a goal, where states are sets of facts and actions are described by preconditions and effects. exploits that structure: describe each action by what must be true before it and what it changes, and let a general-purpose planner find the sequence.
Think of a recipe card versus a cooking video. The video shows one specific run. The card says what each step needs and what it produces ("whisk the eggs: needs eggs and a bowl; gives beaten eggs"), so a cook can reorder steps, skip ones already done, and adapt when the pantry differs. Planning languages are recipe cards for actions. Write them once, and a planner can solve any problem in that domain, from three blocks to a fleet of robots, without new code.
How it works
Step 1: STRIPS, actions as preconditions and effects
The STRIPSA classic action representation from 1971: each action has preconditions that must hold and effects given as an add list and a delete list of facts. representation, introduced in 1971 for a mobile robot called Shakey, describes the world as a set of true facts. Everything not listed is false: the closed-world assumption. Each action has three parts:
- Preconditions: facts that must hold for the action to apply.
- Add list: facts the action makes true.
- Delete list: facts the action makes false.
Everything else stays the same, which neatly sidesteps the frame problem from Knowledge representation . In the blocks world, the classic test domain, blocks sit on a table or on each other, and one action moves a clear block:
Step 2: PDDL, the standard language
PDDLPlanning Domain Definition Language: the standard language for classical planning problems, split into a domain file (types, predicates, actions) and a problem file (objects, initial state, goal). (Planning Domain Definition Language) is the modern standard, used by planning competitions since 1998. It separates the domain, the predicates and action schemas, from the problem, the objects, initial state and goal:
(:action move
:parameters (?x ?from ?to)
:precondition (and (on ?x ?from) (clear ?x) (clear ?to))
:effect (and (on ?x ?to) (clear ?from)
(not (on ?x ?from)) (not (clear ?to))))
(:init (on C A) (on A table) (on B table) (clear C) (clear B))
(:goal (and (on A B) (on B C)))
The same domain file serves every blocks problem; only the problem file changes. Off-the-shelf planners read both and return a plan.
Step 3: Planning as state-space search
With states as fact sets and actions as STRIPS operators, planning is search ( Uninformed search: BFS, DFS, uniform cost ). Forward (progression) search starts at the initial state and applies any action whose preconditions hold. Backward (regression) search starts from the goal and asks which action could achieve one of its facts, and what must have held before it. Here is the plan for the problem above, one action at a time:
- move(C, A, table) C is clear, so it can be lifted off A and put on the table. Now A is clear too.
- move(B, table, C) B and C are both clear, so B goes on C. The goal fact on(B, C) is now true.
- move(A, table, B) A and B are clear, so A goes on B. Both goal facts hold: the plan is complete.
from collections import deque
from itertools import permutations
BLOCKS = "ABC"
# A state is a frozenset of facts: ("on", "C", "A"), ("clear", "B"), ...
def clear(b): # the table is always clear
return {("clear", b)} if b != "T" else set()
def actions():
"""STRIPS actions: (name, preconditions, add list, delete list)."""
for x, y, z in permutations(BLOCKS + "T", 3): # T is the table
if x == "T" or y == z:
continue
name = f"move({x}, {y}, {z})"
pre = {("on", x, y), ("clear", x)} | clear(z)
add = {("on", x, z)} | clear(y)
dele = {("on", x, y)} | clear(z)
yield name, pre, add, dele
ACTIONS = list(actions())
def plan(start, goal):
"""Breadth-first search through states: the shortest plan."""
frontier, seen, expanded = deque([(start, [])]), {start}, 0
while frontier:
state, steps = frontier.popleft()
expanded += 1
if goal <= state: # every goal fact holds
return steps, expanded
for name, pre, add, dele in ACTIONS:
if pre <= state: # preconditions hold
nxt = (state - dele) | add # apply the effects
if nxt not in seen:
seen.add(nxt)
frontier.append((nxt, steps + [name]))
# The Sussman anomaly: C sits on A; the goal is A on B and B on C.
start = frozenset({("on", "C", "A"), ("on", "A", "T"), ("on", "B", "T"),
("clear", "C"), ("clear", "B")})
goal = {("on", "A", "B"), ("on", "B", "C")}
steps, expanded = plan(start, goal)
print(f"{len(ACTIONS)} ground actions, expanded {expanded} states")
for i, s in enumerate(steps, 1):
print(f" {i}. {s}")Output
18 ground actions, expanded 13 states
1. move(C, A, T)
2. move(B, T, C)
3. move(A, T, B) The planner generates all 18 ground actions from one schema, then runs breadth-first search over fact sets. Note the three lines that do the work: an action applies when pre <= state, its result is (state - dele) | add, and the goal test is goal <= state (the goal only needs some facts to hold).
Step 4: Heuristics come for free
Breadth-first search is fine for three blocks and hopeless for thirty. Because actions are described declaratively, a planner can compute heuristics automatically for any domain. The classic trick is a relaxed problem ( Informed search and A* ): ignore every delete list. In the relaxed world facts only accumulate, so the problem is much easier, and the number of relaxed actions needed to reach the goal estimates the real distance. Planners such as FF ("Fast Forward") combine this heuristic with greedy or A*-style search and solve problems with huge state spaces. Planning can also be compiled into SAT ( Propositional logic ): "is there a plan of length ?" becomes a formula, and a SAT solver answers it.
Going deeper
The Sussman anomaly and plan-space planning
The goal above, , is the Sussman anomaly, and it embarrassed early planners. A planner that achieves one goal completely, then the other, fails whichever it picks first. Achieve first: clear C off A, put A on B. Now B is covered, so achieving means taking A off again. Achieve first: B goes onto C while C still sits on A, giving a tower B, C, A with A at the bottom. Now getting A onto B means dismantling the tower. The subgoals interact: a correct plan interleaves their steps, starting with a move that serves neither goal directly (C to the table).
Plan-space planningPlanning that searches over partial plans instead of world states: it adds steps, ordering constraints and causal links, committing to an order only when it must. (partial-order planning) handled this by searching over plans instead of states. A partial plan is a set of steps with only the ordering constraints that are needed. Each precondition is supported by a causal link from the step that achieves it; when another step could delete that fact, it is a threat, resolved by ordering the threatening step before or after the link. This least-commitment style is natural for plans that run in parallel, and its ideas survive in schedulers and in explaining why each step of a plan is there.
Hierarchical task networks
People rarely plan with primitive actions. You plan "travel to Lisbon", which decomposes into "get to the airport", "fly", "get to the hotel", and each of those decomposes further. A hierarchical task networkA planning approach in which compound tasks are decomposed by methods into subtasks, recursively, until only primitive actions remain. (HTN) planner works the same way: methods say how a compound task can be broken into subtasks, under which conditions.
HTNs encode expert knowledge about how tasks are usually done, which prunes the search enormously and keeps plans sensible. That makes them popular in practice: video-game characters, military and logistics planning, and manufacturing have used HTN planners, because designers can control the shape of the plans.
Planning and language-model agents
An LLM agent asked to "book a team offsite" does something that looks like HTN planning: it decomposes the request into subtasks, picks tools for each, and executes. The comparison is instructive:
- What the LLM brings: broad common-sense knowledge of how tasks decompose, and the ability to read goals written in plain language, exactly the knowledge that is expensive to hand-write as methods.
- What classical planning brings: guarantees. A STRIPS plan is checked against preconditions at every step; a plan written as prose can include an action whose preconditions do not hold, or forget that one step undoes another, the Sussman problem in disguise.
So practical systems often combine them: the model drafts or decomposes, and explicit checks, validators or even a classical planner (with the model translating the task into PDDL) make sure each step is possible and the goal is actually reached. The agent loop itself is covered in The agent loop (ReAct) .
Trade-offs
| Option | Wins when | Loses when |
|---|---|---|
| Forward state-space search + relaxed heuristics | General domains; strong off-the-shelf planners; easy to explain | Huge state spaces without a good heuristic |
| Plan-space (partial-order) planning | Interacting goals, parallel steps, explaining why each step exists | Search over plans is harder to guide; usually slower today |
| HTN planning | Domains where experts know how tasks decompose; controllable plans | Needs hand-written methods; cannot find plans the methods do not allow |
| LLM-generated plans | Open-ended tasks stated in plain language, with broad common sense | No guarantee each step is valid or the goal is reached without checks |
Common mistakes
- Forgetting delete effects. If moving a block does not delete , the planner will stack two blocks on the same one.
- Achieving goals one at a time and assuming they stay achieved. Subgoals interact, as the Sussman anomaly shows.
- Writing the goal as a complete state. A goal is a set of facts that must hold; everything else may be anything.
- Trusting a plan without simulating it. Executing preconditions and effects step by step catches invalid plans, whoever wrote them.
In the wild
Where you will see this: automated planning has scheduled observations and operations for spacecraft and planetary rovers, controls logistics and manufacturing lines, and drives non-player characters in video games, where HTN and goal-oriented action planning let characters choose sensible sequences of actions. PDDL planners are used in robotics research to sequence pick-and-place tasks. And the planning loops of modern AI agents revisit the same questions classical planning answered: how to decompose, how to check preconditions, and how to recover when the world does not match the plan.
Check yourself
-
In STRIPS, what happens to facts not mentioned in an action's effects?
Show answer
C. They stay as they were Only the add and delete lists change; everything else persists, which is how STRIPS avoids stating every non-change.
-
Why does PDDL separate the domain file from the problem file?
Show answer
B. So one set of action schemas serves every problem in the domain The domain describes how the world works; each problem only supplies objects, an initial state and a goal.
-
What makes the Sussman anomaly hard for a planner that achieves one goal at a time?
Show answer
B. Achieving either goal first forces undoing it to achieve the other The subgoals interact: a correct plan must interleave their steps.
-
The ignore-delete-lists heuristic is useful because:
Show answer
B. The relaxed problem is easy to solve and its cost estimates the real distance for any domain Dropping deletes makes facts accumulate, so the relaxed problem is easy, and planners get a domain-independent heuristic.
-
An LLM agent writes a plan in prose. What does classical planning suggest adding?
Show answer
B. Step-by-step checks that each action's preconditions hold and the goal is reached Simulating preconditions and effects catches invalid or self-undoing plans before they are executed.
Recap
- Classical planning finds action sequences where states are fact sets and actions have preconditions and effects.
- STRIPS uses add and delete lists; PDDL is the standard language, split into domain and problem.
- Planners search forward or backward with domain-independent heuristics such as ignoring delete lists.
- Interacting goals (the Sussman anomaly) motivated plan-space planning; HTNs decompose tasks with expert methods.
- LLM agents decompose tasks like HTNs; classical planning's checks make their plans trustworthy.