Complexity of concurrent temporal planning

Jussi Rintanen

Complexity of concurrent temporal planning

Jussi Rintanen^*

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › peer-review

61 Citations (Scopus)

Abstract

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.

Original language	English
Title of host publication	ICAPS 2007, 17th International Conference on Automated Planning and Scheduling
Publisher	Association for the Advancement of Artificial Intelligence, AAAI
Pages	280-287
Number of pages	8
ISBN (Print)	9781577353447
Publication status	Published - 2007
Event	ICAPS 2007, 17th International Conference on Automated Planning and Scheduling - Providence, RI, United States Duration: 22 Sept 2007 → 26 Sept 2007

Publication series

Name	ICAPS 2007, 17th International Conference on Automated Planning and Scheduling

Conference

Conference	ICAPS 2007, 17th International Conference on Automated Planning and Scheduling
Country/Territory	United States
City	Providence, RI
Period	22/09/07 → 26/09/07

Cite this

@inproceedings{dec87d322b7242a18926244382102f79,

title = "Complexity of concurrent temporal planning",

abstract = "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.",

author = "Jussi Rintanen",

year = "2007",

language = "English",

isbn = "9781577353447",

series = "ICAPS 2007, 17th International Conference on Automated Planning and Scheduling",

publisher = "Association for the Advancement of Artificial Intelligence, AAAI",

pages = "280--287",

booktitle = "ICAPS 2007, 17th International Conference on Automated Planning and Scheduling",

note = "ICAPS 2007, 17th International Conference on Automated Planning and Scheduling ; Conference date: 22-09-2007 Through 26-09-2007",

}

Rintanen, J 2007, Complexity of concurrent temporal planning. in ICAPS 2007, 17th International Conference on Automated Planning and Scheduling. ICAPS 2007, 17th International Conference on Automated Planning and Scheduling, Association for the Advancement of Artificial Intelligence, AAAI, pp. 280-287, ICAPS 2007, 17th International Conference on Automated Planning and Scheduling, Providence, RI, United States, 22/09/07.

Complexity of concurrent temporal planning. / Rintanen, Jussi.
ICAPS 2007, 17th International Conference on Automated Planning and Scheduling. Association for the Advancement of Artificial Intelligence, AAAI, 2007. p. 280-287 (ICAPS 2007, 17th International Conference on Automated Planning and Scheduling).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › peer-review

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 - https://www.scopus.com/pages/publications/57749201775

M3 - Conference Paper

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 -

Complexity of concurrent temporal planning

Abstract

Publication series

Conference

Other files and links

Cite this