Temporal planningComputational complexityTimed automataTiling problems

Decidability and complexity of action-based temporal planning over dense time

In this paper, we study the computational complexity of action-based temporal planning interpreted over dense time. When time is assumed to be discrete, the problem is known to be EXPSPACE-complete. However, the official PDDL 2.1 semantics and many …