Malte Helmert – Publikationen

(Alle Abstracts einblenden) (Alle Abstracts ausblenden)

2011

Raz Nissim, Jörg Hoffmann und Malte Helmert.
Computing Perfect Heuristics in Polynomial Time: On Bisimulation and Merge-and-Shrink Abstractions in Optimal Planning.
In Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence (IJCAI 2011), S. 1983-1990. 2011.
Erratum: In Section 7, we introduce greedy bisimulation as only respecting the bisimulation property for transitions (s, l, s') where sd(s) <= sd(s'). The implementation we evaluate in Section 8 is actually even more greedy than that, only respecting transitions where sd(s) < sd(s'). Using the definition from Section 7 leads to a strategy that behaves very similarly to the strategies using regular (non-greedy) bisimulation on these benchmarks..
(Abstract einblenden) (Abstract ausblenden) (PDF)

A* with admissible heuristics is a very successful approach to optimal planning. But how to derive such heuristics automatically? Merge-and-shrink abstraction (M&S) is a general approach to heuristic design whose key advantage is its capability to make very fine-grained choices in defining abstractions. However, little is known about how to actually make these choices. We address this via the well-known notion of bisimulation. When aggregating only bisimilar states, M&s yields a perfect heuristic. Alas, bisimulations are exponentially large even in trivial domains. We show how to apply label reduction -- not distinguishing between certain groups of operators -- without incurring any information loss, while potentially reducing bisimulation size exponentially. In several benchmark domains, the resulting algorithm computes perfect heuristics in polynomial time. Empirically, we show that approximating variants of this algorithm improve the state of the art in M&S heuristics. In particular, a hybrid of two such variants is competitive with the leading heuristic LM-cut.
Carmel Domshlak, Malte Helmert, Erez Karpas, Emil Keyder, Silvia Richter, Gabriele Röger, Jendrik Seipp und Matthias Westphal.
BJOLP: The Big Joint Optimal Landmarks Planner (planner abstract).
In Seventh International Planning Competition (IPC 2011), Deterministic Part, S. 91-95. 2011.
(Abstract einblenden) (Abstract ausblenden) (PDF)

BJOLP, The Big Joint Optimal Landmarks Planner uses landmarks to derive an admissible heuristic, which is then used to guide a search for a cost-optimal plan. In this paper we review landmarks and describe how they can be used to derive an admissible heuristic. We conclude with presenting the BJOLP planner.
Silvia Richter, Matthias Westphal und Malte Helmert.
LAMA 2008 and 2011 (planner abstract).
In Seventh International Planning Competition (IPC 2011), Deterministic Part, S. 50-54. 2011.
(Abstract einblenden) (Abstract ausblenden) (PDF)

LAMA is a propositional planning system based on heuristic search with landmarks. This paper describes two versions of LAMA that were entered into the 2011 International Planning Competition: the original LAMA as developed for the 2008 competition and a new re-implementation of LAMA that uses the latest version of the Fast Downward Planning Framework.

Landmarks are propositions that must be true in every solution of a planning task. LAMA uses a heuristic derived from landmarks in conjunction with the well-known FF heuristic. LAMA builds on the Fast Downward Planning System using non-binary (but finite domain) state variables and multi-heuristic search. A weighted A* search is used with iteratively decreasing weights, so that the planner continues to search for plans of better quality until the search is terminated. LAMA combines cost-to-goal and distance-to-goal estimates with the aim of finding good solutions using reasonable runtime.
Malte Helmert und Carmel Domshlak.
LM-Cut: Optimal Planning with the Landmark-Cut Heuristic (planner abstract).
In Seventh International Planning Competition (IPC 2011), Deterministic Part, S. 103-105. 2011.
(Abstract einblenden) (Abstract ausblenden) (PDF)

The LM-Cut planner uses the landmark-cut heuristic, introduced by the authors in 2009, within a standard A* progression search framework to find optimal sequential plans for STRIPS-style planning tasks. This short paper recapitulates the main ideas surrounding the landmark-cut heuristic and provides pointers for further reading.
Raz Nissim, Jörg Hoffmann und Malte Helmert.
The Merge-and-Shrink Planner: Bisimulation-based Abstraction for Optimal Planning (planner abstract).
In Seventh International Planning Competition (IPC 2011), Deterministic Part, S. 106-107. 2011.
(Abstract einblenden) (Abstract ausblenden) (PDF)

Merge-and-shrink abstraction is a general approach to heuristic design whose key advantage is its capability to make very fine-grained choices in defining abstractions. The Merge-and-shrink planner uses two different strategies for making these choices, both based on the well-known notion of bisimulation. The resulting heuristics are used in two sequential runs of A* search.
Carmel Domshlak, Malte Helmert, Erez Karpas und Shaul Markovitch.
The SelMax Planner: Online Learning for Speeding up Optimal Planning (planner abstract).
In Seventh International Planning Competition (IPC 2011), Deterministic Part, S. 108-112. 2011.
(Abstract einblenden) (Abstract ausblenden) (PDF)

The SelMax planner combines two state-of-the-art admissible heuristics using an online learning approach. In this paper we describe the online learning approach employed by SelMax, briefly review the Fast Downward framework, and describe the SelMax planner.
Malte Helmert, Gabriele Röger, Jendrik Seipp, Erez Karpas, Jörg Hoffmann, Emil Keyder, Raz Nissim, Silvia Richter und Matthias Westphal.
Fast Downward Stone Soup (planner abstract).
In Seventh International Planning Competition (IPC 2011), Deterministic Part, S. 38-45. 2011.
(Abstract einblenden) (Abstract ausblenden) (PDF)

Fast Downward Stone Soup is a sequential portfolio planner that uses various heuristics and search algorithms that have been implemented in the Fast Downward planning system.

We present a simple general method for concocting "planner soups", sequential portfolios of planning algorithms, and describe the actual recipes used for Fast Downward Stone Soup in the sequential optimization and sequential satisficing tracks of IPC 2011.
Chris Fawcett, Malte Helmert, Holger Hoos, Erez Karpas, Gabriele Röger und Jendrik Seipp.
FD-Autotune: Automated Configuration of Fast Downward (planner abstract).
In Seventh International Planning Competition (IPC 2011), Deterministic Part, S. 31-37. 2011.
(Abstract einblenden) (Abstract ausblenden) (PDF)

The FD-Autotune submissions for the IPC-2011 sequential tracks consist of three instantiations of the latest, highly parametric version of the Fast Downward Planning Framework. These instantiations have been automatically configured for performance on a wide range of planning domains, using the well-known ParamILS configurator. Two of the instantiations were entered into the sequential satisficing track and one into the sequential optimising track. We describe how the extremely large configuration space of Fast Downward was restricted to a subspace that, although still very large, can be managed by state-of-the-art automated configuration procedures, and how ParamILS was then used to obtain performance-optimised configurations.
Chris Fawcett, Malte Helmert, Holger Hoos, Erez Karpas, Gabriele Röger und Jendrik Seipp.
FD-Autotune: Domain-Specific Configuration using Fast Downward (planner abstract).
In Seventh International Planning Competition (IPC 2011), Planning and Learning Part. 2011.
(Abstract einblenden) (Abstract ausblenden) (PDF)

The FD-Autotune learning planning system is based on the idea of domain-specific configuration of the latest, highly parametric version of the Fast Downward Planning Framework by means of a generic automated algorithm configuration procedure. We describe how the extremely large configuration space of Fast Downward was restricted to a subspace that, although still very large, can be managed by state-of-the-art automated configuration procedures. FD-Autotune uses the well-known ParamILS configurator and was realised using the recently developed HAL experimentation environment.
Malte Helmert, Gabriele Röger und Erez Karpas.
Fast Downward Stone Soup: A Baseline for Building Planner Portfolios.
In Proceedings of the ICAPS-2011 Workshop on Planning and Learning (PAL), S. 28-35. 2011.
(Abstract einblenden) (Abstract ausblenden) (PDF)

Fast Downward Stone Soup is a sequential portfolio planner that uses various heuristics and search algorithms that have been implemented in the Fast Downward planning system.

We present a simple general method for concocting "planner soups", sequential portfolios of planning algorithms, and describe the actual recipes used for Fast Downward Stone Soup in the sequential optimization and sequential satisficing tracks of IPC 2011.

This paper is, first and foremost, a planner description. Fast Downward Stone Soup was entered into the sequential (non-learning) tracks of IPC 2011. Due to time constraints, we did not enter it into the learning competition at IPC 2011. However, we believe that the approach might still be of interest to the planning and learning community, as it represents a baseline against which other, more sophisticated portfolio learners can be usefully compared.
Chris Fawcett, Malte Helmert, Holger Hoos, Erez Karpas, Gabriele Röger und Jendrik Seipp.
FD-Autotune: Domain-Specific Configuration using Fast Downward.
In Proceedings of the ICAPS-2011 Workshop on Planning and Learning (PAL), S. 13-20. 2011.
(Abstract einblenden) (Abstract ausblenden) (PDF)

In this work, we present the FD-Autotune learning planning system, which is based on the idea of domain-specific configuration of the latest, highly parametric version of the Fast Downward Planning Framework by means of a generic automated algorithm configuration procedure. We describe how the extremely large configuration space of Fast Downward was restricted to a subspace that, although still very large, can be managed by a state-of-the-art automated configuration procedure. Additionally, we give preliminary results obtained from applying our approach to the nine domains of the IPC-2011 learning track, using the well-known ParamILS configurator and the recently developed HAL experimentation environment.
Raz Nissim, Jörg Hoffmann und Malte Helmert.
Computing Perfect Heuristics in Polynomial Time: On Bisimulation and Merge-and-Shrink Abstractions in Optimal Planning.
In Proceedings of the ICAPS-2011 Workshop on Heuristics for Domain-independent Planning (HDIP), S. 5-13. 2011.
Superseded by the IJCAI 2011 paper by the same name.
(Abstract einblenden) (Abstract ausblenden) (PDF)

A* with admissible heuristics is a very successful approach to optimal planning. But how to derive such heuristics automatically? Merge-and-shrink abstraction (M&S) is a general approach to heuristic design whose key advantage is its capability to make very fine-grained choices in defining abstractions. However, little is known about how to actually make these choices. We address this via the well-known notion of bisimulation. When aggregating only bisimilar states, M&s yields a perfect heuristic. Alas, bisimulations are exponentially large even in trivial domains. We show how to apply label reduction -- not distinguishing between certain groups of operators -- without incurring any information loss, while potentially reducing bisimulation size exponentially. In several benchmark domains, the resulting algorithm computes perfect heuristics in polynomial time. Empirically, we show that approximating variants of this algorithm improve the state of the art in M&S heuristics. In particular, a hybrid of two such variants is competitive with the leading heuristic LM-cut.
Jendrik Seipp und Malte Helmert.
Fluent Merging for Classical Planning Problems.
In Proceedings of the ICAPS-2011 Workshop on Knowledge Engineering for Planning and Scheduling (KEPS), S. 47-53. 2011.
Note: This version of the paper fixes two mistakes (in Def. 2 and in the text after Def. 3) that are present in the version of the paper that is linked from the workshop webpage..
(Abstract einblenden) (Abstract ausblenden) (PDF)

Fluent merging is a reformulation technique for classical planning problems that can be applied automatically or semi-automatically. The reformulation strives to transform a planning task into a representation that allows a planning algorithm to find solutions more efficiently or to find solutions of better quality. This work introduces different approaches for fluent merging and evaluates them within a state-of-the-art planning system.
Fahiem Bacchus, Carmel Domshlak, Stefan Edelkamp und Malte Helmert (Hrsg.).
Proceedings of the 21st International Conference on Automated Planning and Scheduling (ICAPS 2011).
AAAI Press, Menlo Park, California, USA 2011.

2010

Malte Helmert und Gabriele Röger.
Relative-Order Abstractions for the Pancake Problem.
In Helder Coelho, Rudi Studer und Michael Wooldridge (Hrsg.), Proceedings of the 19th European Conference on Artificial Intelligence (ECAI 2010), S. 745-750. IOS Press 2010.
(Abstract einblenden) (Abstract ausblenden) (PDF)

The pancake problem is a famous search problem where the objective is to sort a sequence of objects (pancakes) through a minimal number of prefix reversals (flips). The best approaches for the problem are based on heuristic search with abstraction (pattern database) heuristics. We present a new class of abstractions for the pancake problem called relative-order abstractions. Relative-order abstractions have three advantages over the object-location abstractions considered in previous work. First, they are size-independent, i.e., do not need to be tailored to a particular instance size of the pancake problem. Second, they are more compact in that they can represent a larger number of pancakes within abstractions of bounded size. Finally, they can exploit symmetries in the problem specification to allow multiple heuristic lookups, significantly improving search performance over a single lookup. Our experiments show that compared to object-location abstractions, our new techniques lead to an improvement of one order of magnitude in runtime and up to three orders of magnitude in the number of generated states.
Blai Bonet und Malte Helmert.
Strengthening Landmark Heuristics via Hitting Sets.
In Helder Coelho, Rudi Studer und Michael Wooldridge (Hrsg.), Proceedings of the 19th European Conference on Artificial Intelligence (ECAI 2010), S. 329-334. IOS Press 2010.
(Abstract einblenden) (Abstract ausblenden) (PDF) (technical report with proofs; PDF) (slides of Blai's ECAI 2010 presentation; PDF) (slides of Malte's SS 2010 group seminar presentation; PDF)

The landmark cut heuristic is perhaps the strongest known polytime admissible approximation of the optimal delete relaxation heuristic h⁺. Equipped with this heuristic, a best-first search was able to optimally solve 40% more benchmark problems than the winners of the sequential optimization track of IPC 2008. We show that this heuristic can be understood as a simple relaxation of a hitting set problem, and that stronger heuristics can be obtained by considering stronger relaxations. Based on these findings, we propose a simple polytime method for obtaining heuristics stronger than landmark cut, and evaluate them over benchmark problems. We also show that hitting sets can be used to characterize h⁺ and thus provide a fresh and novel insight for better comprehension of the delete relaxation.
Emil Keyder, Silvia Richter und Malte Helmert.
Sound and Complete Landmarks for And/Or Graphs.
In Helder Coelho, Rudi Studer und Michael Wooldridge (Hrsg.), Proceedings of the 19th European Conference on Artificial Intelligence (ECAI 2010), S. 335-340. IOS Press 2010.
(Abstract einblenden) (Abstract ausblenden) (PDF)

Landmarks for a planning problem are subgoals that are necessarily made true at some point in the execution of any plan. Since verifying that a fact is a landmark is PSPACE-complete, earlier approaches have focused on finding landmarks for the delete relaxation Π⁺. Furthermore, some of these approaches have approximated this set of landmarks, although it has been shown that the complete set of causal delete-relaxation landmarks can be identified in polynomial time by a simple procedure over the relaxed planning graph. Here, we give a declarative characterisation of this set of landmarks and show that the procedure computes the landmarks described by our characterisation. Building on this, we observe that the procedure can be applied to any delete-relaxation problem and take advantage of a recent compilation of the m-relaxation of a problem into a problem with no delete effects to extract landmarks that take into account delete effects in the original problem. We demonstrate that this approach finds strictly more causal landmarks than previous approaches and discuss the relationship between increased computational effort and experimental performance, using these landmarks in a recently proposed admissible landmark-counting heuristic.
Malte Helmert.
Lessons Learned from Benchmarking in the Automated Planning Community.
In Proceedings of the ECAI 2010 Workshop on Benchmarking Intelligent (Multi-) Robot Systems. 2010.
(PDF)
Patrick Eyerich, Thomas Keller und Malte Helmert.
High-Quality Policies for the Canadian Traveler's Problem.
In Maria Fox und David Poole (Hrsg.), Proceedings of the Twenty-Fourth AAAI Conference on Artificial Intelligence (AAAI 2010), S. 51-58. AAAI Press 2010.
(Abstract einblenden) (Abstract ausblenden) (PDF)

We consider the stochastic variant of the Canadian Traveler's Problem, a path planning problem where adverse weather can cause some roads to be untraversable. The agent does not initially know which roads can be used. However, it knows a probability distribution for the weather, and it can observe the status of roads incident to its location. The objective is to find a policy with low expected travel cost.

We introduce and compare several algorithms for the stochastic CTP. Unlike the optimistic approach most commonly considered in the literature, the new approaches we propose take uncertainty into account explicitly. We show that this property enables them to generate policies of much higher quality than the optimistic one, both theoretically and experimentally.
Patrick Eyerich, Thomas Keller und Malte Helmert.
High-Quality Policies for the Canadian Traveler's Problem (Extended Abstract).
In Ariel Felner und Nathan Sturtevant (Hrsg.), Proceedings of the Third Annual Symposium on Combinatorial Search (SoCS 2010), S. 147-148. AAAI Press 2010.
Extended abstract of the AAAI paper by the same name.
(PDF)
Malte Helmert.
Landmark Heuristics for the Pancake Problem.
In Ariel Felner und Nathan Sturtevant (Hrsg.), Proceedings of the Third Annual Symposium on Combinatorial Search (SoCS 2010), S. 109-110. AAAI Press 2010.
(Abstract einblenden) (Abstract ausblenden) (PDF)

We describe the gap heuristic for the pancake problem, which dramatically outperforms current abstraction-based heuristics for this problem. The gap heuristic belongs to a family of landmark heuristics that have recently been very successfully applied to planning problems.
Malte Helmert und Hauke Lasinger.
The Scanalyzer Domain: Greenhouse Logistics as a Planning Problem.
In Ronen Brafman, Héctor Geffner, Jörg Hoffmann und Henry Kautz (Hrsg.), Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS 2010), S. 234-237. AAAI Press 2010.
(Abstract einblenden) (Abstract ausblenden) (PDF)

