When is temporal planning really temporal?

William Cushing, Subbarao Kambhampati, Mausam, Daniel S. Weld

Research output: Chapter in Book/Report/Conference proceedingConference contribution

124 Scopus citations


While even STRIPS planners must search for plans of unbounded length, temporal planners must also cope with the fact that actions may start at any point in time. Most temporal planners cope with this challenge by restricting action start times to a small set of decision epochs, because this enables search to be carried out in state-space and leverages powerful state-based reachability heuristics, originally developed for classical planning. Indeed, decision-epoch planners won the International Planning Competition's Temporal Planning Track in 2002, 2004 and 2006. However, decision-epoch planners have a largely unrecognized weakness: they are incomplete. In order to characterize the cause of incompleteness, we identify the notion of required concurrency, which separates expressive temporal action languages from simple ones. We show that decisionepoch planners are only complete for languages in the simpler class, and we prove that the simple class is 'equivalent' to STRIPS! Surprisingly, no problems with required concurrency have been included in the planning competitions. We conclude by designing a complete state-space temporal planning algorithm, which we hope will be able to achieve high performance by leveraging the heuristics that power decision epoch planners.

Original languageEnglish (US)
Title of host publicationIJCAI International Joint Conference on Artificial Intelligence
Number of pages8
StatePublished - 2007
Event20th International Joint Conference on Artificial Intelligence, IJCAI 2007 - Hyderabad, India
Duration: Jan 6 2007Jan 12 2007


Other20th International Joint Conference on Artificial Intelligence, IJCAI 2007

ASJC Scopus subject areas

  • Artificial Intelligence


Dive into the research topics of 'When is temporal planning really temporal?'. Together they form a unique fingerprint.

Cite this