Tight Bounds for Hybrid Planning
Authors: Pascal Bercher, Songtuan Lin, Ron Alford
IJCAI 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper we study the computational complexity of such hybrid planning problems. More specifically, we provide missing membership results to existing hardness proofs and thereby provide tight complexity bounds for all known subclasses of hierarchical planning problems. We also re-visit and correct a result from the literature for plan veriļ¬cation showing that it remains NP-complete even in the absence of a task hierarchy. |
| Researcher Affiliation | Collaboration | Pascal Bercher1 , Songtuan Lin1 , Ron Alford2 1The Australian National University 2The MITRE Corporation |
| Pseudocode | No | The paper describes conceptual definitions and procedures (e.g., Definition 9 for Progression) but does not provide structured pseudocode or algorithm blocks. |
| Open Source Code | No | No statement about providing open-source code for the methodology described in this paper is found. |
| Open Datasets | No | This is a theoretical paper focusing on computational complexity, thus it does not use or reference datasets for training or evaluation. |
| Dataset Splits | No | This is a theoretical paper focusing on computational complexity, thus it does not describe training, validation, or test dataset splits. |
| Hardware Specification | No | This is a theoretical paper focusing on computational complexity, and therefore does not mention hardware specifications for experiments. |
| Software Dependencies | No | This is a theoretical paper focusing on computational complexity, and therefore does not mention specific software dependencies with version numbers. |
| Experiment Setup | No | This is a theoretical paper focusing on computational complexity, and therefore does not describe an experimental setup or hyperparameters. |