Research Project: Let Grounding Do the Heavy Lifting: Lifted Heuristics by Task Compilation

Project still available?

To check whether I still supervise research projects, please check out my main page on research projects.

(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.
  • Knowledge of classical planning and related algorithms, such as heuristic search, or familiarity with logic programming paradigms like Datalog, is an advantage but not required. These concepts can be learned while pursuing the project (or ideally shortly earlier).
  • A foundational understanding of Complexity Theory or Algorithms and Data Structures is required. The main focus is on implementation, though certain guarantees (correctness & runtime) for the underlying algorithm need to be proven. A good understanding of theory will help improve the idea and is important for achieving top marks. (If you are familiar with competitive programming, our setup is similar: you will develop a theoretical idea that you know works and then evaluate it in practice by implementing it.)
  • Some familiarity with programming in Python and C++ is expected, as the existing code base uses both languages.
  • Clear HD marks in relevant courses are expected for successful candidates, as the aim is to publish results at a top-tier (A*) venue. If your marks do not meet this criterion, please consider alternative projects.

Project Description

TLDR: The schematic input provided to planners is called lifted. It typically gets grounded to a non-schematic representation. This is not always possible. In this case, we want to search on the lifted model and use a heuristic to guide the search. You should use an existing planning task transformation that enables grounding under delete relaxation. This approach allows the use of grounded heuristics (for the relaxed task) in a lifted planning setting.

The slightly longer version: Lifted planning tasks are represented at a higher, schematic level using first-order logic, as opposed to the grounded, propositional form typically used in most planning approaches. The lifted representation avoids the exponential cost of grounding, which involves deriving all possible specific versions of a schema. However, it introduces challenges in re-using ideas of heuristics designed for grounded representations. One of the main objectives surrounding planning on lifted representations is to adapt grounded heuristics to the lifted setting while maintaining computational efficiency.

You will extend current lifted heuristics by using an existing method that relaxes the planning task. Relaxing the task means allowing more possible solutions (i.e., including those that would not solve the original, unrelaxed problem), which can still be useful for heuristic guidance. The particular relaxation we are interested in delete relaxes the task and transforms it into a Datalog program (which is a subset of lifted planning tasks). The key property of this specific relaxation is that it enables more efficient grounding. By grounding the relaxed task, we can compute grounded heuristics on the relaxed task and use it in a lifted search for the original task.

The preliminaries you need to understand are:

  • What is heuristic search?
  • What lifted vs. grounded planning models are.
  • How to ground a planning task using Datalog.
  • What is Delete Relaxation, and why it makes grounding more efficient.

This may seem like a lot, but all these concepts are foundational and should be easy to grasp. They are also all related to each other, which makes learning them slightly easier.

Your task is:

  • Read up the related work to understand the preliminaries.
  • Implement a pipeline for computing heuristics on the grounded tasks after applying a transformation to a Datalog task.
  • Evaluate the performance of the created heuristics on standard benchmarks.
  • Potentially: Propose improvements by partially integrating delete effects into the task transformation. Or, investigate how admissibility in the grounded planning task translates to the lifted one.
  • Report findings using the LaTeX template for research projects.
  • Potentially: Assist me in putting together a scientific paper at an A* conference.

For the required tasks, most of it is already well-documented in both theory and practice. Your task is to connect the existing pieces. For a great thesis, the next step will involve refining the existing Datalog construction. (Indicated by the first potential step.) I can provide ideas and already have a list of potential improvements.

Further Reading

For your thesis, it is needed to explain the context of your topic and build a solid background. I will start by listing the necessities you need to understand. After it there follows a long list of literature that you could use to further expand your background on the topic (Including all citations I mention in the following.)

For the main approach, you only need to focus on understanding these two key points:

  1. Planning Task Encoding and Grounding: Understand how a planning task is encoded into Datalog and grounded, as detailed by Helmert (2009). This forms the basis for connecting lifted and grounded representations.

  2. Task Transformation Improvement: Study the refinement introduced by Corrêa et al. (2021), which improves the encoding by allowing action schemas being split into smallter ones to result in less groundings.

Putting both together completes the task transformation you will use in your work. Additionally, understand why a Datalog encoding is a planning task and explain why and when this approach is beneficial. (But both should be rather easy observations.)

This project is on classical planning. If you are not familiar with this planning paradigm yet, here are a few notes to get started:

  • Classical planning is a sequential problem-solving formalism. It involves a set of actions that need to be performed in order to transition from an initial state to a desired goal state. Each action has specific preconditions that must be satisfied before it can be executed, and effects that change the state after execution.
  • You find further reading recommendations on basic classical planning on my page with resources for students. But please don't invest more than a handful of minutes (if any) before your application, since I don't want you to waste any time before I formally agree to supervise your project.

Below is a list of related literature to help situate the general context of your topic. It is by far not necessary to read all of it. But there are some talks and slides listed that should be comparably easy to take a look at. The short list of necessities you need to understand is listed after this literature list.

  • This paper introduced the grounding method, and many of its ideas are still used today, sometimes in improved versions: M. Helmert Concise finite-domain representations for PDDL planning tasks Artificial Intelligence, 2009 (PDF)
  • This thesis introduced an effective lifted search and provides a clear overview of the general motivation behind lifted planning: A. B. Corrêa Planning using Lifted Task Representations Master's thesis, University of Basel, 2019. (PDF,slides)
  • The corresponding paper to the mentioned thesis covers the same topic, but I believe the thesis is much easier for students to understand. However, the talk might also be helpful: A. B. Corrêa, F. Pommerening, M. Helmert and G. Francès Lifted Successor Generation using Query Optimization Techniques International Conference on Automated Planning and Scheduling (ICAPS), 2020. (PDF,slides,talk,poster)
  • This paper provides a clear intuition of the challenging differences between lifted and grounded heuristics: P. Lauer, A. Torralba, D. Fišer, D. Höller, J. Wichlacz, and J. Hoffmann
    Polynomial-Time in PDDL Input Size: Making the Delete Relaxation Feasible for Lifted Planning,
    International Joint Conference on Artificial Intelligence (IJCAI), 2021. (PDF, talk)
  • This paper modifies the Datalog encoding used for grounding to compute a lifted version of the hAdd heuristic: A. B. Corrêa, G. Francès, F. Pommerening and M. Helmert Delete-Relaxation Heuristics for Lifted Classical Planning International Conference on Automated Planning and Scheduling (ICAPS), 2021. (PDF,slides,recording,poster)
  • This paper uses an encoding similar to the one for the hAdd heuristic to enhance the grounding process: A. B. Corrêa, M. Hecher, M. Helmert, D. M. Longo, F. Pommerening and S. Woltran Grounding Planning Tasks Using Tree Decompositions and Iterated Solving International Conference on Automated Planning and Scheduling (ICAPS), 2023. (PDF,slides,poster)
  • All of the Datalog/task transformation methods can be viewed as breaking one action into smaller ones, a process known as action schema splitting. The following paper provides an automated way to achieve this. While the automation itself may not be necessary for your work, the theory behind it offers a clear introduction to action schema splitting and will help you understand how it connects to your topic: C. Areces, F. Bustos, M. Dominguez, and J. Hoffmann Optimizing Planning Domains by Automatic Action Schema Splitting International Conference on Automated Planning and Scheduling (ICAPS), 2014. (PDF)