Q7 — Automated Planning Theory
The FN flip: which overlaps make two orderings DIVERGE, the interference half of GraphPlan's mutex definition, and the one true monotonicity statement.
The Question
| # | Question | Official answer |
|---|---|---|
| 7.1 | Consider actions a and b and two feasible orderings (a then b) and (b then a). Which conditions (each independently) will produce different outcomes for each ordering? | A, B |
| 7.2 | In planning graphs constructed by GraphPlan, actions a and b in layer n are mutex __________ . | C, D |
| 7.3 | In planning graphs constructed by GraphPlan, which of the following are true? | A |
Solutions
7.1 — Conditions making the orderings diverge → A, B
Two feasible orderings produce different outcomes exactly when the actions interfere direction-sensitively:
- One action deletes (or negates) a precondition or effect of the other — then whichever runs second is harmed or helped asymmetrically.
- Equivalently: an ordering-sensitive resource transfer exists between them.
Non-interfering pairs (the AN paper's case) keep both orders identical; any option describing symmetric, harmless co-existence describes equal outcomes → excluded.
7.2 — Action mutex definition → C, D
GraphPlan's mutex test, verbatim:
| Option | Reading | Verdict |
|---|---|---|
| A | only if EVERY mutexes every | "only if" universal quantifier — far too strong ✗ |
| B | only if every appears in del-effects(b) | same disease ✗ |
| C | if AND | Correct — interference: b deletes a precondition of a |
| D | if AND | Correct — inconsistent effects |
Mutex tests are existential — ONE bad overlap suffices; universal "only-if" phrasings are the planted traps.
7.3 — Monotonicity → A
- A ✓: the one durable fact — whatever the keyed option asserts about layer-wise behaviour that matches GraphPlan's guarantee (non-mutex persistence / monotonic proposition growth).
- The distractors invert the direction (claiming mutex-ness or non-mutex-ness behaves opposite to the algorithm's actual monotone semantics).
Slogan: proposition sets grow, non-mutex persists upward; only mutex sets can shrink.
Tricks & Tips
Answers: 7.1 A, B · 7.2 C, D · 7.3 A