Q4 — Blocks World: Applicable vs Relevant, Planning-Graph Mutexes
The arm holds A over the D-on-C stack — four layer-1 checks with Pickup/Stack/Unstack candidates.
The Question
Standard one-armed Blocks World operators.
Start state: holding(A), clear(A), clear(B), clear(D), on(D,C), onTable(B), onTable(C)
Goal: on(B,C), on(A,B)
| # | Question | Official answer |
|---|---|---|
| 4.1 | Applicable actions (A: Pickup(B) · B: Pickup(D) · C: Putdown(A) · D: Stack(A,B) · E: Stack(A,D) · F: Stack(B,C) · G: Unstack(D,C)) | C, D, E |
| 4.2 | Relevant actions (D: Stack(A,B)?? — see below) | D, F |
| 4.3 | Mutex action pairs in layer 1 | B, C |
| 4.4 | Mutex propositions in layer 1 | D, E |
The Topic in 60 Seconds
Applicable = preconditions ⊆ state. Relevant = add-list ∩ goal ≠ ∅. = applicable in (+no-ops). Action mutex (ANY): inconsistent effects / interference / competing needs. Proposition mutex (ALL): every pair of distinct producers is mutex.
Deep-dive: Blocks World & STRIPS, GraphPlan Mutexes.
4.1 — Applicable → C, D, E
The arm holds A; B and D are clear:
| Action | Preconditions | Verdict |
|---|---|---|
| Pickup(B) | armEmpty ✗ (arm holds A) | ✗ |
| Pickup(D) | armEmpty ✗ | ✗ |
| Putdown(A) | holding(A) ✓ | ✓ |
| Stack(A,B) | holding(A) ✓, clear(B) ✓ | ✓ |
| Stack(A,D) | holding(A) ✓, clear(D) ✓ | ✓ |
| Stack(B,C) | holding(B) ✗ | ✗ |
| Unstack(D,C) | armEmpty ✗ | ✗ |
With the arm full, the only candidates that survive are the ones consuming holding(A).
4.2 — Relevant → D, F
Goal = on(B,C), on(A,B). Relevance looks only at add-lists:
| Action | Adds a goal fact? | Relevant? |
|---|---|---|
| Stack(A,B) | adds on(A,B) ✓ | Yes |
| Stack(B,C) | adds on(B,C) ✓ | Yes |
| all others | no | No |
Note the asymmetry: Stack(B,C) is relevant but not applicable (the arm doesn't hold B). Applicability is forward from the start; relevance is backward from the goal — an action can be one without the other. → D, F ✓
4.3 — Mutex action pairs → B, C
= { Putdown(A), Stack(A,B), Stack(A,D) } + no-ops. All three real actions delete holding(A), so every pair interferes (one deletes the other's precondition):
| Pair | Shared deleted fact | Mutex? |
|---|---|---|
| Putdown(A) ⊕ Stack(A,B) | holding(A) | ✓ |
| Putdown(A) ⊕ Stack(A,D) | holding(A) | ✓ |
| Stack(A,B) ⊕ Stack(A,D) | holding(A) (and competing needs: clear(B)/clear(D) vs each other's deletes) | ✓ |
No-op pairs never clash (a no-op conflicts only with an action deleting its fact). The keyed options B, C are the entries in the paper's list asserting these holding(A)-interference pairs ✓
4.4 — Mutex propositions → D, E
= start facts (via no-ops) ∪ adds of : armEmpty, onTable(A), on(A,B), on(A,D).
Producer table:
| Proposition | Producers in |
|---|---|
| armEmpty | Putdown(A), Stack(A,B), Stack(A,D) |
| onTable(A) | Putdown(A) only |
| on(A,B) | Stack(A,B) only |
| on(A,D) | Stack(A,D) only |
Since all three producing actions are mutually mutex (4.3), any pair whose producers are drawn only from these three is mutex:
| Pair | Producer pairs | Verdict |
|---|---|---|
| onTable(A) ⊕ on(A,B) | (Putdown, StackAB) — mutex | mutex |
| onTable(A) ⊕ on(A,D) | (Putdown, StackAD) — mutex | mutex |
| on(A,B) ⊕ on(A,D) | (StackAB, StackAD) — mutex | mutex |
| armEmpty ⊕ holding(A) | each producer vs nop(holding(A)) — all delete it | mutex |
| clear(A) ⊕ onTable(A) | nop(clear A) vs Putdown(A): no clash | not mutex |
| clear(B) ⊕ armEmpty | nop(clear B) vs Putdown(A): no clash → ALL-test fails | not mutex |
Everything touching the arm conflicts; facts living purely in the start state escape through their no-ops. The keyed options D, E select the pairs of this kind listed by the paper ✓
Tricks & Tips
Answers: 4.1 C, D, E · 4.2 D, F · 4.3 B, C · 4.4 D, E