We introduce the Scanalyzer planning domain, a domain for classical planning which models the problem of automatic greenhouse logistic management.

At its mathematical core, the Scanalyzer domain is a permutation problem with striking similarities to common search benchmarks such as Rubik's Cube or TopSpin. At the same time, it is also a real application domain, and efficient algorithms for the problem are of considerable practical interest.

The Scanalyzer domain was used as a benchmark for sequential planners at the last International Planning Competition. The competition results show that domain-independent automated planners can find solutions of comparable quality to those generated by specialized algorithms developed by domain experts, while being considerably more flexible.
Robert Mattmüller, Manuela Ortlieb, Malte Helmert und Pascal Bercher.
Pattern Database Heuristics for Fully Observable Nondeterministic Planning.
In Ronen Brafman, Héctor Geffner, Jörg Hoffmann und Henry Kautz (Hrsg.), Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS 2010), S. 105-112. AAAI Press 2010.
(Abstract einblenden) (Abstract ausblenden) (PDF) (slides; PDF)

When planning in an uncertain environment, one is often interested in finding a contingent plan that prescribes appropriate actions for all possible states that may be encountered during the execution of the plan. We consider the problem of finding strong and strong cyclic plans for fully observable nondeterministic (FOND) planning problems. The algorithm we choose is LAO*, an informed explicit state search algorithm. We investigate the use of pattern database (PDB) heuristics to guide LAO* towards goal states. To obtain a fully domain-independent planning system, we use an automatic pattern selection procedure that performs local search in the space of pattern collections. The evaluation of our system on the FOND benchmarks of the Uncertainty Part of the International Planning Competition 2008 shows that our approach is competitive with symbolic regression search in terms of problem coverage and speed.
Gabriele Röger und Malte Helmert.
The More, the Merrier: Combining Heuristic Estimators for Satisficing Planning.
In Ronen Brafman, Héctor Geffner, Jörg Hoffmann und Henry Kautz (Hrsg.), Proceedings of the 20th International Conference on Automated Planning and Scheduling (ICAPS 2010), S. 246-249. AAAI Press 2010.
(Abstract einblenden) (Abstract ausblenden) (PDF) (technical report; PDF)

