Decidability and Complexity of Action-Based Temporal Planning over Dense Time

Authors

  • Nicola Gigante University of Udine
  • Andrea Micheli Fondazione Bruno Kessler
  • Angelo Montanari University of Udine
  • Enrico Scala University of Brescia

DOI:

https://doi.org/10.1609/aaai.v34i06.6539

Abstract

This paper studies the computational complexity of temporal planning, as represented by PDDL 2.1, interpreted over dense time. When time is considered discrete, the problem is known to be EXPSPACE-complete. However, the official PDDL 2.1 semantics, and many implementations, interpret time as a dense domain. This work provides several results about the complexity of the problem, studying a few interesting cases: whether a minimum amount ϵ of separation between mutually exclusive events is given, in contrast to the separation being simply required to be non-zero, and whether or not actions are allowed to overlap already running instances of themselves. We prove the problem to be PSPACE-complete when self-overlap is forbidden, whereas, when allowed, it becomes EXPSPACE-complete with ϵ-separation and undecidable with non-zero separation. These results clarify the computational consequences of different choices in the definition of the PDDL 2.1 semantics, which were vague until now.

Downloads

Published

2020-04-03

How to Cite

Gigante, N., Micheli, A., Montanari, A., & Scala, E. (2020). Decidability and Complexity of Action-Based Temporal Planning over Dense Time. Proceedings of the AAAI Conference on Artificial Intelligence, 34(06), 9859-9866. https://doi.org/10.1609/aaai.v34i06.6539

Issue

Section

AAAI Technical Track: Planning, Routing, and Scheduling