Decidability and Complexity of Action-Based Temporal Planning over Dense Time
Authors: Nicola Gigante, Andrea Micheli, Angelo Montanari, Enrico Scala9859-9866
AAAI 2020 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | This paper studies the computational complexity of temporal planning, as represented by PDDL 2.1, interpreted over dense time. 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. |
| Researcher Affiliation | Academia | 1University of Udine, Italy {nicola.gigante, angelo.montanari}@uniud.it 2Fondazione Bruno Kessler, Trento, Italy amicheli@fbk.eu 3University of Brescia, Italy enrico.scala@unibs.it |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any statement or link indicating the release of source code for the methodology described. |
| Open Datasets | No | The paper describes theoretical results and does not use datasets for empirical evaluation. |
| Dataset Splits | No | The paper describes theoretical results and does not report on dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper describes theoretical results and does not provide hardware specifications for running experiments. |
| Software Dependencies | No | The paper describes theoretical results and does not provide specific software dependencies with version numbers. |
| Experiment Setup | No | The paper describes theoretical results and does not provide details about an experimental setup. |