We empirically examine several ways of exploiting the information of multiple heuristics in a satisficing best-first search algorithm, comparing their performance in terms of coverage, plan quality, speed, and search guidance. Our results indicate that using multiple heuristics for satisficing search is indeed useful. Among the combination methods we consider, the best results are obtained by the alternation method of the "Fast Diagonally Downward" planner.
Patrick Eyerich, Thomas Keller und Malte Helmert.
High-Quality Policies for the Canadian Traveler's Problem.
In Proceedings of the ICAPS-2010 Workshop on Planning and Scheduling Under Uncertainty. 2010.
Superseded by the AAAI 2010 paper by the same name.
(Abstract einblenden) (Abstract ausblenden) (PDF)

We consider the stochastic variant of the Canadian Traveler's Problem, a path planning problem where adverse weather can cause some roads to be untraversable. The agent does not initially know which roads can be used. However, it knows a probability distribution for the weather, and it can observe the status of roads incident to its location. The objective is to find a policy with low expected travel cost.

We introduce and compare several algorithms for the stochastic CTP. Unlike the optimistic approach most commonly considered in the literature, the new approaches we propose take uncertainty into account explicitly. We show that this property enables them to generate policies of much higher quality than the optimistic one, both theoretically and experimentally.

2009

Dunbo Cai, Jörg Hoffmann und Malte Helmert.
Enhancing the Context-Enhanced Additive Heuristic with Precedence Constraints.
In Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS 2009), S. 50-57. AAAI Press 2009.
(Abstract einblenden) (Abstract ausblenden) (PDF)

