The project is currently taken by another student. If a follow-up will be possible in the future I will update this here. (No point in contacting me about this project I guess.)
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.)
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:
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:
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:
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. :)