PDDL is a standardized "Planning Domain Definition Language" which is widely used to describe planning domains as well as problem instances. It was initially developed for use in an International Planning Competition (IPC) in 1998, allowing all competing planners to use the same input language, and has been gradually extended and polished since that time. Currently almost all new planners support some subset of PDDL.
The PDDL language supports many different levels of expressivity. As you will see later, any domain definition must explicitly declare its requirements in terms of expressivity in the shape of a :requirements clause. This allows a PDDL parser to verify that you only use features you have explicitly requested, and allows a planner to easily tell you whether you are requesting features it does not support.
The most basic level of expressivity is called STRIPS, approximately corresponding to what was supported by the STanford Research Institute Problem Solver in 1971. To request this level of expressivity, say (:requirements :strips) – details below.
A later language called ADL, Action Description Language, added support for a number of different extensions to STRIPS: Negative preconditions (you can only move from A to B if you are NOT carrying anything), disjunctive preconditions (you can only travel by train if you have money OR you already have a ticket), disjunctive goals (you want to own a car OR a motorcycle), and a few other extensions. You can request full ADL expressivity using (:requirements :adl).
Many planners do not support all of the features of ADL. The reason for this is creating plans efficiently is quite difficult, requiring clever internal plan structures and search spaces. Some search spaces work very well given certain limitations on expressivity, but cannot easily be extended to work outside those limitations. For example, in forward state space search (10.2.1 in the book) we always have a complete state in which a precondition should be evaluated and therefore supporting disjunctive preconditions is trivial. On the other hand, if our planner is based on backward state space search (10.2.2), disjunctive preconditions lead to an explosion in the search space, as regression no longer returns a unique preceding state but a set of potential preceding states.
It is still quite common that planners support some extensions to plain STRIPS, though. As seen below, PDDL allows us to request such extensions at a fine level of granularity, as in (:requirements :strips :disjunctive-preconditions).
For those of you who want to go straight to the source, here is the IPC 1998 specification of PDDL. This version should be taken with a grain of salt, however. The IPC 2000 specification is significantly reduced, and closer to what most planning systems actually support. The specification for IPC 2002 (often called PDDL 2.1) adds many new features, including numerical state variables, actions with duration and the possibility to specify a metric to optimize in addition to the logical problem goal. However, there are still many planners not supporting these extensions.
We provide several examples of PDDL domain and problem definitions using only the STRIPS subset of PDDL as well as several examples using object types and some ADL features.
We also provide several variants of the Satellite domain used in IPC 2002, which illustrate the extended features of PDDL 2.1.
A PDDL definition consists of two parts: The domain and the problem definition. Although not required by the PDDL standard, many planners require that the two parts are in separate files.
Comments in a PDDL file start with a semicolon (";") and last to the end of the line.
Because PDDL is a very general language and most planners support only a subset, domains may declare requirements. The most commonly used requirements are:
The domain definition contains the domain predicates and operators (called actions in PDDL). It may also contain types (see Typing, below), constants, static facts and many other things, but these are not supported by the majority of planners.
The format of a (simple) domain definition is as follows. You may want to keep one or two of the example domain definitions open while you read this.
(define (domain DOMAIN_NAME)
(:requirements [:strips] [:equality] [:typing] [:adl])
(:predicates (PREDICATE_1_NAME [?A1 ?A2 ... ?AN])
(PREDICATE_2_NAME [?A1 ?A2 ... ?AN])
...)
(:action ACTION_1_NAME
[:parameters (?P1 ?P2 ... ?PN)]
[:precondition PRECOND_FORMULA]
[:effect EFFECT_FORMULA]
)
(:action ACTION_2_NAME
...)
...)
Elements in []'s are optional, for those not familiar with formal grammars.
Names (domain, predicate, action, etc.) may usually contain alphanumeric characters, hyphens ("-") and underscores ("_"), though there may be some planners that allow less.
Parameters of predicates and actions are distinguished by beginning with a question mark ("?").
The parameters used in predicate declarations (the :predicates part) have no other function than to specify the number of arguments that the predicate should have, i.e. the parameter names do not matter (as long as they are distinct). Predicates can have zero parameters (but in this case, the predicate name still has to be written within parentheses).
All parts of an action definition except the name are, according to the spec, optional (although, of couse, an action without effects is pretty useless). However, for an action that has no preconditions some planners may require an "empty" precondition, on the form :precondition () (some planners may also require an empty :parameter list for actions without parameters).
Note: Some planners only try to apply actions where all arguments are different, i.e. the same object may not be used as a value of two distinct parameters of the same action. Such planners might use actions such as move(A,B) and move(B,A), but would not consider move(A,A) or move(B,B) to be a valid action. In this particular example, forbidding a move from one position to the same position seems quite reasonable, but for other actions it may cause some difficulties. Consider the action moveto(?piece,?destcolumn,?destrow) for example. If we represent both columns and rows are represented by the constants A/B/C/D/E/F/G/H, a planner of the type discussed here would never use an action such as moveto(bishop1,A,A) or moveto(pawn2,C,C), making it impossible to move to a position on the diagonal and making some problems unsolvable. See the SlideTile domain definition and the two problem definitions eight01.pddl and eight01x.pddlfor an example of this problem and how to fix it.
In a STRIPS domain, a precondition formula may be:
An atomic formula:
(PREDICATE_NAME ARG1 ... ARG_N)
The predicate
arguments must be parameters of the action (or constants declared
in the domain, if the domain has constants).
A conjunction of atomic formulas:
(and ATOM1 ... ATOM_N)
If the domain uses :equality, an atomic formula may also be of the form (= ARG1 ARG2). Many planners that support equality also allow negated equality, which is written (not (= ARG1 ARG2)), even if they do not allow negation in any other part of the definition.
In an ADL domain, a precondition may in addition be:
A general negation, conjunction or disjunction:
(not CONDITION_FORMULA)
(and CONDITION_FORMULA1 ... CONDITION_FORMULA_N)
(or CONDITION_FORMULA1 ... CONDITION_FORMULA_N)
A quantified formula:
(forall (?V1 ?V2 ...) CONDITION_FORMULA)
(exists (?V1 ?V2 ...) CONDITION_FORMULA)
In a STRIPS domain, an effect formula may consist of:
An added atom:
(PREDICATE_NAME ARG1 ... ARG_N)
The predicate
arguments must be parameters of the action (or constants declared
in the domain, if the domain has constants).
A deleted atom:
(not (PREDICATE_NAME ARG1 ... ARG_N))
A conjunction of atomic effects:
(and ATOM1 ... ATOM_N)
In an ADL domain, an effect formula may in addition contain:
A conditional effect:
(when CONDITION_FORMULA EFFECT_FORMULA)
The
interpretation is that the specified effect takes place only if
the specified condition formula is true in the state where the
action is executed. Conditional effects are often but not always
placed within quantifiers.
A universally quantified formula:
(forall (?V1 ?V2 ...) EFFECT_FORMULA)
The format of a (simple) problem definition is:
(define (problem PROBLEM_NAME) (:domain DOMAIN_NAME) (:objects OBJ1 OBJ2 ... OBJ_N) (:init ATOM1 ATOM2 ... ATOM_N) (:goal CONDITION_FORMULA) )
The initial state description (the :init section) is simply a list of all the ground atoms that are true in the initial state. All other atoms are by definition false. The goal description is a formula of the same form as an action precondition. All predicates used in the initial state and goal description should naturally be declared in the corresponding domain.
In difference to action preconditions, however, the initial state and goal descriptions should be ground, meaning that all predicate arguments should be object or constant names rather than parameters. (An exception is quantified goals in ADL domains, where of course the quantified variables may be used within the scope of the quantifier. However, even some planners that claim to support ADL do not allow quantifiers in goals.)
Second, the type names have to be declared before they are used (which usually means before the :predicates declaration). This is done with the declaration
(:types NAME1 ... NAME_N)
Then, to declare the type of a parameter of a predicate or action one writes ?X - TYPE_OF_X. A list of parameters of the same type can be abbreviated to ?X ?Y ?Z - TYPE_OF_XYZ. Note that the hyphen between parameter and type name has to be "free-standing", i.e. surrounded by whitespace.
The syntax is the same for declaring types of objects in the problem definition.