Recently, Helmert and Geffner proposed the context-enhanced additive heuristic, where fact costs are evaluated relative to context states that arise from achieving first a pivot condition of each operator. As Helmert and Geffner pointed out, the method can be generalized to consider contexts arising from arbitrary precedence constraints over operator conditions instead. Herein, we provide such a generalization. We extend Helmert and Geffner's equations, and discuss a number of design choices that arise. Drawing on previous work on goal orderings, we design a family of methods for automatically generating precedence constraints. We run large-scale experiments, showing that the technique can help significantly, depending on the choice of precedence constraints. We shed some light on this by profiling the behavior of all possible precedence constraints, using a sampling technique.
Malte Helmert und Carmel Domshlak.
Landmarks, Critical Paths and Abstractions: What's the Difference Anyway?
In Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS 2009), S. 162-169. AAAI Press 2009.
(Abstract einblenden) (Abstract ausblenden) (PDF) (Dagstuhl abstract; PDF)

Current heuristic estimators for classical domain-independent planning are usually based on one of four ideas: delete relaxations, critical paths, abstractions, and, most recently, landmarks. Previously, these different ideas for deriving heuristic functions were largely unconnected.

We prove that admissible heuristics based on these ideas are in fact very closely related. Exploiting this relationship, we introduce a new admissible heuristic called the landmark cut heuristic, which compares favourably with the state of the art in terms of heuristic accuracy and overall performance.
Silvia Richter und Malte Helmert.
Preferred Operators and Deferred Evaluation in Satisficing Planning.
In Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS 2009), S. 273-280. AAAI Press 2009.
(Abstract einblenden) (Abstract ausblenden) (PDF)

Heuristic forward search is the dominant approach to satisficing planning to date. Most successful planning systems, however, go beyond plain heuristic search by employing various search-enhancement techniques. One example is the use of helpful actions or preferred operators, providing information which may complement heuristic values. A second example is deferred heuristic evaluation, a search variant which can reduce the number of costly node evaluations. Despite the wide-spread use of these search-enhancement techniques however, we note that few results have been published examining their usefulness. In particular, while various ways of using, and possibly combining, these techniques are conceivable, no work to date has studied the performance of such variations. In this paper, we address this gap by examining the use of preferred operators and deferred evaluation in a variety of settings within best-first search. In particular, our findings are consistent with and help explain the good performance of the winners of the satisficing tracks at IPC 2004 and 2008.
Christoph Betz und Malte Helmert.
Planning with h+ in Theory and Practice.
In Proceedings of the 2nd Workshop on Heuristics for Domain-independent Planning at ICAPS 2009. 2009.
(Abstract einblenden) (Abstract ausblenden) (PDF)

Many heuristic estimators for classical planning are based on the so-called delete relaxation, which ignores negative effects of planning operators. Ideally, such heuristics would compute the actual goal distance in the delete relaxation, i.e., the cost of an optimal relaxed plan, denoted by h+. However, current delete relaxation heuristics only provide (often inadmissible) estimates to h+ because computing the correct value is an NP-hard problem.

In this work, we consider the approach of planning with the actual h+ heuristic from a theoretical and computational perspective. In particular, we provide domain-dependent complexity results that classify some standard benchmark domains into ones where h+ can be computed efficiently and ones where computing h+ is NP-hard. Moreover, we study domain-dependent implementations of h+ which show that the h+ heuristic provides very informative heuristic estimates compared to other state-of-the-art heuristics.
Gabriele Röger und Malte Helmert.
Combining Heuristic Estimators for Satisficing Planning.
In Proceedings of the 2nd Workshop on Heuristics for Domain-independent Planning at ICAPS 2009. 2009.
(Abstract einblenden) (Abstract ausblenden) (PDF)

The problem of effectively combining multiple heuristic estimators has been studied extensively in the context of optimal planning, but not in the context of satisficing planning. To narrow this gap, we empirically examine several ways of exploiting the information of multiple heuristics in a satisficing best-first search algorithm, comparing their performance in terms of coverage, plan quality and runtime. Our empirical results indicate that using multiple heuristics for satisficing search is indeed useful and that the best results are not obtained by the most obvious combination methods.
Christoph Betz und Malte Helmert.
Planning with h+ in Theory and Practice.
In Bärbel Mertsching, Marcus Hund und Zaheer Aziz (Hrsg.), Proceedings of the 32nd Annual German Conference on Artificial Intelligence (KI 2009), S. 9-16. Springer-Verlag 2009.
(Abstract einblenden) (Abstract ausblenden) (PDF)

Many heuristic estimators for classical planning are based on the so-called delete relaxation, which ignores negative effects of planning operators. Ideally, such heuristics would compute the actual goal distance in the delete relaxation, i.e., the cost of an optimal relaxed plan, denoted by h+. However, current delete relaxation heuristics only provide (often inadmissible) estimates to h+ because computing the correct value is an NP-hard problem.

In this work, we consider the approach of planning with the actual h+ heuristic from a theoretical and computational perspective. In particular, we provide domain-dependent complexity results that classify some standard benchmark domains into ones where h+ can be computed efficiently and ones where computing h+ is NP-hard. Moreover, we study domain-dependent implementations of h+ which show that the h+ heuristic provides very informative heuristic estimates compared to other state-of-the-art heuristics.
Martin Wehrle und Malte Helmert.
The Causal Graph Revisited for Directed Model Checking.
In Jens Palsberg und Zhendong Su (Hrsg.), Proceedings of the 16th International Static Analysis Symposium (SAS 2009), S. 86-101. Springer-Verlag 2009.
(Abstract einblenden) (Abstract ausblenden) (PDF) (Dagstuhl abstract; PDF)

Directed model checking is a well-established technique to tackle the state explosion problem when the aim is to find error states in large systems. In this approach, the state space traversal is guided through a function that estimates the distance to nearest error states. States with lower estimates are preferably expanded during the search. Obviously, the challenge is to develop distance functions that are efficiently computable on the one hand and as informative as possible on the other hand. In this paper, we introduce the causal graph structure to the context of directed model checking. Based on causal graph analysis, we first adapt a distance estimation function from AI planning to directed model checking. Furthermore, we investigate an abstraction that is guaranteed to preserve error states. The experimental evaluation shows the practical potential of these techniques.
Malte Helmert.
Research Statement: Heuristic Search for Domain-Independent Planning.
In 2nd International Symposium on Combinatorial Search (SoCS 2009). 2009.
(PDF)
Jörg Hoffmann, Piergiorgio Bertoli, Malte Helmert und Marco Pistore.
Message-Based Web Service Composition, Integrity Constraints, and Planning under Uncertainty: A New Connection.
Journal of Artificial Intelligence Research 35, S. 49-117. 2009.
(Abstract einblenden) (Abstract ausblenden) (PDF)

