Theory: HTN Plan Existence Complexities

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

Project still available?

To check whether I still supervise research projects, please check out my main page on research projects.

(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.)

Requirements

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

TLDR:

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).

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

Project still available?

Requirements

Project Description

Further Reading