Research Project: Analyzing A* in HTN PlanningSearch

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 (but only over two semesters!) or as 24 pt Honours project.
  • You don't need background on AI planning as learning that in the first two weeks should be easy.
  • You must have completed the AI course, so that you have basics in heuristic search. That is, concepts like admissibility should not be new to you.
  • In this project you will have to prove theoretical properties of heuristics, so it is primarily a theoeretical work. Since this work has the potential to get published at a top-tier conference (and since it might turn out to be challenging), I will only accept students with 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 analyze existing HTN heuristics on admissibility and consistency and furthermore whether they could, depending on the planning domain, return zero estimates for non-solution search nodes (i.e., estimating the true goal distance to zero, correctly or by underestimating). The second task is to investigate how to deal with such cases with the goal to still be able to find solutions without being stuck in plateaus.

The slightly longer version:

This work is about analyzing A in HTN planning in the presence of search nodes that get estimated with zero heuristics. More specifically, existing heuristics in Hierarchical Task Network (HTN) planning are to be analyzed for admissibility and consistency. It should further be analyzed under which circumstances (if any) these heuristics may return zero for non-goal search nodes and to analyze the impact of such situations on completeness when using A search. In classical (i.e., non-hierarchical) planning, there exist techniques on how to deal with such situations during search, which may naturally arise with zero-cost actions. It is to be checked whether these techniques can be transferred to the non-hierarchical setting.

Your task is:

  • Analyze all existing HTN heuristics whether they are admissible or consistent.
  • Analyze the impact of zero cost actions on completeness of A* search.
  • 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.

Specifically for this project the following papers of mine are recommended:

  • "Delete- and Ordering-Relaxation Heuristics for HTN Planning", IJCAI 2020
  • "Landmark Generation in HTN Planning", AAAI 2021
  • "An Admissible HTN Planning Heuristic", IJCAI 2017
  • "A Generic Method to Guide HTN Progression Search with Classical Heuristics", ICAPS 2018
  • "HTN Planning as Heuristic Progression Search ", JAIR 2020