Introduction to the Semantics of PDDL2.1

In Sections 7 and 8 we provide a formal semantics for the numeric extension and temporal extension of PDDL2.1. Together these sections contain 20 definitions. The lengthy treatment is necessary because the semantics we have developed adds four significant extensions over classical planning and the semantics Lifschitz developed for STRIPS [LifschitzLifschitz1986]. These are:

• the introduction of time, so that plans describe behaviour relative to a real time line;
• related to the first extension, the treatment of concurrency -- actions can be executed in parallel, which can lead to plans that contain concurrent interacting processes (although these processes are encapsulated in durative actions in PDDL2.1);
• an extension to handle numeric-valued fluents;
• the use of conditional effects, both alone and in conjunction with all of the above extensions.

The semantics is built on a familiar state-transition model. The requirements of the semantics can be reduced to four essential elements.

1. To define what is a state. The introduction of both time and numeric values complicate the usual definition of a state as a set of atoms.
2. To define when a state satisfies a propositional formula representing a goal condition or precondition of an action. An extension of the usual interpretation of a state as a valuation in which an atom is true if and only if the atom is in the state (the Closed World Assumption) is required in order to handle the numeric values in the state.
3. To define the state transition induced by application of an action. The update rule for the logical state must be supplemented with an explanation of the consequences for the numeric part of the state.
4. To define when two actions can be applied concurrently and how their concurrent application affects the application of those actions individually.

The structure of the definitions is as follows. Definitions 1 to 15, given in Section 7, define what it means for a plan to be valid when the plan consists of only non-durative actions. Definitions 1 to 6 set up the basic terminology, the foundational structures and the framework for handling conditional effects and primitive numeric expressions. Definition 2 meets the first requirement identified above, defining states. Definition 9 meets the second requirement, defining when a goal description is satisfied in a state. Definition 11 defines a simple plan, extending the classical notion of a sequence of actions by adding time. Definitions 12 meets the fourth requirement, by defining when two actions cannot be executed concurrently. Definition 13 meets the third requirement, defining what we mean by execution of actions, including concurrent execution of actions. Definitions 14 and 15 define the execution of a plan and what it means for a plan to be valid, given the basis laid in the previous definitions.

In Section 8 the semantics is extended to give meaning to durative actions. We begin with Definition 16, which defines ground durative actions analogously to Definition 6 for simple (that is, non-durative) actions. Similarly, Definition 17 parallels the definition of a simple plan (Definition 11) and Definitions 19 and 20 parallel those for the execution and validity of simple plans (Definitions 14 and 15). Definition 18 is the critical definition for the semantics of plans with durative actions, supplying a transformation of temporal plans into simple plans, whose validity according to the semantics of purely simple plans, can be used to determine the validity of the original temporally structured plans.