BA/MA Thesis: A systematic view on Complexity Results for Hierarchical Planning


Hierarchical Planning is a planning formalism that's concerned with the step-wise refinement of abstract tasks until a primitive plan is found -- so hierarchical planning is completely similar formal grammars, where an initial non-terminal is refined into a sequence of terminal symbols. The main differences are that (a) primitive tasks (corresponding to terminal symbols) have preconditions and effects, to not every plan is executable and (b) the means to refine compound tasks (which correspond to production rules from formal grammars) are only partially ordered rather than totally as in formal grammars.

There already exists a variety of complexity results for the plan existence problem in hierarchical planning answering the question about the computational hardness for deciding whether a given planning problem does possess a solution. The computational hardness of this problem ranges from P (polynomial time) up to undecidable depending on various restrictions.

In this thesis, we will first take a systematic look at those existing results to identify further restrictions that could be posed. The second main step is to identify a set of interesting missing results and prove their complexities, possibly by exploiting existing results.


  • Categorize existing complexity results wrt problem properties that need to be formalized
  • Prove the computational complexity of the plan existence problem for some interesting novel problem classes


  • A solid understanding of formal grammars and the basics of computational complexity (e.g., the classes P, NP, NP-complete, etc.)
  • Having fun in formalizing!
  • Knowledge in Classical Planning in particular or Articial Intelligence in general is helpful, but not required

Background Literature

  • Thomas Geier, Pascal Bercher: On the Decidability of HTN Planning with Task Insertion. IJCAI 2011, p.1955-1961. AAAI Press.
  • Ron Alford, Pascal Bercher, David W. Aha: Tight Bounds for HTN Planning. ICAPS 2015: p.7-15. AAAI Press
  • Ron Alford, Pascal Bercher, David W. Aha: Tight Bounds for HTN Planning with Task Insertion. IJCAI 2015. p.1502-1508. AAAI Press
  • Pascal Bercher, Ron Alford, Daniel Höller: A Survey on Hierarchical Planning – One Abstract Idea, Many Concrete Realizations. IJCAI 2019, p.6267-6275.

For more literature visit my webpage:


  • You will pursue state-of-the-art research in Artificial Intelligence Planning
  • The work, if successful, is (hopefully) going to be published in an A* venue


  • Complexity Theory
  • Theoretical Computer Science
  • Artificial Intelligence
  • Automated Planning

Updated:  1 June 2019/Responsible Officer:  Dean, CECS/Page Contact:  CECS Marketing