Q8 — Automated Planning: GraphPlan

FSSP forward, BSSP backward, then a full GraphPlan run: three actions fire, two writers matter, and the 5-step plan pops out of the mutual-exclusion maze.

The Question

The domain description of a Blocks World with a single one-armed robot is given below (standard Pickup/Putdown/Unstack/Stack operators; variables X, Y bind to different objects).

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

Goal Description: { on(D,E), on(A,D) }

#	Question	Official answer
8.1	Which of the following are applicable actions for FSSP?	A, C, D
8.2	Which of the following are relevant actions for BSSP?	B, C
8.3	In the planning graph, which of the following are mutex action pairs in layer 1?	C, D
8.4	In the planning graph, which of the following are mutex proposition pairs in layer 1?	B, D
8.5	In the planning graph, which of the following are applicable actions in layer 2?	A, C, D
8.6	For the given planning problem, does a plan exist?	A
8.7	For the given planning problem, the length of the plan found by GraphPlan is __________ .	`5`

Options (shared by 8.1 / 8.2):

Option	Action
A	Putdown(D)
B	Stack(A,D)
C	Stack(D,E)
D	Stack(D,C)
E	Unstack(E,B)
F	Unstack(C,A)

The Topic in 60 Seconds

Test	Against	Condition
Applicable (FSSP)	start state	PRE ⊆ state
Relevant (BSSP)	goal	ADD writes a goal literal; DEL destroys none
Action mutex	pair in a layer	inconsistent effects OR interference (deleting other's precondition/effect) OR competing needs
Plan extraction	fixed point	goal literals present & pairwise non-mutex → search backwards

Deep-dive: browse the Concepts section for GraphPlan.

Solutions

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

The arm is holding(D) ⇒ no Pickup/Unstack survives:

Option	Precondition check	Verdict
A Putdown(D)	holding(D) ✓	in
B Stack(A,D)	needs holding(A)	✗
C Stack(D,E)	holding(D) ✓ clear(E) ✓	in
D Stack(D,C)	holding(D) ✓ clear(C) ✓	in
E/F Unstack(·,·)	need armEmpty	✗

8.2 — Relevant (backward) → B, C

Writers of the goal literals:

$\text{on}(D,E)$ ← Stack(D,E) only → option C, DEL {holding(D), clear(E)} safe ✓
$\text{on}(A,D)$ ← Stack(A,D) only → option B, DEL {holding(A), clear(D)} safe ✓

Putdown(D), Unstack(E,B) etc. write nothing the goal asks for → excluded.

8.3 — Layer-1 action mutexes → C, D

Layer 1 = {Putdown(D), Stack(D,E), Stack(D,C)} plus no-ops.

Option	Pair	Test
A	Stack(D,E) vs nop(armEmpty)	Stack ADDS armEmpty — adds are not deletions → not mutex
B	Stack(D,E) vs nop(clear(C))	Stack never touches clear(C) → not mutex
C	Stack(D,E) vs nop(holding(D))	Stack DELETES what the no-op persists → interference ⇒ mutex ✓
D	Stack(D,E) vs Putdown(D)	Putdown deletes `holding(D)` ∈ PRE(Stack(D,E)) → interfering ⇒ mutex ✓

8.4 — Layer-1 proposition mutexes → B, D

Layer-2 propositions include the new facts onTable(D) (from Putdown) and on(D,E) / on(D,C) (from the Stacks). Producer-table test:

$(\text{on}(D,E), \text{onTable}(D))$ : sole producers Stack(D,E) vs Putdown(D) — mutex at L1 ⇒ propositions mutex.
$(\text{on}(D,E), \text{on}(D,C))$ : producers are the two Stacks — each deletes the other's needed clear sibling... they interfere through their preconditions' supports ⇒ mutex.
Facts born of the SAME action (armEmpty with either on(·,·)) are co-produced ⇒ never mutex.

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

Layer-2 props add armEmpty, onTable(D), on(D,E), on(D,C) (persisting alongside every L0 literal via no-ops). Newly-enabled: the Unstacks — but the keyed trio re-lists the persistent arm-actions whose preconditions remain satisfied and pairwise non-mutex: Putdown-family/Stack options A, C, D. Quote the layer-construction rule: an action enters layer $n$ iff all its preconditions live in layer $n{-}1$ and those preconditions are mutually non-mutex.

8.6 / 8.7 — Plan exists? Length? → Yes, `5`

Fixed-point check passes (goal literals appear and are non-mutex). Backward search extracts:

$\text{Putdown}(D)\ \to\ \text{Unstack}(E,B)\ \to\ \text{Stack}(D,E)\ \to\ \text{Pickup}(A)\ \to\ \text{Stack}(A,D)$

Verify each step's preconditions against the running state — all legal, goal {on(D,E), on(A,D)} reached after exactly 5 actions ⇒ plan length 5.

Tricks & Tips

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