{"_id":"WyxoDH4N5AxbNgEPw","bibbaseid":"chen-bercher-fullyobservablenondeterministichtnplanningformalisationandcomplexityresults-2021","authorIDs":["qRXT9gMNhQE98wFSS"],"author_short":["Chen, D.","Bercher, P."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Dillon"],"propositions":[],"lastnames":["Chen"],"suffixes":[]},{"firstnames":["Pascal"],"propositions":[],"lastnames":["Bercher"],"suffixes":[]}],"title":"Fully Observable Nondeterministic HTN Planning – Formalisation and Complexity Results","booktitle":"Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS 2021)","year":"2021","pages":"74–84","publisher":"AAAI Press","doi":"10.1609/icaps.v31i1.15949","abstract":"Much progress has been made in advancing the state of the art of HTN planning theory in recent years. However, scarce studies have been made with regards to the theory and complexity of HTN problems on nondeterministic domains. In this paper we provide a novel formalisation for fully observable nondeterministic HTN planning. We propose and study different solution criteria which differ in when nondeterministic action outcomes are considered: at plan generation or at plan execution. We integrate our solution criteria with notions of weak and strong plans canonical in nondeterministic planning and identify similarities and differences with plans in other fields of AI planning. We also provide completeness results for a majority of HTN problem subclasses and show the significant result that problems are not made any harder under nondeterminism for certain solution criteria by using compilation techniques to deterministic HTN planning. This supports and justifies the practicality and scalability of extending HTN problems over nondeterministic domains to deal with real world scenarios.","url_paper":"https://bercher.net/publications/2021/Chen2021FONDHTNs.pdf","url_video_of_presentation":"https://icaps21.icaps-conference.org/papers/exhibition_files/index_44.html","note":"<b><i>This paper won the ICAPS 2021 Best Undergraduate Student Paper Award</i></b>","keywords":"conference","bibtex":"@InProceedings{Chen2021FONDHTN,\n author = {Dillon Chen and Pascal Bercher},\n title = {Fully Observable Nondeterministic HTN Planning -- Formalisation and Complexity Results},\n booktitle = {Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS 2021)},\n year = {2021},\n pages = {74--84},\n publisher = {AAAI Press},\n doi = {10.1609/icaps.v31i1.15949},\n abstract = {Much progress has been made in advancing the state of the art of HTN planning theory in recent years. However, scarce studies have been made with regards to the theory and complexity of HTN problems on nondeterministic domains. In this paper we provide a novel formalisation for fully observable nondeterministic HTN planning. We propose and study different solution criteria which differ in when nondeterministic action outcomes are considered: at plan generation or at plan execution. We integrate our solution criteria with notions of weak and strong plans canonical in nondeterministic planning and identify similarities and differences with plans in other fields of AI planning. We also provide completeness results for a majority of HTN problem subclasses and show the significant result that problems are not made any harder under nondeterminism for certain solution criteria by using compilation techniques to deterministic HTN planning. This supports and justifies the practicality and scalability of extending HTN problems over nondeterministic domains to deal with real world scenarios.},\n url_Paper = {https://bercher.net/publications/2021/Chen2021FONDHTNs.pdf},\n url_video_of_presentation = {https://icaps21.icaps-conference.org/papers/exhibition_files/index_44.html},\n note = {<b><i>This paper won the ICAPS 2021 Best Undergraduate Student Paper Award</i></b>},\n keywords = {conference}\n}\n\n","author_short":["Chen, D.","Bercher, P."],"key":"Chen2021FONDHTN","id":"Chen2021FONDHTN","bibbaseid":"chen-bercher-fullyobservablenondeterministichtnplanningformalisationandcomplexityresults-2021","role":"author","urls":{" paper":"https://bercher.net/publications/2021/Chen2021FONDHTNs.pdf"," video of presentation":"https://icaps21.icaps-conference.org/papers/exhibition_files/index_44.html"},"keyword":["conference"],"metadata":{"authorlinks":{"bercher, p":"https://bercher.net/my-publications/conference-papers"}},"downloads":39},"bibtype":"inproceedings","biburl":"https://bercher.net/bibtex/bibliography.bib","creationDate":"2021-02-17T00:12:23.624Z","downloads":39,"keywords":["conference"],"search_terms":["fully","observable","nondeterministic","htn","planning","formalisation","complexity","results","chen","bercher"],"title":"Fully Observable Nondeterministic HTN Planning – Formalisation and Complexity Results","year":2021,"dataSources":["upePYbh3wGv9oDZcn","zKgS72cAu6Ez7npdh","Dv9ACZYWLXYQhNhm2","bPpsmYWjffAy6QHP5","wYF8yPQT6a4TgShWe"]}