Language Classification of Hierarchical Planning Problems
Höller Daniel, Gregor Behnke, Pascal Bercher, Susanne Biundo · Frontiers in artificial intelligence and applications · 2014
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.