My Research

I am mostly working in automated planning, a subdiscipline of Artificial Intelligence. On this part of my webpage, I first give some introduction to planning -- mostly for those who do not know the field at all yet, such as students interested in doing a project with me, or just random webpage visitors. :)

Thus, I might get a bit more technical in parts, which is however required to tell certain problem settings apart, and to get a deeper understanding of what I'm interested in. I also provide pointers to scientific papers, intended for student projects or even PhD applicants to ground everybody to the same minimal knowledge.

I will first explain "the base terminology" of planning, including different variants of "planning problems" that I'm working with (because there are many different ones, basically all different kinds of aspects of the world one could model or ignore such as time, observability, uncertainty, and much, much more). After that, I lay out my two main "research areas", i.e., main questions that I am interested in. They cover multiple problem classes, and so these two sections can be combined almost arbitrarily to their cross product: {problem classes} x {research questions}.

Introduction: What Is Automated Planning?

Automated planning is a core discipline of Artificial Intelligence that evolves around reasoning about actions. In its simplest form, an action can be thought of the very same it means in natural language: something you do, which changes the world. You can think of "the world" as a collection of all the facts currently true. For example, it's true that you are reading this page right now, that's "a fact", you might be bored in this moment (I hope not!), or slightly entertained (I give my best! :)), and so on. All these "facts" make up the current world state. And world states can be changed by performing actions, i.e., "doing something". Not every action can be taken all the time. For example, you reading this page has the prerequisite (we call it an action precondition) that you have this page displayed in front of you. You might have made that fact true by opening a browser on your computer and navigated to this page. This is what "planning" is about: We usually want to solve a planning problem, which consists of:

  • All the facts true in the initial state, the one we start planning from.
  • All actions that exist in our domain, i.e., the means to transition from some world state to another. Actions describe their preconditions: all facts that must be true for the action to be executable. They also describe their effects: how facts evolve, i.e., which facts get added to a state (become true) and which get deleted (become false).
  • Finally, the set of goal facts we care for, i.e., all world properties we'd like to achieve. (Being rich? Being healthy? Whatever fact is modeled can be demanded as desired.)

These are always the base-ingredients of planning problems, yet there are dozens to thousands or more (depending on how one counts) variants and questions one could be interested in. The most basic one is whether there is a solution, called a plan, which, in its most simple form, is a sequence of actions in which each action is executable in the state in which it is applied, and transforms the initial state into one in which all desired goals hold. Beyond how to find solutions, there is a vast amount of research. Thus, there are basically always two questions that have to be combined in order to form a research direction, namely what is the exact problem class, and which question are we interested in solving. We start with the first.

What is the exact problem class considered? For example:

  • Is there only one agent acting or multiple ones? If multiple ones, are they antagonistic or share one common goal? How is knowledge shared or communicated?
  • Is the world fully observable or is there partial information? Can it be observed somehow?
  • Is the world deterministic, non-deterministic/probabilistic? For example, throwing a die is non-deterministic: we know possible outcomes, but not which one will happen in advance. Whereas solutions to deterministic problems are called plans (and are simply action sequences), solutions to problems with uncertainty are usually called policies (and are mappings from state to action). That's because non-deterministic problems can, due to the influence of uncertainty during plan execution, not be a fixed action sequence anymore, but action selection depends on the current state.
  • Are world states discrete or continuous? Discrete world states are relatively simplistic, such as being collections of true facts. Continuous domains are more expressive and can model more realistic properties, such as energy or fuel levels, etc.
  • Is there time involved or are all actions instantaneous? Reasoning with time is more complex and leads to more complex solutions, since we'll need a schedule, specifying which action is scheduled when, rather than just providing a simple sequence of actions.
  • What is the goal we plan for? Do we care only for the final state produced (and plan achieving that is fine), or do we impose additional constraints on what is regarded a solution? For example, we could demand that every state traversed by a solution plan must satisfy some properties. In a robotics domain, we could for example require that a specific robot may never enter an area declared hazardous, although the available actions would in principle allow to do so.
  • There are many more "technical" differences in action representation that influence theory and algorithms, but these are too complex to get into here. But in a nutshell, there are multiple "language features" that can be used to express a desired action.

The most simplistic form -- single-agent, fully observable, deterministic, discrete states, no time, simple goals -- is referred to as classical planning and forms the basis of most of my research, although I also work on extensions thereof, such as hierarchical planning (which imposes additional constraints on desired solutions). If interested, I have a survey at IJCAI 2019 on different problem classes in hierarchical planning (see my conference publication list).

The following graphic illustrates a "transition system" on the top-right, i.e., a graphical illustration of all existing states and the actions that turn them into each other. Below, a sequence of actions (over two lines) is presented, where the lines and facts on the left are preconditions and those on the right are effects. The depicted sets are states. Plan illustration

