Research Project: Special-Case Heuristics for HTN Planning Problems

Project still available?

Somebody is currently working on that project. Unless you have straight (upper!) HD marks, this project is taken. Otherwise I might consider creating a similar project with related, but not identical ideas.

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.
  • It is required that you have at least some basic knowledge about complexity theory (classes P, NP, and how reductions are done).
  • 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 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 this project you will develop specialized heuristics for HTN planning that will be highly efficient for the class that they are designed for, but they will fall in all others.

The slightly longer version:

Heuristic search is one of the most successful approaches to solving planning problems. This is the case both in classical (non-hierarchical) planning, as well as in hierarchical task network (HTN) planning. At the moment, the number of available heuristics in HTN planning is rather limited. Those that exist are all tailored for the general case, i.e., partially ordered HTN problems without any further assumptions. During search, many search nodes do however show specific properties, for example being acyclic or totally ordered. This project aims at the development of specialized heuristics that exploit these special cases. Some are based on complexity results from the literature, others by refining existing heuristics to make them specific for the investigated class.

Your task is:

  • Understand existing HTN planning heuristics as well as some of the most relevant complexity results.
  • Develop a range of HTN heuristics that exploit certain special cases.
  • Conduct an empirical evaluation on a large set of benchmark problems.
  • Report on the findings (using my LaTeX template for research projects).
  • Assist in putting together a scientific paper for an A* conference paper.

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.