M. S. Boddy
Volume 20, 2003Links to Full Text:
Journal of Artiï¬cial Intelligence Research 20 (2003) 133-137 Submitted 09/03; published 12/03 Commentary Imperfect Match: PDDL 2.1 and Real Applications Mark Boddy email@example.com 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 variousï¬avors of mathematical optimization. There is no equivalent discipline for planning, and soit is more diï¬cult 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 diï¬cult 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 eï¬ect 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 eï¬ects, and actions with uncertain eï¬ects, 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 diï¬erence 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 ï¬guring out how to resolveresource conï¬icts, within the other constraints in the problem statement. 3.1 Form Follows Function The signiï¬cance of the distinction between what can expressed and how easily it can beexpressed or manipulated depends on what roles the language is intended to ï¬ll. 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 diï¬erent requirements from a competitionstandard, diï¬erent again from a language used to pass planning problems and solutionsin machine-readable forms, diï¬erent 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 diï¬erent techniques on the same data.1 3.2 Speciï¬c Problems with the Language Finally, there are some speciï¬c 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 ï¬nite set of ground actions, speciï¬cally because some planning algo-rithms require this. This precludes the modeling of a number of diï¬erent kinds of domainfeatures, for example the explicit creation and destruction of objects (e.g., intermediate dataproducts, in an image-processing application), or ï¬exible 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 actiondeï¬ned in Figure 12 of Section 5.3, whose duration is deï¬ned to be precisely that requiredto raise the water to 100 C. This has the curious result that in any well-deï¬ned plan,the duration of heat-water must be exactly the time required, taking into account anyoverlapping actions that may also aï¬ect the temperature of the water, where those actionsmay not be speciï¬ed until after the heat-water action is added to the plan. Finally, the authors deï¬ne 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-deï¬ned 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 eï¬ects, claiming that using their t notation, it is possible to express a variety ofdiï¬erent nonlinear functions of time. At least as presented in that section, the t construc-tion does not appear to permit the deï¬nition, implicit or otherwise, of nonlinear continuousfunctions. In their example of expressing the eï¬ect 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 signiï¬cantlyincrease 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 ï¬nite 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 conï¬guration of a piece of communication equipment, say). Finally, the authorsâ decision to support âUndeï¬nedâ values for numeric ï¬uents is by their statement intended to allow actions to determine ï¬uent 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 deï¬nite step in the direction of a language inwhich complex planning problems can be expressed. Fox and Long have done the planningcommunity a considerable service, ï¬rst, 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 ï¬eld into mutually incompatible sub-ï¬elds. 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 diï¬erences in problem statement lead to very diï¬erent complexity classes. Classiï¬cation bycomplexity class may be less relevant in a ï¬eld where almost every interesting problem isat least NP-hard, but a similar phenomenon will arise from the fact that some problemsrequire diï¬erent expressive capabilities than others (resource constrained project schedulingproblems, versus manuever planning for satellite constellations, for example), or are hardto solve in very diï¬erent ways (ï¬nding a correct ordering on plan steps, versus resolvingconï¬icts 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, signiï¬cant continuous dynamics. As a ï¬nal 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 simpliï¬cations 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 Artiï¬cial 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. Artiï¬cial Intelligence, 4, 145â180. McCarthy, J., & Hayes, P. J. (1969). Some philosophical problems from the standpoint of artiï¬cial 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