Search
Exercise 1: Blocks World belongs to the oldest planning domain. There are several blocks on a table, and we can build piles out of those blocks. I simplified the domain a bit so that it has only two action schemata: stack and unstack. stack takes a block lying on the table (there cannot be any other block above it) and puts it on the top of any pile (even a single block forms a pile). unstack is a reversed action schema. It removes a block on top of a pile and places it on the table. Consider the following problem instance:
stack
unstack
Model this problem in STRIPS.
Solution
To model the above problem as a STRIPS planning task $\Pi=\langle F,A,s_0,g\rangle$, we must first invent a suitable set of facts $F$ to capture each possible planning state. We have to know for each block whether it is on the table, stacked on another block, or the top block of a pile. Thus \[F=\{on(A,B),on(A,C),on(A,T),on(B,A),on(B,C),on(B,T),on(C,A),on(C,B),on(C,T),cl(A),cl(B),cl(C)\}.\] For instance, $on(B,C)$ expresses that $B$ is on top of $C$, and $on(B,T)$ means that $B$ is on the table. Finally, $cl(B)$ means that $B$ is clear, i.e., a top block of a pile.
For each pair of different blocks $X,Y\in\{A,B,C\}$, we introduce actions $stack(X,Y)$ and $unstack(X,Y)$. The preconditions, add effects, and delete effects are defined as follows:
The initial state $s_0=\{on(A,T),on(C,A),on(B,T),cl(B),cl(C)\}$. The goal state is $g=\{on(A,B),on(B,C),on(C,T)\}$.
Exercise 2: Model the above planning task as an FDR task $\Pi=\langle V,A,s_0,g\rangle$.
One can easily transform a STRIPS task into an FDR task simply by introducing a $\{0,1\}$-valued variable for each fact. Nevertheless, we might try to detect some mutex groups and make the state space more compact. There can be several mutex groups, so we select the largest ones covering as many facts as possible. Consider the block $A$. It can lie on the table, $B$, or $C$. Thus, \[\{on(A,B),on(A,C),on(A,T)\}\] is a mutex group as exactly one of those facts is true in any reachable state. Similarly, \[\{on(B,A),on(B,C),on(B,T)\},\ \{on(C,A),on(C,B),on(C,T)\}\] are mutex groups.
To cover all facts, we consider three variables $v_A, v_B, v_C$ whose values correspond to the above mutex groups and three $\{0,1\}$-valued variables $c_A,c_B,c_C$ corresponding to the fact $cl(A),cl(B),cl(C)$ respectively. So we have $V=\{v_A,v_B,v_C,c_A,c_B,c_C\}$ with the domains
The initial state $s_0$ is a total function assigning a value from its domain to each variable. We have \[s_0=\{(v_A,on(A,T)),(v_B,on(B,T)),(v_C,on(C,A)),(c_A,0),(c_B,1),(c_C,1)\}.\] The goal is the partial function \[g=\{(v_A,on(A,B)),(v_B,on(B,C)),(v_C,on(C,T))\}.\]
Finally, for each pair of different blocks $X,Y\in\{A,B,C\}$, we introduce actions $stack(X,Y)$ and $unstack(X,Y)$. The preconditions and effects are defined as follows:
Note that we use names of the facts and variable values like $on(A,B)$. We did so to make it more readable for humans as it has a clear meaning. However, when we code a planner, numbers usually index the facts or variable values, and the planner works only with the numbers.
In the second homework assignment, you will implement a planner for FDR tasks. The input for your planner will be a SAS file created by the Fast Downward planner from PDDL. This file is just the equivalent FDR representation of the PDDL task. If you want to create this file, execute the following command:
./fast-downward.sif domain.pddl problem.pddl
output.sas
Consider a PDDL formulation of the above-described Blocks World domain. The domain file:
(define (domain BLOCKS) (:requirements :strips) (:predicates (on ?x ?y) (clear ?x) (ontable ?x) ) (:action stack :parameters (?x ?y) :precondition (and (clear ?x) (clear ?y) (ontable ?x) (not (= ?x ?y))) :effect (and (not (clear ?y)) (not (ontable ?x)) (on ?x ?y))) (:action unstack :parameters (?x ?y) :precondition (and (on ?x ?y) (clear ?x)) :effect (and (clear ?y) (ontable ?x) (not (on ?x ?y)))))
The problem file:
(define (problem p01) (:domain BLOCKS) (:objects A B C) (:init (clear C) (clear B) (ontable A) (ontable B) (on C A)) (:goal (and (on A B) (on B C))) )
If we ask Fast Downward to create the FDR representation, it generates a SAS file built from several sections. The header contains a version (always 3 for us) and the metric expressing whether the task uses action costs.
begin_version 3 end_version begin_metric 0 end_metric
Next, the file defines FDR variables and their domains. The first number 6 says that there are six variables. For each variable, there is a name like var0, you can ignore the value -1, the number of its values, and the values themselves.
6
var0
-1
6 begin_variable var0 -1 3 Atom on(c, a) Atom on(c, b) Atom ontable(c) end_variable begin_variable var1 -1 2 Atom clear(a) NegatedAtom clear(a) end_variable ... other variables
Next, there could be several sections with identified mutex groups. You can safely ignore them in your planner.
The sections with the initial state and goal follow. The initial state is just a sequence of numbers indexing the values of all variables starting from 0. The goal section tells us that goal states must assign to var4 the value from its domain indexed by 0 and to var5 the value indexed by 1.
var4
var5
begin_state 0 1 0 0 2 2 end_state begin_goal 2 4 0 5 1 end_goal
Finally, there is a section defining actions (called operators). The first number tells us that there are 12 operators. Each operator has its name, like stack a b. The last number before end_operator is the cost of the action. The remaining numbers encode the precondition and effect; explained below.
stack a b
end_operator
12 begin_operator stack a b 1 1 0 2 0 2 0 1 0 4 2 0 1 end_operator begin_operator stack a c 1 1 0 2 0 3 0 1 0 4 2 1 1 end_operator ... other operators
Due to historical reasons, the SAS file splits the variables into two parts. The first defines prevailing variables, i.e., variables whose values must have a certain value to execute the action, but the action does not change the value. The second part consists of the variables whose values are changed by the action. Consider again the action stack a b above. The rows
1 1 0
var1
a
The remaining rows
2 0 3 0 1 0 4 2 1
var3