Reversibility and Reachability in HTN Planning: Formalization and Computational Complexities in the Totally-Ordered Setting
Proceedings of the International Conference on Automated Planning and Scheduling · 08.06.2026 · 36 (1) · 181-190
DOI: 10.1609/icaps.v36i1.42827 ↗Kurz gefasst
Fachartikel in der Zeitschrift Proceedings of the International Conference on Automated Planning and Scheduling, online erschienen am 08.06.2026. Verfasst von Jakub Med und 3 weiteren Autor:innen.
Abstract (Originalsprache)
Action reversibility, that is, whether it is possible to undo effects of an action by other actions, has been studied in classical planning and, recently, in non-deterministic planning. In this paper, we formalize the notions of method and primitive task reversibility in the context of hierarchical task network (HTN) planning and provide complexity results. On top of that, we introduce various notions of reachability in the HTN setting, for which the reachability is still an unexplored area (in contrast to classical planning, in which reachability is well studied) We divide the reachability into two classes based on two perspectives, one restricting the allowed progression rules (i.e., reachability using executions of primitive tasks, or reachability using decompositions of compound tasks), and the other focusing on the desired target (i.e., a state, independently on a task network; a task network, independently of a state; or both at once). We show that the complexity of these problems varies significantly, ranging from EXPTIME-complete to constant-time. We also show that the introduced reversibility problems exhibit theoretical properties and complexity results analogous to the broader reachability classes.
Zitieren
APA
Med, J., Yousefi, M., Chrpa, L., & Bercher, P. (2026). Reversibility and Reachability in HTN Planning: Formalization and Computational Complexities in the Totally-Ordered Setting. Proceedings of the International Conference on Automated Planning and Scheduling, 36(1), 181-190. https://doi.org/10.1609/icaps.v36i1.42827
Vancouver
Med J, Yousefi M, Chrpa L, Bercher P. Reversibility and Reachability in HTN Planning: Formalization and Computational Complexities in the Totally-Ordered Setting. Proceedings of the International Conference on Automated Planning and Scheduling. 2026;36(1):181-190. doi:10.1609/icaps.v36i1.42827
BibTeX
@article{Med2026,
author = {Med, Jakub and Yousefi, Mohammad and Chrpa, Lukáš and Bercher, Pascal},
title = {Reversibility and Reachability in HTN Planning: Formalization and Computational Complexities in the Totally-Ordered Setting},
journal = {Proceedings of the International Conference on Automated Planning and Scheduling},
year = {2026},
volume = {36},
number = {1},
pages = {181--190},
doi = {10.1609/icaps.v36i1.42827}
}
EUVIMED