Revision 5 as of 2011-07-04 08:55:18

Clear message

Output of the Fast Downward Translator

The translator generates two output files:

  1. output.sas: The SAS encoding of the planning task.

    • We call this the "translation".
  2. test.groups: A human-readable description of the relationship
    • between propositions in the original STRIPS representation and variable/value pairs in the SAS encoding. We call this the "translation key".

The translation contains all information required for solving the task. The translation key is only generated for the benefit of the human using the translator.

Roughly speaking, the translation process works by determining sets of mutually exclusive propositions in the STRIPS task, then replacing each such set {p_0, p_1, ..., p_{k-1}} by a single SAS variable with domain {0, 1, ..., k}, where a value of i < k means that proposition p_i is true and all others are false, while a value of k means that all propositions in the set are false.

Any set of propositions can be covered by such mutex groups because it is always possible to put a STRIPS proposition into a singleton set, which will be translated to a binary SAS variable, amounting to a trivial translation. Of course, the translator tries to avoid such trivial translations, preferring encodings which use few SAS variables. The actual mutex group cover computed by the translator is written to the translation key file "test.groups".

ADDENDUM: Depending on how they are configured, the most recent versions of the translator may create the additional output file "all.groups" containing additional mutex information. This is used by the landmark planner described in the AAAI 2008 paper by Richter, Helmert and Westphal. There is no documentation available for this file.

Translation Key Example

Let us explain the translation key file with a small example from the Gripper domain, namely prob01.pddl from IPC-1. The relevant (non-constant) STRIPS propositions in this task are the following:

The test.groups file generated by the translator looks as follows (slight differences in translation are possible because the translator is not completely deterministic; however, in this example, these will not amount to a qualitative difference):

Sample test.groups file (Gripper domain): 

  var0:
    0: Atom carry(ball3, left)
    1: Atom free(left)
    2: Atom carry(ball2, left)
    3: Atom carry(ball1, left)
    4: Atom carry(ball4, left)
    5: <none of those>
  var1:
    0: Atom carry(ball1, right)
    1: Atom carry(ball2, right)
    2: Atom carry(ball3, right)
    3: Atom free(right)
    4: Atom carry(ball4, right)
    5: <none of those>
  var2:
    0: Atom at(ball1, rooma)
    1: Atom at(ball1, roomb)
    2: <none of those>
  var3:
    0: Atom at(ball2, rooma)
    1: Atom at(ball2, roomb)
    2: <none of those>
  var4:
    0: Atom at(ball3, rooma)
    1: Atom at(ball3, roomb)
    2: <none of those>
  var5:
    0: Atom at(ball4, rooma)
    1: Atom at(ball4, roomb)
    2: <none of those>
  var6:
    0: Atom at-robby(roomb)
    1: Atom at-robby(rooma)
    2: <none of those>

This means that the translator generates a SAS encoding using seven state variables. Variable var0 with domain {0, 1, 2, 3, 4, 5} encodes which ball the left gripper is carrying if it is currently carrying a ball (values 0, 2, 3, 4 corresponding to ball3, ball2, ball1, ball4), whether the left gripper is currently free (value 4), or whether the gripper is neither carrying a ball nor free (value 5).

Note that value 5 is actually unreachable, since a given gripper that is not carrying a ball must be free. In general, the translator does not try to detect such unreachable values because the Fast Downward planner is not sensitive to them. If you want to use the translator within another planning system, you might want to prune away impossible values such as this one after the translation phase. Most unreachable values are trivially unreachable because there is no operator that could establish them. For example, in this Gripper task, there is no operator that sets the value of the first state variable to 5, and the initial value is also different from 5.

The second SAS variable (var1) similarly encodes the status of the right gripper. Variables var2 through var5 encode the status of a given ball. For example, variable var4 assumes the value 0 if ball3 is in rooma, the value 1 if ball3 is in roomb, and the value 2 if neither is the case (which implies that ball3 is currently being carried).

Finally, the seventh SAS variable (var6) encodes the location of the robot, with 0 and 1 corresponding to rooma and roomb. Like for the first two state variables, the last value (neither in rooma nor in roomb) is actually unreachable.

Translation Key Notes

In some planning tasks, the translator introduces new predicates for compiling away axioms, quantified effects or non-STRIPS goal conditions. These always have names containing an '@' sign to distinguish them from regular predicates.

