Research Project: Partial Order Planning Complexities

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.)


  • This project can be carried out as 12 pt project (but only over two semesters!). Potentially it could also be carried out as a 24 pt Honours project, but the first is preferred.
  • 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 Complexity Theory. Specifically, you must be able to understand NP membership and hardness reductions.
  • If you don't have problems understanding hardness reductions between problems (e.g., for NP hardness proofs), then this project shouldn't be overly hard to do. Yet, since I plan to publish this at an international top-tier (i.e., A*) journal (specifically as a technical note at JAIR), 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


In a very nutshell, your task is to "translate" a scientific paper with complexity results from one formalism into another. I.e., results have been described for a specific formalism, which is equivalent to another more modern (and easier/more intuitive) one, so it should be re-written by relying on the other formalism. A few new results should be added on top.

The slightly longer version:

The project is concerned with reasoning about partially ordered, non-hierarchical plans. Such partially ordered sets of actions compactly represent an up to exponential number of totally ordered action sequences. Yet, not every such sequence might be executable. It is therefore natural to ask whether some state property is satisfied at a given position in the plan (i.e., before or after the execution of a certain action). This can be asked for potential and guaranteed truth, i.e., whether a property is guaranteed to hold for all possible linearizations or whether there exists at least one for which it holds.

There's a paper that investigates the computational complexity of this reasoning task for various special cases of such plans. (These special cases restrict the way in which preconditions and effects of actions can interact.) The investigated questions are called plan validity investigations, and they have been done for a formalism from the 90s, called Event Systems. These systems, while syntactically very complicated, are semantically equivalent to standard STRIPS plans known from classical planning. Since Event Systems are not in use anymore today, these results are a bit "hidden" from today's research community. The main task is therefore for translate the existing proofs relying on Event Systems to classical planning STRIPS plans or Partial Order Causal Link (POCL) plans.

Your task is:

  • Understand the entire paper (i.e., all proofs) from the respective paper.
  • Re-write the paper, but based on the novel formalism for STRIPS and/or POCL plans (this has to be done using my LaTeX template for research projects).
  • Check whether further results can be achieved, in particular by studying the difference between standard plans and POCL plans.
  • Assist me in putting together a scientific paper for the A* journal JAIR.

Further Reading

This project is on reasoning about partially ordered plans. The base problem class is classical planning. If you are not familiar with this planning paradigm yet, here are a few notes to get started:

  • 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.
  • You should read the following papers of mine:
    • "POP ≡ POCL, right? Complexity Results for Partial Order (Causal Link) Makespan Minimization", AAAI 2020
    • "A Closer Look at Causal Links: Complexity Results for Delete-Relaxation in Partial Order Causal Link (POCL) Planning", ICAPS 2021
  • The paper that is to be "translated" is "The Complexity of Partial-Order Plan Viability Problems", ICAPS 2014
  • The paper "Ignoring Delete Lists” Works: Local Search Topology in Planning Benchmarks", JAIR 2005, should be checked as well as it could extend the results of the ICAPS 14 paper. More specifically, it could show cases where not ignoring certain delete effects might not increase computational complexity.
  • "The Complexity of Planning Problems With Simple Causal Graphs", JAIR 2008, should also be checked.