Thanks to recent advances, AI Planning has become the underlying technique for several applications. Figuring prominently among these is automated Web Service Composition (WSC) at the "capability" level, where services are described in terms of preconditions and effects over ontological concepts. A key issue in addressing WSC as planning is that ontologies are not only formal vocabularies; they also axiomatize the possible relationships between concepts. Such axioms correspond to what has been termed "integrity constraints" in the actions and change literature, and applying a web service is essentially a belief update operation. The reasoning required for belief update is known to be harder than reasoning in the ontology itself. The support for belief update is severely limited in current planning tools.

Our first contribution consists in identifying an interesting special case of WSC which is both significant and more tractable. The special case, which we term forward effects, is characterized by the fact that every ramification of a web service application involves at least one new constant generated as output by the web service. We show that, in this setting, the reasoning required for belief update simplifies to standard reasoning in the ontology itself. This relates to, and extends, current notions of "message-based" WSC, where the need for belief update is removed by a strong (often implicit or informal) assumption of "locality" of the individual messages. We clarify the computational properties of the forward effects case, and point out a strong relation to standard notions of planning under uncertainty, suggesting that effective tools for the latter can be successfully adapted to address the former.

Furthermore, we identify a significant sub-case, named strictly forward effects, where an actual compilation into planning under uncertainty exists. This enables us to exploit off-the-shelf planning tools to solve message-based WSC in a general form that involves powerful ontologies, and requires reasoning about partial matches between concepts. We provide empirical evidence that this approach may be quite effective, using Conformant-FF as the underlying planner.
Malte Helmert.
Concise finite-domain representations for PDDL planning tasks.
Artificial Intelligence 173, S. 503-535. 2009.
(Abstract einblenden) (Abstract ausblenden) (PDF)

We introduce an efficient method for translating planning tasks specified in the standard PDDL formalism into a concise grounded representation that uses finite-domain state variables instead of the straight-forward propositional encoding.

Translation is performed in four stages. Firstly, we transform the input task into an equivalent normal form expressed in a restricted fragment of PDDL. Secondly, we synthesize invariants of the planning task that identify groups of mutually exclusive propositions which can be represented by a single finite-domain variable. Thirdly, we perform an efficient relaxed reachability analysis using logic programming techniques to obtain a grounded representation of the input. Finally, we combine the results of the third and fourth stage to generate the final grounded finite-domain representation.

The presented approach has originally been implemented as part of the Fast Downward planning system for the 4th International Planning Competition (IPC4). Since then, it has been used in a number of other contexts with considerable success, and the use of concise finite-domain representations has become a common feature of state-of-the-art planners.

2008

Gabriele Röger, Malte Helmert und Bernhard Nebel.
On the Relative Expressiveness of ADL and Golog: The Last Piece in the Puzzle.
In Proceedings of the Eleventh International Conference on Principles of Knowledge Representation and Reasoning (KR 2008), S. 544-550. AAAI Press 2008.
(Abstract einblenden) (Abstract ausblenden) (PDF)

Integrating agent programming languages and efficient action planning is a promising approach because it combines the expressive power of languages such as Golog with the possibility of searching for plans efficiently. In order to integrate a Golog interpreter with a planner, one has to understand, however, which part of the expressiveness of Golog can be captured by the planning language. Using Nebel's compilation framework, we identify a maximal fragment of basic action theories, the formalism Golog is based on, that is expressively equivalent to the ADL subset of PDDL. As we will show, almost all features that permit to specify incomplete information in basic action theories cannot be compiled to ADL.
Malte Helmert und Héctor Geffner.
Unifying the Causal Graph and Additive Heuristics.
In Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS 2008), S. 140-147. AAAI Press 2008.
(Abstract einblenden) (Abstract ausblenden) (PDF)

Many current heuristics for domain-independent planning, such as Bonet and Geffner's additive heuristic and Hoffmann and Nebel's FF heuristic, are based on delete relaxations. They estimate the goal distance of a search state by approximating the solution cost in a relaxed task where negative consequences of operator applications are ignored. Helmert's causal graph heuristic, on the other hand, approximates goal distances by solving a hierarchy of "local" planning problems that only involve a single state variable and the variables it depends on directly.

Superficially, the causal graph heuristic appears quite unrelated to heuristics based on delete relaxation. In this contribution, we show that the opposite is true. Using a novel, declarative formulation of the causal graph heuristic, we show that the causal graph heuristic is the additive heuristic plus context. Unlike the original heuristic, our formulation does not require the causal graph to be acyclic, and thus leads to a proper generalization of both the causal graph and additive heuristics. Empirical results show that the new heuristic is significantly better informed than both Helmert's original causal graph heuristic and the additive heuristic and outperforms them across a wide range of standard benchmarks.
Malte Helmert, Patrik Haslum und Jörg Hoffmann.
Explicit-State Abstraction: A New Method for Generating Heuristic Functions.
In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI 2008), S. 1547-1550. AAAI Press 2008.
(Abstract einblenden) (Abstract ausblenden) (PDF) (slides; PDF)

Many AI problems can be recast as finding an optimal path in a discrete state space. An abstraction defines an admissible heuristic function as the distances in a smaller state space where arbitrary sets of states are "aggregated" into single states. A special case are pattern database (PDB) heuristics, which aggregate states iff they agree on the state variables inside the pattern. Explicit-state abstraction is more flexible, explicitly aggregating selected pairs of states in a process that interleaves composition of abstractions with abstraction of the composites. The increased flexibility gains expressive power: sometimes, the real cost function can be represented concisely as an explicit-state abstraction, but not as a PDB. Explicit-state abstraction has been applied to planning and model checking, with highly promising empirical results.
Malte Helmert und Gabriele Röger.
How Good is Almost Perfect?
In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI 2008), S. 944-949. AAAI Press 2008.
(Abstract einblenden) (Abstract ausblenden) (PDF) (slides; PDF)

Heuristic search using algorithms such as A* and IDA* is the prevalent method for obtaining optimal sequential solutions for classical planning tasks. Theoretical analyses of these classical search algorithms, such as the well-known results of Pohl, Gaschnig and Pearl, suggest that such heuristic search algorithms can obtain better than exponential scaling behaviour, provided that the heuristics are accurate enough.

Here, we show that for a number of common planning benchmark domains, including ones that admit optimal solution in polynomial time, general search algorithms such as A* must necessarily explore an exponential number of search nodes even under the optimistic assumption of almost perfect heuristic estimators, whose heuristic error is bounded by a small additive constant.

Our results shed some light on the comparatively bad performance of optimal heuristic search approaches in "simple" domains such as GRIPPER. They suggest that in many domains, further improvements in run-time require changes to other parts of the planning algorithm than the heuristic estimator.
Malte Helmert und Robert Mattmüller.
Accuracy of Admissible Heuristic Functions in Selected Planning Domains.
In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI 2008), S. 938-943. AAAI Press 2008.
(Abstract einblenden) (Abstract ausblenden) (PDF) (slides; PDF)

