Planning Competition’s Temporal Planning.pdfVIP

When is Temporal Planning Really Temporal? William Cushing and Subbarao Kambhampati Dept. of Comp. Sci. and Eng. Arizona State University Tempe, AZ 85281 Mausam and Daniel S. Weld Dept. of Comp. Sci. and Eng. University of Washington Seattle, WA 98195 Abstract 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 en- ables search to be carried out in state-space and leverages powerful state-based reachability heuris- tics, originally developed for classical planning. Indeed, decision-epoch planners won the Interna- tional 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 lan- guages from simple ones. We show that decision- epoch planners are only complete for languages in the simpler class, and we prove that the simple class is ‘equivalent’ to STRIPS! Surprisingly, no prob- lems with required concurrency have been included in the planning competitions. We conclude by de- signing 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. 1 Introduction Although researchers have investigated a variety of architec- tures for temporal planning (e.g., plan-space: ZENO [Pen- berthy and Weld, 1994], VHPOP [Younes and Simmons, 2003]; extended planning graph: TGP [Smith and Weld, 1999], LPG [Gerevini and Serina, 2002]; reduction to lin- ear programming: LPGP [Long and Fox, 2003]; and others), the most popular current approach is progression (or regres- sion) search through an e