Language Classification of Hierarchical Planning Problems

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.

Paper doi abstract bibtex 3 downloads

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.

@InProceedings{Hoeller2014HTNLanguage,
  Title     = {Language Classification of Hierarchical Planning Problems},
  Author    = {Daniel H{\"o}ller and Gregor Behnke and Pascal Bercher and Susanne Biundo},
  Booktitle = {Proceedings of the 21st European Conference on Artificial Intelligence ({ECAI} 2014)},
  Year      = {2014},
  pages     = {447--452},
  publisher = {{IOS} Press},
  doi       = {10.3233/978-1-61499-419-0-447},
  abstract  = {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.},
  url_Paper = {https://bercher.net/publications/2014/Hoeller2014HTNLanguages.pdf}
}

Downloads: 3