Research Project: TIHTN Planning Algorithm

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.
  • Some background in complexity theory would be helpful, but is not strictly required.
  • You should be proficient in coding C++, as we will have to extend an existing planner written in that language.
  • 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 extend an existing HTN planning system (called PANDA) to being able to do "task insertion". The respective problem is called TIHTN Planning: HTN Planning with task insertion. Here, we still need to decompose all initially given compound tasks into primitive ones, but on top of that we are always allowed to insert additional actions into plans.

The slightly longer version:

In HTN planning, all initially given compound tasks have to be turned into primitive action plans by adhering the task hierarchy. The process is completely identical to turning the start symbol of a formal grammar into a word (a sequence of terminal symbols). The sole difference is that in planning, terminal symbols (actions) have preconditions and effects, so not all action sequences are executable. The idea in TIHTN planning is to allow arbitrary task insertion, which means that we still need to follow the production rules of the grammar, but on top of that we can insert actions into plans, thus allowing for further plans to become executable. Currently, no such planners exist.

There are several possibilities on how this task can be achieved (at least three). All these should be implemented. One of them (the others are conveyed personally) is to extend the currently best-performing planner and its heuristics to deal with this more flexible (but computationally less expressive) problem class. (An extension of this problem class is to allow for only some tasks to be inserted, but not all; which ones should be specified in the problem description.)

Your task is:

  • Understand the difference of HTN and TIHTN planning problems.
  • Implement three different ways how such problems could be solved.
  • 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 with task insertion. If you are not familiar with the HTN planning paradigm yet, here are a few notes on how 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 formal problem definition of TIHTN planning:
    • On the Decidability of HTN Planning with Task Insertion, IJCAI 2011 (note that the problem, only in that single paper, was still called "hybrid problem").
    • "Tight Bounds for HTN with Task Insertion Planning", ICAPS 2015
  • For the PANDA planner that's going to be extended:
    • A Generic Method to Guide HTN Progression Search with Classical Heuristics, ICAPS 2018
    • HTN Planning as Heuristic Progression Search, JAIR 2020
    • On Succinct Groundings of HTN Planning Problems, AAAI 2020