A Structural Complexity Analysis of Hierarchical Task Network Planning
Authors: Cornelius Brand, Robert Ganian, Fionn Mc Inerney, Simon Wietheger
IJCAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We perform a refined complexity-theoretic analysis of three classical problems in the context of Hierarchical Task Network planning: the verification of a provided plan, whether an executable plan exists, and whether a given state can be reached. Our focus is to identify structural properties yielding tractability. We obtain new polynomial-time algorithms for all three problems on a natural class of primitive networks, along with corresponding lower bounds. We also obtain an algorithmic meta-theorem for lifting polynomial-time solvability from primitive to general task networks, and prove that its preconditions are tight. Lastly, we analyze the parameterized complexity of the three problems. |
| Researcher Affiliation | Collaboration | Cornelius Brand1 , Robert Ganian2 , Fionn Mc Inerney3 and Simon Wietheger2 1Algorithms & Complexity Theory Group, Regensburg University, Germany 2Algorithms and Complexity Group, TU Wien, Austria 3Telef onica Scientific Research, Barcelona, Spain EMAIL, EMAIL, EMAIL |
| Pseudocode | No | The paper describes algorithms and complexity analyses in prose, within the main body of text and proofs of theorems. There are no explicitly labeled pseudocode blocks or algorithm listings in a structured format. |
| Open Source Code | No | The paper does not provide any information about the availability of open-source code for the described methodology. There are no links to repositories, explicit statements of code release, or references to supplementary materials containing code. |
| Open Datasets | No | The paper focuses on theoretical complexity analysis and algorithmic results for Hierarchical Task Network planning. It does not describe any experiments that would utilize specific datasets, nor does it provide information about the availability of any open datasets. |
| Dataset Splits | No | The paper does not present any empirical evaluation using datasets, and therefore no dataset splits are discussed or provided. |
| Hardware Specification | No | The paper is theoretical, focusing on complexity analysis and algorithmic meta-theorems. It does not include any experimental results that would require specific hardware, and thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper does not provide details on software dependencies, including specific version numbers for libraries or solvers, as it focuses on theoretical complexity analysis and algorithmic design rather than concrete implementations. |
| Experiment Setup | No | This paper is theoretical in nature, presenting complexity analyses and algorithmic meta-theorems. It does not include an experimental section, and consequently, no experimental setup details such as hyperparameters or specific training configurations are provided. |