Research Project: HTN Heuristic based on Integer Linear Programming (ILP)

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 12 pt project.
  • You will have to have background on AI planning as well as on SAT (Satisfiability, i.e., Logic) or CSP (Constraint Satisfaction Problem) solving.
  • This project is particularly challenging since it encodes Planning problems as ILPs (Integer Linear Programs). I also plan 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 this project you will encode a delete-relaxed totally ordered HTN planning problem as an ILP and develop techniques to make the encoding more efficient, e.g., by incorporating information obtained from previous search nodes (each search node is a new delete-relaxed totally ordered HTN planning problem).

The slightly longer version:

In this work, we deal with solving totally ordered HTN planning problems via heuristic search. Thus, during search, we compute a heuristic value for each search node, which normally resembles the number of missing actions that still need to be inserted into a plan to turn it into a solution. There are only a few heuristics available in the context of HTN planning, one of them being based on first relaxing the problem by ignoring all ordering constraints and second by ignoring all delete effects of actions. With these relaxations, the problem is encoded as an Integer Linear Program (ILP). The resulting heuristic was published at IJCAI 2020, title see below.

When we assume a totally ordered HTN setting, we can exploit more information compared to the previous work where the heuristic relaxed (i.e., ignored) information on ordering. The idea is to consider the current (totally ordered) task network t1, t2, ..., tn and keep this ordering, but still relax all ordering constraints of all subtasks of t1, t2, and so on. That way, each problem induced by the individual top-level tasks is still ordering-relaxed, while the respective subtasks are still kept separate. E.g., subtasks of tn cannot be used to enable the execution of t2. This can thus lead to much more informed heuristics as more infeasible solutions can be ruled out that way.

The project will be co-supervised by Conny Olz from Ulm University, Germany -- one of my PhD students.

Your task is:

  • Comprehend an existing implementation of the ILP encoding for totally ordered, delete-relaxed HTN problems. This encoding already extends the one described in the base paper and was created as preparation work by the supervisors of this project.
  • Develop ideas and implement them to make the ILP solver solve these problems more efficiently as of now.
  • Conduct an empirical evaluation on a large set of benchmark problems.
  • Report on the findings (using my LaTeX template for research projects).
  • Assist your supervisors in putting together a scientific paper for an A* conference paper.

Further Reading

This project is both on HTN planning, and on ILPs. 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.
  • For ILPs, I don't have concrete recommendations as of now, but there should be tons of tutorials, as it's a highly-used standard technique for modeling and solving combinatorial problems.

Literature-wise, please follow the ones outlined on the page linked above. On top, you will have to read the following paper as our work is a direct extension of its approach as well as its actual code base:

  • Delete- and Ordering-Relaxation Heuristics for HTN Planning. By Daniel Höller, Pascal Bercher, and Gregor Behnke. You find it on my webpage (publications).

According to the project description above, it will not be clear to you yet why the following literature is relevant, but you may read it anyway. :)

  • Revealing Hidden Preconditions and Effects of Compound HTN Planning Tasks – A Complexity Analysis. Conny Olz, Susanne Biundo, and Pascal Bercher.