BA/MA research project: A systematic view on Complexity Results for Hierarchical 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.

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.

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