@InProceedings{Dekker2024HTNComplexityResults,
  author    = {Maurice Dekker and Gregor Behnke},
  booktitle = {Proceedings of the 7th ICAPS Workshop on Hierarchical Planning (HPlan 2024)},
  title     = {Barely Decidable Fragments of HTN Planning},
  year      = {2024},
  abstract  = {Unrestricted HTN planning is undecidable. However some fragments of HTN planning - such as totally-ordered or tail-recursive HTNs - are decidable. Studying these restricted fragments has lead to valuable insights, which ultimately gave rise to the development of new efficient HTN planning algorithms. We identify new decidable fragments of HTN planning. In a one-hole-digging problem, every task network contains at most a single compound task. In an initial problem, compound tasks are order-minimal in all task networks, while in a final problem, they are order-maximal. We precisely determine the complexity of these fragments - they are Ackermann-complete. This remains true even under the restriction that there is only one compound task and only two methods for it.},
  url_paper = {https://icaps24.icaps-conference.org/program/workshops/hplan/HPlan2024_paper_10.pdf},
  pages     = {19--26}
}

{"_id":"qLG7HBQhLTF2rK5Ba","bibbaseid":"dekker-behnke-barelydecidablefragmentsofhtnplanning-2024","author_short":["Dekker, M.","Behnke, G."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Maurice"],"propositions":[],"lastnames":["Dekker"],"suffixes":[]},{"firstnames":["Gregor"],"propositions":[],"lastnames":["Behnke"],"suffixes":[]}],"booktitle":"Proceedings of the 7th ICAPS Workshop on Hierarchical Planning (HPlan 2024)","title":"Barely Decidable Fragments of HTN Planning","year":"2024","abstract":"Unrestricted HTN planning is undecidable. However some fragments of HTN planning - such as totally-ordered or tail-recursive HTNs - are decidable. Studying these restricted fragments has lead to valuable insights, which ultimately gave rise to the development of new efficient HTN planning algorithms. We identify new decidable fragments of HTN planning. In a one-hole-digging problem, every task network contains at most a single compound task. In an initial problem, compound tasks are order-minimal in all task networks, while in a final problem, they are order-maximal. We precisely determine the complexity of these fragments - they are Ackermann-complete. This remains true even under the restriction that there is only one compound task and only two methods for it.","url_paper":"https://icaps24.icaps-conference.org/program/workshops/hplan/HPlan2024_paper_10.pdf","pages":"19–26","bibtex":"@InProceedings{Dekker2024HTNComplexityResults,\n author = {Maurice Dekker and Gregor Behnke},\n booktitle = {Proceedings of the 7th ICAPS Workshop on Hierarchical Planning (HPlan 2024)},\n title = {Barely Decidable Fragments of HTN Planning},\n year = {2024},\n abstract = {Unrestricted HTN planning is undecidable. However some fragments of HTN planning - such as totally-ordered or tail-recursive HTNs - are decidable. Studying these restricted fragments has lead to valuable insights, which ultimately gave rise to the development of new efficient HTN planning algorithms. We identify new decidable fragments of HTN planning. In a one-hole-digging problem, every task network contains at most a single compound task. In an initial problem, compound tasks are order-minimal in all task networks, while in a final problem, they are order-maximal. We precisely determine the complexity of these fragments - they are Ackermann-complete. This remains true even under the restriction that there is only one compound task and only two methods for it.},\n url_paper = {https://icaps24.icaps-conference.org/program/workshops/hplan/HPlan2024_paper_10.pdf},\n pages = {19--26}\n}","author_short":["Dekker, M.","Behnke, G."],"key":"Dekker2024HTNComplexityResults","id":"Dekker2024HTNComplexityResults","bibbaseid":"dekker-behnke-barelydecidablefragmentsofhtnplanning-2024","role":"author","urls":{" paper":"https://icaps24.icaps-conference.org/program/workshops/hplan/HPlan2024_paper_10.pdf"},"metadata":{"authorlinks":{}},"downloads":4},"bibtype":"inproceedings","biburl":"https://icaps24.icaps-conference.org/program/workshops/hplan/hplan.bib","dataSources":["obo5j8TzJxMFi59JG","T9LQLt3D2MDhrCfjh"],"keywords":[],"search_terms":["barely","decidable","fragments","htn","planning","dekker","behnke"],"title":"Barely Decidable Fragments of HTN Planning","year":2024,"downloads":4}