Q7 — Planning: Applicable/Relevant/Mutex
Blocks World planning graph — applicable B,C,D; relevant F,G; layer-1 mutex pairs A,B for both actions and propositions.
The Question
The domain description of a Blocks World with a single one-armed robot is given below.
PREDICATES
armEmpty — the arm holds nothing. holding(X) — the arm holds X. onTable(X) — X rests on the table. clear(X) — nothing on top of X. on(X,Y) — X is directly on Y.
OPERATORS
| Operator | Preconditions | Adds | Deletes |
|---|---|---|---|
| Pickup(X) | armEmpty, clear(X), onTable(X) | holding(X) | armEmpty, onTable(X) |
| Putdown(X) | holding(X) | armEmpty, onTable(X) | holding(X) |
| Unstack(X,Y) | armEmpty, clear(X), on(X,Y) | holding(X), clear(Y) | armEmpty, on(X,Y) |
| Stack(X,Y) | holding(X), clear(Y) | armEmpty, on(X,Y) | holding(X), clear(Y) |
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 |
|---|---|---|
| 7.1 | Which of the following are applicable actions in the start state? (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 |
| 7.2 | Which of the following are relevant actions in the goal state? | F,G |
| 7.3 | In the planning graph, which of the following are 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,B |
| 7.4 | In the planning graph, which of the following are mutex proposition pairs 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 ≠ ∅. = actions applicable in plus no-ops. Action mutex needs ANY test: inconsistent effects, interference (one deletes other's precondition), competing needs. Proposition mutex needs ALL producer pairs mutex.
Deep-dive: Blocks World & STRIPS, GraphPlan Mutexes.
7.1 — Applicable in the start state → B,C,D
The arm is empty, so only unstacks/pickups can qualify:
| Action | Preconditions vs start state | 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); also onTable(A) ✗ | ✗ |
| Stack(B,A) / Stack(A,C) | holding(·) ✗ | ✗ |
→ B, C, D ✓
7.2 — Relevant to the goal → F,G
An action is relevant if it achieves some goal literal:
| Action | Add-list vs goal on(A,C), on(B,A) | Verdict |
|---|---|---|
| Stack(A,C) | adds on(A,C) ✓ | ✓ |
| Stack(B,A) | adds on(B,A) ✓ | ✓ |
| everything else | no goal literal in add-list | ✗ |
→ F, G ✓
7.3 — Mutex action pairs in → A,B
= Unstack(D,B), Unstack(C,A), Pickup(E) + no-ops (options C and D name Stacks, which are not even applicable — instant rejects).
| Pair | Test | Verdict |
|---|---|---|
| Unstack(D,B) ⊕ Pickup(E) | both delete armEmpty → interference | mutex ✓ |
| Unstack(D,B) ⊕ Unstack(C,A) | both delete armEmpty → interference | mutex ✓ |
(Pickup(E) ⊕ Unstack(C,A) is also mutex, but that pair isn't offered; every listed option containing a Stack fails.) → A, B ✓
7.4 — Mutex propositions in → A,B
= start facts (via no-ops) ∪ additions: clear(B), holding(D), clear(A), holding(C), holding(E).
| Pair | Producer analysis | Verdict |
|---|---|---|
| clear(B) ⊕ holding(C) | clear(B): only Unstack(D,B); holding(C): only Unstack(C,A); those two actions are mutex (7.3) → all-producer-pairs-mutex holds | mutex ✓ |
| clear(B) ⊕ clear(A) | clear(A): only Unstack(C,A); again paired against mutex producer Unstack(D,B) | mutex ✓ |
| clear(E) ⊕ on(D,B) | both are start facts persisting via no-ops; no-op producers are never mutex unless the facts already were in — they were not | not mutex |
| clear(E) ⊕ holding(D) | clear(E): no-op only; holding(D): Unstack(D,B). A single non-mutex action vs a no-op cannot be an ALL-side mutex | not mutex |
→ A, B ✓
Tricks & Tips
Answers: 7.1 B,C,D · 7.2 F,G · 7.3 A,B · 7.4 A,B