AI Search · Exam notes

Automated Planning: Blocks World, Applicability, Relevance, Mutexes

One planning comprehension per paper, four sub-questions on one start/goal pair: which actions are applicable? which are relevant? which action pairs are mutex in Layer 1? which proposition pairs are mutex in Layer 1? One chain answers all: test preconditions against the start state, test effects against the goal, then build one planning-graph layer and check producers.

Points 1 and 2 are the rules. Point 3 applies them to a five-block problem. Point 4 has two drills to solve with a pen.

1. Domain in two tables

PredicateMeaning
on(X,Y)X sits directly on Y
onTable(X)X sits on the table
clear(X)nothing is on X
holding(X)the arm holds X
armEmptythe arm holds nothing
ActionPreconditionsAddDelete
Pickup(X)onTable(X), clear(X), armEmptyholding(X)onTable(X), armEmpty
Putdown(X)holding(X)onTable(X), armEmptyholding(X)
Unstack(X,Y)on(X,Y), clear(X), armEmptyholding(X), clear(Y)on(X,Y), armEmpty
Stack(X,Y)holding(X), clear(Y)on(X,Y), armEmptyholding(X), clear(Y)

2. The four checks

  1. Applicable in start (asked as FSSP): every precondition is in the start state. One missing precondition kills the action. Not clear and not held are the usual killers. FSSP is forward search from the start, so it asks applicable actions.
  2. Relevant to goal (asked as BSSP): add effects hit the goal (\(add \cap goal \ne \emptyset\)) AND delete effects miss the goal (\(del \cap goal = \emptyset\)). Both must hold. BSSP is backward search from the goal, so it asks relevant actions.
  3. Mutex actions in Layer 1: a pair is mutex if any one holds: inconsistent effects (one adds P, the other deletes P), interference (one deletes the other's precondition), or competing needs (preconditions mutex, which includes two actions consuming the one arm, since each deletes \(armEmpty\) the other needs).
  4. Mutex propositions in Layer 1: P and Q are mutex only if every way of producing P is mutex with every way of producing Q. Ways = applicable domain actions plus the no-op (persistence) of each start proposition. One non-mutex producer pair kills the mutex.

3. Worked example: five blocks, goal on(B,C), on(A,B)

3a. Start and goal, redrawn from the data (solve from this, then check the animation)

D
A
E
B
C

Start. Arm: empty.

A
B
C

Goal: on(B,C), on(A,B).

StatePropositions
StartonTable(A), onTable(B), onTable(C), clear(D), clear(E), clear(C), on(D,A), on(E,B), armEmpty
Goalon(B,C), on(A,B)
Layer 1 actionGrounded pre / add / del
Unstack(D,A)pre: armEmpty, clear(D), on(D,A). add: holding(D), clear(A). del: on(D,A), armEmpty.
Unstack(E,B)pre: armEmpty, clear(E), on(E,B). add: holding(E), clear(B). del: on(E,B), armEmpty.
Pickup(C)pre: armEmpty, clear(C), onTable(C). add: holding(C). del: onTable(C), armEmpty.
No-ops (9)Each start proposition persists itself: pre P, add P, no deletes.

New propositions in Layer 1: clear(A), holding(D), clear(B), holding(E), holding(C). Everything else persists via no-ops.

3b. Walkthrough: test every candidate on chips, one step at a time

Step 0 | filled chip = present in start / hits goal, dashed chip = absent / misses goal, thick chip = deletes a goal literal and kills relevance

Why this step

Tracker

3c. The four questions

Blocks World with one arm, start and goal as above. Candidates: Putdown(D), Unstack(D,A), Unstack(E,B), Pickup(C), Pickup(A), Stack(A,B), Stack(B,C).

  1. Which are applicable actions in the start state?
  2. Which are relevant actions for the goal?
  3. Which pairs are mutex actions in Layer 1? Candidates: (Unstack(D,A), Pickup(C)), (Unstack(D,A), Unstack(E,B)), (Pickup(C), Stack(A,B)), (Pickup(C), Stack(B,C)).
  4. Which pairs are mutex propositions in Layer 1? Candidates: (clear(A), holding(E)), (clear(A), clear(B)), (clear(C), on(D,A)), (clear(C), holding(E)).

3d. Answers first, then the working

Applicable: Unstack(D,A), Unstack(E,B), Pickup(C). Relevant: Stack(A,B), Stack(B,C). Mutex actions: (Unstack(D,A), Pickup(C)), (Unstack(D,A), Unstack(E,B)). Mutex propositions: (clear(A), holding(E)), (clear(A), clear(B)).

CandidatePre checkApplicable?
Putdown(D)holding(D) missing (arm is empty)No
Unstack(D,A)armEmpty, clear(D), on(D,A) all presentYes
Unstack(E,B)armEmpty, clear(E), on(E,B) all presentYes
Pickup(C)armEmpty, clear(C), onTable(C) all presentYes
Pickup(A)clear(A) missing (D sits on A)No
Stack(A,B)holding(A) missingNo
Stack(B,C)holding(B) missingNo
Candidateadd vs goaldel vs goalRelevant?
Putdown(D){armEmpty, onTable(D)} hits nothing-No
Unstack(D,A){holding(D), clear(A)} hits nothing-No
Unstack(E,B){holding(E), clear(B)} hits nothing-No
Pickup(C){holding(C)} hits nothing-No
Pickup(A){holding(A)} hits nothing-No
Stack(A,B)adds on(A,B): hits goal{holding(A), clear(B)} misses goalYes
Stack(B,C)adds on(B,C): hits goal{holding(B), clear(C)} misses goalYes
  1. Mutex actions. (Unstack(D,A), Pickup(C)): each deletes \(armEmpty\), which the other needs. Interference both ways: mutex. (Unstack(D,A), Unstack(E,B)): same reason: mutex. (Pickup(C), Stack(A,B)) and (Pickup(C), Stack(B,C)): Stack needs holding, which Pickup neither needs nor deletes, and Pickup deletes nothing Stack needs. No clash: not mutex. (Stack is not even in Layer 1, its preconditions are absent from the start state.)
  2. Mutex propositions. (clear(A), holding(E)): clear(A) comes only from Unstack(D,A); holding(E) only from Unstack(E,B); that producer pair is mutex, so the pair is mutex. (clear(A), clear(B)): same two producers: mutex. (clear(C), on(D,A)): clear(C) persists only by no-op, on(D,A) persists only by no-op, and no-ops are never mutex with each other: not mutex. (clear(C), holding(E)): clear(C) only by no-op; holding(E) only by Unstack(E,B); Unstack(E,B) deletes \(armEmpty\) and \(on(E,B)\), needs \(armEmpty, clear(E), on(E,B)\), none of which touches clear(C): not mutex with the no-op: not mutex.

4. Practice: two drills

Solve each with a pen before opening the answer. Each drill is self contained.

Drill P1: two blocks on the table

Start: onTable(A), onTable(B), clear(A), clear(B), armEmpty. Goal: on(A,B). Q1: which of Pickup(A), Pickup(B), Unstack(A,B), Stack(A,B), Putdown(A) are applicable? Q2: which are relevant?

Step 0

Why this step

Tracker

Answer P1

Applicable: Pickup(A), Pickup(B). Unstack(A,B) needs on(A,B), absent. Stack(A,B) and Putdown(A) need holding, absent. Relevant: Stack(A,B) only: it adds on(A,B) and deletes neither goal literal. Pickup adds only holding, Unstack adds holding(A) and clear(B), Putdown adds onTable: none hit the goal.

Drill P2: mutexes on the same two blocks

Same start as P1. Layer 1 actions: Pickup(A), Pickup(B), plus no-ops. New props: holding(A), holding(B). Q1: is (Pickup(A), Pickup(B)) mutex? Q2: which of (holding(A), holding(B)), (holding(A), armEmpty), (onTable(A), clear(A)), (clear(A), holding(B)) are mutex in Layer 1?

Step 0

Why this step

Tracker

Answer P2

Q1: yes, interference: each deletes \(armEmpty\), which the other needs. Q2: (holding(A), holding(B)) mutex (sole producers Pickup(A), Pickup(B) are mutex). (holding(A), armEmpty) mutex (holding(A) only from Pickup(A), which deletes \(armEmpty\) that the persisting no-op needs). (onTable(A), clear(A)): both persist by no-ops only: not mutex. (clear(A), holding(B)): clear(A) by no-op, holding(B) by Pickup(B), and Pickup(B) neither needs nor deletes clear(A): not mutex.

5. Exam checklist (write this on the rough sheet)

  1. Write the full start set. Missing clear and missing holding kill most options.
  2. Applicable: every precondition present. Check armEmpty first, it kills Stack and Putdown fast.
  3. Relevant: add hits goal AND delete misses goal. Test both, in that order.
  4. Mutex actions: check interference first (delete vs precondition), then inconsistent effects, then competing needs. The arm is one resource: two arm-users are mutex.
  5. Mutex propositions: list every producer (domain action or no-op) of each side. One non-mutex producer pair means not mutex.
  6. No-ops are never mutex with each other. Persistence is always safe.