Representation of, and reasoning with, statements about time and the temporal extent of propositions has long been a subject of research in AI including planning research [AllenAllen1984,McDermottMcDermott1982,SandewallSandewall1994,Kowalski SergotKowalski Sergot1986,Laborie GhallabLaborie Ghallab1995,MuscettolaMuscettola1994,Bacchus KabanzaBacchus Kabanza2000]. Important issues raised during the extension of PDDL to handle temporal features have, of course, already been examined by other researchers, for example in Shanahan's work shanahan on continuous change within the event calculus, in Shoham's work shoham and Reichgelt's work reichgelt on temporal reasoning and work on non-reified temporal systems [Bacchus, Tenenberg, KoomenBacchus et al.1991]. Vila vila provides an excellent survey of work in temporal reasoning in AI. In this section we briefly review some of the central issues that have been addressed, and their treatment in the literature, and set PDDL2.1 in the context of research in temporal logics.
Several researchers in temporal logics have considered the problems of reasoning about concurrency, continuous change and temporal extent. These works have focussed on the problem of reasoning about change when the world is described using arbitrary logical formulae, and most have been concerned with making meta-level statements (such as that effect cannot precede cause). The need to handle complex logical formulae makes the frame problem difficult to resolve, and an approach based on circumscription [McCarthyMcCarthy1980] and default reasoning [ReiterReiter1980] is typical. The STRIPS assumption provides a simple solution to the frame problem when states are described using atomic formulae. The classical planning assumption is that states can be described atomically but this is not a general view of the modelling of change. Although simplifying, this assumption is surprisingly expressive. The bench mark domains introduced in the third International Planning Competition suggest that atomic modelling is powerful enough to capture some complex domains which closely approximate real problems. The temporal reasoning issues we confront are not simplified as a consequence of having made a simplifying assumption about how states are updated. We remain concerned with the major issues of temporal reasoning: concurrency, continuous change and temporal extent.
In the development of PDDL2.1 we made a basic decision to consider the end points of durative actions as instantaneous state transitions. This allows us to concentrate on the truth of propositions at points instead of over intervals. The decision to consider actions in this way is similar to that made by many temporal reasoning researchers [ShanahanShanahan1990,McCarthy HayesMcCarthy Hayes1969,McDermottMcDermott1982]. In the context of PDDL2.1 the approach has the advantage of smoothly integrating with the classical planning view of actions as state transitions. Nevertheless, Allen has shown that a temporal ontology based on intervals can be a basis for planning [AllenAllen1984,AllenAllen1991] and several planning systems have been strongly influenced by the intervals approach [MuscettolaMuscettola1994,Rabideau, Knight, Chien, Fukunaga, GovindjeeRabideau et al.1999]. Allen later moved away from his initial position that instants are not required, introducing the notion of moments [Hayes AllenHayes Allen1987], which are a concept that attempts to reconcile the stance that nothing is instantaneous (so there should only be intervals) and the observation that changes in values of discrete-valued variables, such as propositional variables, apparently cannot avoid changing at instants. This view is consistent with the approach we take in the modelling of continuous durative actions, and with the view of change as consisting of both discrete and continuous aspects [HenzingerHenzinger1996].
In the remainder of this section we compare the PDDL extensions that we propose with previous work in temporal reasoning by considering the three central issues identified above. Our objective is not to claim that our extensions improve on previous work, but instead to demonstrate that the implementation of solutions to these three problems within the PDDL framework makes their exploitation directly accessible to planning in a way that they are not when embedded within a logic and accompanying proof theory.