courses:pui:tutorials:tutorial03 [CourseWare Wiki]

3. Propositional Representation STRIPS and FDR

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:

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:

action	precondition	add effect	delete effect
stack(X,Y)	$\{on(X,T),cl(X),cl(Y)\}$	$\{on(X,Y)\}$	$\{on(X,T),cl(Y)\}$
unstack(X,Y)	$\{on(X,Y),cl(X)\}$	$\{on(X,T),cl(Y)\}$	$\{on(X,Y)\}$

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$.

Solution

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

variable	domain
$v_A$	$\{on(A,B),on(A,C),on(A,T)\}$
$v_B$	$\{on(B,A),on(B,C),on(B,T)\}$
$v_C$	$\{on(C,A),on(C,B),on(C,T)\}$
$c_A$	$\{0,1\}$
$c_B$	$\{0,1\}$
$c_C$	$\{0,1\}$

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:

action	precondition	effect
stack(X,Y)	$\{(v_X,on(X,T)),(c_X,1),(c_Y,1)\}$	$\{(v_X,on(X,Y)),(c_Y,0)\}$
unstack(X,Y)	$\{(v_X,on(X,Y)),(c_X,1)\}$	$\{(v_X,on(X,T)),(c_Y,1)\}$

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

It creates a file called output.sas. Its syntax is described here.

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
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.

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.

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

tell us that there is one prevailing variable, the variable var1 whose value must be 0. If you check the variable var1 and its values above, you can see that this means that the block a must be clear.

The remaining rows

2
0 3 0 1
0 4 2 1

tell us that there are two variables whose values are changed by the action, namely var3 and var4. The initial zeros on the second and third rows can be ignored. It expresses the number of conditional effects we will not consider in the homework assignment. The remaining numbers define that the value of var3 must be 0, which will be changed to 1. Analogously, the value of var4 must be 2 and will be changed to 1. Sometimes, the number on the right of the number of the variable can be -1. In that case, the variable's value can be arbitrary but will be changed based on the last number on the row.