Graphplan and Mutual Exclusion

Build the space of all possible plans as a layered graph, then hunt mutex pairs — the technique that jumped planning from 15 to 200 steps

The Simplest Explanation

Earlier planners searched for ONE plan at a time. Graphplan (Blum & Furst, 1995) does something cleverer:

Stage 1: build a "planning graph" — a compact summary of EVERYTHING that could possibly happen at each time step. Stage 2: search inside it for a real plan.

The magic ingredient is mutex (mutual exclusion): pairs of actions or facts that cannot both be true at the same step. Mutex reasoning prunes impossible combinations before search ever touches them. Result: solvable plan lengths jumped from ~15 steps to ~200.

Remember This

Planning graph layers alternate: P₀ → A₁ → P₁ → A₂ → P₂ … Facts live in P layers, actions in A layers, and every fact has an invisible no-op action keeping it alive into later layers.

Building the Planning Graph

Start with $P_0$ = start state's propositions. Then repeat:

$A_i$ = all actions whose preconditions all appear in $P_{i-1}$ (plus no-ops)
$P_i$ = union of all effects (adds) of actions in $A_i$

Three kinds of edges connect action→proposition layers:

Edge	Meaning
Precondition links	action ← facts it needs
Positive effect links (+)	facts it adds
Negative effect links (−)	facts it deletes

Example: Blocks World

Start: OnTable(A), OnTable(B), Clear(A), Clear(B), ArmEmpty.

Note $a_1$ and $a_2$ : both need ArmEmpty and each deletes it — they are mutex, so Holding(A) and Holding(B) will be mutex in $P_1$ . The one-armed robot can't hold two blocks!

Mutex Rules (the exam's favorite table)

Two actions in the same layer are mutex if ANY holds:

Condition	Intuition
Inconsistent effects	one adds $p$ , the other deletes $p$
Interference	one deletes a precondition of the other
Competing needs	their preconditions include propositions that are mutex
Inconsistent support / same resource	both consume the same required resource (e.g., both need ArmEmpty)

Two propositions in the same layer are mutex if ALL pairs of actions producing them are mutex.

Direction Matters

Action mutex is an ANY-condition test; proposition mutex is an ALL-producers test. Mixing these up is the most common exam mistake.

NOP-Action Distractors (2024 papers)

Papers include no-op actions as answer options in Layer-1 action-mutex questions. Remember: every proposition carries a nop, and a nop can absolutely participate in mutexes — e.g., Stack(C,D) and the nop for holding(C) are mutex (Stack deletes/uses holding(C); inconsistent effects + interference). Don't dismiss an option just because it says "nop". Judge it by the same four conditions.

Monotonicity, Leveling Off, Termination

Proposition layers grow monotonically (facts only get added, never removed — thanks to no-ops)
Action layers likewise
Mutex relations first increase, then shrink as more supportive actions appear in later layers
When layer $k$ and $k+1$ have identical facts AND identical mutexes → leveled off

Termination logic:

All goal facts present in some $P_i$ and pairwise non-mutex → try solution extraction (backward search picking non-mutex actions)
Graph leveled off without goal facts appearing → provably no solution exists
Extraction fails? Grow one more layer and retry — the first successful extraction gives a minimum-makespan (shortest parallel) plan

Worked Exam-Style Check

Q: In the graph above, is the pair ⟨Pickup(A), Pickup(B)⟩ mutex at $A_1$ ?

Check each condition:

Inconsistent effects? Pickup(A) adds Holding(A); neither deletes the other's add... no direct conflict.
Interference? Does either delete a precondition of the other? Pickup(B)'s preconditions: OnTable(B), Clear(B), ArmEmpty. Neither pickup deletes those... wait — actually neither deletes the other's preconditions directly.
Competing needs? Their shared precondition ArmEmpty is trivially non-mutex with itself...
Same resource? Both require AND delete ArmEmpty ✓

⟨Pickup(A), Pickup(B)⟩ = mutex by inconsistent-support/resource consumption. Consequently Holding(A) ⊕ Holding(B) are mutex at $P_1$ (their only producers are mutually exclusive).

Exam answers should cite the specific condition name, not just "yes".

Properties

Property	Value
Complete?	Yes — levels off in finite domains; absence of goal then proves unsolvability
Optimal?	Yes w.r.t. makespan (number of parallel time steps), NOT number of actions
Planning-graph size	Polynomial in problem size (vs exponential state space)
Key weakness	Solution extraction can fail spuriously (mutexes are conservative), forcing extra layers

QuizWhy does every proposition get a 'no-op' action in the planning graph?

QuizPropositions p and q in the SAME layer are mutex when...

QuizIf the planning graph levels off and some goal proposition never appeared, we may conclude...