For example, the test.groups file obtained for the first task in the PSR-Middle domain (ADL + derived predicates formulation) of IPC4 contains the following fragment:

test.groups fragment (PSR-Middle domain) 

  var359:
    0: Atom new-axiom@0()
    1: <none of those>

The predicate new-axiom@0 is introduced here to compile away the non-STRIPS goal condition (forall (?b - DEVICE) (not (affected ?b))).

Translation File Format

The translation file consists of six sections:

  1. Metric section

  2. Variable section

  3. Initial state section

  4. Goal section

  5. Operator section

  6. Axiom section

We explain these five sections in sequence.

Translation File Format: Metric Section

The metric section indicates whether action costs are used or not. It begins with the line "begin_metric", followed by either a 0 or 1. 0 indicates that action costs are not used, and all actions are treated as unit-cost. 1 indicates that action costs are used. The section ends with the line "end_metric".

Sample metric section (Gripper domain): 

begin_metric
0
end_metric

Translation File Format: Variable Section

The variable section begins with the line "begin_variables", followed by a line containing the number of SAS state variables. This is followed by one line for each state variable, which contains three parts separated by spaces:

For state variables that do not correspond to axioms, i.e. which are not computed from the values of other state variables, the axiom layer is always -1. For state variables that do correspond to axioms, the axiom layer determines the order of evaluation of axiom rules, described further below in the section "Evaluating Axioms".

The variable section ends with the line "end_variables".

Here is an example from the same Gripper task we used before:

Sample variable section (Gripper domain): 

  begin_variables
  7
  var0 6 -1
  var1 6 -1
  var2 3 -1
  var3 3 -1
  var4 3 -1
  var5 3 -1
  var6 3 -1
  end_variables

The example shows that there are 7 SAS variables in this task, the first two of which can assume 6 different values (in the set {0, 1, 2, 3, 4, 5}), and the other of which can assume 3 different values (in the set {0, 1, 2}). This is consistent with our earlier explanation of the translation key. None of those variables corresponds to a derived predicate, so all axiom layers are -1.

Translation File Format: Initial State Section

The initial state section begins with the line "begin_state", followed by one line for each SAS state variable. Each of those lines contains a single number, denoting the value of the given state variable in the initial state (for state variables which do not correspond to derived predicates) or the "default value" of the state variable (for state variables corresponding to derived predicates; see section "Evaluating Axioms" below). The section ends with the line "end_state".

Here is the initial state section for the Gripper example:

Sample initial state section (Gripper domain): 

  begin_state
  1
  3
  0
  0
  0
  0
  1
  end_state

So the initial value of var0 in the example is 1, the initial value of var1 is 3, the initial values of var2 through var5 are 0, and the initial value of var6 is 1. Recalling the translation key shown earlier, this means that exactly the following STRIPS propositions are true in the initial state:

Translation File Format: Goal Section

The goal section begins with the line "begin_goal", followed by a line which contains the number of goal pairings. This is followed by one line for each goal pairing, where a goal pairing is given by two numbers separated by spaces, where the pair "i j" means that "var<i>" must have the value j in the goal. The goal section ends with the line "end_goal".

Here is the goal section for the Gripper example:

Sample goal section (Gripper domain): 

  begin_goal
  4
  2 1
  3 1
  4 1
  5 1
  end_goal

We see that there are four goal conditions: Each of the variables var2 through var5 shall assume the value 1. In other words, the goal is reached if all four balls are in roomb.

Note that the goal condition of the translated task is always a simple conjunction of atomic goals. If the original PDDL goal is more complicated, it is transformed by the translator to fit this requirement. In some cases, this leads to the introduction of new derived predicates and axiom rules.

Translation File Format: Operator Section

Unlike the previous sections, the operator section does not begin with a specific line. Instead, it begins with a line containing a single number, the number of operators in the task. Following that line, each operator is defined in sequence.

An operator definition is structured as follows:

Of these parts, the lines that describe an effect are most complicated because effects can have associated effect conditions (often called "secondary preconditions" in the literature) and a condition on the old value of the affected state variable (called a "precondition" as opposed to a "prevail condition" in the SAS+ literature). An effect is always given in a single line, with the individual parts separated by spaces. It is structured as follows:

Even for fairly small examples, the operator section becomes quite big, so we omit most operator definitions of the Gripper example:

