Handling ADL

PDDL [McDermott 2000] (the Planning Domain Definition Language) was first defined for use in the First International Planning Competition (IPC 1) at AIPS-98. Over the subsequent competitions, modifications have been made to the language as planning technology has evolved.

In the first three competitions, domains were available in which only STRIPS [Fikes & Nilsson 1971] actions were used. STRIPS actions have conjunctive predicate preconditions, add effects, and delete effects defined in terms of action schema parameters and constant entities. To determine the preconditions and effects of a given ground action instance (an action whose parameters have been bound to specific entities) the action's parameters are substituted into the schema. For the action to be applicable in a given state, all of the precondition predicates must hold in that state; if the action is applied, a new state is generated from the previous state by removing all the predicates present in the delete effect list and adding those in the add effect list..

ADL action schemata [Pednault 1989] extend the syntax of STRIPS action schemata. In ADL domains the language used to describe the preconditions of an action is extended to allow disjunctive, quantified and negative preconditions as well as the conjunctive preconditions that can be used in STRIPS domains. The syntax for describing the effects of actions is also extended to allow conditional effects--effects which are applied whenever a given condition holds.

The extended syntax provided by ADL not only increases the convenience with which a domain can be encoded, but can also reduce the size of the domain descriptions needed. For example, if an action schema has, as a precondition (or A B C) then, without ADL, three copies of the action schema would need to be made: one with a precondition (A), one with a precondition (B) and one with a precondition (C). If one is willing to tolerate such increases in domain-description size, and the number of objects in the domain is finite, it is possible to compile a given ADL domain and problem-instance pair into a domain-problem pair containing only STRIPS actions: in general, this compilation must be done once for each problem instance, not just once for each ADL domain. The ability to compile ADL domains into STRIPS domains was first demonstrated by the compilation procedure devised by Gazen and Knoblock (1997). Using these techniques in a preprocessing stage, FF is able to handle domains containing ADL actions whilst only reasoning about STRIPS actions internally. The output from FF's preprocessor stage was made available in IPC 4 to allow planners which could not handle ADL directly to solve compiled STRIPS formulations of the problems by loading a compiled domain-problem pair for each of the original problem instances in a given domain.

Whereas in previous competitions the ADL domains were simplified or manually reformulated to produce STRIPS domains, the STRIPS domains in IPC 4 were compiled automatically from ADL. The compilation used, based on the preprocessor of FF, results in a compiled domain-problem pair for each original problem instance. This compilation explicitly grounds many of the original actions, producing one compiled action schema (with preconditions and effects whose parameters refer to PDDL constants) per ground action that could arise in the original ADL problem. Whilst these compilations produce STRIPS domains that allow planning to be performed, they replace general action schemata with sets of specific action instances.

To allow the new features in Marvin to be used in the competition, Marvin was extended to include native support for ADL. By reasoning with the original ADL domain it is able to effectively abstract macro-actions from action sequences.

Andrew Coles and Amanda Smith 2007-01-09