Research Group on the Foundations of Artificial Intelligence

(Show all abstracts) (Hide all abstracts)

2009

• Dunbo Cai, Jörg Hoffmann and 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), pp. 50-57. AAAI Press 2009.
  (Show abstract) (Hide abstract) (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 and 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), pp. 162-169. AAAI Press 2009.
  (Show abstract) (Hide 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 and Malte Helmert.
  Preferred Operators and Deferred Evaluation in Satisficing Planning.
  In Proceedings of the 19th International Conference on Automated Planning and Scheduling (ICAPS 2009), pp. 273-280. AAAI Press 2009.
  (Show abstract) (Hide abstract) (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 and 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.
  (Show abstract) (Hide abstract) (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 and Malte Helmert.
  Combining Heuristic Estimators for Satisficing Planning.
  In Proceedings of the 2nd Workshop on Heuristics for Domain-independent Planning at ICAPS 2009. 2009.
  (Show abstract) (Hide abstract) (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 and Malte Helmert.
  Planning with h+ in Theory and Practice.
  In Bärbel Mertsching, Marcus Hund and Zaheer Aziz, Proceedings of the 32nd Annual German Conference on Artificial Intelligence (KI 2009), pp. 9-16. Springer-Verlag 2009.
  (Show abstract) (Hide abstract) (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 and Malte Helmert.
  The Causal Graph Revisited for Directed Model Checking.
  In Jens Palsberg and Zhendong Su, Proceedings of the 16th International Static Analysis Symposium (SAS 2009), pp. 86-101. Springer-Verlag 2009.
  (Show abstract) (Hide 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 International Symposium on Combinatorial Search (SoCS-2009). 2009.
  (PDF)
  

• Jörg Hoffmann, Piergiorgio Bertoli, Malte Helmert and Marco Pistore.
  Message-Based Web Service Composition, Integrity Constraints, and Planning under Uncertainty: A New Connection.
  Journal of Artificial Intelligence Research 35, pp. 49-117. 2009.
  (Show abstract) (Hide abstract) (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, pp. 503-535. 2009.
  (Show abstract) (Hide abstract) (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 and 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), pp. 544-550. AAAI Press 2008.
  (Show abstract) (Hide abstract) (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 and Héctor Geffner.
  Unifying the Causal Graph and Additive Heuristics.
  In Proceedings of the 18th International Conference on Automated Planning and Scheduling (ICAPS 2008), pp. 140-147. AAAI Press 2008.
  (Show abstract) (Hide abstract) (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 and 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), pp. 1547-1550. AAAI Press 2008.
  (Show abstract) (Hide abstract) (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 and Gabriele Röger.
  How Good is Almost Perfect?
  In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI 2008), pp. 944-949. AAAI Press 2008.
  (Show abstract) (Hide abstract) (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 and Robert Mattmüller.
  Accuracy of Admissible Heuristic Functions in Selected Planning Domains.
  In Proceedings of the 23nd AAAI Conference on Artificial Intelligence (AAAI 2008), pp. 938-943. AAAI Press 2008.
  (Show abstract) (Hide abstract) (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 and Matthias Westphal.
  Landmarks Revisited.
  In Proceedings of the 23rd AAAI Conference on Artificial Intelligence (AAAI 2008), pp. 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.
  (Show abstract) (Hide abstract) (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.
  Volume 4929 of Lecture Notes in Artificial Intelligence.
  Springer-Verlag, Heidelberg 2008.
  (Springer Online)
  

2007

• Malte Helmert, Patrik Haslum and Jörg Hoffmann.
  Flexible Abstraction Heuristics for Optimal Sequential Planning.
  In Proceedings of the Seventeenth International Conference on Automated Planning and Scheduling (ICAPS 2007), pp. 176-183. AAAI Press 2007.
  (Show abstract) (Hide abstract) (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 and 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.
  (Show abstract) (Hide abstract) (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 and 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.
  (Show abstract) (Hide abstract) (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 and Charles Gretton.
  A Stochastic Local Search Approach to Vertex Cover.
  In Proceedings of the 30th Annual German Conference on Artificial Intelligence (KI 2007), pp. 412-426. 2007.
  (Show abstract) (Hide abstract) (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 and 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), pp. 1007-1012. AAAI Press 2007.
  (Show abstract) (Hide abstract) (PDF) (PS.GZ)
  

  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 and Sven Schewe.
  Selective Approaches for Solving Weak Games.
  In Proceedings of the Fourth International Symposium on Automated Technology for Verification and Analysis (ATVA 2006), pp. 200-214. Springer-Verlag 2006.
  (Show abstract) (Hide abstract) (PDF) (PS.GZ)
  

  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 and Gabriele Röger.
  Approximation Properties of Planning Benchmarks.
  In Proceedings of the 17th European Conference on Artificial Intelligence (ECAI 2006), pp. 585-589. 2006.
  (Show abstract) (Hide abstract) (PDF) (PS.GZ)
  

  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), pp. 52-61. AAAI Press 2006.
  (Show abstract) (Hide abstract) (PDF) (PS.GZ)
  

  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 and Malte Helmert.
  A Skat Player Based on Monte Carlo Simulation.
  In H. Jaap van den Herik, Paolo Ciancarini and H. H. L. M. Donkers, Proceedings of the Fifth International Conference on Computer and Games (CG 2006), pp. 135-147. Springer-Verlag 2006.
  (Show abstract) (Hide abstract) (PDF) (BIB)
  

  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, pp. 191-246. 2006.
  (Show abstract) (Hide abstract) (PDF) (PS.GZ)
  

  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), pp. 161-170. AAAI Press 2004.
  (Show abstract) (Hide abstract) (PDF) (PS.GZ)
  

  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), pp. 219-262. 2003.
  (Show abstract) (Hide abstract) (PDF) (PS.GZ)
  

  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 and P. Traverso, Proceedings of the Sixth International Conference on Artificial Intelligence Planning and Scheduling (AIPS 2002), pp. 303-312. AAAI Press 2002.
  (Show abstract) (Hide abstract) (PDF) (PS.GZ)
  

  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 and Malte Helmert.
  The Model Checking Integrated Planning System (MIPS).
  AI Magazine 22 (3), pp. 67-71. 2001.
  (Show abstract) (Hide abstract) (PDF) (PS.GZ)
  

  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 and D. Borrajo, Proceedings of the 6th European Conference on Planning (ECP 2001), pp. 349-360. 2001.
  (Show abstract) (Hide abstract) (PDF) (PS.GZ)
  

  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.
  Diploma thesis, Albert-Ludwigs-Universität Freiburg, 2001.
  (Show abstract) (Hide abstract) (PDF) (PS.GZ)
  

  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 and Malte Helmert.
  On the Implementation of MIPS.
  In Proceedings of the AIPS-2000 Workshop on Model-Theoretic Approaches to Planning. 2000.
  (Show abstract) (Hide abstract) (PDF) (PS.GZ)
  

  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.
  Student project, Albert-Ludwigs-Universität Freiburg, 1999.
  In German.
  (Show abstract) (Hide abstract) (PDF) (PS.GZ)
  

  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 and Malte Helmert.
  Exhibiting Knowledge in Planning Problems to Minimize State Encoding Length.
  In Maria Fox and Susanne Biundo, Proceedings of the 5th European Conference on Planning (ECP 1999), pp. 135-147. 1999.
  (Show abstract) (Hide abstract) (PDF) (PS.GZ)
  

  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.