AI Search · Exam notes

Planning Graphs: GraphPlan Layers, Applicability, Mutexes

Newer papers ask GraphPlan mid-flight: two proposition layers are given and you populate what is between them. Four sub-questions: is layer k the start? which actions enter layer k+1? which action pairs are mutex? why is a proposition pair non-mutex? One chain answers all: mutexes rule out the start state, pres plus pairwise mutexes admit actions, effects plus pres decide action mutexes, producers decide proposition mutexes.

Points 1 and 2 are the rules. Point 3 applies them to a mid-flight graph on blocks A, B, C. Point 4 has two drills to solve with a pen.

1. Structure in two tables

LayerContents
P0, P1, ...Proposition layers. P0 is the start state and never has mutexes. Each next layer keeps old props (via no-ops) and adds action effects.
A1, A2, ...Action layers. An action enters A(n+1) only if its pres are present in Pn AND pairwise non-mutex there. No-ops (persist P) are always in.
No-opPre P, add P, no deletes. Never mutex with another no-op. Numbered nop-1, nop-2, ... in layer order.
Mutex ruleTest (any one kills)
Actions: interferencedel(a) hits pre(b), either way round
Actions: inconsistent effectsadd(a) hits del(b), either way round
Actions: competing needsa pre and a pre of b are mutex in Pn (includes sharing the one arm)
Props: mutexEVERY producer pair (action or no-op) is mutex. One clean pair kills the mutex.

Memory hooks from the theory sub-questions: actions need any of the conditions (all four listed options hold at once); propositions need every producer pair mutex, so non-mutex needs only one clean pair. Ordering outcomes: pre+del across two actions makes one ordering infeasible; add+del makes both feasible with different results.

2. The four checks

  1. Is layer k the start? P0 never carries mutexes. Any mutex pair in the layer rules out the start state at once.
  2. Applicable in k+1? Pres present in layer k AND pairwise non-mutex there. In layer 1 (built on a mutex-free start) presence alone decides; deeper layers need both tests.
  3. Mutex actions? Run interference first (del vs pre), then inconsistent effects (add vs del), then competing needs (pre vs pre in the mutex list).
  4. Prop pair in k+1? List every producer of each side (domain actions that add it, plus its no-op), then test every producer pair. Name the one clean pair for non-mutex, or show all pairs dirty for mutex.
Theory sub-questionVerified key
Orderings: only one of (a then b) / (b then a) feasibleP in pre(a) and P in del-effects(b)
Orderings: both feasible with different outcomesP in add-effects(a) and P in del-effects(b)
Actions a,b mutex in layer nALL FOUR hold at once: competing needs, pre plus del both ways, interference, inconsistent effects
Props P,Q mutexEVERY producer pair mutex
Props P,Q non-mutexAT LEAST ONE producer pair non-mutex

3. Worked example: mid-flight graph, layers k and k+1

3a. The layers as tables (solve from this, then check the walkthrough)

Layer k (7 props)Mutex pairs in k (4)
clear(A), on(A,B), armEmpty, clear(B), holding(A), on(B,C), onTable(C)(on(A,B),holding(A)), (on(A,B),clear(B)), (armEmpty,clear(B)), (armEmpty,holding(A))
No-opPersistsLayer k+1 (8 props)
nop-1 .. nop-7clear(A), on(A,B), armEmpty, clear(B), holding(A), on(B,C), onTable(C)all 7 persist, plus new onTable(A) (added by Putdown(A))
CandidateGrounded pre / add / del
Putdown(A)pre: holding(A). add: armEmpty, onTable(A). del: holding(A).
Stack(A,B)pre: holding(A), clear(B). add: armEmpty, on(A,B). del: holding(A), clear(B).
Unstack(A,B)pre: armEmpty, clear(A), on(A,B). add: holding(A), clear(B). del: armEmpty, on(A,B).
Unstack(B,C)pre: armEmpty, clear(B), on(B,C). add: holding(B), clear(C). del: armEmpty, on(B,C).

Cover the walkthrough. Test each candidate against layer k, pair the survivors, then settle the producers of armEmpty and clear(B).

3b. Walkthrough: one verdict per step

Step 0 | filled chip = present / mutex / clean pair, dashed chip = absent / killed, struck pair = the mutex that kills

Why this step

Tracker

3c. The four questions

