@InProceedings{Yousefi2025ImperfectAStar,
  author    = {Mohammad Yousefi and Mario Schmautz and Patrik Haslum and Pascal Bercher},
  booktitle = {Proceedings of the 35th International Conference on Automated Planning and Scheduling ({ICAPS 2025})},
  title     = {How Good is Perfect? On the Incompleteness of A* for Total-Order HTN Planning},
  year      = {2025},
  publisher = {AAAI Press},
  abstract  = {This paper highlights a critical limitation in applying A* search to Hierarchical Task Network (HTN) planning -- the predominant approach for solving problems optimally. We demonstrate that A* search is incomplete even in the severely restricted case of totally-ordered problems, and surprisingly, the result holds even when using the perfect heuristic. Nevertheless, we prove that decomposition patterns that lead to incompleteness can be detected prior to search in polynomial-time. We also introduce a mapping that preserves domain semantics while ensuring the completeness of A* in the transformed space. Our evaluation of the International Planning Competition (IPC) 2023 benchmarks reveals the frequency of these problematic conditions in real-world scenarios.},
  keywords  = {conference,DECRA},
  url_Paper = {https://bercher.net/publications/2025/Yousefi2025ImperfectAStar.pdf}
}

{"_id":"ckYdqEtsi9maX3hhC","bibbaseid":"yousefi-schmautz-haslum-bercher-howgoodisperfectontheincompletenessofafortotalorderhtnplanning-2025","author_short":["Yousefi, M.","Schmautz, M.","Haslum, P.","Bercher, P."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Mohammad"],"propositions":[],"lastnames":["Yousefi"],"suffixes":[]},{"firstnames":["Mario"],"propositions":[],"lastnames":["Schmautz"],"suffixes":[]},{"firstnames":["Patrik"],"propositions":[],"lastnames":["Haslum"],"suffixes":[]},{"firstnames":["Pascal"],"propositions":[],"lastnames":["Bercher"],"suffixes":[]}],"booktitle":"Proceedings of the 35th International Conference on Automated Planning and Scheduling (ICAPS 2025)","title":"How Good is Perfect? On the Incompleteness of A* for Total-Order HTN Planning","year":"2025","publisher":"AAAI Press","abstract":"This paper highlights a critical limitation in applying A* search to Hierarchical Task Network (HTN) planning – the predominant approach for solving problems optimally. We demonstrate that A* search is incomplete even in the severely restricted case of totally-ordered problems, and surprisingly, the result holds even when using the perfect heuristic. Nevertheless, we prove that decomposition patterns that lead to incompleteness can be detected prior to search in polynomial-time. We also introduce a mapping that preserves domain semantics while ensuring the completeness of A* in the transformed space. Our evaluation of the International Planning Competition (IPC) 2023 benchmarks reveals the frequency of these problematic conditions in real-world scenarios.","keywords":"conference,DECRA","url_paper":"https://bercher.net/publications/2025/Yousefi2025ImperfectAStar.pdf","bibtex":"@InProceedings{Yousefi2025ImperfectAStar,\n author = {Mohammad Yousefi and Mario Schmautz and Patrik Haslum and Pascal Bercher},\n booktitle = {Proceedings of the 35th International Conference on Automated Planning and Scheduling ({ICAPS 2025})},\n title = {How Good is Perfect? On the Incompleteness of A* for Total-Order HTN Planning},\n year = {2025},\n publisher = {AAAI Press},\n abstract = {This paper highlights a critical limitation in applying A* search to Hierarchical Task Network (HTN) planning -- the predominant approach for solving problems optimally. We demonstrate that A* search is incomplete even in the severely restricted case of totally-ordered problems, and surprisingly, the result holds even when using the perfect heuristic. Nevertheless, we prove that decomposition patterns that lead to incompleteness can be detected prior to search in polynomial-time. We also introduce a mapping that preserves domain semantics while ensuring the completeness of A* in the transformed space. Our evaluation of the International Planning Competition (IPC) 2023 benchmarks reveals the frequency of these problematic conditions in real-world scenarios.},\n keywords = {conference,DECRA},\n url_Paper = {https://bercher.net/publications/2025/Yousefi2025ImperfectAStar.pdf}\n}\n\n","author_short":["Yousefi, M.","Schmautz, M.","Haslum, P.","Bercher, P."],"key":"Yousefi2025ImperfectAStar","id":"Yousefi2025ImperfectAStar","bibbaseid":"yousefi-schmautz-haslum-bercher-howgoodisperfectontheincompletenessofafortotalorderhtnplanning-2025","role":"author","urls":{" paper":"https://bercher.net/publications/2025/Yousefi2025ImperfectAStar.pdf"},"keyword":["conference","DECRA"],"metadata":{"authorlinks":{}},"downloads":1},"bibtype":"inproceedings","biburl":"https://bercher.net/bibtex/bibliography.bib","dataSources":["bPpsmYWjffAy6QHP5"],"keywords":["conference","decra"],"search_terms":["good","perfect","incompleteness","total","order","htn","planning","yousefi","schmautz","haslum","bercher"],"title":"How Good is Perfect? On the Incompleteness of A* for Total-Order HTN Planning","year":2025,"downloads":4}