Research Project: A Portfolio Planner for HTN Planning

Project still available?

This project is already taken for 2023.

Requirements

  • This project can be carried out as 12 pt project (but only over two semesters!) or as a 24 pt Honours project. The latter is preferred, but both is possible.
  • 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 Machine Learning.
  • The project is rather challenging and it's my aim to publish it at an international top-tier (i.e., A*) conference, so 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 classifier that's used to decide, given an Hierarchical Task Network (HTN) planning problem, which HTN planning system to solve a given problem to get it solved as quickly as possible. (I.e., pick the best planner.)

The slightly longer version:

There exist multiple HTN planning systems, but they all have different strengths, meaning that no single planner is better than all others in all domains. In an ideal world, we would know prior to solving a problem which planner is going to perform best so that this planner could be chosen. Clearly, such an oracle does not exist, but using Machine Learning we can predict from the past. That is, one can measure the performance of existing planners on existing benchmarks and use this to train a classifier for novel problems. The training is done based on a set of features extracted from the problems. Given a new problem to solve, the system extract the features so that it can decide, based on the previous training, which planner to use to solve the problem. Such a system is called Portfolio Planner.

Your task is:

  • Conduct a comprehensive literature research on portfolio planners in classical (i.e., non-hierarchical) planning
  • Implement the feature extraction in the Panda-Pi planner.
  • Conduct the training and thereby construct a complete portfolio planner. The portfolio planner should be usable in the sense that there is a single script that needs to be called, it then performs the feature extraction and runs the respective planner.
  • Report on the findings (using my LaTeX template for research projects).
  • Assist me in putting together a scientific paper at an A* conference (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.

I can provide you with further literature recommendations, in particular on classical portfolio planners, once we started doing the project.