Action Ordering and GraphPlan Properties

When does order matter? When do mutexes persist? The theoretical edge cases that become multiple-choice traps

The Simplest Explanation

Two questions appear as theory MCQs independent of any Blocks World state:

Do two orderings a then b vs b then a give different results?
Do mutexes, once formed, persist?

Both test understanding of effects and monotonicity.

Remember This

Order matters only if actions interfere via add/del/prec overlap. Mutexes between actions, once broken, never return — but mutexes between propositions can shrink as more producers appear.

1. When Do Two Orderings Differ?

Papers ask (26T1 Q7.1): actions a and b, orderings a→b vs b→a, which conditions (each independently) make outcomes differ?

Condition	Why order matters	Example
P ∈ pre(a) and Q ∈ del(b) (or vice versa) where? Actually: if `a` needs P that `b` deletes, then `b→a` may become inapplicable	Precondition clobbered	`a` needs `clear(X)`, `b` = `Stack(Y,X)` deletes `clear(X)`
P ∈ add(a) ∩ del(b) (one adds, other deletes same fact)	Final state differs	`a` adds `on(A,B)`, `b` deletes `on(A,B)`
P ∈ pre(a) ∩ pre(b) with no interaction	Both need same fact → both orderings feasible (both can run, though perhaps not in same layer)	Both need `armEmpty` — order matters for feasibility only if resource consumed

Exam answer for 26T1 FN Q7.1: Options A (P in pre(a), Q in del(b)) and B (P in add(a) ∩ del(b)) — both make orderings differ. Option C "None" is wrong.

For 26T1 AN Q7.1: P ∈ pre(a)∩pre(b) and P ∈ del(a)∩del(b) — both keep orderings feasible (both need same resource or both delete same) → both orderings feasible.

2. GraphPlan Mutex Persistence

Q7.2 style: Which statements about mutex are true?

26T1 FN Q7.2: a and b in layer n are mutex if:

(C) P ∈ pre(a) ∩ del(b) → true (interference)
(D) P ∈ add(a) ∩ del(b) → true (inconsistent effects)
(A) "only if every P in pre(a) is mutex with every Q in pre(b)" → false (needs ANY, not EVERY — competing needs is ∃ mutex preconditions, not ∀)
(B) "only if every P in pre(a) is in del(b)" → false

Q7.3: True statements:

(A) If A and B are non-mutex in layer n, they remain non-mutex in all future layers → true (once mutex broken, never returns: more supporting actions appear, never fewer)
(B) Can become mutex later → false
Similarly for propositions: if P,Q non-mutex in layer 0, they remain so forever (A true), can become mutex later is false.

This monotonicity is key: mutexes only shrink over time (propositions monotonically increase, so more ways to achieve them appear).

Planning Graph vs Search

Layer 0 propositions = start state
Each layer adds no-ops (frame axioms) → $P_i \subseteq P_{i+1}$
Mutexes are over-approximations: non-mutex ≠ guaranteed co-achievable, but mutex = definitely not co-achievable at that layer

First layer where goals are non-mutex and extraction succeeds = optimal parallel plan length.

QuizActions a and b have P ∈ add(a) and P ∈ del(b). Are they mutex?

QuizIf two actions are non-mutex at layer 5, what about layer 6?