Sample operator section (Gripper domain): 

  34
  begin_operator
  move rooma roomb
  0
  1
  0 6 1 0
  0
  end_operator
  begin_operator
  pick ball4 rooma left
  1
  6 1
  2
  0 0 1 4
  0 5 0 2
  0
  end_operator
  [... 31 operators omitted]
  begin_operator
  pick ball1 roomb right
  1
  6 0
  2
  0 1 3 0
  0 2 1 2
  0
  end_operator

The example shows that there are 34 operators in this domain, and three of them are shown in detail.

The first operator is called "move rooma roomb" and has no prevail conditions (0) and one effect (1). The effect has no associated effect conditions (0) and affects var6 (6). It requires that the old value of the variable is 1, so it is only applicable if the robot is in rooma. It establishes the value 0, so that the robot will be in roomb afterwards.

The two pick-up operators are similar, so we only explain the first one. Its name is "pick ball4 rooma left". It has one prevail condition, namely that var6 has the value 1 (i.e. the robot is in rooma). It has two effects. The first effect has no associated conditions, requires that var0 currently has value 1 (that is, the left gripper is free) and changes var0 to value 4 (the left gripper carries ball4). The second effect has no associated conditions either, requires that var5 currently has value 0 (ball4 is in rooma) and sets it to value 2 (ball4 is in neither room afterwards).

As an example of an operator involving effect conditions and the don't care value -1 for an effect precondition, consider the following operator from a task in the Schedule domain:

Sample operator with effect conditions and cost (Schedule domain - modified): 

  begin_operator
  do-polish a0
  1
  7 0
  4
  0 24 1 0
  0 3 -1 0
  1 29 1 29 -1 0
  0 22 1 0
  7
  end_operator

The operator is named "do-polish a0". The prevail condition "7 0" requires that the temperature of object a0 is cold. The four effects of the operators are:

Note that the only effect with an effect condition (1 29 1 29 -1 0) could be rewritten as (0 29 -1 0) in this situation, because var29 can only take on the possible values 0 and 1 anyway. However, the translator does not try to detect and simplify this effect pattern, which occurs quite commonly in some of the planning benchmarks.

Finally, the 7 before the "end_operator" line indicates that this operator has a cost of 7.

Translation File Format: Axiom Section

The axiom section is similar in structure to the operator section, as axiom rules can be considered to be operators that are automatically executed whenever applicable. However, the section is somewhat simpler in structure because axiom rules only ever affect a single state variable.

Similar to the operator section, the axiom section begins with a line containing the number of axiom rules. Following that line, each axiom rule is defined in sequence.

An axiom rule is structured as follows:

Variables appearing in the head of axiom rules (axiom variables) are disjoint from variables affected by operators. In the current version of the translator, axiom variables always have a binary domain, so the "old value" for the affected variable is always the complement of the new value and can be safely ignored.

In the Gripper example, the axiom section looks as follows:

Sample axiom section (Gripper domain): 

  0

This shows that there are no axiom rules in this domain, which is the case for all pure-STRIPS benchmarks. Axiom rules will of course be generated for domains that contain derived predicates, but they can also be generated for PDDL tasks without derived predicates if they use non-STRIPS features such as universally quantified conditions, as some of these are compiled away with the help of axioms. As an example, here is an axiom rules from a Miconic-FullADL task:

Sample axiom section (Miconic-FullADL domain): 

  1
  begin_rule
  2
  1 0
  3 0
  5 0 1
  end_rule

The axiom section contains a single axiom rule. It has two conditions in the body, namely that var1 and var3 are both set to 0, i.e. that passengers p1 and p0 have both been served. The head of the axiom states that if the condition is satisfied, then var5 will assume the value 1 if it currently has the value0. Variable var5 corresponds to a proposition over a newly introduced predicate "new-axiom@9" which has been generated to simplify the original PDDL goal (forall (?p - passenger) (served ?p)). (Of course, in this case the goal could also have been transformed to a simple conjunction in a different way that does not require axioms.)

Evaluating Axioms

State variables that correspond to derived predicates are not directly affected by operator applications. Instead, their values in a given world state are computed from the values of the other state variables using the following algorithm:

The semantics of the translation guarantees that the algorithm always terminates and that the result is independent of the order in which axiom rules at the same layer are considered.