Research Project: A Systematic View on Complexity Results for HTN Planning

Project still available?

The project is not yet taken by another student.

It might however be that I don't have capacities left in general. Please check out the main page on research projects to see whether I'm maxed out. (I don't post this here so that I don't have to update all my project descriptions in case I don't accept more students.)


  • This project can only be carried out as 24 pt Honours project.
  • You don't need background on AI planning as learning that in the first two weeks should be easy.
  • You must have some background on Complexity Theory. Specifically, you must be able to understand NP membership and hardness reductions.
  • If you don't have problems understanding hardness reductions between problems (e.g., for NP hardness proofs), then this project shouldn't be overly hard to do. Yet, since I plan to publish this at an international top-tier (i.e., A*) venue (conference paper, journal, or both -- depending on the number of results achieved), you should have very clear HD marks throughout. Please take a look at any of my other projects should your marks not be strong enough.

Project Description


In a very nutshell, your task is to take all existing complexity results and find new ones by systematically investigating the required properties. For example, by exploiting symmetries, most results can simply be doubled, but many additional results should follow easily as well.

The slightly longer version:

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 project, we will first take a systematic look at those existing results to identify further restrictions that could be posed. The overall goal would be to have a systematic categorization of restrictions that can be posed, so that existing restrictions follow as special cases. The second main step is to prove the complexities of as many open cases as possible, whereas many should be able to be shown by exploiting symmetries. For example, regular HTN problems are knows to be PSPACE-complete. These problems have at most one compound task in each decomposition method, and if present, it has to be the very last one. This corresponds to right-regular formal languages. Clearly, we obtain the very same result for left-regular problems (where a compound task, if one exists, has to be the very first) -- yet, this isn't published yet.

Your task is:

  • Understand all existing complexity results for HTN planning.
  • Propose a systematic set of restrictions that can be posed on HTN planning problems so that those restrictions used for the existing results follow as special case.
  • Conduct a comprehensive complexity analysis to prove as many open results as possible.
  • Report on the findings (using my LaTeX template for research projects).
  • Assist me in putting together a scientific paper (or multiple ones, based on the number of achieved results) at an A* conference, journal, or both (most likely after the project).

Further Reading

This project is on HTN planning. If you are not familiar with this planning paradigm yet, here are a few notes to get started:

  • HTN 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 quite similar to formal grammars, where an initial non-terminal symbol 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.
  • You find further reading recommendations on my page with resources for students. But please don't invest more than a few minute (if any) before your application, since I don't want you to waste any time before I formally agree to supervise your project.

Specifically for this project the following papers of mine are recommended:

  • "Tight Bounds for HTN Planning", ICAPS 2015
  • "Tight Bounds for HTN Planning with Task Insertion", IJCAI 2015
  • "Tight Bounds for Hybrid Planning", IJCAI 2022
  • "Language Classification of Hierarchical Planning Problems", ECAI 2014
  • "Assessing the Expressivity of Planning Formalisms through the Comparison to Formal Languages", ICAPS 2016