Project Overview#

HTN Planning is a powerful formalism to express control rules on how plans may be generated. Here, action sequences are generated from an initially given abstract task, which is step-wise refined until an executable primitive action sequence is obtained (similar to formal grammars/languages).

In this project, a standard formalism for HTN planning should be extended so that its actions (and possibly also its abstract tasks) can express time, i.e., action duration. Once this is achieved, the problems expressible in the resulting formalism should be analyzed for its computational complexity.


  • Enjoy reading scientific papers as well as formalizing problems.
  • Strong foundations in complexity theory are required (i.e., high marks in related courses).
  • Able to conduct reductions, e.g., to prove NP membership as well as hardness.
  • A solid understanding of AI planning before starting the project would be highly beneficial.


bars search times arrow-up