Theory: Partial Order Planning Complexities

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

Requirements

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

TLDR:

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.

Research Project: Partial Order Planning Complexities

Project still available?

Requirements

Project Description

Further Reading