Spanning the Middle Ground between Classical and Temporal Planning

Abstract. A recent evaluation of the complexity of temporal planning by Cushing et al. [1] unveiled the interesting result that many current temporal planning problems may be transformed into classical ones in linear time; in other words, they are actually not temporal. Based on this insight, we introduce a new, graded classification of classical planning problems that are temporal to some degree. We present a simple and complete solution method for solving temporally non-simple, expressive problems that makes use of this concept.