The efficiency of optimal planning algorithms based on heuristic search crucially depends on the accuracy of the heuristic function used to guide the search. Often, we are interested in domain-independent heuristics for planning. In order to assess the limitations of domain-independent heuristic planning, it appears interesting to analyse the (in)accuracy of common domain-independent planning heuristics in the IPC benchmark domains. For a selection of these domains, we analytically investigate the accuracy of the h⁺ heuristic, the h^m family of heuristics, and certain (additive) pattern database heuristics, compared to the perfect heuristic h^*. Whereas h⁺ and additive pattern database heuristics usually return cost estimates proportional to the true cost, non-additive h^m and non-additive pattern-database heuristics can yield results underestimating the true cost by arbitrarily large factors.
Silvia Richter, Malte Helmert und Matthias Westphal.
Landmarks Revisited.
In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI 2008), S. 975-982. AAAI Press 2008.
Note: After publication, we found a bug in our implementation that affects the results in the columns "CG heuristic/local" and "blind heuristic/local" of Table 1. The version of the paper available for download here corrects these errors.
(Abstract einblenden) (Abstract ausblenden) (PDF) (slides; PDF)

Landmarks for propositional planning tasks are variable assignments that must occur at some point in every solution plan. We propose a novel approach for using landmarks in planning by deriving a pseudo-heuristic and combining it with other heuristics in a search framework. The incorporation of landmark information is shown to improve success rates and solution qualities of a heuristic planner. We furthermore show how additional landmarks and orderings can be found using the information present in multi-valued state variable representations of planning tasks. Compared to previously published approaches, our landmark extraction algorithm provides stronger guarantees of correctness for the generated landmark orderings, and our novel use of landmarks during search solves more planning tasks and delivers considerably better solutions.
Malte Helmert.
Understanding Planning Tasks: Domain Complexity and Heuristic Decomposition.
Band 4929 von Lecture Notes in Artificial Intelligence.
Springer-Verlag, Heidelberg 2008.
(Springer Online)

2007

Malte Helmert, Patrik Haslum und Jörg Hoffmann.
Flexible Abstraction Heuristics for Optimal Sequential Planning.
In Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling (ICAPS 2007), S. 176-183. AAAI Press 2007.
(Abstract einblenden) (Abstract ausblenden) (PDF)

We describe an approach to deriving consistent heuristics for automated planning, based on explicit search in abstract state spaces. The key to managing complexity is interleaving composition of abstractions over different sets of state variables with abstraction of the partial composites.

The approach is very general and can be instantiated in many different ways by following different abstraction strategies. In particular, the technique subsumes planning with pattern databases as a special case. Moreover, with suitable abstraction strategies it is possible to derive perfect heuristics in a number of classical benchmark domains, thus allowing their optimal solution in polynomial time.

To evaluate the practical usefulness of the approach, we perform empirical experiments with one particular abstraction strategy. Our results show that the approach is competitive with the state of the art.
Malte Helmert und Gabriele Röger.
How Good is Almost Perfect?
In Proceedings of the ICAPS-2007 Workshop on Heuristics for Domain-independent Planning: Progress, Ideas, Limitations, Challenges. 2007.
Superseded by the AAAI 2008 paper by the same name.
(Abstract einblenden) (Abstract ausblenden) (PDF)

Heuristic search using algorithms such as A* and IDA* is the prevalent method for obtaining optimal sequential solutions for classical planning tasks. Theoretical analyses of these classical search algorithms, such as the well-known results of Pohl, Gaschnig and Pearl, suggest that such heuristic search algorithms can obtain better than exponential scaling behaviour, provided that the heuristics are accurate enough.

Here, we show that for a number of common planning benchmark domains, including ones that admit optimal solution in polynomial time, general search algorithms such as A* must necessarily explore an exponential number of search nodes even under the optimistic assumption of almost perfect heuristic estimators, whose heuristic error is bounded by a small additive constant.

Our results shed some light on the comparatively bad performance of optimal heuristic search approaches in "simple" domains such as GRIPPER. They suggest that in many domains, further improvements in run-time require changes to other parts of the planning algorithm than the heuristic estimator.
Malte Helmert und Robert Mattmüller.
On the Accuracy of Admissible Heuristic Functions in Selected Planning Domains.
In Proceedings of the ICAPS-2007 Workshop on Heuristics for Domain-independent Planning: Progress, Ideas, Limitations, Challenges. 2007.
Superseded by the AAAI 2008 paper by the same name.
(Abstract einblenden) (Abstract ausblenden) (PDF)

The efficiency of optimal planning algorithms based on heuristic search crucially depends on the accuracy of the heuristic function used to guide the search. Often, we are interested in domain-independent heuristics for planning. In assessing the limitations of domain-independent heuristic planning, it appears interesting to analyse the (in)accuracy of common domain-independent planning heuristics in the IPC benchmark domains. For a selection of these domains, we analytically investigate the accuracy of the h⁺ heuristic, the h^k family of heuristics, and certain (additive) pattern database heuristics, compared to the optimal heuristic h^*. Whereas h⁺ and additive pattern database heuristics usually return cost estimates proportional to the true cost, non-additive h^k and non-additive pattern-database heuristics can yield results underestimating the true cost by arbitrarily large factors.
Silvia Richter, Malte Helmert und Charles Gretton.
A Stochastic Local Search Approach to Vertex Cover.
In Proceedings of the 30th Annual German Conference on Artificial Intelligence (KI 2007), S. 412-426. 2007.
(Abstract einblenden) (Abstract ausblenden) (PDF)

We introduce a novel stochastic local search algorithm for the vertex cover problem. Compared to current exhaustive search techniques, our algorithm achieves excellent performance on a suite of problems drawn from the field of biology. We also evaluate our performance on the commonly used DIMACS benchmarks for the related clique problem, finding that our approach is competitive with the current best stochastic local search algorithm for finding cliques. On three very large problem instances, our algorithm establishes new records in solution quality.
Patrik Haslum, Adi Botea, Malte Helmert, Blai Bonet und Sven Koenig.
Domain-Independent Construction of Pattern Database Heuristics for Cost-Optimal Planning.
In Proceedings of the 22nd AAAI Conference on Artificial Intelligence (AAAI 2007), S. 1007-1012. AAAI Press 2007.
(Abstract einblenden) (Abstract ausblenden) (PDF)

Heuristic search is a leading approach to domain-independent planning. For cost-optimal planning, however, existing admissible heuristics are generally too weak to effectively guide the search. Pattern database heuristics (PDBs), which are based on abstractions of the search space, are currently one of the most promising approaches to developing better admissible heuristics. The informedness of PDB heuristics depends crucially on the selection of appropriate abstractions (patterns). Although PDBs have been applied to many search problems, including planning, there are not many insights into how to select good patterns, even manually. What constitutes a good pattern depends on the problem domain, making the task even more difficult for domain-independent planning, where the process needs to be completely automatic and general. We present a novel way of constructing good patterns automatically from the specification of planning problem instances. We demonstrate that this allows a domain-independent planner to solve planning problems optimally in some very challenging domains, including a STRIPS formulation of the Sokoban puzzle.

