Research Project: HTN Planning with Time

Project still available?

The project is not yet taken by another student.

It might however be that I don't have capacities left in general. Please check out the main page on research projects to see whether I'm maxed out. (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 instantanous state changes. In many (if not most) real-world scenarious, time is however an integral part of the domain/problem description. This means that actions are not instantanous, 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).

Further Reading

This project is on HTN planning. If you are not familiar with this planning paradigm yet, here are a few notes to get started:

  • HTN 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 quite similar to formal grammars, where an initial non-terminal symbol 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.
  • You find further reading recommendations on my page with resources for students. But please don't invest more than a few minute (if any) before your application, since I don't want you to waste any time before I formally agree to supervise your project.

Specifically for this project the following papers are recommended:

  • For the computational complexity of hierarchical planning:
    • "Tight Bounds for HTN Planning", ICAPS 2015
    • "Tight Bounds for Hybrid Planning", IJCAI 2022
  • For temporal classical (i.e., non-hierarchical) planning"
    • "PDDL2.1 : An Extension to PDDL for Expressing Temporal Planning Domains", JAIR 2003
  • For temporal HTN planning:
    • "Temporal Hierarchical Task Network Planning with Nested Multi-Vehicle Routing Problems -- A Challenge to be Resolved", HPlan 2021. This gives an overview of (hopefully) most of the important works in temporal HTN planning, so please check that out too.
    • "The ANML language", KEPS 2008
    • "Delete-Free Reachability Analysis for Temporal and Hierarchical Planning", ECAI 2016
    • "A Flexible ANML Actor and Planner in Robotics", PlanRob 2014
    • "Planning and Acting with Temporal and Hierarchical Decomposition Models", ICTAI 2014