Language Classification of Hierarchical Planning Problems. Höller, D., Behnke, G., Bercher, P., & Biundo, S. In Proceedings of the 21st European Conference on Artificial Intelligence (ECAI 2014), pages 447–452, 2014. IOS Press.
Language Classification of Hierarchical Planning Problems [pdf]Paper  doi  abstract   bibtex   
Theoretical results on HTN planning are mostly related to the plan existence problem. In this paper, we study the structure of the generated plans in terms of the language they produce. We show that such languages are always context-sensitive. Furthermore we identify certain subclasses of HTN planning problems which generate either regular or context-free languages. Most importantly we have discovered that HTN planning problems, where preconditions and effects are omitted, constitute a new class of languages that lies strictly between the context-free and context-sensitive languages.

Downloads: 0