@article{Behnke_Höller_Biundo_2015, title={On the Complexity of HTN Plan Verification and Its Implications for Plan Recognition}, volume={25}, url={https://ojs.aaai.org/index.php/ICAPS/article/view/13728}, DOI={10.1609/icaps.v25i1.13728}, abstractNote={ <p> In classical planning it is easy to verify if a given sequence of actions is a solution to a planning problem. It has to be checked whether the actions are applicable in the given order and if a goal state is reached after executing them. In this paper we show that verifying whether a plan is a solution to an HTN planning problem is much harder. More specifically, we prove that this problem is NP-complete, even for very simple HTN planning problems. Furthermore, this problem remains NP-complete if an executable sequence of tasks is already provided. HTN-like hierarchical structures are commonly used to represent plan libraries in plan and goal recognition. By applying our result to plan and goal recognition we provide insight into its complexity. </p> }, number={1}, journal={Proceedings of the International Conference on Automated Planning and Scheduling}, author={Behnke, Gregor and Höller, Daniel and Biundo, Susanne}, year={2015}, month={Apr.}, pages={25-33} }