Complexity of Concurrent Temporal Planning

Jussi Rintanen

We consider the problem of temporal planning in which a given goal is reached by taking a number of actions which may temporally overlap and interfere, and the interference may be essential for reaching the goals. We formalize a general temporal planning problem, show that its plan existence problem is EXPSPACE-complete, and give conditions under which it is reducible to classical planning and is therefore only PSPACE-complete. Our results are the first to show that temporal planning can be computationally more complex than classical planning. They also show how and why a very large and important fragment of temporal PDDL is reducible to classical planning.

Subjects: 1.11 Planning; 9.2 Computational Complexity

Submitted: Jun 27, 2007

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.