19983
Comment:

← Revision 5 as of 20161221 14:04:44 ⇥
20337
Add big warning about outstanding changes to this page.

Deletions are marked like this.  Additions are marked like this. 
Line 3:  Line 3: 
This page describes the output format of the translation component of Fast Downward. The output format of the preprocessing module is very similar, but has some additional sections at the end to represent the successor generator, domain transition graps, and causal graph.  This page describes the output format of the translation component of Fast Downward. 
Line 8:  Line 8: 
/!\ '''NOTE: After work on this page has begun, there have been changes to TranslatorOutputPage that have not yet been ported to this page. (See the history for that page.) It is probably difficult to try to keep this in sync all the time because not everyone is aware of the existence of this page, so I suggest we do a diff/meld/trawl through the history to see which changes to TranslatorOutputPage need to be merged to this page at the time that this page becomes the "official" documentation page for the translator output format.''' 
Output of the Fast Downward translator
This page describes the output format of the translation component of Fast Downward.
Version history
This page describes version 4 of the output file format. The following list gives a brief version history:
NOTE: After work on this page has begun, there have been changes to TranslatorOutputPage that have not yet been ported to this page. (See the history for that page.) It is probably difficult to try to keep this in sync all the time because not everyone is aware of the existence of this page, so I suggest we do a diff/meld/trawl through the history to see which changes to TranslatorOutputPage need to be merged to this page at the time that this page becomes the "official" documentation page for the translator output format.
Version 1 (introduced 2004): the original Fast Downward translator, generating the output.sas file with information for the preprocessor and search code and a test.groups file with some additional information for human users. Output files from this version can be identified by their lack of either a version or metric section.
Version 2 (introduced 2008): added the metric section and action cost information and introduced a third output file, all.groups, with mutex information used by the landmark generation procedures. Output files from this version can be identified by their lack of a version and inclusion of a metric section.
Version 3 (introduced September 2011): integrated the three output files into one and added the version section.
Version 4 (not yet stable): do not distinguish prevail and preconditions; changed order of sections; new axiom_defaults section; require specific order of output;
Translation file format
The translation file consists of eight sections:
Translation file format: version section
The version section includes a version number that is used by the preprocessor to determine if its input has been generated by a compatible translator version.
It always looks like this for the version of the translator documented here:
Sample version section:
begin_version 4 end_version
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 unitcost. 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: variables section
Background: the translation process works by partitioning the fluent facts of the grounded PDDL task into sets of mutually exclusive propositions ("mutex groups"). Such a partitioning is always possible since a decomposition into trivial mutex groups with only one element always works. However, the translator prefers to use larger mutex groups, trying to find a cover with few groups. A mutex group consisting of facts {p_1, ..., p_k} is turned into a finitedomain variable with domain {0, 1, ..., k}, where value i < k means that fact p_{i+1} is true and all others are false, and value k means that all facts are false. (Sometimes this last value is omitted because the translator detects that at least one fact from the group must always be true.)
The variables section begins with a line containing a single number, the number of finitedomain variables in the task. Following that line, each variable is defined in sequence.
An variable definition is structured as follows:
 The first line is "begin_variable".
 The second line contains the name of the variable (which is usually a nondescriptive name like "var7").
 The third line specifies the axiom layer of the variable.
