Q7 — Automated Planning Theory

GraphPlan's fine print: when two orderings are twins, exactly which precondition/effect overlaps make actions mutex, and the monotonicity of NON-mutex.

The Question

Answer the given subquestions.

#	Question	Official answer
7.1	Consider actions a and b and the two orderings (a then b) and (b then a). Which of the following conditions (each taken independently) will make both of the ...	A, B
7.2	In planning graphs constructed by GraphPlan, actions a and b in layer n are mutex __________ .	A, B
7.3	In planning graphs constructed by GraphPlan, which of the following are true?	A, B

The Topic in 60 Seconds

Concept	Test
Interchangeable orderings	neither action deletes a precondition or effect of the other, and their preconditions are jointly satisfiable
Action mutex (layer $n$ )	inconsistent effects: some add of one is deleted by the other; OR interference: one deletes a precondition/effect of the other; OR competing needs: some $p \in \text{pre}(a)$ , $q \in \text{pre}(b)$ are proposition-mutex in layer $n{-}1$
Non-mutex monotonicity	once two propositions co-exist in one layer, they co-exist in every later layer

Deep-dive: browse the Concepts section for GraphPlan.

Solutions

7.1 — Both orderings feasible → A, B

$(a \text{ then } b)$ and $(b \text{ then } a)$ succeed identically exactly when the actions do not step on each other:

No interference: $a$ deletes nothing that $b$ needs as precondition or brings as effect — and symmetrically for $b$ against $a$ .
Jointly satisfiable preconditions: running second leaves enough of the state intact for the other's PRE list.

Any condition asserting "a must delete something of b" or demanding exclusive resources kills one of the two orders → wrong by construction.

7.2 — Action mutex definition → A, B

Option	Reading	Verdict
A	$P \in \text{pre}(a)$ , $Q \in \text{pre}(b)$ are mutex in layer $n{-}1$	Correct — textbook competing needs
B	$P$ is in $\text{pre}(a)$ , in $\text{del}(a)$ , in $\text{pre}(b)$ and in $\text{del}(b)$	Correct — each action needs what both destroy (inconsistent supports); they cannot co-exist
C	only if EVERY precondition of $a$ is deleted by $b$	Far too strong — ONE overlapping deletion suffices ("only if" poisons it)
D	only if every add-effect of $a$ is deleted by $b$	Same disease

7.3 — Non-mutex monotonicity → A, B

GraphPlan's persistence semantics: if $P$ and $Q$ genuinely hold together in some layer (non-mutex), the no-op edges carry both forward forever — co-existence never regresses:

A ✓: non-mutex at layer 0 (the initial state) persists through all layers.
B ✓: non-mutex at any layer $n$ persists to all future layers.
C ✗: claims future mutex-ification — contradicts monotonicity; mutex sets can SHRINK going up, never the non-mutex relation.

The asymmetry to memorise: mutex-ness is proved fresh each layer (may disappear); non-mutex-ness, once established, is forever.

Tricks & Tips

Answers: 7.1 A, B · 7.2 A, B · 7.3 A, B