Q11 — AUTOMATED PLANNING

Holding D opens exactly three doors right now, but relevance only blesses the two Stack actions that write goal facts directly.

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 that is directly 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 directly on top of Y.
  Preconditions: { holding(X), clear(Y) }
  Add Effects  : { armEmpty, on(X,Y) }
  Del Effects  : { holding(X), clear(Y) }

Consider the following planning problem.

Start State: Start: { onTable(A), onTable(B), on(C,B), clear(A), clear(C), clear(D), holding(D) }

Goal Description: Goal: { on(A,D), on(B,C) }

#	Question	Official answer
11.1	Which of the following are applicable actions for the given problem?	A, B, C
11.2	Which of the following are relevant actions for the given problem?	A, B

The Topic in 60 Seconds

Notion	Tested against	Meaning
Applicable	Start state	every literal of $\text{PRE}(a)$ is present right now
Relevant	Goal description	$\text{ADD}(a)$ writes a goal literal and $\text{DEL}(a)$ destroys none of them

The two tests are independent: an applicable action can be useless; a relevant action may need five moves before it can run.

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

Solutions

11.1 — Applicable actions → A, B, C

Start state highlights: armEmpty is absent — the robot is holding(D) — while A, C, D are all clear.

Option	Preconditions required	Present?	Verdict
A `Putdown(D)`	holding(D)	✓	Applicable
B `Stack(D,A)`	holding(D) ✓, clear(A) ✓	both	Applicable
C `Stack(D,C)`	holding(D) ✓, clear(C) ✓	both	Applicable
D `Pickup(A)`	needs armEmpty	✗ robot busy	Not applicable
E `Stack(A,D)`	needs holding(A)	✗ holding D	Not applicable
F `Stack(B,C)`	needs holding(B)	✗	Not applicable

Exactly three actions fire — put D down, or drop it onto either exposed block.

11.2 — Relevant actions → A, B

Regress the goal $\{\text{on}(A,D),\ \text{on}(B,C)\}$ :

$\text{on}(A,D)$ is added by exactly one action: Stack(A,D) → option A. Its delete list {holding(A), clear(D)} touches no goal literal → relevant.
$\text{on}(B,C)$ is added by exactly one action: Stack(B,C) → option B. Delete list {holding(B), clear(C)} also goal-safe → relevant.

Why the others miss:

Option	Why not relevant
C `Putdown(D)`	adds `armEmpty`, `onTable(D)` — neither is a goal literal
D `Pickup(A)`	adds `holding(A)` — enabling at best, never a goal fact
E `Stack(C,B)`	adds `on(C,B)` — the REVERSE of goal literal `on(B,C)`! Classic trap
F `Stack(D,C)`	adds `on(D,C)` — again not asked for

Tricks & Tips

Answers: 11.1 A, B, C · 11.2 A, B