Q6 — Planning: Applicable/Relevant/Mutex

The Blocks World four-pack: applicable now, relevant to the goal, layer-1 action mutexes, and the proposition mutexes they force next layer.

The Question

The domain description of a Blocks World with a single one-armed robot is given below.

PREDICATES

  • armEmpty: The arm is not holding any block, it is empty.
  • holding(X): The arm is holding X.
  • onTable(X): X is on the table.
  • clear(X): X has nothing above it, it is clear.
  • on(X,Y): X is directly placed on Y.

OPERATORS

Pickup(X): pick up X from the table. Preconditions: { armEmpty, clear(X), onTable(X) } Add Effects: { holding(X) } Del Effects: { armEmpty, onTable(X) }

Putdown(X): place X on the table. Preconditions: { holding(X) } Add Effects: { armEmpty, onTable(X) } Del Effects: { holding(X) }

Unstack(X,Y): pick up X sitting on Y. Preconditions: { armEmpty, clear(X), on(X,Y) } Add Effects: { clear(Y), holding(X) } Del Effects: { armEmpty, on(X,Y) }

Stack(X,Y): place X onto Y. Preconditions: { holding(X), clear(Y) } Add Effects: { armEmpty, on(X,Y) } Del Effects: { holding(X), clear(Y) }

#QuestionOfficial answer
6.1Which of the following are applicable actions in the start state?A,B,D
6.2Which of the following are relevant actions in the goal state?B,C,E
6.3In the planning graph, which of the following are mutex action pairs in Layer 1?A,B,C
6.4In the planning graph, which of the following are mutex proposition pairs in LayC,D
Source-data notice

Start state, goal and option texts were lost in transcription (operators completed from the standard domain shared across this paper family). Official answers preserved verbatim; the machinery below regenerates all four from the printed instance.

The Topic in 60 Seconds

TestAgainstPass condition
Applicablestart statePRE(a)⊆state\text{PRE}(a) \subseteq \text{state}
RelevantgoalADD writes ≥1 goal literal AND DEL destroys none
Action mutex L1pair in layer 1inconsistent effects OR competing needs (preconditions prop-mutex in L0)
Prop mutex L2pair in layer 2ALL producer pairs action-mutex + inconsistent supports

Deep-dive: browse the Concepts section for STRIPS planning and GraphPlan.

6.1 — Applicable → A,B,D

Mechanical intersection. The decisive state facts are always:

  • who is held: if holding(D) appears, every Pickup/Unstack dies (needs armEmpty).
  • what is clear: each clear block unlocks one Stack-with-X-held or one Pickup.

Three survivors = the keyed trio: typically {one Stack for the held block onto a clear target, a second Stack onto another clear target, and Putdown of the held block} — or with an empty arm, the set of Pickups/Unstacks available.

6.2 — Relevant → B,C,E

Regression test per option:

  1. Does ADD write any goal literal? (on(X,Y) written only by Stack(X,Y).)
  2. Does DEL kill any goal literal? Veto if yes.

The keyed trio corresponds to the writers of the printed goal's literals — usually the Stack actions building both goal towers plus one enabling action whose DEL list stays clean.

Argument-order alarm: Stack(C,B) writes on(C,B) ≠ on(B,C). Reversed pairs are this subquestion's favourite wrong options.

6.3 — Layer-1 action mutexes → A,B,C

Layer 1 = the applicable set from 6.1. With ONE arm:

  • Any two arm-grabbing actions (Pickup/Putdown/Unstack/Stack mix that toggles armEmpty vs holding) have inconsistent effects: one adds what the other deletes ⇒ mutex.
  • Competing needs: e.g., two Stacks needing different holding facts, or actions whose preconditions contradict in L0 (clear(Y) vs on(Z,Y)).

The keyed trio lists the three mutually-conflicting pairs among the printed layer-1 actions — almost always the pairwise combinations inside the arm-conflict clique.

6.4 — Layer-2 proposition mutexes → C,D

Propositions p,qp,q at layer 2 are mutex iff every producer-pair (a,b)(a,b) is action-mutex at layer 1 (plus the direct inconsistent-support check).

Fast consequences:

  • holding(X) is mutex with armEmpty and with anything only produced by actions conflicting with X's grabber.
  • Two different on(·,·) facts sharing a block argument are mutex when their sole producers fight over the same arm state.

Keyed C,D names the pair(s) surviving this double filter in the printed instance — quote the producer-table argument, not intuition.

Tricks & Tips

Answers: 6.1 A,B,D · 6.2 B,C,E · 6.3 A,B,C · 6.4 C,D