@InProceedings{Lin2021CorrectingHTNModels,
  author     = {Songtuan Lin and Pascal Bercher},
  title      = {On the Computational Complexity of Correcting HTN Domain Models},
  booktitle  = {Proceedings of the 4th ICAPS Workshop on Hierarchical Planning (HPlan 2021)},
  year       = {2021},
  pages      = {35--43},
  abstract   = {Incorporating user requests into planning processes is a key concept in developing flexible planning technologies. Such systems may be required to change its planning model to adapt to certain user requests. In this paper, we assume a user provides a non-solution plan to a system and asks it to change the planning model so that the plan becomes a solution. We study the computational complexity of deciding whether such changes exist in the context of Hierarchical Task Network (HTN) planning. We prove that the problem is NP-complete in general independent of what or how many changes are allowed. We also identify several conditions which make the problem tractable when they are satisfied.},
  url_Paper  = {https://bercher.net/publications/2021/Lin2021HTNChangeComplexity.pdf},
  url_Slides = {https://bercher.net/publications/2021/Lin2021HTNChangeComplexitySlides.pdf},
  url_Poster = {https://bercher.net/publications/2021/Lin2021HTNChangeComplexityPoster.pdf},
  keywords   = {workshop}
}

{"_id":"2W9ermJnMGqXXvtay","bibbaseid":"lin-bercher-onthecomputationalcomplexityofcorrectinghtndomainmodels-2021","author_short":["Lin, S.","Bercher, P."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Songtuan"],"propositions":[],"lastnames":["Lin"],"suffixes":[]},{"firstnames":["Pascal"],"propositions":[],"lastnames":["Bercher"],"suffixes":[]}],"title":"On the Computational Complexity of Correcting HTN Domain Models","booktitle":"Proceedings of the 4th ICAPS Workshop on Hierarchical Planning (HPlan 2021)","year":"2021","pages":"35–43","abstract":"Incorporating user requests into planning processes is a key concept in developing flexible planning technologies. Such systems may be required to change its planning model to adapt to certain user requests. In this paper, we assume a user provides a non-solution plan to a system and asks it to change the planning model so that the plan becomes a solution. We study the computational complexity of deciding whether such changes exist in the context of Hierarchical Task Network (HTN) planning. We prove that the problem is NP-complete in general independent of what or how many changes are allowed. We also identify several conditions which make the problem tractable when they are satisfied.","url_paper":"https://bercher.net/publications/2021/Lin2021HTNChangeComplexity.pdf","url_slides":"https://bercher.net/publications/2021/Lin2021HTNChangeComplexitySlides.pdf","url_poster":"https://bercher.net/publications/2021/Lin2021HTNChangeComplexityPoster.pdf","keywords":"workshop","bibtex":"@InProceedings{Lin2021CorrectingHTNModels,\n author = {Songtuan Lin and Pascal Bercher},\n title = {On the Computational Complexity of Correcting HTN Domain Models},\n booktitle = {Proceedings of the 4th ICAPS Workshop on Hierarchical Planning (HPlan 2021)},\n year = {2021},\n pages = {35--43},\n abstract = {Incorporating user requests into planning processes is a key concept in developing flexible planning technologies. Such systems may be required to change its planning model to adapt to certain user requests. In this paper, we assume a user provides a non-solution plan to a system and asks it to change the planning model so that the plan becomes a solution. We study the computational complexity of deciding whether such changes exist in the context of Hierarchical Task Network (HTN) planning. We prove that the problem is NP-complete in general independent of what or how many changes are allowed. We also identify several conditions which make the problem tractable when they are satisfied.},\n url_Paper = {https://bercher.net/publications/2021/Lin2021HTNChangeComplexity.pdf},\n url_Slides = {https://bercher.net/publications/2021/Lin2021HTNChangeComplexitySlides.pdf},\n url_Poster = {https://bercher.net/publications/2021/Lin2021HTNChangeComplexityPoster.pdf},\n keywords = {workshop}\n}\n\n","author_short":["Lin, S.","Bercher, P."],"key":"Lin2021CorrectingHTNModels","id":"Lin2021CorrectingHTNModels","bibbaseid":"lin-bercher-onthecomputationalcomplexityofcorrectinghtndomainmodels-2021","role":"author","urls":{" paper":"https://bercher.net/publications/2021/Lin2021HTNChangeComplexity.pdf"," slides":"https://bercher.net/publications/2021/Lin2021HTNChangeComplexitySlides.pdf"," poster":"https://bercher.net/publications/2021/Lin2021HTNChangeComplexityPoster.pdf"},"keyword":["workshop"],"metadata":{"authorlinks":{}},"downloads":11},"bibtype":"inproceedings","biburl":"https://bercher.net/bibtex/bibliography.bib","dataSources":["Gq638hec4HPziarNx","jTtEZEw8NJc375xGA","WvkzCyK6mKXCp2WFz","T9LQLt3D2MDhrCfjh","rta5EvLvgMEDFTyZk","bPpsmYWjffAy6QHP5","wYF8yPQT6a4TgShWe"],"keywords":["workshop"],"search_terms":["computational","complexity","correcting","htn","domain","models","lin","bercher"],"title":"On the Computational Complexity of Correcting HTN Domain Models","year":2021,"downloads":11}