2006

Malte Helmert, Robert Mattmüller und Sven Schewe.
Selective Approaches for Solving Weak Games.
In Proceedings of the Fourth International Symposium on Automated Technology for Verification and Analysis (ATVA 2006), S. 200-214. Springer-Verlag 2006.
(Abstract einblenden) (Abstract ausblenden) (PDF)

Model-checking alternating-time properties has recently attracted much interest in the verification of distributed protocols. While checking the validity of a specification in alternating-time temporal logic (ATL) against an explicit model is cheap (linear in the size of the formula and the model), the problem becomes EXPTIME-hard when symbolic models are considered. Practical ATL model-checking therefore often consumes too much computation time to be tractable.

In this paper, we describe a novel approach for ATL model-checking, which constructs an explicit weak model-checking game on-the-fly. This game is then evaluated using heuristic techniques inspired by efficient evaluation algorithms for and/or-trees.

To show the feasibility of our approach, we compare its performance to the ATL model-checking system MOCHA on some practical examples. Using very limited heuristic guidance, we achieve a significant speedup on these benchmarks.
Malte Helmert, Robert Mattmüller und Gabriele Röger.
Approximation Properties of Planning Benchmarks.
In Proceedings of the 17th European Conference on Artificial Intelligence (ECAI 2006), S. 585-589. 2006.
(Abstract einblenden) (Abstract ausblenden) (PDF)

For many classical planning domains, the computational complexity of non-optimal and optimal planning is known. However, little is known about the area in between the two extremes of finding some plan and finding optimal plans. In this contribution, we provide a complete classification of the propositional domains from the first four International Planning Competitions with respect to the approximation classes PO, PTAS, APX, poly-APX, and NPO.
Malte Helmert.
New Complexity Results for Classical Planning Benchmarks.
In Proceedings of the Sixteenth International Conference on Automated Planning and Scheduling (ICAPS 2006), S. 52-61. AAAI Press 2006.
(Abstract einblenden) (Abstract ausblenden) (PDF)

The 3rd and 4th International Planning Competitions have enriched the set of benchmarks for classical propositional planning by a number of novel and interesting planning domains. Although they are commonly used for the purpose of evaluating planner performance, the planning domains themselves have not yet been studied in depth. In this contribution, we prove complexity results for the decision problems related to finding some plan, finding an optimal sequential plan, and finding an optimal parallel plan in these planning domains. Our results also provide some insights into the question why planning is hard for some of the domains under consideration.
Sebastian Kupferschmid und Malte Helmert.
A Skat Player Based on Monte Carlo Simulation.
In H. Jaap van den Herik, Paolo Ciancarini und H. H. L. M. Donkers (Hrsg.), Proceedings of the Fifth International Conference on Computer and Games (CG 2006), S. 135-147. Springer-Verlag 2006.
(Abstract einblenden) (Abstract ausblenden) (PDF)

We apply Monte Carlo simulation and alpha-beta search to the card game of Skat, which is similar to Bridge, but different enough to require some new algorithmic ideas besides the techniques developed for Bridge. Our Skat-playing program integrates well-known techniques such as move ordering with two new search enhancements. Quasi-symmetry reduction generalizes symmetry reductions, popularized by Ginsberg's Partition Search algorithm, to search states which are "almost equivalent". Adversarial heuristics generalize ideas from single-agent search algorithms like A* to two-player games, leading to guaranteed lower and upper bounds for the score of a game position. Combining these techniques with state-of-the-art tree search algorithms, our program determines the game-theoretical value of a typical Skat hand (with perfect information) in 10 milliseconds.
Malte Helmert.
The Fast Downward Planning System.
Journal of Artificial Intelligence Research 26, S. 191-246. 2006.
(Abstract einblenden) (Abstract ausblenden) (PDF)

Fast Downward is a classical planning system based on heuristic search. It can deal with general deterministic planning problems encoded in the propositional fragment of PDDL2.2, including advanced features like ADL conditions and effects and derived predicates (axioms). Like other well-known planners such as HSP and FF, Fast Downward is a progression planner, searching the space of world states of a planning task in the forward direction. However, unlike other PDDL planning systems, Fast Downward does not use the propositional PDDL representation of a planning task directly. Instead, the input is first translated into an alternative representation called multi-valued planning tasks, which makes many of the implicit constraints of a propositional planning task explicit. Exploiting this alternative representation, Fast Downward uses hierarchical decompositions of planning tasks for computing its heuristic function, called the causal graph heuristic, which is very different from traditional HSP-like heuristics based on ignoring negative interactionse of operators.

In this article, we give a full account of Fast Downward's approach to solving multi-valued planning tasks. We extend our earlier discussion of the causal graph heuristic to tasks involving axioms and conditional effects and present some novel techniques for search control that are used within Fast Downward's best-first search algorithm: preferred operators transfer the idea of helpful actions from local search to global best-first search, deferred evaluation of heuristic functions mitigates the negative effect of large branching factors on search performance, and multi-heuristic best-first search combines several heuristic evaluation functions within a single search algorithm in an orthogonal way. We also describe efficient data structures for fast state expansion (successor generators and axiom evaluators) and present a new non-heuristic search algorithm called focused iterative-broadening search, which utilizes the information encoded in causal graphs in a novel way.

Fast Downward has proven remarkably successful: It won the "classical" (i.e., propositional, non-optimising) track of the 4th International Planning Competition at ICAPS 2004, following in the footsteps of planners such as FF and LPG. Our experiments show that it also performs very well on the benchmarks of the earlier planning competitions and provide some insights about the usefulness of the new search enhancements.

2004

Malte Helmert.
A Planning Heuristic Based on Causal Graph Analysis.
In Proceedings of the Fourteenth International Conference on Automated Planning and Scheduling (ICAPS 2004), S. 161-170. AAAI Press 2004.
(Abstract einblenden) (Abstract ausblenden) (PDF)

In recent years, heuristic search methods for classical planning have achieved remarkable results. Their most successful representative, the FF algorithm, performs well over a wide spectrum of planning domains and still sets the state of the art for STRIPS planning. However, there are some planning domains in which algorithms like FF and HSP perform poorly because their relaxation method of ignoring the "delete lists" of STRIPS operators loses too much vital information.

Planning domains which have many dead ends in the search space are especially problematic in this regard. In some domains, dead ends are readily found by the human observer yet remain undetected by all propositional planning systems we are aware of. We believe that this is partly because the STRIPS representation obscures the important causal structure of the domain, which is evident to humans.

In this paper, we propose translating STRIPS problems to a planning formalism with multi-valued state variables in order to expose this underlying causal structure. Moreover, we show how this structure can be exploited by an algorithm for detecting dead ends in the search space and by a planning heuristic based on hierarchical problem decomposition.

Our experiments show excellent overall performance on the benchmarks from the international planning competitions.

2003

Malte Helmert.
Complexity results for standard benchmark domains in planning.
Artificial Intelligence 143 (2), S. 219-262. 2003.
(Abstract einblenden) (Abstract ausblenden) (PDF)

