@InProceedings{Lin2023RepairingHTNModelsComplexity,
  author     = {Songtuan Lin and Pascal Bercher},
  booktitle  = {Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI 2023)},
  title      = {Was Fixing this Really That Hard? On the Complexity of Correcting HTN Domains},
  year       = {2023},
  pages      = {12032--12040},
  publisher  = {AAAI Press},
  abstract   = {Automated modeling assistance is indispensable to the AI planning being deployed in practice, notably in industry and other non-academic contexts. Yet, little progress has been made that goes beyond smart interfaces like programming environments. They focus on autocompletion, but lack intelligent support for guiding the modeler. As a theoretical foundation of a first step towards this direction, we study the computational complexity of correcting a flawed Hierarchical Task Network (HTN) planning domain. Specifically, a modeler provides a (white) list of plans that are supposed to be solutions, and likewise a (black) list of plans that shall not be solutions. We investigate the complexity of finding a set of (optimal or suboptimal) model corrections so that those plans are (respective not) solutions to the corrected model. More specifically, we factor out each hardness source that contributes towards NP-hardness, including one that we deem important for many other complexity investigations that go beyond our specific context of application. All complexities range between NP and Sigma-2-p, raising the hope for efficient practical tools in the future.},
  doi        = {10.1609/aaai.v37i10.26419},
  url_Paper  = {https://bercher.net/publications/2023/Lin2023RepairingHTNModelsComplexity.pdf},
  url_Poster = {https://bercher.net/publications/2023/Lin2023RepairingHTNModelsComplexityPoster.pdf},
  url_Slides = {https://bercher.net/publications/2023/Lin2023RepairingHTNModelsComplexitySlides.pdf},
  keywords   = {conference}
}

{"_id":"ALZJnNQRNy7mXoE8b","bibbaseid":"lin-bercher-wasfixingthisreallythathardonthecomplexityofcorrectinghtndomains-2023","author_short":["Lin, S.","Bercher, P."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Songtuan"],"propositions":[],"lastnames":["Lin"],"suffixes":[]},{"firstnames":["Pascal"],"propositions":[],"lastnames":["Bercher"],"suffixes":[]}],"booktitle":"Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI 2023)","title":"Was Fixing this Really That Hard? On the Complexity of Correcting HTN Domains","year":"2023","pages":"12032–12040","publisher":"AAAI Press","abstract":"Automated modeling assistance is indispensable to the AI planning being deployed in practice, notably in industry and other non-academic contexts. Yet, little progress has been made that goes beyond smart interfaces like programming environments. They focus on autocompletion, but lack intelligent support for guiding the modeler. As a theoretical foundation of a first step towards this direction, we study the computational complexity of correcting a flawed Hierarchical Task Network (HTN) planning domain. Specifically, a modeler provides a (white) list of plans that are supposed to be solutions, and likewise a (black) list of plans that shall not be solutions. We investigate the complexity of finding a set of (optimal or suboptimal) model corrections so that those plans are (respective not) solutions to the corrected model. More specifically, we factor out each hardness source that contributes towards NP-hardness, including one that we deem important for many other complexity investigations that go beyond our specific context of application. All complexities range between NP and Sigma-2-p, raising the hope for efficient practical tools in the future.","doi":"10.1609/aaai.v37i10.26419","url_paper":"https://bercher.net/publications/2023/Lin2023RepairingHTNModelsComplexity.pdf","url_poster":"https://bercher.net/publications/2023/Lin2023RepairingHTNModelsComplexityPoster.pdf","url_slides":"https://bercher.net/publications/2023/Lin2023RepairingHTNModelsComplexitySlides.pdf","keywords":"conference","bibtex":"@InProceedings{Lin2023RepairingHTNModelsComplexity,\n author = {Songtuan Lin and Pascal Bercher},\n booktitle = {Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI 2023)},\n title = {Was Fixing this Really That Hard? On the Complexity of Correcting HTN Domains},\n year = {2023},\n pages = {12032--12040},\n publisher = {AAAI Press},\n abstract = {Automated modeling assistance is indispensable to the AI planning being deployed in practice, notably in industry and other non-academic contexts. Yet, little progress has been made that goes beyond smart interfaces like programming environments. They focus on autocompletion, but lack intelligent support for guiding the modeler. As a theoretical foundation of a first step towards this direction, we study the computational complexity of correcting a flawed Hierarchical Task Network (HTN) planning domain. Specifically, a modeler provides a (white) list of plans that are supposed to be solutions, and likewise a (black) list of plans that shall not be solutions. We investigate the complexity of finding a set of (optimal or suboptimal) model corrections so that those plans are (respective not) solutions to the corrected model. More specifically, we factor out each hardness source that contributes towards NP-hardness, including one that we deem important for many other complexity investigations that go beyond our specific context of application. All complexities range between NP and Sigma-2-p, raising the hope for efficient practical tools in the future.},\n doi = {10.1609/aaai.v37i10.26419},\n url_Paper = {https://bercher.net/publications/2023/Lin2023RepairingHTNModelsComplexity.pdf},\n url_Poster = {https://bercher.net/publications/2023/Lin2023RepairingHTNModelsComplexityPoster.pdf},\n url_Slides = {https://bercher.net/publications/2023/Lin2023RepairingHTNModelsComplexitySlides.pdf},\n keywords = {conference}\n}\n\n","author_short":["Lin, S.","Bercher, P."],"key":"Lin2023RepairingHTNModelsComplexity","id":"Lin2023RepairingHTNModelsComplexity","bibbaseid":"lin-bercher-wasfixingthisreallythathardonthecomplexityofcorrectinghtndomains-2023","role":"author","urls":{" paper":"https://bercher.net/publications/2023/Lin2023RepairingHTNModelsComplexity.pdf"," poster":"https://bercher.net/publications/2023/Lin2023RepairingHTNModelsComplexityPoster.pdf"," slides":"https://bercher.net/publications/2023/Lin2023RepairingHTNModelsComplexitySlides.pdf"},"keyword":["conference"],"metadata":{"authorlinks":{}},"downloads":36},"bibtype":"inproceedings","biburl":"https://bercher.net/bibtex/bibliography.bib","dataSources":["WvkzCyK6mKXCp2WFz","zKgS72cAu6Ez7npdh","rta5EvLvgMEDFTyZk","BLJPWpPi3hneTGaPF","bPpsmYWjffAy6QHP5","wYF8yPQT6a4TgShWe"],"keywords":["conference"],"search_terms":["fixing","really","hard","complexity","correcting","htn","domains","lin","bercher"],"title":"Was Fixing this Really That Hard? On the Complexity of Correcting HTN Domains","year":2023,"downloads":36}