The fourth line specifies the variable's range, i.e., the number of different values it can take it on. The value of a variable is always from the set {0, 1, 2, ..., range  1}.
The following range lines specify the symoblic names for each of the range values the variable can take on, one at a time. These typically correspond to grounded PDDL facts, except for values that represent that none out a set of PDDL facts is true.
 The final line is "end_variable".
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".
Sample variables section (Gripper domain, prob01.pddl from IPC 1998):
7 begin_variable var0 1 5 Atom carry(ball1, right) Atom carry(ball2, right) Atom carry(ball3, right) Atom free(right) Atom carry(ball4, right) end_variable begin_variable var1 1 5 Atom carry(ball3, left) Atom free(left) Atom carry(ball2, left) Atom carry(ball1, left) Atom carry(ball4, left) end_variable begin_variable var2 1 3 Atom at(ball4, rooma) Atom at(ball4, roomb) <none of those> end_variable begin_variable var3 1 3 Atom at(ball3, rooma) Atom at(ball3, roomb) <none of those> end_variable begin_variable var4 1 3 Atom at(ball1, rooma) Atom at(ball1, roomb) <none of those> end_variable begin_variable var5 1 3 Atom at(ball2, rooma) Atom at(ball2, roomb) <none of those> end_variable begin_variable var6 1 2 Atom atrobby(roomb) Atom atrobby(rooma) end_variable
The example shows that there are 7 finitedomain variables in this task. Please note that the order in which the variables are generated and the order of their values are not deterministic and can vary between translator runs.
The first variable is not a derived variable (its axiom layer is 1), and it can take on 5 different values (from the set {0, 1, 2, 3, 4, 5}), which correspond to the PDDL facts (carry ball1 right), (carry ball2 right), (carry ball3 right), (free right), and (carry ball4 right). This represents the state of the right gripper. The next variable is similar, but represents a state of the left gripper.
The third variable is again not derived (axiom layer 1) and takes on three values, corresponding to ball4 being in rooma, ball4 being in roomb, and ball4 being in neither room (which implies that it is carried by either gripper). The next three state variables similarly represent the other balls, and the final state variable represents the location of the robot.
Translation file format: mutex section
The mutex section encodes additional mutual exclusion constraints in the form of mutex groups (groups of variable/value pairs of which no two can be simultaneously true). A mutex group is called trivial if it only represents information that is obvious from the finitedomain representation (that the same variable cannot hold two different values concurrently). The translator may construct some such trivial mutex groups; however, the preprocessor will filter them out, so they will not be seen by the search code.
The mutex section begins with a line containing a single number, the number of mutex groups in the task. Following that line, each mutex group is defined in sequence.
An mutex group definition is structured as follows:
 The first line is "begin_mutex_group".
 The second line contains a single number, denoting the number of facts in the mutex group.
 The following lines describe the facts in the group, one line for each fact. Each fact is is given by two numbers separated by a space, denoting the variable (indexing into the variable section above, counting from 0) and a value for that variable (indexing into the list of value names for that variable, counting from 0).
 The final line is "end_mutex_group".
Sample mutex section (Gripper):
7 begin_mutex_group 4 1 4 0 4 2 0 2 1 end_mutex_group begin_mutex_group 4 1 0 0 2 3 0 3 1 end_mutex_group begin_mutex_group 4 1 3 0 0 4 0 4 1 end_mutex_group begin_mutex_group 5 1 1 1 4 1 0 1 2 1 3 end_mutex_group begin_mutex_group 5 0 3 0 4 0 2 0 1 0 0 end_mutex_group begin_mutex_group 2 6 1 6 0 end_mutex_group begin_mutex_group 4 1 2 0 1 5 0 5 1 end_mutex_group
There are 7 mutex groups.
The first group encodes that the following variable/value pairs are mutually exclusive: variable 1 has value 4; variable 0 has value 4; variable 2 has value 0; variable 2 has value 1. This corresponds to the PDDL facts (carry ball4 left), (carry ball4 right), (at ball4 rooma), (at ball4 roomb).
The second, third and seventh mutex groups encode similar mutual exclusion constraints for the other three balls.
The fourth, fifth and sixth mutex groups are trivial.
Translation file format: axiom defaults section
The axiom defaults section begins with the line "begin_axiom_defaults", followed by the number of axiom variables (with a nonnegative axiom layer). Each of the following lines contains the number of an axiom variable and its "default value" (see section "Evaluating Axioms" below). The axiom defaults specification is ordered by increasing variable index. The section ends with the line "end_axiom_defaults".
Here are the axiom defaults for the Gripper example:
Sample axiom defaults section (Gripper domain):
begin_axiom_defaults 0 end_axiom_defaults
This shows that there are no axiom variables in this domain, which is the case for all pureSTRIPS benchmarks. Axiom variables 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 nonSTRIPS 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 MiconicFullADL task:
Sample axiom defaults section (MiconicFullADL domain):
begin_axiom_defaults 1 2 0 end_axiom_defaults
Translation file format: Axiom 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:
 The first line is "begin_rule"
 The second line contains a single number, denoting the number of conditions in the "body" of the rule.
 The following lines describe these conditions, one line for each condition. A condition is given by two numbers separated by spaces, denoting a variable/value pairing. The lines with the conditions are lexicographically ordered.
 The following line contains two numbers, denoting the variable affected by the axiom rule, and the new value assigned to this variable. The variable and this latter value together form the "head" of the rule.
 The final line is "end_rule".
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.
Axiom rules are ordered increasingly by the affected variable and the assigned value.
In the Gripper example, the axiom section (which has no axiom variables) looks as follows:
Sample axiom section (Gripper domain):
0
As an example for a task with axiom variables, here is an axiom rules from a MiconicFullADL task:
Sample axiom section (MiconicFullADL domain):
1 begin_rule 2 4 0 5 0 3 1 end_rule
The axiom section contains a single axiom rule. It has two conditions in the body, namely that var4 and var5 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 var3 will assume the value 1. Variable var5 corresponds to a proposition over a newly introduced predicate "newaxiom@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.)
Translation file format: operator section
The operator section 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:
 The first line is "begin_operator".
 The second line contains the name of the operator.
 The third line contains a single number, denoting the number of preconditions.
 The following lines describe the preconditions, one line for each condition. A precondition is given by two numbers separated by spaces, denoting a variable/value pairing in the same notation for goals described below. The precondition lines are lexicographically ordered.
 The first line after the preconditions contains a single number, denoting the number of effects.
 The following lines describe the effects, one line for each effect (read on).