GraphPlan mid-flight on Blocks World. Layers k and k+1 as above, both fully populated; layer-k mutexes as above. Action layer holds nop-1..nop-7 plus applicable domain actions.

  1. Layer k: start state / cannot be start / insufficient information?
  2. Applicable in k+1: Putdown(A), Stack(A,B), Unstack(A,B), Unstack(B,C)?
  3. Mutex pairs in k+1: (Putdown(A),Stack(A,B)), (Stack(A,B),Unstack(A,B)), (nop-3,nop-4)?
  4. armEmpty and clear(B) in k+1 are non-mutex because: nop-3+nop-4 clean / Putdown(A)+nop-4 clean / None?

3d. Answers first, then the working

Layer k cannot be the start state. Applicable: Putdown(A), Stack(A,B), Unstack(A,B). Mutex: all three pairs. armEmpty + clear(B) non-mutex because Putdown(A) and nop-4 are clean.

CandidatePres in k?Pre pairs mutex in k?In?
Putdown(A)holding(A) presentsingle pre: no pairYes
Stack(A,B)holding(A), clear(B) present(holding(A),clear(B)) not in mutex listYes
Unstack(A,B)armEmpty, clear(A), on(A,B) presentnone of the 3 pairs in the listYes
Unstack(B,C)armEmpty, clear(B), on(B,C) present(armEmpty,clear(B)) IS in the listNo
  1. Q21: layer k carries four mutex pairs; P0 never has any. Cannot be the start state.
  2. Q23 pairs. (Putdown(A),Stack(A,B)): Putdown deletes holding(A), which Stack needs: interference, mutex. (Stack(A,B),Unstack(A,B)): Stack adds armEmpty and on(A,B) while Unstack deletes both: inconsistent effects (plus competing needs via holding(A) vs armEmpty), mutex. (nop-3,nop-4): pres armEmpty vs clear(B) are mutex in k: competing needs, mutex.
  3. Q24 producers. armEmpty in k+1 comes from nop-3, Putdown(A) (adds armEmpty) and Stack(A,B) (adds armEmpty). clear(B) comes from nop-4 and Unstack(A,B) (adds clear(B)). Six producer pairs: (nop-3,nop-4) mutex by competing needs; (nop-3,Unstack(A,B)) mutex by interference (Unstack deletes armEmpty); (Putdown(A),Unstack(A,B)) mutex by inconsistent effects (armEmpty added and deleted); (Stack(A,B),nop-4) mutex by interference (Stack deletes clear(B)); (Stack(A,B),Unstack(A,B)) mutex (see Q23). The one clean pair is Putdown(A)+nop-4: deletes {holding(A)} vs pre {clear(B)}, adds {armEmpty, onTable(A)} vs no deletes, needs holding(A) vs clear(B) not mutex in k. One clean pair kills the mutex: non-mutex because of Putdown(A)+nop-4. The first option is the trap: nop-3 and nop-4 ARE mutex.

4. Practice: two drills

Solve each with a pen before opening the answer. Each drill is self contained.

Drill G1: clean layer, arm clash

Layer k props: holding(A), clear(B), armEmpty, no mutexes. Q1: which of Putdown(A), Stack(A,B), Pickup(A) are applicable in k+1? Q2: is (Putdown(A),Stack(A,B)) mutex?

Step 0

Why this step

Tracker

Answer G1

Q1: Putdown(A), Stack(A,B). Pickup(A) needs onTable(A), absent. With no mutexes in k, presence alone decides. Q2: yes, interference: Putdown deletes holding(A), which Stack needs.

Drill G2: mutex pres kill the action

Layer k props: holding(A), clear(B), mutex: (holding(A),clear(B)). Q1: is Stack(A,B) applicable in k+1? Is Putdown(A)? Q2: in k+1, is (onTable(A),clear(B)) mutex? Producers: onTable(A) only from Putdown(A); clear(B) only from its no-op.

Step 0

Why this step

Tracker

Answer G2

Q1: Stack(A,B) is OUT: both pres present but mutex in k. Putdown(A) is IN (single pre, no pair to check). Q2: mutex, via competing needs: Putdown(A) needs holding(A), the no-op needs clear(B), and that pair is mutex in k. Lesson: pres can clash even when the actions never touch the same literal.

5. Exam checklist (write this on the rough sheet)

  1. Any mutex in the layer rules out the start state at once.
  2. Applicable = pres present AND pairwise non-mutex in the layer below. Single-pre actions skip the second test.
  3. New props in k+1 come only from action adds. Name the adding action (here Putdown(A) gives onTable(A)).
  4. Mutex actions: interference first, then inconsistent effects, then competing needs.
  5. Prop pairs: list every producer of each side first. One clean producer pair means non-mutex; name it.
  6. No-op vs no-op is never mutex. An action vs a no-op still can be (its pre or add may clash).