Q6 — Blocks World: Applicable vs Relevant, Planning-Graph Mutexes
The arm holds D while A, B, E sit clear — applicable vs relevant splits cleanly and the layer-1 mutexes all hinge on holding(D).
The Question
Standard one-armed Blocks World operators.
Start state: holding(D), clear(D), clear(A), clear(B), clear(E), on(B,C), onTable(A), onTable(C), onTable(E)
Goal: holding(B), on(D,A), on(A,C)
| # | Question | Official answer |
|---|---|---|
| 6.1 | Applicable actions (A: Putdown(D) · B: Stack(D,C) · C: Pickup(B) · D: Stack(D,A) · E: Stack(A,C)) | A, D |
| 6.2 | Relevant actions (A: Pickup(B) · B: Putdown(D) · C: Unstack(B,E) · D: Stack(D,C) · E: Stack(D,A)) | A, C, E |
| 6.3 | Mutex action pairs in layer 1 (A: Unstack(B,C),Putdown(D) · B: Stack(D,A),Putdown(D) · C: Stack(D,A),nop(armEmpty) · D: Stack(D,A),Stack(D,E) · E: Pickup(A),Putdown(D)) | B, D |
| 6.4 | Mutex propositions in layer 1 (A: on(D,A),armEmpty · B: on(D,A),onTable(D) · C: on(D,A),on(D,B) · D: holding(D),clear(A) · E: on(D,A),clear(A)) | B, C, E |
The Topic in 60 Seconds
Applicable = preconditions ⊆ state. Relevant = add-list hits the 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 → A, D
The arm holds D; A, B, E are clear:
| Action | Preconditions | Verdict |
|---|---|---|
| Putdown(D) | holding(D) ✓ | ✓ |
| Stack(D,C) | holding(D) ✓, clear(C) ✗ (B sits on C) | ✗ |
| Pickup(B) | armEmpty ✗ | ✗ |
| Stack(D,A) | holding(D) ✓, clear(A) ✓ | ✓ |
| Stack(A,C) | holding(A) ✗ | ✗ |
6.2 — Relevant → A, C, E
An action is relevant when its add-list contains any goal fact — whether or not it is applicable now.
| Action | Adds | Hits goal? |
|---|---|---|
| Pickup(B) | holding(B) | ✓ holding(B) |
| Putdown(D) | armEmpty, onTable(D) | ✗ |
| Unstack(B,E) | holding(B), clear(E) | ✓ holding(B) (never mind that B is not on E) |
| Stack(D,C) | on(D,C), armEmpty | ✗ (goal wants on(D,A)) |
| Stack(D,A) | on(D,A), armEmpty | ✓ on(D,A) |
6.3 — Mutex action pairs in layer 1 → B, D
= every action whose preconditions hold in : Putdown(D), Stack(D,A), plus the ones the options don't mention — Stack(D,B) (holding(D) ✓, clear(B) ✓) and Stack(D,E) (holding(D) ✓, clear(E) ✓) — and a no-op for each start fact. Unstack(B,C)/Pickup(A) need armEmpty ✗ → options A and E name non-existent actions; option C pairs with nop(armEmpty) but armEmpty ∉ P0, so that no-op doesn't exist either.
Every real action here consumes holding(D):
| Pair | Test | Mutex? |
|---|---|---|
| Stack(D,A) ⊕ Putdown(D) | Stack deletes holding(D) = Putdown's precondition → interference | ✓ |
| Stack(D,A) ⊕ nop(armEmpty) | no such no-op exists | ✗ |
| Stack(D,A) ⊕ Stack(D,E) | both delete holding(D) → interference | ✓ |
6.4 — Mutex propositions in layer 1 → B, C, E
= start facts (via clean no-ops) ∪ adds: armEmpty, onTable(D) [Putdown], on(D,A) [Stack(D,A)], on(D,B) [Stack(D,B)], on(D,E) [Stack(D,E)].
The key test: producers of on(D,A) = {Stack(D,A)} only. Producers of armEmpty = {Putdown(D), Stack(D,A), Stack(D,B), Stack(D,E)} — which includes Stack(D,A) itself, and an action is never mutex with itself, so the ALL-producers test fails for any pair involving armEmpty.
| Pair | Producers | Verdict |
|---|---|---|
| on(D,A) ⊕ armEmpty | {Stack(D,A)} × {Putdown, Stacks} — the pair (Stack(D,A), Stack(D,A)) is a self-pair, non-mutex | Not mutex |
| on(D,A) ⊕ onTable(D) | onTable(D): only Putdown(D); on(D,A): only Stack(D,A); that pair IS mutex (6.3) | ✓ |
| on(D,A) ⊕ on(D,B) | on(D,B): only Stack(D,B); mutex with Stack(D,A) (both delete holding(D)) | ✓ |
| holding(D) ⊕ clear(A) | holding(D) is a start fact → its no-op is clean against everything | Not mutex |
| on(D,A) ⊕ clear(A) | clear(A)'s only producer is its start-state no-op; Stack(D,A) deletes clear(A) = the nop's precondition → interference → mutex | ✓ |
Row E in one line: placing D on A destroys A's clearness in every successor state — Stack(D,A) deletes clear(A), so on(D,A) and clear(A) can never coexist in → per the paper's key this counts as mutex ✓
Every real action in consumes holding(D) — so all action pairs are mutex, every "new" proposition (on(D,·), onTable(D)) has a small single-producer set locked to those mutex actions, and only facts that already existed in the start state escape via their clean no-ops.
Tricks & Tips
Answers: 6.1 A, D · 6.2 A, C, E · 6.3 B, D · 6.4 B, C, E