The line before last gives the operator cost. This line only matters if metric is 1 (otherwise, any number here will be treated as 1).
 The final line is "end_operator".
Effects can have associated effect conditions (similar to axiom rules). An effect is always given in a single line, with the individual parts separated by spaces. It is structured as follows:
 First comes the number of effect conditions. In STRIPS domains, this will usually be 0 (additional effect conditions can be introduced by the translator in rare cases, though).
 This is followed by one variable/value pair for each effect condition. This is given as two numbers and sorted like for goal conditions and preconditions.
 This is followed by a number denoting the variable affected by the effect in the thirdlast position.
 Finally, the last number denotes the new value for the affected variable.
Effects are sorted increasingly by the affected variable. For each variable the effects do not need to be sorted.
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 drop ball1 rooma left 2 4 0 5 0 2 0 0 0 0 5 4 1 end_operator [... 33 operators omitted]
The example shows that there are 34 operators in this domain, and two of them are shown in detail.
The first operator is called "drop ball1 rooma left" and has two preconditions: It requires that var4 and var5 are both set to 0 (robot must be in room A and must carry ball 1 in the left gripper). The two effects are unconditional and set var0 to 0 (ball 1 in room A) and var5 to 4 (left gripper empty).
This domain does not use explicit action_costs (as encoded in the metric section), so the final line is 1.
As an example of an operator involving effect conditions, consider the following operator from a task in the Schedule domain:
Sample operator with effect conditions and cost (miconic simpleadl domain, modified with costs):
begin_operator stop f1 1 1 1 1 1 2 1 0 0 7 end_operator
The operator is named "stop f1". It is applicable if the lift is at floor f1 (var1=1). There is only one effect with one effect condition: If var2 is 1 (passenger p0 not served) then it sets var0 to 0 (passenger p0 boarded).
Finally, the 7 before the "end_operator" line indicates that this operator has a cost of 7.
Translation file format: initial state section
The initial state section begins with the line "begin_initial_state", followed by the number of SAS state variables which are no axiom variables (i.e., which do not correspond to derived predicates). Each of the following lines contains the value of one such variable, given by two numbers separated by spaces: pair "i j" means that "var<i>" has initially the value j. These lines are sorted by variable index i. The section ends with the line "end_initial_state".
Here is the initial state section for the Gripper example:
Sample initial state section (Gripper domain):
begin_initial_state 7 0 0 1 0 2 0 3 0 4 0 5 4 6 4 end_initial_state
There are 7 nonaxiom variables (in this STRIPS tasks there are no axiom variables). The initial value of variables var0 to var4 is intitially 0 and the value of var5 and var6 is 4. Looking up the meaning of these values in the variable section shown earlier, this means that exactly the following STRIPS propositions are true in the initial state:
(free right), (free left), (at ball4 rooma), (at ball3 rooma), (at ball1 rooma), (at ball2 rooma), (atrobby rooma).
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. These lines are sorted by variable index i. 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 derived variables, even if the original PDDL task did not use derived predicates.
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:
 First, all axiom state variables are set to their default value (the one specified in the axiom defaults section).
 Second, all axiom rules which affect variables at axiom layer 0 are evaluated. An axiom rule is evaluated by determining whether all variable/value pairings in its body match the current state. If so, the variable in the head is changed to the value in the head. This process is repeated until no further changes occur.
 Third, all axioms rules which affect variables at axiom layer 1 are evaluated.
 Fourth, all axioms rules which affect variables at axiom layer 2 are evaluated.
 ...
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.