STRIPS planning
Means-ends reasoning as search. Describe each action by what it needs and what it adds and deletes, then look for a sequence of actions that turns the start state into one where the goal holds.
Kind: deliberative technique (the “how” half of BDI).
Week: 2 (slides 32 to 41).
Book: Wooldridge 4.2 Means-ends reasoning (pp. 69 to 75).
Techniques on this page: the planning problem, the transition function, applying STRIPS actions in the blocks world, checking a plan state by state, plan libraries and HTN.
The problem it solves
A BDI agent decides what to achieve (an intention). It still needs to work out how. Planning is automatic programming: give it a goal, the available actions and the current state, and it produces the program (the plan) itself.
This is the only real maths in week 2, and “verify this plan state by state” is a very likely exam question. It also explains a modern worry: an LLM can write a plan that looks right but contains a step whose preconditions don’t hold.
Words you’ll hear
| Word or symbol | Plain meaning |
|---|---|
| \(m_0\) | the start state: a set of facts that are true |
| \(g_t\) | the goal: facts that must be true at the end |
| \(A\) | the available actions |
| \(pre(a)\) | preconditions: facts that must hold before \(a\) can run |
| \(add(a)\), \(del(a)\) | facts \(a\) makes true, facts \(a\) makes false |
| \(\tau(m, a)\) | the state after doing \(a\) in state \(m\) |
| plan \(\pi\) | a sequence of actions \(\langle a_1, \dots, a_n \rangle\) |
| closed world | a fact not in the state is false |
| HTN | hierarchical task network: break a big task into smaller tasks |
Technique 1: the planning problem
Problem it solves: states exactly what a planner is given and what counts as success.
A planning problem is \(\langle m_0, g_t, A \rangle\). Each action is \(a = \langle pre(a), \langle del(a), add(a) \rangle \rangle\).
\[\tau(m, a) = (m \setminus del(a)) \cup add(a), \qquad \text{allowed only if } pre(a) \subseteq m.\]
In words: if every precondition is in the state, remove the delete list and add the add list.
A plan \(\pi\) solves the problem if, applying each action in turn, every action is allowed and the final state contains the goal: \(g_t \subseteq m_n\). So planning is search through the graph of states that \(\tau\) creates.
Why a delete list? Under the closed world assumption a state lists only the true facts. Actions make some facts false (after a pickup the arm isn’t empty), and the only way to say so is to remove them.
Technique 2: STRIPS actions in the blocks world
Problem it solves: the standard example, used on the slides and in the book.
Facts: \(on(X,Y)\), \(onTable(X)\), \(clear(X)\) (nothing on top of \(X\)), \(holding(X)\), \(armEmpty\).
| Action | pre | del | add |
|---|---|---|---|
| \(stack(X,Y)\) | \(clear(Y), holding(X)\) | \(clear(Y), holding(X)\) | \(armEmpty, on(X,Y)\) |
| \(unstack(X,Y)\) | \(on(X,Y), clear(X), armEmpty\) | \(on(X,Y), armEmpty\) | \(holding(X), clear(Y)\) |
| \(pickup(X)\) | \(clear(X), onTable(X), armEmpty\) | \(onTable(X), armEmpty\) | \(holding(X)\) |
| \(putdown(X)\) | \(holding(X)\) | \(holding(X)\) | \(armEmpty, onTable(X)\) |
\(stack\)/\(unstack\) and \(pickup\)/\(putdown\) undo each other. Note \(clear(X)\) stays true while \(X\) is held.
Technique 3: checking a plan state by state
Problem it solves: proves a plan works, and catches steps that can’t run.
Worked example: build the tower A on B on C.
\(m_0 = \{armEmpty, clear(A), on(A,B), onTable(B), onTable(C), clear(C)\}\) (A on B; B and C on the table). Goal \(g_t = \{on(A,B), on(B,C), onTable(C)\}\).
| Step | Action | pre ✓? | Removed | Added |
|---|---|---|---|---|
| 1 | \(unstack(A,B)\) | \(on(A,B), clear(A), armEmpty\) ✓ | \(on(A,B), armEmpty\) | \(holding(A), clear(B)\) |
| 2 | \(putdown(A)\) | \(holding(A)\) ✓ | \(holding(A)\) | \(armEmpty, onTable(A)\) |
| 3 | \(pickup(B)\) | \(clear(B), onTable(B), armEmpty\) ✓ | \(onTable(B), armEmpty\) | \(holding(B)\) |
| 4 | \(stack(B,C)\) | \(clear(C), holding(B)\) ✓ | \(clear(C), holding(B)\) | \(armEmpty, on(B,C)\) |
| 5 | \(pickup(A)\) | \(clear(A), onTable(A), armEmpty\) ✓ | \(onTable(A), armEmpty\) | \(holding(A)\) |
| 6 | \(stack(A,B)\) | \(clear(B), holding(A)\) ✓ | \(clear(B), holding(A)\) | \(armEmpty, on(A,B)\) |
Final state \(\{clear(A), on(A,B), on(B,C), onTable(C), armEmpty\}\) contains the goal, so the plan works. It’s also shortest: B must end on C but starts under A, so A has to come off, go somewhere, and go back.
Worked example: spot the illegal step. From \(m_0\) above, can we start with \(pickup(B)\)? It needs \(clear(B)\), but A is on B, so no. A planner that checks \(pre(a) \subseteq m\) would never propose it.
How big is the search? With 3 blocks there are 13 ways to arrange them in stacks, plus 9 states with one block held: 22 states. Small here, but it explodes as blocks are added, which is why planning is expensive.
Technique 4: first principles, libraries and HTN
Problem it solves: planning from scratch is slow, so real BDI systems usually don’t.
- Planning from first principles: search for \(\pi\) from the STRIPS descriptions, as above. General, but expensive.
- Plan libraries: the programmer writes plans for particular goals in advance. Cheap, but brittle (no plan for a situation nobody foresaw). PRS and AgentSpeak use libraries.
- Plans can be richer than lists (
while,if-then-else). - HTN: break a high-level task into subtasks, recursively, down to primitive actions (“move tower” → “clear top”, “move block”, …). Often much cheaper when subtasks repeat.
Discussion (slide 41): is an LLM’s chain of thought planning? It looks like first-principles search, but it draws on patterns from training, more like an implicit library. And unlike a STRIPS planner it doesn’t check \(pre(a) \subseteq m\), so it can produce plans that look right but can’t run. A sensible design: let the LLM propose, and check with \(\tau\).
What to read in the book
| Section | Read? | Why |
|---|---|---|
| 4.2 Means-ends reasoning, pp. 69 to 75 | Read | STRIPS and the blocks world with the same predicates and four actions as the slides. Core |
| HTN | Slides only | Slides 39 to 41 |
Page numbers are the book’s; in the scanned PDF add 21.
Practice prompt
I'm studying CS5940 Intelligent Agents (Wooldridge, An Introduction to MultiAgent Systems, 2nd ed., 4.2). I want practice on STRIPS PLANNING in the blocks world, worked by hand:
- the planning problem <m0, g, A>, actions as <pre, del, add>, and tau(m, a) = (m minus del) union add, defined only if pre is a subset of m
- whether an action is applicable in a given state, and the state after applying it
- writing a plan from one arrangement of blocks to another, and verifying it state by state
- spotting an illegal step in a proposed plan
- why STRIPS needs delete lists (closed world assumption)
- counting states for small numbers of blocks
- planning from first principles vs plan libraries vs HTN, and whether an LLM's chain of thought counts as planning
Please:
1. Use plain, everyday language and explain any symbol in one short sentence.
2. Give me ONE question at a time, easy first, then harder; always list the states as sets of facts.
3. Wait for my answer, then mark it and show the full state-by-state working.
4. If I get it wrong, explain the mistake and give me a similar question.
5. Every 5 questions, summarise my strengths and what to practise.