Theory: HTN Planning with Time

Research Project: HTN Planning with Time

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 should not have any problems with understanding membership and hardness proofs and feel confident to do your own proofs.
You also should not be afraid of reading (and understanding, of course!) several papers, as literature research will be an important part of this project.
Since this project is rather challenging, and since I aim at publishing this work at an international top-tier (i.e., A*) venue (conference paper or journal, 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 create a novel formalism for HTN planning with time and study the resulting formalism, notably its computational complexity of deciding whether there's a solution. Positioning (e.g., 'defending', in a sense) the resulting formalism compared to other HTN formalisms with time is another important requirement.

The slightly longer version:

AI planning problems do, in their most basic form, not feature time. In such settings actions perform instantaneous state changes. In many (if not most) real-world scenarios, time is however an integral part of the domain/problem description. This means that actions are not instantaneous, but instead take some time to finish. This also means that action preconditions may be temporal in the sense that they may have to hold at certain times during action execution. Likewise, effects may not all happen exactly at the end of action execution, but at different times during its execution, or even continuously like for example the consumption of fuel during a drive action.

Planning formalisms supporting time do exist, but accepted standards primarily exist in classical (i.e., non-hierarchical) planning. In Hierarchical Task Network (HTN), there's no single accepted formalism, only a few attempts exist in the literature -- but no formalism has been described on a truly formal level yet. The purpose of this work is therefore to define a unified formalism for HTN planning, based on work from the literature, both in temporal classical and temporal as well as non-temporal HTN planning. To "round up" the work, two additions are required: The modeling of at least one temporal planning domain, for which both temporal classical domains can be considered as a basis, as well as temporal hierarchical domains. Secondly, the computational complexity of such problems shall be studied under various restrictions as also done in non-temporal HTN planning.

Your task is:

Understand all existing temporal HTN planning formalism as well as the most important temporal classical formalism.
Propose a novel temporal HTN planning formalism based on this related work.
Model a temporal HTN domain.
Study the formalism formally by investigating its computational complexity and by comparing it formally to the related work.
Report on the findings (using my LaTeX template for research projects).
Assist me in putting together a scientific paper for an A* conference or journal (most likely after the project).

Research Project: HTN Planning with Time

Project still available?

Requirements

Project Description

Further Reading