Now, having fixed some of the countless many possible problem classes one might work with (note that any of the bullet points above can be combined with each other), there are also many possible research questions one might want to investigate. The most obvious one is solving these kinds of problems, i.e., finding a plan or policy to a given problem. Yet, this is only one of many, and even that one includes many subquestions. Below, I give just a collection of some of the questions one might be interested in:

  • How to design algorithms to solve planning problems quickly? Note that there are many completely different algorithms to do so, and each of the possible algorithms has multiple important subquestions to solve. For example,
    • One can translate a planning problem into a different kind of problem, solve that instead using existing solvers for this other problem class, and translate back the solution. This is called a "problem compilation". Here, important questions are which problem to translate it into, how to encode the problem, and which solver to pick.
    • If one solved the problem directly, the question is how to do that, especially how to guide the solution process through the search space to save computational resources. The most famous approach is heuristic search, where heuristics, which guide the search by estimating the distance between a current search node and a solution. Just heuristic design alone is one of the major research areas in automated planning: making them faster and more accurate.
  • How to design algorithms to verify solutions? If a planning system is correct, any plan/policy provided is naturally indeed a solution. Trust is good, but control is better. So, we need, for example in the context of planning competitions, or simply in safety-critical scenarios, methods that receive a planning problem and its potential solution as an input, and then answer whether it is indeed a solution, or not. If not, ideally, an explanation shall be provided that explains why it is not a solution.
  • How to optimize a given solution? It is well known that finding some solution is significantly easier/quicker than finding an optimal one. So, if optimality isn't essential, yet "better solutions" are still preferred, then the most effective approach is finding some solution first, and then optimize that plan. There is a vast range of research on how such plans can be improved. If interested, I have a survey on this topic at IJCAI 2024 (see my conference publication list).
  • So far, we were always assuming a problem has a solution. However, not every problem does. In case a problem does not, one important research question is how to prove this formally, and whether this can be convincingly "explained" in an intuitive way.
  • There are many questions around model engineering. Whereas those questions above that the required models "just exist", and the designed algorithms simply do their job with them, they do of course have to be created in the first place. This large research area is referred to as model engineering and covers many more concrete research questions. For example:
    • How can models be learned from scratch from different inputs? This input might be formal, such as plan traces, state traces, or any generalization thereof. If can also be less formal, such as videos or natural language descriptions, which might be assessed by large language models (LLMs).
    • How can existing models be verified for correctness (or other desired properties) and corrected automatically? If interested, I have a survey on this topic at IJCAI 2025 (see my conference publication list).
  • Expressivity analysis: As evident from the list of different problem classes, there is a vast range of different problems that can be expressed. Expressivity studies analyze formally which formalisms are more "powerful" than others through a very specific lense. The goal is to have a formal notion of which formalism will be able to express which problem, which increases our theoretical understanding, and also helps choosing the right formalism for a given problem to model.
  • Computational complexity analysis. Every formal problem can not just be solved in practice, but also analyzed theoretically for its computational hardness. Note that all questions can be analyzed computationally, such as plan existence, plan verification, plan optimization, model repair, and many more. These studies deploy techniques from Theoretical Computer Science (if interested: see my ANU course Theory of Computation) to analyze the worst-case requirements of computational resources a problem expressed in the current framework might take. This leads to membership in standard classes known to literature, such as a problem being NP-complete, PSPACE-complete, or anything below (easier), above (harder), or in between (harder than NP, but easier than PSPACE). Knowing this is not just important by itself as it makes us understand the problem better, but has concrete practical implications. This is because:
    • If a problem is in a certain class (like PSPACE), we know that a problem compilation to any of the other problems in the same class (i.e., any problem that is PSPACE-complete) must exist, and so one can start looking for some. Likewise, one knows that a compilation to a certain problem can not exist, which prevents one from wasting time. For example, if a problem is PSPACE-complete we know that we don't need to bother searching for a compilation to a problem that's NP-complete (technically, this might be possible, but if this succeeds, one instantly wins a Turing Award), unless one accepts an exponential increase in the problem size. So, in conclusion, it assists in identifying suitable compilations.
    • Knowing the computational complexity also helps in the design of specialized algorithms. For example, if a problem is NP-complete, one should not bother trying to design an algorithm that has a worst-case runtime of a polynomial (technically, this might again be possible, but if this succeeds, one instantly wins a Turing Award; and nobody believes it is). So, complexity bounds also loosely assist in designing algorithms.
  • Applications. Not explicitly a research question, but -- luckily -- still appreciated by the research community, is the application of planning technology to any concrete real-world scenario (or inspired by one). Such papers, usually called "application papers" explain how planning technology can be deployed for the respective application, and which benefits it brings compared to the past best approach of tackling the problem.

