The Complexity of Flexible FOND HTN Planning. Chen, D. & Bercher, P. In Proceedings of the 4th ICAPS Workshop on Hierarchical Planning (HPlan 2021), pages 62–70, 2021.
The Complexity of Flexible FOND HTN Planning [pdf]Paper  abstract   bibtex   1 download  
Hierarchical Task Network (HTN) planning is an expressive planning formalism that has often been advocated as a first choice to address real-world problems. Yet only a few extensions exist that can deal with the many challenges encountered in the real world. One of them is the capability to express uncertainty. Recently, a new HTN formalism for Fully Observable Nondeterministic (FOND) problems was proposed and studied theoretically. In this paper, we lay out limitations of that formalism and propose an alternative definition, which addresses and resolves such` limitations. We conduct a complexity study of an alternative, more flexible formalism and provide tight complexity bounds for most of the investigated special cases of the problem.

Downloads: 1