Planning Domain Definition Language

The Planning Domain Definition Language (PDDL) is an attempt to standardize Artificial Intelligence (AI) planning languages. It was first developed by Drew McDermott and his colleagues in 1998 (inspired by STRIPS and ADL among others) mainly to make the 1998/2000 International Planning Competition (IPC) possible, and then evolved with each competition. 'The adoption of a common formalism for describing planning domains fosters far greater reuse of research and allows more direct comparison of systems and approaches, and therefore supports faster progress in the field. A common formalism is a compromise between expressive power (in which development is strongly driven by potential applications) and the progress of basic research (which encourages development from well-understood foundations). The role of a common formalism as a communication medium for exchange demands that it is provided with a clear semantics.' The Planning Domain Definition Language (PDDL) is an attempt to standardize Artificial Intelligence (AI) planning languages. It was first developed by Drew McDermott and his colleagues in 1998 (inspired by STRIPS and ADL among others) mainly to make the 1998/2000 International Planning Competition (IPC) possible, and then evolved with each competition. 'The adoption of a common formalism for describing planning domains fosters far greater reuse of research and allows more direct comparison of systems and approaches, and therefore supports faster progress in the field. A common formalism is a compromise between expressive power (in which development is strongly driven by potential applications) and the progress of basic research (which encourages development from well-understood foundations). The role of a common formalism as a communication medium for exchange demands that it is provided with a clear semantics.' This was the official language of the 1st and 2nd IPC in 1998 and 2000 respectively.It separated the model of the planning problem in two major parts: (1) domain description and (2) the related problem description. Such a division of the model allows for an intuitive separation of those elements, which are (1) present in every specific problem of the problem-domain (these elements are contained in the domain-description), and those elements, which (2) determine the specific planning-problem (these elements are contained in the problem-description). Thus several problem-descriptions may be connected to the same domain-description (just like several instances may exist of a class in OOP (Object Oriented Programming) or in OWL (Web Ontology Language) for example). Thus a domain and a connecting problem description forms the PDDL-model of a planning-problem, and eventually this is the input of a planner (usually domain-independent AI planner) software, which aims to solve the given planning-problem via some appropriate planning algorithm. The output of the planner is not specified by PDDL, but it is usually a totally or partially ordered plan (a sequence of actions, some of which may be executed even in parallel sometimes). Now lets take a look at the contents of a PDDL1.2 domain and problem description in general...(1) The domain description consisted of a domain-name definition, definition of requirements (to declare those model-elements to the planner which the PDDL-model is actually using), definition of object-type hierarchy (just like a class-hierarchy in OOP), definition of constant objects (which are present in every problem in the domain), definition of predicates (templates for logical facts), and also the definition of possible actions (operator-schemas with parameters, which should be grounded/instantiated during execution). Actions had parameters (variables that may be instantiated with objects), preconditions and effects. The effects of actions could be also conditional (when-effects).(2) The problem description consisted of a problem-name definition, the definition of the related domain-name, the definition of all the possible objects (atoms in the logical universe), initial conditions (the initial state of the planning environment, a conjunction of true/false facts), and the definition of goal-states (a logical expression over facts that should be true/false in a goal-state of the planning environment). Thus eventually PDDL1.2 captured the 'physics' of a deterministic single-agent discrete fully accessible planning environment. This was the official language of the 3rd IPC in 2002.It introduced numeric fluents (e.g. to model non-binary resources such as fuel-level, time, energy, distance, weight, ...), plan-metrics (to allow quantitative evaluation of plans, and not just goal-driven, but utility-driven planning, i.e. optimization, metric-minimization/maximization), and durative/continuous actions (which could have variable, non-discrete length, conditions and effects). Eventually PDDL2.1 allowed the representation and solution of many more real-world problems than the original version of the language. This was the official language of the deterministic track of the 4th IPC in 2004.It introduced derived predicates (to model the dependency of given facts from other facts, e.g. if A is reachable from B, and B is reachable from C, then A is reachable from C (transitivity)), and timed initial literals (to model exogenous events occurring at given time independently from plan-execution). Eventually PDDL2.2 extended the language with a few important elements, but wasn't a radical evolution compared to PDDL2.1 after PDDL1.2. This was the official language of the deterministic track of the 5th IPC in 2006.It introduced state-trajectory constraints (hard-constraints in form of modal-logic expressions, which should be true for the state-trajectory produced during the execution of a plan, which is a solution of the given planning problem) and preferences (soft-constraints in form of logical expressions, similar to hard-constraints, but their satisfaction wasn't necessary, although it could be incorporated into the plan-metric e.g. to maximize the number of satisfied preferences, or to just measure the quality of a plan) to enable preference-based planning. Eventually PDDL3.0 updated the expressiveness of the language to be able to cope with recent, important developments in planning. This was the official language of the deterministic track of the 6th and 7th IPC in 2008 and 2011 respectively.It introduced object-fluents (i.e. functions' range now could be not only numerical (integer or real), but it could be any object-type also). Thus PDDL3.1 adapted the language even more to modern expectations with a syntactically seemingly small, but semantically quite significant change in expressiveness. The latest version of the language is PDDL3.1. The BNF (Backus–Naur Form) syntax definition of PDDL3.1 can be found among the resources of the IPC-2011 homepage or the IPC-2014 homepage. This extension of PDDL2.1 from around 2002–2006 provides a more flexible model of continuous change through the use of autonomous processes and events.The key this extension provides is the ability to model the interaction between the agent's behaviour and changes that are initiated by the agent's environment. Processes run over time and have a continuous effect on numeric values. They are initiated and terminated either by the direct action of the agent or by events triggered in the environment. This 3-part structure is referred to as the start-process-stop model. Distinctions are made between logical and numeric states: transitions between logical states are assumed to be instantaneous whilst occupation of a given logical state can endure over time. Thus in PDDL+ continuous update expressions are restricted to occur only in process effects. Actions and events, which are instantaneous, are restricted to the expression of discrete change. This introduces the before mentioned 3-part modelling of periods of continuous change: (1) an action or event starts a period of continuous change on a numeric variable expressed by means of a process; (2) the process realizes the continuous change of the numeric variable; (3) an action or event finally stops the execution of the process and terminates its effect on the numeric variable. Comment: the goals of the plan might be achieved before an active process is stopped. NDDL (New Domain Definition Language) is NASA's response to PDDL from around 2002.Its representation differs from PDDL in several respects: 1) it uses a variable/value representation (timelines/activities) rather than a propositional/first-order logic, and 2) there is no concept of states or actions, only of intervals (activities) and constraints between those activities. In this respect, models in NDDL look more like schemas for SAT encodings of planning problems rather than PDDL models. Because of the mentioned differences planning and execution of plans (e.g. during critical space missions) may be more robust when using NDDL, but the correspondence to standard planning-problem representations other than PDDL may be much less intuitive than in case of PDDL.