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

Description

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.

Please note that I have several topics on complexity results (for Hierarchical Planning, non-hierarchical planning, but even other formalisms) available, this is just the only one I've put online. So if you are interested into theoretical investigations, please contact me even if this particular topic does not seem interesting to you.

Goals

  • 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

Requirements

  • 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
  • For this very project (for other projects it's definitely different) I will only accept students who have clearly straight HD grades, in particular in all theory-related courses.
  • I also accept Mathematicians, as long as you have a solid understanding of related content, such as graph theory.

Please send me:

  • The course code.
  • The URL of your course.
  • The number of points your course has (i.e., 6, 12, 24, or 24 honours final project).
  • When you would like to do your project.

Background Literature

For more literature visit my webpage: https://cecs.anu.edu.au/people/pascal-bercher

Gain

  • 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
  • If successful, we can easily extend this to a PhD project

Keywords

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

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