The efficiency of AI planning systems is usually evaluated empirically. For the validity of conclusions drawn from such empirical data, the problem set used for evaluation is of critical importance. In planning, this problem set usually, or at least often, consists of tasks from the various planning domains used in the first two international planning competitions, hosted at the 1998 and 2000 AIPS conferences. It is thus surprising that comparatively little is known about the properties of these benchmark domains, with the exception of BLOCKSWORLD, which has been studied extensively by several research groups.

In this contribution, we try to remedy this fact by providing a map of the computational complexity of non-optimal and optimal planning for the set of domains used in the competitions. We identify a common transportation theme shared by the majority of the benchmarks and use this observation to define and analyze a general transportation problem that generalizes planning in several classical domains such as LOGISTICS, MYSTERY and GRIPPER. We then apply the results of that analysis to the actual transportation domains from the competitions. We next examine the remaining benchmarks, which do not exhibit a strong transportation feature, namely SCHEDULE and FREECELL.

Relating the results of our analysis to empirical work on the behavior of the recently very successful FF planning system, we observe that our theoretical results coincide well with data obtained from empirical investigations.

2002

Malte Helmert.
Decidability and Undecidability Results for Planning with Numerical State Variables.
In M. Ghallab, J. Hertzberg und P. Traverso (Hrsg.), Proceedings of the Sixth International Conference on Artificial Intelligence Planning and Scheduling (AIPS 2002), S. 303-312. AAAI Press 2002.
(Abstract einblenden) (Abstract ausblenden) (PDF)

These days, propositional planning can be considered a quite well-understood problem. Good algorithms are known that will solve a wealth of very different and sometimes challenging planning tasks, and theoretical computational properties of both general STRIPS-style planning and the best-known benchmark problems have been established.

However, propositional planning has a major drawback: The formalism is too weak to allow for the easy encoding of many genuinely interesting planning problems, specifically those involving numbers. A recent effort to enhance the PDDL planning language to cope with (among other additions) numerical state variables, to be used at the third international planning competition, has increased interest in these issues.

In this contribution, we analyze "STRIPS with numbers" from a theoretical point of view. Specifically, we show that the introduction of numerical state variables makes the planning problem undecidable in the general case and many restrictions thereof and identify special cases for which we can provide decidability results.

2001

Stefan Edelkamp und Malte Helmert.
The Model Checking Integrated Planning System (MIPS).
AI Magazine 22 (3), S. 67-71. 2001.
(Abstract einblenden) (Abstract ausblenden) (PDF)

MIPS was the first general planning system based on model checking methods. It can handle the STRIPS subset of the PDDL language and some additional features from ADL, namely negative preconditions and (universal) conditional effects. At the AIPS 2000 conference, MIPS was one of five planning systems to be awarded for "Distinguished Performance" in the fully automated track.

This short paper gives a brief introduction to BDDs and explains the basic planning algorithm employed by MIPS, using a simple logistics problem as an example.
Malte Helmert.
On the Complexity of Planning in Transportation Domains.
In A. Cesta und D. Borrajo (Hrsg.), Proceedings of the 6th European Conference on Planning (ECP 2001), S. 349-360. 2001.
(Abstract einblenden) (Abstract ausblenden) (PDF)

The efficiency of AI planning systems is usually evaluated empirically. Some benchmark problems are of particular importance in this context, especially the ones used in the competitions of the 1998 and 2000 AIPS conferences. Many of these benchmarks share a common theme of transporting portables, making use of mobiles traversing a map of locations and roads.

In this contribution, we embed these benchmarks into a well-structured hierarchy of transportation problems and study the computational complexity of optimal and non-optimal planning in this family of domains. We identify the key domain features that make transportation tasks hard and try to shed some light on the recent success of planning systems based on heuristic local search, as observed in the AIPS 2000 competition.
Malte Helmert.
On the Complexity of Planning in Transportation and Manipulation Domains.
Diplomarbeit, Albert-Ludwigs-Universität Freiburg, 2001.
(Abstract einblenden) (Abstract ausblenden) (PDF)

The efficiency of AI planning systems is usually evaluated empirically. Some benchmark problems are of particular importance in this context, especially the ones used in the competitions of the planning conferences AIPS '98 and AIPS 2000. Previously, the behaviour of different planning systems on these problems was only used to judge their relative performance. However, it would be interesting to be able to compare their performance to the theoretical optimum.

To this end, we have studied the computational complexity of these benchmark domains. Grouping them into natural hierarchies of "transportation" and "manipulation" problems, we are now able to state which of the problems are difficult to solve and which of them are not, and can also provide some insights regarding the sources of hardness in these domains. Interestingly, some of the results of this work help to understand the recent success of planning systems based on heuristic local search, as observed in the AIPS 2000 competition.

2000

Stefan Edelkamp und Malte Helmert.
On the Implementation of MIPS.
In Proceedings of the AIPS-2000 Workshop on Model-Theoretic Approaches to Planning. 2000.
(Abstract einblenden) (Abstract ausblenden) (PDF)

Planning is a central topic of AI and provides solutions to problems given in a problem independent formalism. Recent successes in the exploration of model checking and single-agent search problems have led to a generalization of the symbolic exploration method with binary decision diagrams (BDDs).

In this paper we present the use, architecture, implementation and performance of our STRIPS planner MIPS abbreviating intelligent model checking and planning system. With BDD refinements, symbolic and single state heuristic search engines we highlight recent improvements that have been added to the system.

1999

Malte Helmert.
Implementation eines Planers zur symbolischen Exploration mit binären Entscheidungsdiagrammen.
Studienarbeit, Albert-Ludwigs-Universität Freiburg, 1999.
In German.
(Abstract einblenden) (Abstract ausblenden) (PDF)

Diese Studienarbeit befasst sich mit der Konzeption und Implementation eines vollwertigen Planungssystems auf Grundlage von symbolischen Explorationstechniken mithilfe von binären Entscheidungsdiagrammen (BDDs).

Das Planungssystem umfasst einen Parser zum Einlesen von Problemspezifikationen in der Sprache PDDL/STRIPS, ein Modul zur Inferenz einer effizienten binären Zustandskodierung für das spezifizierte Planungsproblem, sowie Module zum Aufbau der Übergangsfunktion und symbolischen Exploration.
Stefan Edelkamp und Malte Helmert.
Exhibiting Knowledge in Planning Problems to Minimize State Encoding Length.
In Maria Fox und Susanne Biundo (Hrsg.), Proceedings of the 5th European Conference on Planning (ECP 1999), S. 135-147. 1999.
(Abstract einblenden) (Abstract ausblenden) (PDF)

In this paper we present a general-purpose algorithm for transforming a planning problem specified in STRIPS into a concise state description for single state or symbolic exploration.

The process of finding a state description consists of four phases. In the first phase we symbolically analyze the domain specification to determine constant and one-way predicates, i.e. predicates that remain unchanged by all operators or toggle in only one direction, respectively.

In the second phase we symbolically merge predicates which leads to a drastic reduction of state encoding size, while in the third phase we constrain the domains of the predicates to be considered by enumerating the operators of the planning problem. The fourth phase combines the result of the previous phases.