@inproceedings{99c71ddf5af445c1b735dab22c0faef4,
title = "Symmetries and Other Variations of “End-Recursive” HTN Problems: Mapping the Border Between Decidable and Undecidable Restrictions",
abstract = "In this paper, we investigate the complexity of determining if various restricted forms of hierarchical task network (HTN) planning have a plan. We perform a systematic analysis of new restrictions formed by applying symmetries and relaxations to two existing restrictions called regularity and tailrecursiveness. By doing so, we confirm that many variations on common restrictions do not affect the complexity of the plan existence problem. However, we also obtain the counterintuitive result that combining some of these seemingly inert relaxations together renders the plan existence problem undecidable. Additionally, we unearth a critical difference in definitions between an early paper on HTN planning and modern formalisms that appears to have gone unnoticed.",
author = "Hadyn Tang and Pascal Bercher",
note = "Publisher Copyright: {\textcopyright} 2026, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.; 40th AAAI Conference on Artificial Intelligence, AAAI 2026 ; Conference date: 20-01-2026 Through 27-01-2026",
year = "2026",
month = mar,
day = "14",
doi = "10.1609/aaai.v40i43.40962",
language = "English",
isbn = "9781577359067",
volume = "40",
series = "Proceedings of the AAAI Conference on Artificial Intelligence",
publisher = "AAAI Press",
number = "43",
pages = "36412--36420",
editor = "Sven Koenig and Chad Jenkins and Taylor, \{Matthew E.\}",
booktitle = "Proceedings of the AAAI Conference on Artificial Intelligence",
edition = "43",
}