If you are a beginner in planning and would like to get started in research -- or in case you will have an interview with me and need to prepare :) -- I recommend to look at the page "resources-for-students", specifically the section "Basics to get started with Planning".

POCL Planning

Partial-Order Causal Link (POCL) planning refers to planning formalisms and research questions where the "plan data structure" has a very specific form. As mentioned above, in their most simplistic form, plans are just sequences of actions.

In the 80s, the first algorithms to solve planning problems were using a solving procedure that inherently required plans to be POCL plans (so-called POCL search algorithms), a more complex (partially ordered) plan representation (more below). Although these algorithms are severely out of date for solving classical planning problems -- meaning that POCL plans play no role anymore for solving classical problems -- they are still in use by some solvers for hierarchical planning problems (more details below), and, more importantly, they are used for some other applications, most notably for plan optimization (if interested, see my IJCAI 2024 survey on this topic).

The plan below shows, schematically, part of a POCL plan. POCL plans are partially ordered sequences of actions where executability is ensured via the addition of so-called causal links. Those connect action effects with action preconditions. Once all preconditions are protected by causal links, and no causal threats exist -- actions that could invalidate some causal link (see graphic) -- a plan is executable and all linearizations are classical solutions. Plan illustration

I am still very much interested in reasoning about POCL plans, and I believe I am one of only a few remaining experts, which is due to the width of my expertise that involves them:

  • Algorithm and heuristic design:
    • I've been working on POCL planning, i.e., classical problem solving via POCL planning, exactly what was done in the 80s and mostly abandoned in the 2000s. This involves algorithm as well as heuristic design. (Publications: KI 2013, ICTAI 2013, my dissertation)
    • I've been working on hierarchical planning that combines with POCL planning. This is extending the last point to task hierarchies, and thus also involves heuristic search. (Publications: SoCS 2014, IJCAI 2017, my dissertation)
  • Complexity investigations:
    • Again for non-hierarchical POCL planning, I have done complexity investigations, studying how hard it is to turn a given POCL plan into a solution. (Publications: ICTAI 2013, my dissertation, ICAPS 2021)
    • I studied the same question for hierarchical planning with causal links, which make some of the definitions and constraints more complex. (Publications: ECAI 2016, my dissertation, IJCAI 2022)
    • Beyond solving planning problems, I also investigated the complexity of optimizing POCL plans, both regarding their number of actions as well as regarding their makespan. (Publications: ICAPS 2019, AAAI 2020)

Hierarchical Task Network (HTN) Planning

The other planning paradigm where I am a renowned expert is Hierarchical Task Network (HTN) planning. HTN planning extends classical planning by introducing hierarchical control knowledge in the form of tasks and methods. Intuitively, it's inspired by how humans (are believed by many to) plan: we do not reason directly on primitive actions, but rather decompose abstract tasks into smaller, more concrete subtasks until everything is executable. (I say "are believed by many", since we find these statements in many papers by non-experts, yet the insights by actual psychologists are a bit more nuanced, so it would actually be inappropriate to claim that humans do HTN planning.)

Formally, HTN planning problems specify:

  • As in non-hierarchical planning, we have:
    • an initial state that describes the world state before acting,
    • primitive tasks, which are exactly the same as actions from non-hierarchical planning, and
    • a set of goal facts, those that we want to be true at the end,
  • compound tasks (by some called abstract tasks), which represent abstract activities to be refined according to rules on how to do so, the so-called methods, and
  • methods (or decomposition methods), which describe rules on how a compound task can be decomposed into a partially (or totally) ordered set of subtasks, each of which may again be compound or primitive. Each compound task may have several methods, introducing the source of hardness: which method to pick, and
  • an initial compound task that needs to be planned for.

A solution to an HTN planning problem is a sequence of actions that is executable and makes the goals true, and, most significantly, such a plan must be derived from the initial compound task using the available methods.

In other words, not every plan that achieves the goal facts is a valid HTN plan - only those that conform to the given decomposition model are allowed. So, another way to formalize HTN problems is to regard solutions to an HTN problem as the intersection of two plan sets: (1) solutions from the induced classical planning problem (ignoring the task hierarchy), and (2) solutions from the induced task hierarchy (ignoring preconditions and effects). This view gives a beautiful way of looking at HTN problems: They are simply a filter on a classical problem, rejecting all those classical solutions that are not obtainable from the task hierarchy. Should you be more interested in this analogy, it has been studied formally (as expressivity analysis) in papers I have at ECAI 2014, ICAPS 2016, and ICAPS 2022.

