Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2401.14174 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913660330311680 |
|---|---|
| author | Brand, Cornelius Ganian, Robert Inerney, Fionn Mc Wietheger, Simon |
| author_facet | Brand, Cornelius Ganian, Robert Inerney, Fionn Mc Wietheger, Simon |
| contents | 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 lies on identifying structural properties which yield tractability. We obtain new polynomial 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. Finally, we analyze the parameterized complexity of the three problems. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_14174 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A Structural Complexity Analysis of Hierarchical Task Network Planning Brand, Cornelius Ganian, Robert Inerney, Fionn Mc Wietheger, Simon Computational Complexity Artificial Intelligence 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 lies on identifying structural properties which yield tractability. We obtain new polynomial 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. Finally, we analyze the parameterized complexity of the three problems. |
| title | A Structural Complexity Analysis of Hierarchical Task Network Planning |
| topic | Computational Complexity Artificial Intelligence |
| url | https://arxiv.org/abs/2401.14174 |