TY - GEN
T1 - Complexity of concurrent temporal planning
AU - Rintanen, Jussi
PY - 2007
Y1 - 2007
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=57749201775&partnerID=8YFLogxK
M3 - Conference contribution
SN - 9781577353447
T3 - ICAPS 2007, 17th International Conference on Automated Planning and Scheduling
SP - 280
EP - 287
BT - ICAPS 2007, 17th International Conference on Automated Planning and Scheduling
PB - Association for the Advancement of Artificial Intelligence, AAAI
T2 - ICAPS 2007, 17th International Conference on Automated Planning and Scheduling
Y2 - 22 September 2007 through 26 September 2007
ER -