On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence
Abstract
In this paper we study the computational complexity of several reasoning tasks centered around the bounded plan existence problem. We do this for standard classical planning and hierarchical task network (HTN) planning and each for a grounded and a lifted representation. Whereas bounded plan existence complexity is known for classical planning, it has not yet been studied for HTN planning. For plan verification, results were available for both formalisms except for the lifted HTN planning. We will present lower and upper bounds of the complexity of plan verification in lifted HTN planning and provide novel insights into its grounded counterpart, in which we show that verification is not just NP-complete in the general case, but already for a severely restricted special case. Finally, we show the complexity concerning verifying the optimality of a given plan and discuss its connection to the bounded plan existence problem.
Cite
Text
Lin et al. "On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence." AAAI Conference on Artificial Intelligence, 2024. doi:10.1609/AAAI.V38I18.30000Markdown
[Lin et al. "On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence." AAAI Conference on Artificial Intelligence, 2024.](https://mlanthology.org/aaai/2024/lin2024aaai-computational/) doi:10.1609/AAAI.V38I18.30000BibTeX
@inproceedings{lin2024aaai-computational,
title = {{On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence}},
author = {Lin, Songtuan and Olz, Conny and Helmert, Malte and Bercher, Pascal},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2024},
pages = {20203-20211},
doi = {10.1609/AAAI.V38I18.30000},
url = {https://mlanthology.org/aaai/2024/lin2024aaai-computational/}
}