Research

Our research is focused on the development of algorithms and tools for intelligent problem solving. We are interested in all kinds of combinatorial search and optimization problems, with a particular focus on the area of automated planning, the problem of finding a course of action that changes the current state of the world to one that satisfies the planning agent's goals and objectives.

Planning problems come in many shapes and guises, and planning techniques can be applied to problems as diverse as solving combinatorial puzzles, scheduling ground traffic at an airport, controlling intelligent manufacturing plants, verifying the security of communication protocols or the correctness of software and hardware designs, and computing the evolutionary distance of genomes.

Finding solutions to such problems is computationally hard because of fast-growing state spaces. Therefore, a major challenge in search and optimization is to find intelligent ways to handle large state spaces.

Publications

Our publications are available online.

Reading Group

We organize a weekly reading group on planning and search.

Tutorials

Current research projects

AI Planning: Fast Downward

Fast Downward is a domain-independent planning system developed within our research group. Fast Downward can deal with arbitrary planning problems specified in the standardized input language PDDL (Planning Domain Definition Language), supporting all propositional language constructs (STRIPS, ADL, axioms). The system is implemented in Python and C++.

Fast Downward won the "classical" track (propositional problems, no optimization) of the Fourth International Planning Competition (IPC 2004) at the 14th International Conference on Automated Planning and Scheduling (ICAPS 2004). The planner LAMA, implemented on top of Fast Downward by Silvia Richter and Matthias Westphal, won the classical track of the Sixth International Planning Competition (IPC 2008) at the 18th International Conference on Automated Planning and Scheduling (ICAPS 2008). At the Seventh International Planning Competition (IPC 2011) at the 21st International Conference on Automated Planning and Scheduling (ICAPS 2011), different variants of Fast Downward won all five awards (winners and runners-up) in the sequential satisficing and sequential optimization tracks of the competition, as well as a runner-up award in the planning and learning competition.

Further information: Fast Downward

Contact: Malte Helmert and Gabriele Röger

European Robotic Goal-oriented Autonomous Controller: ERGO (funded by the European Research Council)

In recent years, there has been an increasing interest in the autonomy of space missions such as earth observation, space station operations, planetary robotic exploration, and deep space probes. The capabilities of such systems have grown drastically, but the dependency on human supervision slows down many space missions significantly.

The ERGO project is part of the European strategic reasearch cluster on "Space Robotic Technologies". Its main goal is to realise a software framework for the development of highly autonomous space robotics missions. Given a high level goal, the robot will plan and schedule actions such that a goal is achieved under consideration of temporal, spatial and resource constraints. Uncertainty in the plan execution is met with a monitoring and replanning approach.

Limited on-board resources and the need for real-time behaviour will force the planner to compromise between investment of time and energy in planning versus spending resources on execution. An optimal plan is therefore a plan that optimally balances the demand for planning-time resources against the anticipated demand for execution-time resources. Planning techniques where a resource-intensive precomputation (which can be performed on-ground) allows for informative yet compact guidance of the on-board planner are therefore the key challenge of our research.

Contact: Thomas Keller

Relevant publications: (Show)

Reasoning about Plans and Heuristics for Planning and Combinatorial Search: RAPAHPACS (funded by the Swiss National Science Foundation)

The most successful AI planning algorithms of the last decade fall into the general class of heuristic search methods, usually based on A* or a related search algorithm. Hence, much of the classical planning research has been concerned with developing better and better heuristics and furthering our theoretical understanding of existing heuristics. This has led to increasingly more sophisticated approaches. A large amount of human ingenuity has gone into devising today's advanced approaches and developing the underlying theory, especially in the case of optimal planning, where heuristics must satisfy a lower-bound property (be admissible) in order to be safe to use.

The central idea of this project is to shift this burden of sophistication and ingenuity away from the human heuristic designer and onto the machines that perform the heuristic search. Equipped with appropriate reasoning algorithms and representations, computers can derive knowledge about planning tasks more quickly, more reliably and in more complex settings than we humans are capable of. A planning researcher or practitioner should be able to focus on which information a planning algorithm ought to exploit, without having to worry about how to exploit it in the best way. In other words, we are suggesting a declarative approach to heuristic search planning that enables planning algorithms to reason about plans and heuristics in powerful and general ways.

A key research challenge in this endeavour is identifying an appropriate level of representation at which this declarative information is specified. It should be general enough to capture the concepts that today's state-of-the-art planning algorithms rely on in order to obtain accurate heuristic estimates, yet limited enough to afford efficient reasoning algorithms. In this project, we explore this design space in depth, both theoretically and with an emphasis on efficient practical algorithms.

Contact: Malte Helmert and Gabriele Röger

Relevant publications: (Show)

State Space Exploration: Principles, Algorithms and Applications: SSX (funded by the European Research Council)

State-space search, i.e., finding paths in huge, implicitly given graphs, is a fundamental problem in artificial intelligence and other areas of computer science. State-space search algorithms like A*, IDA* and greedy best-first search are major success stories in artificial intelligence. However, despite their success, these algorithms have deficiencies that have not been sufficiently addressed in the past:

