Q4 — Blocks World: Applicable vs Relevant, Planning-Graph Mutexes
A on B, D on C, arm empty — three unstacks/pickups are live and the layer-1 mutexes hinge on armEmpty.
The Question
Standard one-armed Blocks World operators.
Start state: armEmpty, clear(A), clear(D), clear(E), on(A,B), on(D,C), onTable(B), onTable(C), onTable(E)
Goal: on(B,C), on(A,B)
| # | Question | Official answer |
|---|---|---|
| 4.1 | Applicable actions (A: Pickup(A) · B: Pickup(E) · C: Stack(A,B) · D: Stack(B,C) · E: Unstack(A,B) · F: Unstack(B,A) · G: Unstack(D,C)) | B, E, G |
| 4.2 | Relevant actions (C: Stack(A,B) · D: Stack(B,C)) | C, D |
| 4.3 | Mutex action pairs in layer 1 | A, C, E |
| 4.4 | Mutex propositions in layer 1 | A, D |
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 → B, E, G
armEmpty holds; A, D, E are clear:
| Action | Preconditions | Verdict |
|---|---|---|
| Pickup(A) | onTable(A) ✗ (A sits on B) | ✗ |
| Pickup(E) | armEmpty ✓, clear(E) ✓, onTable(E) ✓ | ✓ |
| Stack(A,B) | holding(A) ✗ | ✗ |
| Stack(B,C) | holding(B) ✗ | ✗ |
| Unstack(A,B) | armEmpty ✓, clear(A) ✓, on(A,B) ✓ | ✓ |
| Unstack(B,A) | on(B,A) ✗ | ✗ |
| Unstack(D,C) | armEmpty ✓, clear(D) ✓, on(D,C) ✓ | ✓ |
With an empty arm, only pickups and unstacks are candidates — then the per-action facts filter the rest.
4.2 — Relevant → C, D
Goal = {on(B,C), on(A,B)}. Relevance reads add-lists only:
| 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 |
Both Stacks are relevant and non-applicable right now — relevance is goal-side, not start-side. → C, D ✓
4.3 — Mutex action pairs → A, C, E
= { Pickup(E), Unstack(A,B), Unstack(D,C) } + no-ops. Every real action deletes armEmpty, so every pair interferes:
| Pair | Shared deleted fact | Mutex? |
|---|---|---|
| Pickup(E) ⊕ Unstack(A,B) | armEmpty | ✓ |
| Pickup(E) ⊕ Unstack(D,C) | armEmpty | ✓ |
| Unstack(A,B) ⊕ Unstack(D,C) | armEmpty | ✓ |
No-op pairs never clash. All three real pairs mutex → A, C, E ✓
4.4 — Mutex propositions → A, D
= start facts (via no-ops) ∪ adds: holding(E) (Pickup(E)), holding(A) and clear(B) (Unstack(A,B)), holding(D) (Unstack(D,C)).
Producer table for the new propositions:
| Proposition | Producers in |
|---|---|
| holding(E) | Pickup(E) only |
| holding(A) | Unstack(A,B) only |
| holding(D) | Unstack(D,C) only |
| clear(B) | Unstack(A,B) only |
Any pair whose producers come from two distinct real actions inherits their mutex (4.3):
| Pair | Producer pairs | Verdict |
|---|---|---|
| holding(A) ⊕ holding(D) | (UAB, UDC) — mutex | mutex |
| holding(A) ⊕ holding(E) | (UAB, PE) — mutex | mutex |
| holding(D) ⊕ holding(E) | (UDC, PE) — mutex | mutex |
| clear(B) ⊕ holding(A) | same action (UAB) on both sides — no distinct pair | not mutex |
| clear(B) ⊕ armEmpty | (UAB, PE) mutex, (UAB, UDC) mutex, (UAB, nop-armEmpty) mutex — UAB deletes armEmpty | mutex |
| clear(E) ⊕ anything new | nop(clear E) co-exists with every producer (none deletes or needs clear(E)) | not mutex |
The "holding" family locks together through the shared arm; start-state facts escape via clean no-ops. The keyed options A, D select the mutex pairs from the paper's list ✓
Tricks & Tips
Answers: 4.1 B, E, G · 4.2 C, D · 4.3 A, C, E · 4.4 A, D