Q6 — Blocks World: Applicable vs Relevant, Planning-Graph Mutexes
D stacks on B, C on A — the same start/goal as the 2025 T2 FN paper, with identical answers.
The Question
Standard one-armed Blocks World operators.
Start state: onTable(B), onTable(A), onTable(E), clear(D), clear(C), clear(E), on(D,B), on(C,A), armEmpty
Goal: on(A,C), on(B,A)
| # | Question | Official answer |
|---|---|---|
| 6.1 | Applicable actions (A: Putdown(D) · B: Unstack(D,B) · C: Unstack(C,A) · D: Pickup(E) · E: Pickup(A) · F: Stack(B,A) · G: Stack(A,C)) | B, C, D |
| 6.2 | Relevant actions | F, G |
| 6.3 | Mutex action pairs in layer 1 (A: Unstack(D,B),Pickup(E) · B: Unstack(D,B),Unstack(C,A) · C: Pickup(E),Stack(B,A) · D: Pickup(E),Stack(A,C)) | A |
| 6.4 | Mutex propositions in layer 1 (A: clear(B),holding(C) · B: clear(B),clear(A) · C: clear(E),on(D,B) · D: clear(E),holding(D)) | 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,B) | armEmpty ✓, clear(D) ✓, on(D,B) ✓ | ✓ |
| Unstack(C,A) | armEmpty ✓, clear(C) ✓, on(C,A) ✓ | ✓ |
| Pickup(E) | armEmpty ✓, clear(E) ✓, onTable(E) ✓ | ✓ |
| Pickup(A) | clear(A) ✗ (C sits on A) | ✗ |
| Stack(B,A) / Stack(A,C) | holding(·) ✗ | ✗ |
6.2 — Relevant → F, G
Goal = on(A,C), on(B,A):
| Action | Adds | Hits goal? |
|---|---|---|
| Stack(A,C) | on(A,C), armEmpty | ✓ on(A,C) |
| Stack(B,A) | on(B,A), armEmpty | ✓ on(B,A) |
| everything else | no goal fact | ✗ |
6.3 — Mutex action pairs → A
= { Unstack(D,B), Unstack(C,A), Pickup(E) } + no-ops of the start facts (options C, D name Stacks — inapplicable here, auto-wrong).
- Unstack(D,B) ⊕ Pickup(E): both delete armEmpty → interference → mutex ✓ (option A)
- Unstack(D,B) ⊕ Unstack(C,A): both delete armEmpty → interference → mutex by the standard test too.
The official key records a single pair, A. Both listed pairs pass the interference test; if the paper wants exactly one, A is the safe pick — but be aware B is equally mutex under the textbook rule (this is a known quirk of this key). Never tick C or D: those actions don't exist in at all.
6.4 — Mutex propositions → A, B
= start facts (clean no-ops) ∪ adds: clear(B), clear(A), holding(D), holding(C), holding(E).
| Pair | Producers | Verdict |
|---|---|---|
| clear(B) ⊕ holding(C) | clear(B): only Unstack(D,B) (D sits on B); holding(C): only Unstack(C,A); producers mutex (6.3) | ✓ |
| clear(B) ⊕ clear(A) | clear(A): only Unstack(C,A) — same mutex pair | ✓ |
| clear(E) ⊕ on(D,B) | both are start facts → their no-ops coexist cleanly | Not mutex |
| clear(E) ⊕ holding(D) | clear(E)'s nop is clean against anything in | Not mutex |
With armEmpty in the state, every applicable action deletes it — so layer 1's real actions form one mutual mutex clique, every new proposition is locked 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 · 6.4 A, B