| Title: |
Tight Bounds for Lifted HTN Plan Verification and Bounded Plan Existence |
| Authors: |
Lauer, Pascal; Lin, Songtuan; Bercher, Pascal |
| Source: |
Proceedings of the International Conference on Automated Planning and Scheduling; Vol. 35 (2025): Proceedings of the Thirty-Fifth International Conference on Automated Planning and Scheduling; 64-73 ; 2334-0843 ; 2334-0835 |
| Publisher Information: |
Association for the Advancement of Artificial Intelligence |
| Publication Year: |
2025 |
| Collection: |
Association for the Advancement of Artificial Intelligence: AAAI Publications |
| Description: |
Plan verification is a canonical problem within any planning setting to ensure correctness. This problem is closely linked to the bounded plan existence problem. We analyze the complexity of these problems on lifted representations for Hierarchical Task Network (HTN) Planning. On top of the general analysis, we impose constraints on method orderings and the amount of tasks that methods decompose to. This pinpoints subclasses with lower complexity. Our results confirm the existence of more efficient algorithms when operating on the lifted, instead of grounded, representation. |
| Document Type: |
article in journal/newspaper |
| File Description: |
application/pdf |
| Language: |
English |
| Relation: |
https://ojs.aaai.org/index.php/ICAPS/article/view/36102/38256; https://ojs.aaai.org/index.php/ICAPS/article/view/36102 |
| DOI: |
10.1609/icaps.v35i1.36102 |
| Availability: |
https://ojs.aaai.org/index.php/ICAPS/article/view/36102; https://doi.org/10.1609/icaps.v35i1.36102 |
| Rights: |
Copyright (c) 2024 Association for the Advancement of Artificial Intelligence |
| Accession Number: |
edsbas.B3FE71D2 |
| Database: |
BASE |