@InProceedings{Lin2023VerificationComplexity,
  author     = {Songtuan Lin and Conny Olz and Malte Helmert and Pascal Bercher},
  title      = {On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence},
  booktitle  = {Proceedings of the 6th ICAPS Workshop on Hierarchical Planning (HPlan 2023)},
  pages      = {35--43},
  year       = {2023},
  note       = {<strong>Erratum:</strong> Corollary 1 and Proposition 5 incorrectly claimed NEXPTIME and co-NEXPTIME membership, respectively. Both should be one exponential harder, which is stated correctly in the AAAI 2024 version of this paper (same Corollary and Proposition).},
  abstract   = {In this paper we study the computational complexity of several reasoning tasks centered at the bounded plan existence problem. We do this for standard classical planning and hierarchical task network (HTN) planning and each for the grounded and the lifted representation. Whereas bounded plan existence complexity is known for classical planning, it has not been studied yet for HTN planning. For plan verification, results were available for both formalisms except the lifted representation of HTN planning. We will thus present the lower bound and the upper bound 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 computational complexity concerning the optimality of a given plan, i.e., answering the question whether such a plan is optimal, and discuss its connection to the bounded plan existence problem.},
  url_Paper  = {https://bercher.net/publications/2023/Lin2023LiftedVerificationAndPlanEx.pdf},
  url_Slides = {https://bercher.net/publications/2023/Lin2023LiftedVerificationAndPlanExSlides.pdf},
  url_Poster = {https://bercher.net/publications/2023/Lin2023LiftedVerificationAndPlanExPoster.pdf},
  keywords   = {workshop}
}

{"_id":"KD2KdvECN7CNHdv26","bibbaseid":"lin-olz-helmert-bercher-onthecomputationalcomplexityofplanverificationboundedplanoptimalityverificationandboundedplanexistence-2023","author_short":["Lin, S.","Olz, C.","Helmert, M.","Bercher, P."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Songtuan"],"propositions":[],"lastnames":["Lin"],"suffixes":[]},{"firstnames":["Conny"],"propositions":[],"lastnames":["Olz"],"suffixes":[]},{"firstnames":["Malte"],"propositions":[],"lastnames":["Helmert"],"suffixes":[]},{"firstnames":["Pascal"],"propositions":[],"lastnames":["Bercher"],"suffixes":[]}],"title":"On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence","booktitle":"Proceedings of the 6th ICAPS Workshop on Hierarchical Planning (HPlan 2023)","pages":"35–43","year":"2023","note":"<strong>Erratum:</strong> Corollary 1 and Proposition 5 incorrectly claimed NEXPTIME and co-NEXPTIME membership, respectively. Both should be one exponential harder, which is stated correctly in the AAAI 2024 version of this paper (same Corollary and Proposition).","abstract":"In this paper we study the computational complexity of several reasoning tasks centered at the bounded plan existence problem. We do this for standard classical planning and hierarchical task network (HTN) planning and each for the grounded and the lifted representation. Whereas bounded plan existence complexity is known for classical planning, it has not been studied yet for HTN planning. For plan verification, results were available for both formalisms except the lifted representation of HTN planning. We will thus present the lower bound and the upper bound 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 computational complexity concerning the optimality of a given plan, i.e., answering the question whether such a plan is optimal, and discuss its connection to the bounded plan existence problem.","url_paper":"https://bercher.net/publications/2023/Lin2023LiftedVerificationAndPlanEx.pdf","url_slides":"https://bercher.net/publications/2023/Lin2023LiftedVerificationAndPlanExSlides.pdf","url_poster":"https://bercher.net/publications/2023/Lin2023LiftedVerificationAndPlanExPoster.pdf","keywords":"workshop","bibtex":"@InProceedings{Lin2023VerificationComplexity,\n author = {Songtuan Lin and Conny Olz and Malte Helmert and Pascal Bercher},\n title = {On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence},\n booktitle = {Proceedings of the 6th ICAPS Workshop on Hierarchical Planning (HPlan 2023)},\n pages = {35--43},\n year = {2023},\n note = {<strong>Erratum:</strong> Corollary 1 and Proposition 5 incorrectly claimed NEXPTIME and co-NEXPTIME membership, respectively. Both should be one exponential harder, which is stated correctly in the AAAI 2024 version of this paper (same Corollary and Proposition).},\n abstract = {In this paper we study the computational complexity of several reasoning tasks centered at the bounded plan existence problem. We do this for standard classical planning and hierarchical task network (HTN) planning and each for the grounded and the lifted representation. Whereas bounded plan existence complexity is known for classical planning, it has not been studied yet for HTN planning. For plan verification, results were available for both formalisms except the lifted representation of HTN planning. We will thus present the lower bound and the upper bound 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 computational complexity concerning the optimality of a given plan, i.e., answering the question whether such a plan is optimal, and discuss its connection to the bounded plan existence problem.},\n url_Paper = {https://bercher.net/publications/2023/Lin2023LiftedVerificationAndPlanEx.pdf},\n url_Slides = {https://bercher.net/publications/2023/Lin2023LiftedVerificationAndPlanExSlides.pdf},\n url_Poster = {https://bercher.net/publications/2023/Lin2023LiftedVerificationAndPlanExPoster.pdf},\n keywords = {workshop}\n}\n\n","author_short":["Lin, S.","Olz, C.","Helmert, M.","Bercher, P."],"key":"Lin2023VerificationComplexity","id":"Lin2023VerificationComplexity","bibbaseid":"lin-olz-helmert-bercher-onthecomputationalcomplexityofplanverificationboundedplanoptimalityverificationandboundedplanexistence-2023","role":"author","urls":{" paper":"https://bercher.net/publications/2023/Lin2023LiftedVerificationAndPlanEx.pdf"," slides":"https://bercher.net/publications/2023/Lin2023LiftedVerificationAndPlanExSlides.pdf"," poster":"https://bercher.net/publications/2023/Lin2023LiftedVerificationAndPlanExPoster.pdf"},"keyword":["workshop"],"metadata":{"authorlinks":{}},"downloads":18},"bibtype":"inproceedings","biburl":"https://bercher.net/bibtex/bibliography.bib","dataSources":["XzPF4F9wH9enwN62c","jTtEZEw8NJc375xGA","WvkzCyK6mKXCp2WFz","fwibRLpGQRHh67trH","6h6sNir9HQYRtQmou","T9LQLt3D2MDhrCfjh","rta5EvLvgMEDFTyZk","bPpsmYWjffAy6QHP5","wYF8yPQT6a4TgShWe"],"keywords":["workshop"],"search_terms":["computational","complexity","plan","verification","bounded","plan","optimality","verification","bounded","plan","existence","lin","olz","helmert","bercher"],"title":"On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence","year":2023,"downloads":18}