STRIPS and the Blocks World
The classic planning domain — operators with preconditions, add and delete lists. 'Applicable vs relevant actions' is an exam staple
The Simplest Explanation
Planning means finding a sequence of actions that transforms a start state into a goal state. STRIPS is the classic language for describing actions. Each operator is just three lists:
| Part | Question it answers |
|---|---|
| Preconditions | What must be true to even try this action? |
| Add list | What becomes true after the action? |
| Delete list | What stops being true after the action? |
A state is the set of all currently-true predicates. If a predicate isn't listed, it's false (closed-world assumption).
Applicable = preconditions ⊆ current state (can I do it NOW?). Relevant = add/delete lists interact with the goal (does it help reach the GOAL?). Exams love asking you to distinguish these two.
The Blocks World Domain
Table, one robot arm, blocks A/B/C/D... Predicates:
- — block sits on block
- — rests on the table
- — nothing on top of
- — the arm holds
- — self-explanatory
The Four Operators
| Operator | Preconditions | Add | Delete |
|---|---|---|---|
| Unstack(x, y) | ArmEmpty ∧ On(x,y) ∧ Clear(x) | Holding(x), Clear(y) | ArmEmpty, On(x,y) |
| Pickup(x) | ArmEmpty ∧ OnTable(x) ∧ Clear(x) | Holding(x) | ArmEmpty, OnTable(x) |
| Putdown(x) | Holding(x) | OnTable(x), ArmEmpty | Holding(x) |
| Stack(x, y) | Holding(x) ∧ Clear(y) | On(x,y), ArmEmpty, Clear(x)... see note | Holding(x), Clear(y) |
When you Stack(x,y): x goes onto y, so x becomes Clear again (nothing on it) and y loses Clear. When you Unstack or Pickup, some versions delete Clear(x), others don't — exam questions exploit exactly this choice for multi-arm domains, because deleting Clear(x) creates causal dependencies that force ordering constraints.
Applicable Actions — Worked Example
State: On(A, B), OnTable(B), OnTable(C), Clear(A), Clear(C), ArmEmpty.
Check every operator against the preconditions:
| Operator | Precondition check | Applicable? |
|---|---|---|
| Unstack(A, B) | ArmEmpty ✓, On(A,B) ✓, Clear(A) ✓ | YES |
| Pickup(A) | OnTable(A)? ✗ | no |
| Pickup(B) | Clear(B)? ✗ (A is on B) | no |
| Pickup(C) | all hold ✓ | YES |
| Putdown(any) | Holding(any)? ✗ | no |
| Stack(x, y) | Holding(x)? ✗ | no |
So exactly two actions are applicable: Unstack(A,B) and Pickup(C).
Applying an Action (the state update recipe)
Apply Unstack(A, B):
- Delete
{ArmEmpty, On(A,B)} - Add
{Holding(A), Clear(B)}
New state: OnTable(B), OnTable(C), Clear(A), Clear(C), Holding(A), Clear(B).
That's it — exams award full marks for mechanically correct delete-then-add updates. Always delete first, then add.
Relevant Actions — Worked Example
Goal: On(A, B). Ask of each operator: could this action produce something the goal needs?
| Operator | Interacts with goal On(A,B)? | Relevant? |
|---|---|---|
| Stack(A, y) | adds On(A, y) → yes if y = B | YES |
| Unstack(x, y) | deletes On(x,y) — only destroys | no (unless goal needs Clear effects) |
| Pickup / Putdown | touch Holding/OnTable only | no |
Stack(A, B) is the relevant operator. Its preconditions — Holding(A) ∧ Clear(B) — become the new subgoals. Regressing goals through relevant operators is the heart of backward planning.
From Domain to Search Problem
This domain plugs straight into Week 2's framework:
- MoveGen(n) = apply every applicable operator to state n, each yielding one successor
- GoalTest(n) = check goal predicates ⊆ state n
- BFS/DFID then find shortest plans automatically!
Multi-Arm Robots (exam favorite)
Give each arm its own predicates (, ...) and duplicate operators per arm (, , or generic , ). Two arms act in parallel, shrinking plan length (makespan).
Example: D-on-A, C-on-B → goal On(C,A), On(D,C):
- One arm: 6 steps
- Two arms: step 1 = both unstacks in parallel; step 2 = Stack₂(C,A); step 3 = Stack₁(D,C). Makespan 3.
The delete-Clear(x) Decision
Should Unstack/Pickup delete Clear(x) for the lifted block x?
| Domain | Does it matter? | Why |
|---|---|---|
| One arm | No | after lifting x, only Putdown/Stack apply, both restore Clear(x) before anything else touches x |
| Multi-arm | Yes | parallel actions interact through Clear |
With delete-Clear: after Unstack₂(C,B), C is NOT clear — so Stack₁(D,C) must wait until Stack₂(C,A) restores Clear(C). That causal dependency forces the ordering → makespan 3.
Without delete-Clear: both blocks stay "clear" while held → Stack₁(D,C) could run in parallel with Stack₂(C,A) → apparent makespan 2 — but that's wrong for this domain: you cannot stack onto a block that's still held mid-air. The delete-Clear version captures the true constraint.
Exam questions hand you both variants and ask which makespan is correct — answer via the delete-list semantics, not by intuition.