Q6 — Blocks World: Applicable vs Relevant, Planning-Graph Mutexes
D stacks on A, E on B — the same start/goal as the AN paper with identical answers.
The Question
Standard one-armed Blocks World operators.
Start state: onTable(A), onTable(B), onTable(C), clear(D), clear(E), clear(C), on(D,A), on(E,B), armEmpty
Goal: on(B,C), on(A,B)
| # | Question | Official answer |
|---|---|---|
| 6.1 | Applicable actions (A: Putdown(D) · B: Unstack(D,A) · C: Unstack(E,B) · D: Pickup(C) · E: Pickup(A) · F: Stack(A,B) · G: Stack(B,C)) | B, C, D |
| 6.2 | Relevant actions | F, G |
| 6.3 | Mutex action pairs in layer 1 (A: Unstack(D,A),Pickup(C) · B: Unstack(D,A),Unstack(E,B) · C: Pickup(C),Stack(A,B) · D: Pickup(C),Stack(B,C)) | A, B |
| 6.4 | Mutex propositions in layer 1 (A: clear(A),holding(E) · B: clear(A),clear(B) · C: clear(C),on(D,A) · D: clear(C),holding(E)) | A, B |
The Topic in 60 Seconds
Applicable = preconditions ⊆ state. Relevant = add-list ∩ goal ≠ ∅ (applicability irrelevant). = applicable in (+no-ops). Action mutex (ANY): inconsistent effects / interference / competing needs. Proposition mutex (ALL): every producer pair mutex.
Deep-dive: Blocks World & STRIPS, GraphPlan Mutexes.
6.1 — Applicable → B, C, D
armEmpty holds, so only unstacks and pickups are candidates:
| Action | Preconditions | Verdict |
|---|---|---|
| Putdown(D) | holding(D) ✗ | ✗ |
| Unstack(D,A) | armEmpty ✓, clear(D) ✓, on(D,A) ✓ | ✓ |
| Unstack(E,B) | armEmpty ✓, clear(E) ✓, on(E,B) ✓ | ✓ |
| Pickup(C) | armEmpty ✓, clear(C) ✓, onTable(C) ✓ | ✓ |
| Pickup(A) | clear(A) ✗ (D sits on A) | ✗ |
| Stack(A,B) / Stack(B,C) | holding(·) ✗ | ✗ |
6.2 — Relevant → F, G
Goal = on(B,C), on(A,B):
| Action | Adds | Hits goal? |
|---|---|---|
| Stack(A,B) | on(A,B), armEmpty | ✓ on(A,B) |
| Stack(B,C) | on(B,C), armEmpty | ✓ on(B,C) |
| everything else | no goal fact | ✗ |
6.3 — Mutex action pairs → A, B
= { Unstack(D,A), Unstack(E,B), Pickup(C) } + no-ops of the start facts.
| Pair | Test | Mutex? |
|---|---|---|
| Unstack(D,A) ⊕ Pickup(C) | both delete armEmpty → interference | ✓ |
| Unstack(D,A) ⊕ Unstack(E,B) | both delete armEmpty → interference | ✓ |
| Pickup(C) ⊕ Stack(A,B) / Stack(B,C) | the Stacks are not in at all | options C, D auto-wrong |
All three real actions share the deleted fact armEmpty — one mutual mutex clique → A, B ✓
6.4 — Mutex propositions → A, B
= start facts (clean no-ops) ∪ adds: clear(A) [Unstack(D,A)], clear(B) [Unstack(E,B)], holding(D) [Unstack(D,A)], holding(E) [Unstack(E,B)], holding(C) [Pickup(C)].
| Pair | Producers | Verdict |
|---|---|---|
| clear(A) ⊕ holding(E) | clear(A): only Unstack(D,A) (D sits on A — not a start fact); holding(E): only Unstack(E,B); producers mutex (6.3) | ✓ |
| clear(A) ⊕ clear(B) | clear(B): only Unstack(E,B) — same mutex pair | ✓ |
| clear(C) ⊕ on(D,A) | both are start facts → their no-ops coexist cleanly | Not mutex |
| clear(C) ⊕ holding(E) | clear(C)'s nop is clean against anything in | Not mutex |
With armEmpty in the state, every applicable action deletes it — layer 1's real actions form one mutual mutex clique, each new proposition is chained to its producer's fate, and only start-state facts escape through their clean no-ops.
Tricks & Tips
Answers: 6.1 B, C, D · 6.2 F, G · 6.3 A, B · 6.4 A, B