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.
Our publications are available online.
We organize a weekly reading group on planning and search.
tutorial "An Overview of the International Planning Competition"
(Amanda Coles, Andrew Coles, Florian Pommerening, and Álvaro Torralba)
tutorial "Latest Trends in Abstraction Heuristics for Classical Planning"
(Malte Helmert, Jendrik Seipp, Silvan Sievers)
tutorial "LP-based Heuristics for Cost-optimal Classical Planning"
(Florian Pommerening, Gabriele Röger, Malte Helmert)
AAAI 2015 tutorial
"A Beginner's Introduction to Heuristic Search Planning"
(Malte Helmert, Gabriele Röger)
ICAPS 2013 tutorial "Engineering a Heuristic Search Planner"
(Malte Helmert, Gabriele Röger)
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
AI Planning: Prost
Prost is a domain-independent probabilistic planning system developed in collaboration between research in and outside of our research group. Prost can be used for online planning for fully observable, discrete MDPs that are described in the input language RDDL (Relational Dynamic Influence Diagram Language). The system is implemented in C++.
Prost won the fully observable MDP track of the Seventh International Planning Competition (IPC 2011) at the 21st International Conference on Automated Planning and Scheduling (ICAPS 2011) as well as of the Eighth International Planning Competition (IPC 2014) at the 24th International Conference on Automated Planning and Scheduling (ICAPS 2014). The planner Prost-DD, implemented on top of Prost by Florian Geißer and David Speck, won the fully observable MDP track of the Ninth International Planning Competition (IPC 2018) at the 28th International Conference on Automated Planning and Scheduling (ICAPS 2018).
Further information: Prost
Contact: Thomas Keller
Beyond Distance Estimates: A New Theory of Heuristics for State-Space Search: BDE (funded by the European Research Council)
Many problems in computer science can be cast as state-space search, where the objective is to find a path from an initial state to a goal state in a directed graph called a state space. State-space search is challenging due to the state explosion problem a.k.a. curse of dimensionality: interesting state spaces are often astronomically large, defying brute-force exploration.
State-space search has been a core research problem in Artificial Intelligence since its early days and is alive as ever. Every year, a substantial fraction of research published at the ICAPS and SoCS conferences is concerned with state-space search, and the topic is very active at general AI conferences such as IJCAI and AAAI.
Algorithms in the A* family, dating back to 1968, are still the go-to approach for state-space search. A* is a graph search algorithm whose only “intelligence” stems from a so-called heuristic function, which estimates the distance from a state to the nearest goal state. The efficiency of A* depends on the accuracy of this estimate, and decades of research have pushed the envelope in devising increasingly accurate estimates. In this project, we question the "A* + distance estimator" paradigm and explore three new directions that go beyond the classical approach:
- We propose a new paradigm of declarative heuristics, where heuristic information is not represented as distance estimates, but as properties of solutions amenable to introspection and general reasoning.
- We suggest moving the burden of creativity away from the human expert by casting heuristic design as a meta-optimization problem that can be solved automatically.
- We propose abandoning the idea of exploring sequential paths in state spaces, instead transforming state-space search into combinatorial optimization problems with no explicit sequencing aspect. We argue that the curse of sequentiality is as bad as the curse of dimensionality and must be addressed head-on.
Certified Correctness and Guaranteed Performance for Domain-Independent Planning: CCGP-Plan (funded by the Swiss National Science Foundation)
The research area of domain-independent planning is concerned with the following problem: given formal representations of the world an autonomous agent is situated in, of its capabilities, and of its goals, find a plan (a sequence of actions executable by the agent) that achieves the agent's goals, or prove that no such plan exists. We focus on the classical setting, one of the traditional core areas of artificial intelligence (AI). After decades of intensive research, planning algorithms have recently reached a level of maturity that makes them useful for real-world decision-making scenarios. With this increased maturity of planning algorithms, raw performance is no longer automatically the main concern for AI researchers or AI engineers interested in using planning algorithms in the systems they build. Besides efficiency, increasing demands are placed on the reliability of planning algorithms. We identify two ways in which current planning algorithms are brittle, and we suggest ways to improve their reliability. Specifically, we consider the following two challenges:
Certified Correctness: As planning is a model-based approach, there are clear notions of correctness: a sound and complete planning algorithm must return a solution if one exists and report unsolvability when no solution exists. An optimal planning algorithm must additionally guarantee that all solutions it returns are of optimal quality. This means that planning algorithms can be incorrect in three ways. They can return solutions that do not actually solve the given problem, falsely claim that a problem is unsolvable, or falsely claim that a solution is optimal (or bounded suboptimal). While the first kind of error can be detected with plan validators, the other two are much more challenging. In critical applications, possible algorithmic errors, implementation bugs, or even malicious programming (for example due to manipulated programs or ulterior motives of the algorithm implementers) are serious concerns. We investigate planning algorithms that always justify their answers in a way that can be verified independently, automatically, and efficiently.
Guaranteed Performance: In many scenarios where a planning algorithm could be used, guaranteeing its correctness is not sufficient. It is also necessary to ensure that in all relevant situations, the algorithm reliably produces a plan within the available computational resources. This is especially true in (common) settings where many similar problems must be solved repeatedly. Current algorithms do not provide performance guarantees, and small differences in the input can make the difference between solutions found within milliseconds, days, or not at all. Due to the PSPACE-completeness of classical planning, there will always be cases where quick solutions are not feasible. However, in many scenarios efficient planning is possible. We propose algorithms that identify such scenarios for individual planning tasks, for planning task structures, and for planning domains.
Foundations of Trustworthy AI - Integrating Reasoning, Learning and Optimization: TAILOR (funded by the European Union)
Artificial Intelligence (AI) and all the key digital technologies that are subsumed by the term AI today are an essential part of the answers to many of the daunting challenges that we are facing. AI will impact the everyday lives of citizens as well as all business sectors. To maximize the opportunities and minimize the risks, Europe focuses on human-centered Trustworthy AI, and is taking important steps towards becoming the worldwide centre for Trustworthy AI. Trustworthiness however still requires significant basic research, and it is clear that the only way to achieve this is through the integration of learning, optimisation and reasoning, as neither approach will be sufficient on its own.
The purpose of TAILOR is to build a strong academic-public-industrial research network with the capacity of providing the scientific basis for Trustworthy AI leveraging and combining learning, optimization and reasoning for realizing AI systems that incorporate the safeguards that make them in the reliable, safe, transparent and respectful of human agency and expectations. Not only the mechanisms to maximize benefits, but also those for minimizing harm. The network will be based on a number of innovative state-of-the-art mechanisms. A multi-stakeholder strategic research and innovation research roadmap coordinates and guides the research in the five basic research programs. Each program forming virtual research environments with many of the best AI researchers in Europe addressing the major scientific challenges identified in the roadmap. A collection of mechanisms supporting innovation, commercialization and knowledge transfer to industry. To support network collaboration TAILOR provides mechanisms such as AI-Powered Collaboration Tools, a PhD program, and training programs. A connectivity fund to support active dissemination across Europe through for example allowing the network to grow and to support the scientific stepping up of more research groups.
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.
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.
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ögerRelevant 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
European Robotic Goal-oriented Autonomous Controller: ERGO (funded by the European Union)
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 KellerRelevant 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.
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.
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 HelmertRelevant publications: (Show)