GraphPlan Mid-Flight Layer Reasoning
Given layers k and k+1 mid-planning-graph — can layer k be a state? Which actions apply next? Why are two facts (non-)mutex? The 25T3 question family
The Simplest Explanation
2025 papers stopped asking only about Layer 1 from the start state. Now they hand you a planning graph mid-flight — layers k and k+1 already populated with facts, actions, and mutex pairs — and test whether you understand the machinery:
- Can layer k be the start state?
- Which actions become applicable in layer k+1?
- Which pairs are mutex in layer k+1 — and WHY?
A real state can never contain two mutex facts (they'd have to be simultaneously true and provably incompatible). And mutexes propagate forward through ALL producer pairs — including no-ops.
Question 1 — Can layer k be the start state?
Rule: (start layer) is a single reachable state — every fact in it holds simultaneously. By definition of mutex ("can never co-occur"), any layer containing even one mutex pair cannot be a genuine state, so it cannot be .
Worked check (25T3 FN Q7.1): layer k contains mutex pairs (on(A,B), holding(A)), (armEmpty, clear(B)), … Since e.g. a block can't be both on A and held by the arm, these facts can't co-exist in one state → layer k is NOT the start state. Answer: No.
Question 2 — Applicable actions in layer k+1
An action appears in iff all its preconditions are present AND pairwise non-mutex in layer k.
Blocks World checks (given layer-k facts):
| Action | Preconditions present? | Any mutex among them? | In ? |
|---|---|---|---|
| Stack(A, B) | holding(A) ✓, clear(B) ✓ | holding(A) ⊕ clear(B)? not mutex here ✓ | Yes |
| Unstack(x,y) | needs on(x,y) ∧ clear(x) ∧ armEmpty | on(A,B) ⊕ holding(A) irrelevant; check actual combo | depends |
| Pickup(C) | needs onTable(C) — absent from layer k | — | No (fact missing beats everything) |
Two independent rejection reasons: fact simply absent, or facts present-but-mutex.
Question 3 — Mutex propagation into layer k+1
Propositions p, q are mutex in iff every pair of their producers is mutex in . Producers include the no-ops. Three sources of producer-pair mutex:
| Source | Example |
|---|---|
| nop–nop inheritance | if p ⊕ q mutex at layer k, then nop(p) ⊕ nop(q) mutex at |
| nop–action interference | action deletes p, while nop(p) persists p → they conflict |
| action–action | inconsistent effects / interference / competing needs |
Why would two facts be NON-mutex in k+1?
Exhibit one surviving producer pair. Classic justification (25T3 Q7.4): armEmpty and clear(B) are non-mutex in layer k+1 because
- nop(armEmpty) exists,
- some action adding clear(B) (e.g., Unstack(D,A) adds Clear(A)-type facts… specifically any adder whose preconditions don't clash with ArmEmpty),
- and that action–nop pair shares no deleted/precondition conflict → not mutex → the pair escapes mutex.
One clean producer pair breaks the ALL quantifier.
Conversely — why HOLDING(A) ⊕ ARMEMPTY stays mutex in k+1
Every producer pair is conflicted:
- nop(holding(A)) vs nop(armEmpty): inherited mutex from layer k ✓
- Stack(A,B) (deletes holding(A), adds armEmpty) vs either nop: interference/inconsistent-effects ✓
- Any other action pair touching them likewise.
ALL pairs fail → mutex. (The AN paper made this a multi-select: all three justification types were correct.)
Worked Mini-Trace
Layer k facts: {on(A,B), holding(A), clear(B), clear(D), on(D,C), armEmpty} with known mutexes (on(A,B),holding(A)), (armEmpty,clear(B)).
- Start-state check: mutexes exist → not .
- candidates: Stack(A,B) needs holding(A)+clear(B) — but those are mutex at layer k! → excluded by competing needs, despite both being individually present. Putdown(A) needs only holding(A) ✓ included. Unstack(D,A)? needs on(D,A) — absent → excluded.
- Propagation:
on(A,B)andclear(B)stay mutex at k+1 via nop–nop inheritance (their layer-k mutex propagates).
That triple rhythm — state-check → applicability-with-mutex → propagation — solves every subquestion.