===== 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: {{ :courses:pui:tutorials:blocks.png?400 |}} 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 [[https://www.fast-downward.org/TranslatorOutputFormat|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.