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

Nicola Gigante, Andrea Micheli, Angelo Montanari, Enrico ScalaAAAI 2020 · DOI

Introduction

Temporal planning is a cornerstone of automated scheduling, essential for domains ranging from satellite operations to factory robotics. The industry standard for modeling these problems is PDDL 2.1, which utilizes "dense time" semantics—treating time as a continuous rather than discrete variable. However, for years, a subtle ambiguity has persisted in how PDDL 2.1 handles mutually exclusive (mutex) events. Specifically, it was unclear whether these events must be separated by a fixed constant ($\epsilon$-separation) or merely any value greater than zero (non-zero separation). Furthermore, the impact of allowing an action to "self-overlap"—starting a new instance of an action before the previous one finishes—remained unquantified.

This research settles these long-standing ambiguities by mapping the computational complexity of various semantic choices, identifying which versions of temporal planning are solvable and which are fundamentally impossible.

Methodology: Automata and Tiling

The authors utilize formal language theory and automata theory to categorize planning problems into known complexity classes.

To establish a PSPACE upper bound for planning without self-overlap, they provide a novel polynomial-sized encoding of temporal planning into updatable timed automata. By proving that a valid plan exists if and only if a specific state in the automaton is reachable, they demonstrate that temporal constraints do not necessarily make the search space explode compared to classical planning.

Encoding temporal planning into updatable timed automata for reachability analysis.

For more complex scenarios involving self-overlap, the authors employ corridor tiling problems. These combinatorial puzzles simulate the memory and execution of Turing machines. By reducing these tiling problems to temporal planning, the researchers show that the density of time can allow for "infinite" storage or precision, leading to extreme complexity or undecidability.

The Complexity Landscape

The study identifies three critical factors that determine the difficulty of a planning problem: self-overlap, separation type, and the nature of the temporal bounds. The findings are summarized in a definitive complexity map.

The definitive complexity map for temporal planning under dense time semantics.

Key Insights

  • The Self-Overlap Pivot: If self-overlap is forbidden, the problem remains PSPACE-complete, regardless of the separation rule. This is a vital result for practitioners, suggesting that standard temporal constraints are manageable.
  • The "Density" Trap: When self-overlap is permitted in dense time, a planner can theoretically initiate an infinite number of actions within a single time unit. This "Zeno-like" behavior allows for the encoding of infinite information, which is the root cause of the undecidability result.
  • Separation Matters: There is a massive theoretical gap between $\epsilon$-separation (e.g., at least 0.001s) and non-zero separation (any value $> 0$). The former is hard (EXPSPACE-complete), while the latter is undecidable.

Conclusion and Practical Implications

These results clarify that the "non-zero" separation originally proposed in the PDDL 2.1 specification is theoretically dangerous. To remain computationally sound, planners should default to $\epsilon$-separation or explicitly forbid self-overlap.

Future work remains to be done regarding numeric fluents (variables like fuel or temperature), which likely add further layers of complexity. Additionally, while the encoding into timed automata was used here as a theoretical proof, the authors suggest that utilizing existing timed automata solvers for practical planning is a promising new research direction.

Summary updated

BibTeX
@inproceedings{gigante2020decidability,
  author = {Nicola Gigante and Andrea Micheli and Angelo Montanari and Enrico Scala},
  title = {{Decidability and Complexity of Action-Based Temporal Planning over Dense Time}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2020},
  doi = {10.1609/aaai.v34i06.6539},
}
Figure