Abstract:
PDDL was originally conceived and constructed as a lingua franca for the International Planning Competition. PDDL2.1 embodies a set of extensions intended to support the expression of something closer to ``real planning problems.'' This objective has only been partially achieved, due in large part to a deliberate focus on not moving too far from classical planning models and solution methods.

---

Extracted Text

 


 
commentary.dvi

 
Journal of Artificial Intelligence Research 20 (2003) 133-137
Submitted 09/03; published 12/03
Commentary
Imperfect Match: PDDL 2.1 and Real Applications
Mark Boddy
mark.boddy@adventiumlabs.org
Adventium Labs111 Third Avenue S.Minneapolis, MN 55401 USA
Abstract
pddl was originally conceived and constructed as a lingua franca for the International
Planning Competition. pddl2.1 embodies a set of extensions intended to support theexpression of something closer to “real planning problems.” This objective has only beenpartially achieved, due in large part to a deliberate focus on not moving too far fromclassical planning models and solution methods.
1. Introduction
Fox and Long (2003) describe a set of extensions to pddl. They claim that with theseextensions “PDDL2.1 begins to bridge the gap between basic research and applications-oriented planning by providing the expressive power necessary to capture real problems.”While the expressive extensions embodied in pddl2.1 represent a step in the right direction,the authors’ claim is true only in a limited sense. The rest of this commentary will attemptto make the qualifying reservations clear.
2. Planning and Real Applications
There is no such thing as a “real planning problem,” any more than there is such a thingas a “real mathematical programming problem.” There are real problems, for which peoplehave found it useful to construct models and apply solution techniques that are generallyviewed as planning models and techniques (or math programming techniques, or somethingelse entirely). Examples of problems for which planning models may be useful can bedrawn from manufacturing (e.g., batch manufacturing operations), or from the high-levelcontrol of complex mechanisms such as spacecraft. For math programming, to continue thecomparison, there are disciplines such as Chemical Engineering, a major branch of which isconcerned with how to model and solve problems in chemical manufacturing using variousflavors of mathematical optimization. There is no equivalent discipline for planning, and soit is more difficult to characterize “planning applications” in the same sense in which controlof chemical processes may be described as an application for mathematical optimization.
This lack of an extensive history of applications makes it difficult to assess the relevance
of particular modeling or solution techniques, including those developed within the planningresearch community. The International Planning Competition (IPC), held at AIPS-98,AIPS-00 and AIPS-02, has been attempting to provide the data necessary to make theseassessments. Unfortunately, the approach taken gets things backwards, implicitly asking
c 2003 AI Access Foundation. All rights reserved.

 
Mark Boddy
“how can we extend the models everybody in a particular community is comfortable workingwith, so that they are closer to what we think is needed for a real application?”
If planning research is to be viewed as a discipline akin to mathematics, this kind of
extension from known theoretical constructs makes sense. If planning is engineering andreal applications are the point, theoretical work should emerge from, or at the very least betested against, generalization and abstractions of real applications. The classical planningapproach grew out of work on theorem-proving and dynamic logics, and ever since hasmost fruitfully been applied in domains involving minimal interaction with the physicalworld, which describes some planning domains (softbots and other software agent-basedapplications, for example), but not the vast majority of them. Of the systems cited in Foxand Long’s Introduction as having been applied to real planning problems (SIPE, O-Plan,HSTS, and IxTeT), none are conventional classical planners constructing totally-orderedsequences of operators. All of them use some combination of methods drawn from temporalnetwork planning and HTN (task decomposition) planning. Other work applying planningmethods to real applications, for example ASPEN (Fukunaga et al., 1997), does not makemuch use of classical planning techniques, either. Perhaps classical planning is addressingthe wrong problem, or the wrong parts of the problem, for most real applications.
3. Evaluating the Language Itself
As argued by a long line of people going back at least to Hendrix (1973), a point-basedtemporal model in which instantaneous events effect changes in the world state can be usedto build very expressive models of system dynamics, simply by treating those events asthe starting or ending points of intervals over which propositions hold or processes changethe world state. Over the past decade or so, Reiter (2001) and others have extended thesemantics of the Situation Calculus (McCarthy & Hayes, 1969) to encompass overlappingactions, metric quantities, continuous change, exogenous actions, limited knowledge, con-tingent action effects, and actions with uncertain effects, among other things. As presentedby Fox and Long, pddl2.1 can be used to express many of the things one might want torepresent for a real problem. However, there is a difference between saying that somethingcan be expressed in a given language, and that that expression is natural, intuitive, or easyto use.
Take the modeling of resources as an example: pddl2.1 is expressive enough to rep-
resent unary resources (trucks, tools), capacity resources (power, weight), and consumableresources (fuel). But there is no easy way in the language to refer to properties of theresource itself. Everything is encoded in the action representation, as for example in themodeling of total-fuel-used in the example of Figure 5. In many real domains, resourcesare primary, in the sense that the hard part of the problem is figuring out how to resolveresource conflicts, within the other constraints in the problem statement.
3.1 Form Follows Function
The significance of the distinction between what can expressed and how easily it can beexpressed or manipulated depends on what roles the language is intended to fill. pddl2.1is in its origins and current use a language for the planning competition. As long asthe current language permits the (not necessarily terribly natural) expression of required
134

 
Imperfect Match
features of the domain and planning problem, perhaps there is no problem. Competitorswho wish to construct special-purpose data structures such as explicit representations ofresources are free to do so.
If pddl2.1 is to be employed beyond the IPC, what role(s) are intended? A high-level
modeling language for real applications has very different requirements from a competitionstandard, different again from a language used to pass planning problems and solutionsin machine-readable forms, different yet again from a modular, locally-extensible languageused as a research tool, permitting researchers to exchange example domains so as to beable to compare results using different techniques on the same data.1
3.2 Specific Problems with the Language
Finally, there are some specific problems with the current semantics of pddl2.1, whichshould be addressed pretty much whatever use it is to be put to.
3.2.1 Holdovers From the Classical Model
Fox and Long are explicit about having made choices in both syntax and semantics to keepa familiar feel to the language for the classical planning community. This makes good senseif the objective is to use the language to push the boundaries of what can be done using orextending the models and methods currently popular in the research community, but doeslittle to support, and may in some cases actively hinder, the introduction of features drawnfrom real applications.
There are several problems resulting from this stance. First, the language is explicitly
restricted to ensure a finite set of ground actions, specifically because some planning algo-rithms require this. This precludes the modeling of a number of different kinds of domainfeatures, for example the explicit creation and destruction of objects (e.g., intermediate dataproducts, in an image-processing application), or flexible solution for continuous parameters(for example, trajectory optimization) within an existing or evolving plan. Shouldn’t themodels and methods be following the requirements of the problems to be solved, ratherthan the other way round?
A second problem is the treatment of durative actions as atomic, rather than treating
activities like heating water or lighting matches as starting processes that may proceed ontheir own, until the agent decides again to intervene. Consider the heat-water actiondefined in Figure 12 of Section 5.3, whose duration is defined to be precisely that requiredto raise the water to 100 C. This has the curious result that in any well-defined plan,the duration of heat-water must be exactly the time required, taking into account anyoverlapping actions that may also affect the temperature of the water, where those actionsmay not be specified until after the heat-water action is added to the plan.
Finally, the authors define a semantics for durative actions in which preconditions are
required to be true at the beginning or through the extent of, and postconditions areasserted at the end of, intervals of non-zero width open on the right. This is clean, clear,and requires no special constraints to have a well-defined semantics, at least for totally-ordered begin and end-points. at-end preconditions mess this up, and furthermore are thewrong solution for what the authors appear to be trying to support, which I take to be the
1. For a summary of previous attempts to construct a shared ontology for planning, see Tate (1998).
135

 
Mark Boddy
implicit expression of complex structure within a durative action (“this action requires p tobe true for 2 minutes, from the start of the action”). See Dave Smith’s commentary, alsoin this issue, for a discussion of what a more complete model of complex durative actionsmight look like, if one were less concerned with staying close to the classical planning model.
3.2.2 Problems with the Definition of the Continuous Model
In Section 5.3, Fox and Long introduce a notation for specifying durative actions with con-tinuous effects, claiming that using their t notation, it is possible to express a variety ofdifferent nonlinear functions of time. At least as presented in that section, the t construc-tion does not appear to permit the definition, implicit or otherwise, of nonlinear continuousfunctions. In their example of expressing the effect of acceleration on position by makingvelocity vary over time, evaluating position at t by multiplying t by a time-varying ve-locity also evaluated at t will result in an incorrect answer. The required operation isintegration, not composition.
Also in that section, the authors say that continuous durative actions don’t support
exogenous events. I don’t understand why they can’t, as long as the endpoints of thoseexogenous events also appear in the plan. Incorporating this capability would significantlyincrease the range of real (or realistic) problems that could be represented.
3.2.3 Other Issues
Two other matters are worth pointing out as well. First is the restriction to numeric domainsfor functions, for which a primary motivation cited is the previously-discussed objective ofmaking it possible to construct finite extensional models of the set of possible actions. Non-numeric functions are frequently useful in real domains, for example to refer to the currentstate of an object (the current configuration of a piece of communication equipment, say).
Finally, the authors’ decision to support “Undefined” values for numeric fluents is by
their statement intended to allow actions to determine fluent values by setting them, priorto which the value would be unknown. Representing incomplete information, includingunknown propositional and continuous states, is an important capability, and one thatshould be addressed directly. It might deliberately be left as a later extension but I do notunderstand the merits of addressing it incompletely in this way.
4. Summary and Conclusions
The extensions embodied in pddl2.1 are a definite step in the direction of a language inwhich complex planning problems can be expressed. Fox and Long have done the planningcommunity a considerable service, first, in designing and implementing those extensions, andsecond, in presenting and motivating them in the current paper. The focus on backwardcompatibility with classical planning is problematic, given their expressed desire to addressreal (or at least more realistic) applications, and there are some other necessary cleanupsto the language, noted above.
Any further extensions to pddl2.1 will have to address the very likely fragmenting of
the field into mutually incompatible sub-fields. The logical end of this process can be seenin the survey of scheduling problems compiled by Graham et al. (1977), in which minor
136

 
Imperfect Match
differences in problem statement lead to very different complexity classes. Classification bycomplexity class may be less relevant in a field where almost every interesting problem isat least NP-hard, but a similar phenomenon will arise from the fact that some problemsrequire different expressive capabilities than others (resource constrained project schedulingproblems, versus manuever planning for satellite constellations, for example), or are hardto solve in very different ways (finding a correct ordering on plan steps, versus resolvingconflicts on a unary resource).
Ultimately, techniques developed in the classical planning literature will probably prove
useful in addressing complex, real-world applications. However, I do not believe that theywill in most cases be central to those solutions. The classical planning focus is on individualactions, rather than organizing or synchronizing with operations in the larger environment,on discrete state changes, rather than multiple, interacting asynchronous processes, andon propositional representations, rather than constraints on continuous quantities. Othermethods will have to be brought to bear to address the core complexities of most real“planning” problems, which involve complex resources and other forms of synchronizedbehavior, exogenous events, temporal uncertainties in both the agent’s own actions andother events, and in some cases, significant continuous dynamics.
As a final comment, my reservations regarding the current state of pddl2.1 should not be
taken as an argument against the utility of “toy” problems and abstract languages, especiallyfor such purposes as the IPC. However, the simplifications and abstractions employed shouldpreserve the appropriate structure, such that research results and understanding gained inworking with them can translate to real problems. This is where I believe that continuedfocus on classical planning models and methods will be problematic.
References
Fox, M., & Long, D. (2003). Pddl2.1: An extension to pddl for expressing temporal planning
domains. Journal of Artificial Intelligence Research, ??
Fukunaga, A., Rabideau, G., Chien, S., & Yan, D. (1997). Aspen: A framework for auto-
mated planning and scheduling of spacecraft control and operations. In Proc. Inter-national Symposium on AI, Robotics and Automation in Space.
Graham, R., Lawler, E., Lenstra, J., & Rinnooy Kan, A. (1977). Optimization and approxi-
mation in deterministic sequencing and scheduling: A survey. In Proceedings DiscreteOptimization.
Hendrix, G. (1973). Modeling simultaneous actions and continuous processes. Artificial
Intelligence, 4, 145–180.
McCarthy, J., & Hayes, P. J. (1969). Some philosophical problems from the standpoint of
artificial intelligence. Machine Intelligence, 4.
Reiter, R. (2001). Knowledge in Action: Logical Foundations for Specifying and Implement-
ing Dynamic Systems. MIT Press, Cambridge, Mass.
Tate, A. (1998). Roots of spar - shared planning and activity representation. Knowledge
Engineering Review, 13, 121–128.
137