Below, you an example of a simple HTN planning problem. It consists of just one compound task and two primitive ones, as well as two decomposition methods. Note that the model is lifted, i.e., tasks are instantiated with concrete constants. The top illustrated the domain graphically, the bottom-left shows the method written down in HDDL syntax. The sequence on the right, read from top to bottom, is a solution plan for the planning problem given by the initial compound task makeClear(C). Plan illustration

Just as for non-hierarchical planning, there is again a vast variety of different hierarchical planning formalisms. One of the most noteworthy ones is TIHTN planning, where additionally to task decomposition, one is allowed to insert actions into plans arbitrarily, just as in classical planning. If interested in these variants, see my survey from IJCAI 2019.

All research questions mentioned above naturally also exist for HTN planning. The areas I was most active in are:

  • Complexity results for a range of problems, such as plan existence (identifying special cases under which the computational complexity is reduced), plan verification, and model repair.
  • Planner and heuristic design. I have mostly been working on solving problems via heuristic search, but also via problem compilations.
  • Model repair algorithms, where the input is a flawed model and a set of constraints, and the output is a corrected model. I do this also with support from Large Language Models (LLMs), as they can base decisions on common world knowledge.

In contrast to POCL planning, I didn't list my publications on the respective research questions, since there are essentially just too many, as most of my research is on HTN planning.

If you are a beginner in HTN planning and would like to get started in research -- or in case you will have an interview with me and need to prepare -- I recommend to look at the page "resources-for-students", specifically the section "Basics to get started with HTN Planning".

Also note that I created a webpage on HTN planning, which provides further resources: https://hierarchical-task.net

Main Research Lines

I deploy my knowledge on complexity theory, algorithm and heuristic design, as well as problem compilations to different planning settings, mostly classical planning, POCL planning, and HTN planning, to two major lines of research: Modeling support and solving planning problems.

1. Modeling Support

Planning domains can be difficult to construct correctly — surprisingly, not just for newcomers, but everybody. It is easy to overlook some details, and consequences can be significant. Even a tiny modeling mistake, say a single forgotten or wrongly chosen precondition or effect (or wrong modeled initial state or goal facts) can lead to:

  • wrong solutions: those that solve the modeled problem, but do not work in the real world,
  • missing solutions: some plans that would work in the real world are invalid in the model,
  • unsolvable planning problems: even though there is a solution to the actual problem, its model doesn't admit any. Beyond those most significant modeling issues, creating a model, even if done correctly, can be very hard, time-consuming and hence even frustrating at times.

Thus, providing automated modeling support is essential. The ultimate goal is to:

  • Assist in creating a new model,
  • assist in verifying the correctness of a created model and help correct errors automatically, and
  • to reduce the time required and overall make the entire process intuitive -- and hopefully fun. :)

A very "low-level" contribution I made here was to (let one of my PhD students :D) create a Visual Studio Code plugin that provides syntax highlighting and syntax error reporting for writing HDDL problems. (HDDL is the standard description language to describe HTN problems, see my AAAI 2020 paper.)

Beyond that (mostly engineering contribution), my most important contributions are theory and methods for the automated correction of classical and HTN problems. Specifically, I have publications that all repair problems given a set of white list plans, black list plans, or both. White list plans are those which are declared to work in the repaired model and black list plans are those declared to be invalid in the repaired model.

  • The computational complexity of repairing classical planning problems given a set of white list plans (IJCAI 2021), black or black and white list plans (AAAI 2023a),
  • The computational complexity of repairing HTN problems based on white list plans (IJCAI 2021), or white and black list plans (AAAI 2023b),
  • Algorithms for repairing classical problems based on white list plans (AAAI 2023a), or white and black list plans (AAAI 2024), or with white list plans, where action parameter bindings may be underspecified (ECAI 2025a),
  • Algorithms for repairing classical unsolvable planning problems (ECAI 2025b), and
  • Algorithms for repairing HTN problems based on white list plans (SoCS 2024).

If interested more in this line of research, I have a recent survey on model repair from IJCAI 2025.

2. Solving Planning Problems

This line focuses on solving planning problems fast, and ideally optimally. I work across classical, POCL, and HTN/TIHTN settings with five recurring themes:

  • Heuristic search. I work mostly with progression search (ICAPS 2018 and JAIR 2020) and design domain-independent heuristics (landmarks (AAAI 2020), ILPs (IJCAI 2020, ECAI 2024), translations to planning (ICAPS 2018, JAIR 2020), other estimates (IJCAI 2017)) and pruning techniques (SoCS 2023).
  • I also investigate heuristic search in FOND HTN planning (IJCAI 2024), the extension of deterministic HTN planning to action models with non-deterministic effects.

The references provided here are exclusively on HTN planning. For those on POCL planning, see the paragraph further up.