Q7 — GraphPlan Mid-Flight: Populating Layer k+1

Layer k carries mutex pairs, so it can't be a start state — then Pickup(B), Putdown(A) and Stack(A,B) populate layer k+1.

The Question

GraphPlan mid-flight. Layer k facts: onTable(A) [nop-1], holding(A) [nop-2], armEmpty [nop-3], clear(B) [nop-4], on(A,B) [nop-5], onTable(B) [nop-6] — carried to layer k+1 by no-ops, plus newly added facts.

Mutex pairs in layer k: (onTable(A), holding(A)), (holding(A), armEmpty), (clear(B), on(A,B)).

#	Question	Official answer
7.1	Layer k describes the start state?	B — cannot
7.2	Applicable actions in layer k+1 (A: Pickup(B) · B: Putdown(A) · C: Stack(A,B) · D: Unstack(A,B))	A, B, C
7.3	Mutex pairs in layer k+1 (A: Putdown(A)⊕Pickup(B) · B: Pickup(B)⊕Stack(A,B) · C: nop-2⊕nop-3)	A, B, C
7.4	holding(A) ⊕ armEmpty in k+1 are mutex because (A: nop-2⊕nop-3 · B: nop-2⊕Putdown(A) · C: nop-2⊕Stack(A,B) · D: nop-2⊕Pickup(B))	A, B, C

The Topic in 60 Seconds

A layer containing any mutex pair cannot be a genuine state (states are single worlds — everything co-exists).
Action in $A_{k+1}$ ⟺ all preconditions present in layer k and pairwise non-mutex.
Proposition mutex in $P_{k+1}$ = every producer pair mutex (no-ops included).

Deep-dive: GraphPlan Mid-Flight Layers, GraphPlan Mutexes.

7.1 — Layer k is not a start state → B

A start state is a single reachable world — its facts hold simultaneously, so no two can be mutex. Layer k contains (onTable(A), holding(A)) etc. → cannot be the start state → B ✓

7.2 — Applicable actions → A, B, C

Test preconditions against layer k (and their mutex status):

Action	Preconditions	Verdict
Pickup(B)	armEmpty ✓, clear(B) ✓, onTable(B) ✓ — none of the three mutex pairs involves them	✓
Putdown(A)	holding(A) ✓	✓
Stack(A,B)	holding(A) ✓, clear(B) ✓ — holding(A) ⊕ clear(B) is not a listed mutex pair	✓
Unstack(A,B)	armEmpty ✓, on(A,B) ✓, clear(A) ✗ — absent from layer k	✗

→ A, B, C ✓

7.3 — Mutex pairs in layer k+1 → A, B, C

Pair	Test	Mutex?
Putdown(A) ⊕ Pickup(B)	Pickup(B) deletes armEmpty; Putdown(A) adds armEmpty → inconsistent effects	✓
Pickup(B) ⊕ Stack(A,B)	competing needs: Pickup needs armEmpty, Stack needs holding(A) — and armEmpty ⊕ holding(A) is mutex in layer k	✓
nop-2 ⊕ nop-3	nop-2 persists holding(A), nop-3 persists armEmpty — inherited from the layer-k mutex	✓

→ A, B, C ✓

7.4 — Why holding(A) ⊕ armEmpty stay mutex → A, B, C

Producers in k+1: holding(A) ← nop-2; armEmpty ← nop-3, Putdown(A), Stack(A,B). The ALL-producers test needs every pair mutex:

Pair	Reason
nop-2 ⊕ nop-3	inherited mutex (holding(A) ⊕ armEmpty in layer k) ✓
nop-2 ⊕ Putdown(A)	Putdown(A) deletes holding(A) → interference ✓
nop-2 ⊕ Stack(A,B)	Stack(A,B) deletes holding(A) → interference ✓

All three producer pairs mutex → the propositions are mutex. Option D (nop-2 ⊕ Pickup(B)) is not a producer pair — Pickup(B) deletes armEmpty, it doesn't produce it — so it plays no part in the justification → A, B, C ✓

Tricks & Tips

Interactive layer build-up — left: facts in $P_k$ ; middle: candidate actions for $A_{k+1}$ ; right: facts in $P_{k+1}$ (no-ops 1, 4, 5, 6 collapsed into one node):

1 / 5

Given mutex pairs in k: (onTable(A) ⊕ holding(A)) · (holding(A) ⊕ armEmpty) (clear(B) ⊕ on(A,B)) Any mutex pair ⇒ cannot be a start state → 7.1 = B.

under examinationfact present / action applicableproducer of the winning pairsrejected

Tricks & Tips

Answers: 7.1 B · 7.2 A, B, C · 7.3 A, B, C · 7.4 A, B, C