1. They explore a monolithic model of the world rather than applying a factored perspective.

2. They do not learn from mistakes and hence tend to commit the same mistake repeatedly.

3. For satisficing (i.e., suboptimal) search, the design of the major algorithms like greedy best-first search has been based on rather ad-hoc intuitions.

In this project, we target these three deficiencies. We develop a theory of factored state-space search, a theory of learning from information gathered during search, as well as a decision-theoretic foundation for satisficing search algorithms. Based on these insights, the project aims at designing new state-space search algorithms that improve on the current state of the art.

Contact: Malte Helmert

Relevant publications: (Show)

Previous research projects

Abstraction Heuristics for Planning and Combinatorial Search: AHPACS (funded by the Swiss National Science Foundation)

Abstraction heuristics are used in AI planning to estimate the cost of reaching a goal by solving an abstract version of the problem. Such abstractions (in particular the so-called "merge&shrink abstractions") are currently the most accurate heuristics but still have a large gap between their theoretically proven potential and their practical performance.

The project AHPACS (Abstraction Heuristics for Planning and Combinatorial Search) aims to close this gap. The theoretical side of this project is to compare abstraction heuristics with other heuristic families according to their asymptotic accuracy. Asymptotic accuracy is defined similar to asymptotic complexity using compilability between heuristics of two different families to prove statements about their relative accuracy. On the practical side the project investigates using global information provided by other heuristics and learning from mistakes with a model checking technique called counterexample-guided abstraction refinement (CEGAR). It also looks at how abstractions can be compressed or constrained to useful information to make better use of available resources. The last phase of AHPACS investigates applications for abstraction heuristics outside of automated plannning like model checking or bioinformatics.

Contact: Malte Helmert and Florian Pommerening

Relevant publications: (Show)

Automated Reformulation and Pruning in Factored State Spaces: ARAP (funded by the Swiss National Science Foundation)

This project continues the project SPOSSS by widening its scope to a more general class of pruning and problem transformation methods. In particular, ARAP considers the following research objectives for optimal planning:

1. Advance the theory and practice of symmetry elimination. While related work focuses on pruning symmetric states within a search algorithm, ARAP applies the theory of symmetry elimination to other aspects of state-space search, such as the automatic computation of abstractions.

2. Develop general and efficient methods for dominance pruning in transition systems. While SPOSSS focuses on equivalence pruning, ARAP investigates more general methods that can also detect and exploit situations where transition sequences are strictly less useful than others.

3. Develop problem reformulation methods that automatically enrich the description of a transition system to make it more amenable to the distance estimation techniques used in modern planning algorithms, and to abstract away parts of the system that can be solved without search.

Contact: Malte Helmert and Martin Wehrle

Relevant publications: (Show)

Control Knowledge for Domain-independent AI Planning: KontWiss (funded by the German Research Foundation)

The aim of this project is to enhance the efficiency of heuristic forward search in AI planning by means of automatically generated control knowledge.

One objective is to define a suitable formalism which subsumes diverse families of control knowledge in a common framework. The emphasis lies on a uniform representation that allows utilizing several types of control knowledge with similar or identical methods. Another objective is the comparison of the representational power of existing approaches for generating domain knowledge, aiming at a better understanding that can be used to improve and generalize the existing techniques. Finally, we plan to enhance heuristic search algorithms with control knowledge by new methods that are orthogonal to heuristic estimates.

Contact: Gabriele Röger

Relevant publications: (Show)

Directed Model Checking

Model checking describes the task of checking whether a given (mathematical) model of a system satisfies a given property. Directed model checking is a variant of model checking which is optimized towards efficiently detecting error states in faulty systems. Directed model checking can be considered as the application of heuristic search to model checking. In this approach, the exploration of the state space is (heuristically) guided towards error states. As a consequence, error states can often be found by only exploring a small part of the entire state space.

Mcta is a directed model checking tool for real-time systems modeled as networks of timed automata. It is implemented in Python and C++. Mcta is released under the terms of the GPL. Further information (including the sources and precompiled binaries) can be obtained from the Mcta website.

Further information: Mcta website

Contact: Martin Wehrle

Safe Pruning in Optimal State Space Search: SPOSSS (funded by the Swiss National Science Foundation)

This project investigates pruning techniques in optimal state space planning. In particular, we consider techniques based on partial order reduction and symmetry reduction.

Partial order reduction has been originally proposed in the area of computer aided verification. The basic idea is to tackle the state explosion problem by avoiding a blow-up that is induced by independent actions. Recent results have shown that such techniques can be powerful in the area of automated planning as well. In SPOSSS, we investigate partial order reduction techniques for computer aided verification and for planning both theoretically and practically.

Similar to partial order reduction, techniques based on symmetry reduction have been originally proposed in the area of computer aided verification. In contrast to partial order reduction which exploits symmetric action sequences, techniques based on symmetry reduction compute a quotient structure of the state space, where symmetrical states are considered equivalent. In SPOSSS, we investigate symmetry reduction techniques and their applications to planning.

Contact: Malte Helmert and Martin Wehrle

Relevant publications: (Show)