Decidability and Complexity of Action-Based Temporal Planning over Dense Time
Decidability and Complexity of Action-Based Temporal Planning over Dense Time
复制标题
密集时间内基于行动的时间规划的可判定性和复杂性
DOI：
10.1609/aaai.v34i06.6539
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Enrico Scala
中科院分区：
文献类型：
--
作者：
N. Gigante;A. Micheli;A. Montanari;Enrico Scala
本文研究了时间规划的计算复杂性，以PDDL 2.1为代表，在密集的时间解释。当时间被认为是离散的，这个问题是EXPSPACE完全的。然而，官方PDDL 2.1语义和许多实现将时间解释为密集域。这项工作提供了几个结果的复杂性的问题，研究了一些有趣的情况下：是否一个最小量的互斥事件之间的分离，在对比的分离被简单地要求是非零的，以及是否动作被允许重叠已经运行的实例本身。我们证明了这个问题是PSPACE-完全的自我重叠时，禁止，而当允许，它成为EXPSPACE-完全的与非零分离和不可判定的分离。这些结果澄清了PDDL 2.1语义定义中不同选择的计算后果，直到现在还很模糊。
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.