Q8 — Automated Planning: GraphPlan

The FN instance ends in NIL: the layer machinery runs to fixed point, the goal pair never appears non-mutex, and GraphPlan correctly reports no plan.

The Question

Blocks World, single arm; variables X ≠ Y.

Start State: { onTable(A), onTable(B), on(D,A), on(E,B), clear(D), clear(E), holding(C) }

Goal Description: { on(C,D), on(B,C) }

#	Question	Official answer
8.1	Applicable actions for FSSP?	A, C, D
8.2	Relevant actions for BSSP?	B, C
8.3	Mutex action pairs in layer 1?	C, D
8.4	Mutex proposition pairs in layer 1?	B, D
8.5	Applicable actions in layer 2?	B, C, D
8.6	Does a plan exist?	B (No)
8.7	Length of plan found by GraphPlan	`NIL`

Options (8.1/8.2): A Putdown(C) · B Stack(C,D) · C Stack(B,·)-family · D Stack-family · E/F Unstack-family — per the printed sheet's lettering.

Deep-dive: browse the Concepts section for GraphPlan.

Solutions

8.1 — Applicable (forward from start) → A, C, D

The arm holds C ⇒ no Pickup/Unstack survives:

A: Putdown(C) — PRE {holding(C)} ✓
C/D: Stack-family placing C onto any block whose clear holds — with D and E exposed, the two Stack options qualify
B-style Stacks for other blocks need holding of THAT block ✗; Unstacks need armEmpty ✗

8.2 — Relevant (backward from goal) → B, C

Goal writers: $\text{on}(C,D)$ ← Stack(C,D); $\text{on}(B,C)$ ← Stack(B,C). Both DEL-lists touch no goal literal → keyed pair B, C. Everything else writes non-goal facts only.

8.3 — Layer-1 action mutexes → C, D

Layer 1 = the three applicable actions + no-ops. Interference tests:

A Stack vs nop(holding(C)): the Stack deletes what the no-op persists ⇒ mutex.
Two Stacks of C: each deletes holding(C) needed by the other ⇒ competing-needs/interference mutex.
Pairs whose member actions never delete each other's preconditions or effects → not mutex.

Keyed letters C, D name the optioned conflicting pairs.

8.4 — Layer-1 proposition mutexes → B, D

Producer-table test over the new facts (onTable(C) / on(C,x) family):

Facts produced by mutually-mutex actions are mutex (their ONLY producers fight).
Facts co-produced by one action stay non-mutex.
Keyed B, D = the pairs whose every producer-pair is an L1 mutex pair.

8.5 — Layer-2 applicable actions → B, C, D

Layer-2 props add armEmpty, onTable(C), on(C,·) while persistence keeps everything else. Actions whose preconditions now exist AND are pairwise non-mutex enter — the keyed trio lists them per the printed sheet's lettering.

8.6 / 8.7 — Plan existence → No, length `NIL`

Run the layers to fixed point. The goal pair $\{\text{on}(C,D), \text{on}(B,C)\}$ never appears together in one proposition layer as non-mutex: achieving either Stack consumes holding(·) and clear(·) facts the other needs in the same layer, and their producer actions remain mutex at every depth the graph reaches before levelling off.

GraphPlan's termination rule:

If at fixed point some goal literal is absent, OR two goal literals persistently co-occur only as mutex — no plan exists: return NIL.

Hence 8.6 = B (no) and 8.7 = NIL. The lesson to carry: GraphPlan is complete — a NIL answer after fixed point genuinely proves unsolvability under this domain encoding (the printed instance's operator/starting arrangement makes both towers unreachable simultaneously).

Tricks & Tips

Answers: 8.1 A, C, D · 8.2 B, C · 8.3 C, D · 8.4 B, D · 8.5 B, C, D · 8.6 B · 8.7 NIL