Publications

2024

1. David Speck and Daniel Gnad

   Decoupled Search for the Masses: A Novel Task Transformation for Classical Planning

   In Proceedings of the Thirty-Fourth International Conference on Automated Planning and Scheduling (ICAPS 2024). 2024.

   Abs Bib Code Data PDF

   Automated problem reformulation is a common technique in classical planning to identify and exploit problem structures. Decoupled search is an approach that automatically decomposes planning tasks based on their causal structure, often significantly reducing the search effort. However, its broad applicability is limited by the need for specialized algorithms. In this paper, we present an approach that embodies decoupled search for non-optimal planning through a novel task transformation. Specifically, given a task and a decomposition, we create a transformed task such that the state space of the transformed task is isomorphic to that of decoupled search on the original task. This eliminates the need for specialized algorithms and allows the use of various planning technology in the decoupled-search framework. Empirical evaluation shows that our method is empirically competitive with specialized decoupled algorithms and favorable to other related problem reformulation techniques.

   @inproceedings{speck-gnad-icaps2024,
     author = {Speck, David and Gnad, Daniel},
     title = {Decoupled Search for the Masses: A Novel Task Transformation for Classical Planning},
     editor = {Bernardini, Sara and Muise, Christian},
     booktitle = {Proceedings of the Thirty-Fourth International Conference on Automated Planning and Scheduling (ICAPS 2024)},
     year = {2024},
     publisher = {AAAI Press}
   }

2. Paul Höft,  David Speck, Florian Pommerening and Jendrik Seipp

   Versatile Cost Partitioning with Exact Sensitivity Analysis

   In Proceedings of the Thirty-Fourth International Conference on Automated Planning and Scheduling (ICAPS 2024). 2024.

   Abs Bib Code Data PDF

   Saturated post-hoc optimization is a powerful method for computing admissible heuristics for optimal classical planning. The approach solves a linear program (LP) for each state encountered during the search, which is computationally demanding. In this paper, we theoretically and empirically analyze to which extent we can reuse an LP solution of one state for another. We introduce a novel sensitivity analysis that can exactly characterize the set of states for which a unique LP solution is optimal. Furthermore, we identify two properties of the underlying LPs that affect reusability. Finally, we introduce an algorithm that optimizes LP solutions to generalize well to other states. Our new algorithms significantly reduce the number of necessary LP computations.

   @inproceedings{hoeft-et-al-icaps2024,
     author = {H{\"o}ft, Paul and Speck, David and Pommerening, Florian and Seipp, Jendrik},
     title = {Versatile Cost Partitioning with Exact Sensitivity Analysis},
     editor = {Bernardini, Sara and Muise, Christian},
     booktitle = {Proceedings of the Thirty-Fourth International Conference on Automated Planning and Scheduling (ICAPS 2024)},
     year = {2024},
     publisher = {AAAI Press}
   }

2023

1. Paul Höft,  David Speck and Jendrik Seipp

   Sensitivity Analysis for Saturated Post-hoc Optimization in Classical Planning

   In Proceedings of the Twenty-Sixth European Conference on Artificial Intelligence (ECAI 2023). 2023.

   Abs Bib Code Data PDF

   Cost partitioning is the foundation of today’s strongest heuristics for optimal classical planning. However, computing a cost partitioning for each evaluated state is prohibitively expensive in practice. Thus, existing approaches make an approximation and compute a cost partitioning only for a set of sampled states, and then reuse the resulting heuristics for all other states evaluated during the search. In this paper, we present exact methods for cost partitioning heuristics based on linear programming that fully preserve heuristic accuracy while minimizing computational cost. Specifically, we focus on saturated post-hoc optimization and establish several sufficient conditions for when reusing a cost partitioning computed for one state preserves the estimates for other states, mainly based on a sensitivity analysis of the underlying linear program. Our experiments demonstrate that our theoretical results transfer into practice, and that our exact cost partitioning algorithms are competitive with the strongest approximations currently available,while usually requiring fewer linear program evaluations.

   @inproceedings{hoeft-et-al-ecai2023,
     author = {H{\"o}ft, Paul and Speck, David and Seipp, Jendrik},
     title = {Sensitivity Analysis for Saturated Post-hoc Optimization in Classical Planning},
     editor = {Gal, Kobi},
     booktitle = {Proceedings of the Twenty-Sixth European Conference on Artificial Intelligence (ECAI 2023)},
     year = {2023},
     publisher = {IOS Press}
   }

2. Remo Christen, Salomé Eriksson, Michael Katz, Christian Muise, Alice Petrov, Florian Pommerening, Jendrik Seipp, Silvan Sievers and David Speck

   PARIS: Planning Algorithms for Reconfiguring Independent Sets

   In Proceedings of the Twenty-Sixth European Conference on Artificial Intelligence (ECAI 2023). 2023.

   Abs Bib Code Data PDF

   Combinatorial reconfiguration is the problem of transforming one solution of a combinatorial problem into another, where each transformation may only apply small changes to a solution and may not leave the solution space. An important example is the independent set reconfiguration (ISR) problem, where an independent set of a graph (a subset of its vertices without edges between them) has to be transformed into another by a sequence of transformations that can replace a vertex in the current subset such that the new subset is still an independent set. The 1st Combinatorial Reconfiguration Challenge (CoRe Challenge 2022) was a competition focused on the ISR problem. The PARIS team successfully participated with two solvers that model the ISR problem as a planning task and employ different planning techniques for solving it. In this work, we describe these models and solvers. For a fair comparison to competing ISR approaches, we re-run the entire competition under equal computational conditions. Besides showcasing the success of planning technology, we hope that this work will create a cross-fertilization of the two research fields.

   @inproceedings{christen-et-al-ecai2023,
     author = {Christen, Remo and Eriksson, Salom{\'e} and Katz, Michael and Muise, Christian and Petrov, Alice and Pommerening, Florian and Seipp, Jendrik and Sievers, Silvan and Speck, David},
     title = {{PARIS}: Planning Algorithms for Reconfiguring Independent Sets},
     editor = {Gal, Kobi},
     booktitle = {Proceedings of the Twenty-Sixth European Conference on Artificial Intelligence (ECAI 2023)},
     year = {2023},
     publisher = {IOS Press}
   }

3. David Speck, Paul Höft, Daniel Gnad and Jendrik Seipp

   Finding Matrix Multiplication Algorithms with Classical Planning

   In Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling (ICAPS 2023), pp. 411–416. 2023.

   Abs Bib Code Data PDF

   Matrix multiplication is a fundamental operation of linear algebra, with applications ranging from quantum physics to artificial intelligence. Given its importance, enormous resources have been invested in the search for faster matrix multiplication algorithms. Recently, this search has been cast as a single-player game. By learning how to play this game efficiently, the newly-introduced AlphaTensor reinforcement learning agent discovers many new faster algorithms. In this paper, we show that finding matrix multiplication algorithms can also be cast as a classical planning problem. Based on this observation, we introduce a challenging benchmark suite for classical planning and evaluate state-of-the-art planning techniques on it. We analyze the strengths and limitations of different planning approaches in this domain and show that we can use classical planning to find lower bounds and concrete algorithms for matrix multiplication.

   @inproceedings{speck-et-al-icaps2023,
     author = {Speck, David and H{\"o}ft, Paul and Gnad, Daniel and Seipp, Jendrik},
     title = {Finding Matrix Multiplication Algorithms with Classical Planning},
     editor = {Koenig, Sven and Stern, Roni and Vallati, Mauro},
     booktitle = {Proceedings of the Thirty-Third International Conference on
                       Automated Planning and Scheduling (ICAPS 2023)},
     year = {2023},
     publisher = {AAAI Press},
     pages = {411--416}
   }

4. Gregor Behnke,  David Speck, Michael Katz and Shirin Sohrabi

   On Partial Satisfaction Planning with Total-Order HTNs

   In Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling (ICAPS 2023), pp. 42–51. 2023.

   Abs Bib Code Data PDF

   Since its introduction, partial satisfaction planning (PSP), including both oversubscription (OSP) and net-benefit, has received significant attention in the classical planning community. However, hierarchical aspects have been mostly ignored in this context, although several problem domains that form the main motivation for PSP, such as the rover domain, have an inherent hierarchical structure. In this paper, we are taking the necessary steps for facilitating this research direction. First, we formally define hierarchical partial satisfaction planning problems and discuss the usefulness and necessity of this formalism. Second, we present a carefully structured set of benchmarks consisting of OSP and net-benefit problems with hierarchical structure. We describe and analyze the different domains of the benchmark set and the desiderata that are met to provide an interesting and challenging starting point for upcoming research. Third, we introduce various planning techniques that can solve hierarchical OSP problems and investigate their empirical behaviour on our proposed benchmark.

   @inproceedings{behnke-et-al-icaps2023,
     author = {Behnke, Gregor and Speck, David and Katz, Michael and Sohrabi, Shirin},
     title = {On Partial Satisfaction Planning with Total-Order HTNs},
     editor = {Koenig, Sven and Stern, Roni and Vallati, Mauro},
     booktitle = {Proceedings of the Thirty-Third International Conference on
                       Automated Planning and Scheduling (ICAPS 2023)},
     year = {2023},
     publisher = {AAAI Press},
     pages = {42--51}
   }

5. Dominik Drexler, Daniel Gnad, Paul Höft, Jendrik Seipp,  David Speck and Simon Ståhlberg

   Ragnarok

   In Tenth International Planning Competition (IPC-10): Planner Abstracts. 2023.

   Abs Bib Code PDF

   Ragnarok is a sequential portfolio planner that uses several classical planners developed by members of the Representation, Learning and Planning Lab at Linköping University in Sweden. Much like the Norse saga Ragnarök, from whom our portfolio planner takes its name, our component planners battled each other in a training phase, from which we obtained the time slices for each component to create a portfolio that combines their individual strengths. This portfolio participated in and won the Optimal Track of the International Planning Competition 2023. The Ragnarok source code is published online and we recommend to use the latest version with some post-competition fixes, available at https://github.com/ipc2023-classical/planner17/tree/latest.

   @inproceedings{drexler-et-al-ipc2023a,
     title = {Ragnarok},
     author = {Drexler, Dominik and Gnad, Daniel and H{\"o}ft, Paul and Seipp, Jendrik and Speck, David and St{\aa}hlberg, Simon},
     booktitle = {Tenth {I}nternational {P}lanning {C}ompetition ({IPC}-10):
                       Planner Abstracts},
     year = {2023}
   }

6. Dominik Drexler, Jendrik Seipp and David Speck

   Odin: A Planner Based on Saturated Transition Cost Partitioning

   In Tenth International Planning Competition (IPC-10): Planner Abstracts. 2023.

   Abs Bib Code PDF

   This planner abstract describes an optimal classical planner called Odin. Odin uses A* search (Hart, Nilsson, and Raphael 1968) with an admissible heuristic (Pearl 1984) based on abstraction heuristics and saturated transition cost partitioning (Keller et al. 2016) to find optimal plans. Odin’s main strength is in tasks where optimal plans contain the same actions multiple times, which is often the case in transportation domains.

   @inproceedings{drexler-et-al-ipc2023b,
     title = {Odin: A Planner Based on Saturated Transition Cost Partitioning},
     author = {Drexler, Dominik and Seipp, Jendrik and Speck, David},
     booktitle = {Tenth {I}nternational {P}lanning {C}ompetition ({IPC}-10):
                       Planner Abstracts},
     year = {2023}
   }

7. David Speck

   SymK – A Versatile Symbolic Search Planner

   In Tenth International Planning Competition (IPC-10): Planner Abstracts. 2023.

   Abs Bib Code PDF

   SymK is a planner that performs symbolic search using Binary Decision Diagrams to find a single optimal or the best k plans. It is designed to be a versatile planner by supporting several important and expressive extensions to the classical planning formalism. Our planner, SymK, therefore natively supports features relevant for compact modeling of planning tasks, such as conditional effects and derived predicates with axioms.

   @inproceedings{speck-ipc2023,
     title = {{SymK} -- {A} Versatile Symbolic Search Planner},
     author = {Speck, David},
     booktitle = {Tenth {I}nternational {P}lanning {C}ompetition ({IPC}-10):
                       Planner Abstracts},
     year = {2023}
   }

8. Paul Höft,  David Speck and Jendrik Seipp

   Dofri: Planner Abstract

   In Tenth International Planning Competition (IPC-10): Planner Abstracts. 2023.

   Abs Bib Code PDF

   Cost partitioning is the foundation of today’s strongest heuristics for optimal classical planning. Many cost partitioning algorithms use linear programs (LPs) to compute the heuristic value. In practice, it is often too time-consuming to solve a separate LP for each state, so it is necessary to approximate the heuristic. Our planner, Dofri, uses a refined version of the Saturated Post-hoc Optimization heuristic that reduces the computational cost without approximating the heuristic. This is done by simplifying the LPs and avoiding duplicate computations so that we can precisely compute the heuristics for each state without sacrificing heuristic quality.

   @inproceedings{hoeft-et-al-ipc2023,
     title = {Dofri: Planner Abstract},
     author = {H{\"o}ft, Paul and Speck, David and Seipp, Jendrik},
     booktitle = {Tenth {I}nternational {P}lanning {C}ompetition ({IPC}-10):
                       Planner Abstracts},
     year = {2023}
   }

2022

1. Kilian Hu and David Speck

   On Bidirectional Heuristic Search in Classical Planning: An Analysis of BAE*

   In Proceedings of the 15th Annual Symposium on Combinatorial Search (SoCS 2022), pp. 91–99. 2022.

   Abs Bib Code Data PDF

   Heuristic search is a successful approach to cost-optimal planning. Bidirectional heuristic search algorithms have been around for a long time, but only recent advances have led to algorithms like BAE* that have the potential to outperform unidirectional heuristic search algorithms like A* in practice. In this work, we analyze BAE* for classical planning and the challenges associated with the underlying assumption of an explicit state representation. We show that it is crucial to use mutexes and reachability analysis to reduce the potentially exponential number of goal states, which makes it possible to create an explicit representation of a reversed planning task that can be used for the backward search of BAE*. Our empirical evaluation shows that BAE* solves more instances than A* in multiple domains with significantly fewer node expansions, demonstrating the usefulness of BAE* in planning.

   @inproceedings{hu-speck-socs2022,
     author = {Hu, Kilian and Speck, David},
     title = {On Bidirectional Heuristic Search in Classical Planning: An Analysis of BAE*},
     editor = {Chrpa, Luk{\'a}{\v{s}} and Saetti, Alessandro},
     booktitle = {Proceedings of the 15th Annual Symposium on Combinatorial Search (SoCS 2022)},
     year = {2022},
     publisher = {AAAI Press},
     pages = {91--99}
   }

2. Remo Christen, Salomé Eriksson, Michael Katz, Emil Keyder, Christian Muise, Alice Petrov, Florian Pommerening, Jendrik Seipp, Silvan Sievers and David Speck

   (PARIS) Planning Algorithms for Reconfiguring Independent Sets – Solver Description

   In First CoRe Challenge: Solver and Graph Descriptions, pp. 15–22. 2022.

   Abs Bib PDF

   The general approach to all of the solver tracks was to model the ISR problem as one of automated planning, and use a selection of state-of-the-art solvers to solve these instances. Throughout this document, we describe the encoding, solvers, and overall search setup.

   @inproceedings{christen-et-al-core2022,
     author = {Christen, Remo and Eriksson, Salom{\'e} and Katz, Michael and Keyder, Emil and Muise, Christian and Petrov, Alice and Pommerening, Florian and Seipp, Jendrik and Sievers, Silvan and Speck, David},
     title = {({PARIS}) Planning Algorithms for Reconfiguring Independent Sets -- Solver Description},
     year = {2022},
     editor = {Soh, Takehide and Okamoto, Yoshio and Ito, Takehiro},
     booktitle = {First {CoRe} Challenge: Solver and Graph Descriptions},
     pages = {15--22}
   }

3. André Biedenkapp,  David Speck, Silvan Sievers, Frank Hutter, Marius Lindauer and Jendrik Seipp

   Learning Domain-Independent Policies for Open List Selection

   In ICAPS 2022 Workshop on Bridging the Gap Between AI Planning and Reinforcement Learning (PRL). 2022.

   Abs Bib PDF

   Since its proposal over a decade ago, LAMA has been considered one of the best-performing satisficing classical planners. Its key component is heuristic search with multiple open lists, each using a different heuristic function to order states. Even with a very simple, ad-hoc policy for open list selection, LAMA achieves state-of-the-art results. In this paper, we propose to use dynamic algorithm configuration to learn such policies in a principled and data-driven manner. On the learning side, we show how to train a reinforcement learning agent over several heterogeneous environments, aiming at zero-shot generalization to new related domains. On the planning side, our experimental results show that the trained policies often reach the performance of LAMA, and sometimes even perform better. Furthermore, our analysis of different policies shows that prioritizing states reached via preferred operators is crucial, explaining the strong performance of LAMA.

   @inproceedings{biedenkapp-et-al-icaps2022wsprl,
     title = {Learning Domain-Independent Policies for Open List Selection},
     author = {Biedenkapp, Andr{\'e} and Speck, David and Sievers, Silvan and Hutter, Frank and Lindauer, Marius and Seipp, Jendrik},
     booktitle = {ICAPS 2022 Workshop on Bridging the Gap Between AI Planning and Reinforcement Learning (PRL)},
     year = {2022}
   }

4. David Speck and Jendrik Seipp

   New Refinement Strategies for Cartesian Abstractions

   In Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling (ICAPS 2022), pp. 348–352. 2022.

   Abs Bib Code Data PDF

   Cartesian counterexample-guided abstraction refinement (CEGAR) yields strong heuristics for optimal classical planning. CEGAR repeatedly finds counterexamples, i.e., abstract plans that fail for the concrete task. Although there are usually many such abstract plans to choose from, the refinement strategy from previous work is to choose an arbitrary optimal one. In this work, we show that an informed refinement strategy is critical in theory and practice. We demonstrate that it is possible to execute all optimal abstract plans in the concrete task simultaneously, and present methods to minimize the time and number of refinement steps until we find a concrete solution. The resulting algorithm solves more tasks than the previous state of the art for Cartesian CEGAR, both during refinement and when used as a heuristic in an A* search.

   @inproceedings{speck-seipp-icaps2022,
     author = {Speck, David and Seipp, Jendrik},
     title = {New Refinement Strategies for Cartesian Abstractions},
     editor = {Thi{\'e}baux, Sylvie and Yeoh, William},
     booktitle = {Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling (ICAPS 2022)},
     year = {2022},
     publisher = {AAAI Press},
     pages = {348--352}
   }

5. Julian von Tschammer, Robert Mattmüller and David Speck

   Loopless Top-K Planning

   In Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling (ICAPS 2022), pp. 380–384. 2022.

   Abs Bib Code PDF

   In top-k planning, the objective is to determine a set of k cheapest plans that provide several good alternatives to choose from. Such a solution set often contains plans that visit at least one state more than once. Depending on the application, plans with such loops are of little importance because they are dominated by a loopless representative and can prevent more meaningful plans from being found.

   In this paper, we motivate and introduce loopless top-k planning. We show how to enhance the state-of-the-art symbolic top-k planner, symK, to obtain an efficient, sound and complete algorithm for loopless top-k planning. An empirical evaluation shows that our proposed approach has a higher k-coverage than a generate-and-test approach that uses an ordinary top-k planner, which we show to be incomplete in the presence of zero-cost loops.

   @inproceedings{vontschammer-et-al-icaps2022,
     author = {{von Tschammer}, Julian and Mattm{\"u}ller, Robert and Speck, David},
     title = {Loopless Top-K Planning},
     editor = {Thi{\'e}baux, Sylvie and Yeoh, William},
     booktitle = {Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling (ICAPS 2022)},
     year = {2022},
     publisher = {AAAI Press},
     pages = {380--384}
   }

6. David Speck

   Symbolic Search for Optimal Planning with Expressive Extensions

   PhD thesis, University of Freiburg, Germany, 2022.

   Abs arXiv Bib HTML PDF

   In classical planning, the goal is to derive a course of actions that allows an intelligent agent to move from any situation it finds itself in to one that satisfies its goals. Classical planning is considered domain-independent, i.e., it is not limited to a particular application and can be used to solve different types of reasoning problems. In practice, however, some properties of a planning problem at hand require an expressive extension of the standard classical planning formalism to capture and model them. Although the importance of many of these extensions is well known, most planners, especially optimal planners, do not support these extended planning formalisms. The lack of support not only limits the use of these planners for certain problems, but even if it is possible to model the problems without these extensions, it often leads to increased effort in modeling or makes modeling practically impossible as the required problem encoding size increases exponentially.

   In this thesis, we propose to use symbolic search for cost-optimal planning for different expressive extensions of classical planning, all capturing different aspects of the problem. In particular, we study planning with axioms, planning with state- dependent action costs, oversubscription planning, and top-k planning. For all formalisms, we present complexity and compilability results, highlighting that it is desirable and even necessary to natively support the corresponding features. We analyze symbolic heuristic search and show that the search performance does not always benefit from the use of a heuristic and that the search performance can exponentially deteriorate even under the best possible circumstances, namely the perfect heuristic. This reinforces that symbolic blind search is the dominant symbolic search strategy nowadays, on par with other state-of-the-art cost-optimal planning strategies. Based on this observation and the lack of good heuristics for planning formalisms with expressive extensions, symbolic search turns out to be a strong approach. We introduce symbolic search to support each of the formalisms individually and in combination, resulting in optimal, sound, and complete planning algorithms that empirically compare favorably with other approaches.

   @phdthesis{speck-phd2022,
     author = {Speck, David},
     title = {Symbolic Search for Optimal Planning with Expressive Extensions},
     school = {University of Freiburg, Germany},
     year = {2022}
   }

2021

1. David Speck, David Borukhson, Robert Mattmüller and Bernhard Nebel

   On the Compilability and Expressive Power of State-Dependent Action Costs

   In Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling (ICAPS 2021), pp. 358–366. 2021.

   Abs Bib PDF Poster

   While state-dependent action costs are practically relevant and have been studied before, it is still unclear if they are an essential feature of planning tasks. In this paper, we study to what extent state-dependent action costs are an essential feature by analyzing under which circumstances they can be compiled away. We give a comprehensive classification for combinations of action cost functions and possible cost measures for the compilations.

   Our theoretical results show that if both task sizes and plan lengths are to be preserved polynomially, then the boundary between compilability and non-compilability lies between FP and FPSPACE computable action cost functions (under a mild assumption on the polynomial hierarchy). Preserving task sizes polynomially and plan lengths linearly at the same time is impossible.

   @inproceedings{speck-et-al-icaps2021a,
     author = {Speck, David and Borukhson, David and Mattm{\"u}ller, Robert and Nebel, Bernhard},
     title = {On the Compilability and Expressive Power of State-Dependent Action Costs},
     editor = {Goldman, Robert P. and Biundo, Susanne and Katz, Michael},
     booktitle = {Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling (ICAPS 2021)},
     year = {2021},
     publisher = {AAAI Press},
     pages = {358--366}
   }

2. David Speck, André Biedenkapp, Frank Hutter, Robert Mattmüller and Marius Lindauer

   Learning Heuristic Selection with Dynamic Algorithm Configuration

   In Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling (ICAPS 2021), pp. 597–605. 2021.

   Abs arXiv Bib Code PDF Poster

   A key challenge in satisficing planning is to use multiple heuristics within one heuristic search. An aggregation of multiple heuristic estimates, for example by taking the maximum, has the disadvantage that bad estimates of a single heuristic can negatively affect the whole search. Since the performance of a heuristic varies from instance to instance, approaches such as algorithm selection can be successfully applied. In addition, alternating between multiple heuristics during the search makes it possible to use all heuristics equally and improve performance. However, all these approaches ignore the internal search dynamics of a planning system, which can help to select the most useful heuristics for the current expansion step. We show that dynamic algorithm configuration can be used for dynamic heuristic selection which takes into account the internal search dynamics of a planning system. Furthermore, we prove that this approach generalizes over existing approaches and that it can exponentially improve the performance of the heuristic search. To learn dynamic heuristic selection, we propose an approach based on reinforcement learning and show empirically that domain-wise learned policies, which take the internal search dynamics of a planning system into account, can exceed existing approaches.

   @inproceedings{speck-et-al-icaps2021b,
     author = {Speck, David and Biedenkapp, Andr{\'e} and Hutter, Frank and Mattm{\"u}ller, Robert and Lindauer, Marius},
     title = {Learning Heuristic Selection with Dynamic Algorithm Configuration},
     editor = {Goldman, Robert P. and Biundo, Susanne and Katz, Michael},
     booktitle = {Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling (ICAPS 2021)},
     year = {2021},
     publisher = {AAAI Press},
     pages = {597--605}
   }

3. Dominik Drexler, Jendrik Seipp and David Speck

   Subset-Saturated Transition Cost Partitioning

   In Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling (ICAPS 2021), pp. 131–139. 2021.

   Abs Bib Code Data PDF Poster

   Cost partitioning admissibly combines the information from multiple heuristics for optimal state-space search. One of the strongest cost partitioning algorithms is saturated cost partitioning. It considers the heuristics in sequence and assigns to each heuristic the minimal fraction of the remaining costs that are needed for preserving all heuristic estimates. Saturated cost partitioning has recently been generalized in two directions: first, by allowing to use different costs for the transitions induced by the same operator, and second, by preserving the heuristic estimates for only a subset of states. In this work, we unify these two generalizations and show that the resulting subset-saturated transition cost partitioning algorithm usually yields stronger heuristics than the two generalizations by themselves.

   @inproceedings{drexler-et-al-icaps2021,
     author = {Drexler, Dominik and Seipp, Jendrik and Speck, David},
     title = {Subset-Saturated Transition Cost Partitioning},
     editor = {Goldman, Robert P. and Biundo, Susanne and Katz, Michael},
     booktitle = {Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling (ICAPS 2021)},
     year = {2021},
     publisher = {AAAI Press},
     pages = {131--139}
   }

4. David Speck and Michael Katz

   Symbolic Search for Oversubscription Planning

   In Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI 2021), pp. 11972–11980. 2021.

   Abs Bib Code PDF Poster

   The objective of optimal oversubscription planning is to find a plan that yields an end state with a maximum utility while keeping plan cost under a certain bound. In practice, the situation occurs whenever a large number of possible, often competing goals of varying value exist, or the resources are not sufficient to achieve all goals. In this paper, we investigate the use of symbolic search for optimal oversubscription planning. Specifically, we show how to apply symbolic forward search to oversubscription planning tasks and prove that our approach is sound, complete and optimal. An empirical analysis shows that our symbolic approach favorably competes with explicit state-space heuristic search, the current state of the art for oversubscription planning.

   @inproceedings{speck-katz-aaai2021,
     title = {Symbolic Search for Oversubscription Planning},
     author = {Speck, David and Katz, Michael},
     editor = {Leyton-Brown, Kevin and Mausam},
     booktitle = {Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI 2021)},
     publisher = {AAAI Press},
     year = {2021},
     pages = {11972--11980}
   }

5. Gregor Behnke and David Speck

   Symbolic Search for Optimal Total-Order HTN Planning

   In Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI 2021), pp. 11744–11754. 2021.

   Abs Bib Code PDF Poster

   Symbolic search has proven to be a useful approach to optimal classical planning. In Hierarchical Task Network (HTN) planning, however, there is little work on optimal planning. One reason for this is that in HTN planning, most algorithms are based on heuristic search, and admissible heuristics have to incorporate the structure of the task network in order to be informative. In this paper, we present a novel approach to optimal (totally-ordered) HTN planning, which is based on symbolic search. An empirical analysis shows that our symbolic approach outperforms the current state of the art for optimal totally-ordered HTN planning.

   @inproceedings{behnke-speck-aaai2021,
     title = {Symbolic Search for Optimal Total-Order HTN Planning},
     author = {Behnke, Gregor and Speck, David},
     editor = {Leyton-Brown, Kevin and Mausam},
     booktitle = {Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI 2021)},
     publisher = {AAAI Press},
     year = {2021},
     pages = {11744--11754}
   }

2020

1. David Speck, Florian Geißer and Robert Mattmüller

   When Perfect is not Good Enough: On the Search Behaviour of Symbolic Heuristic Search

   In Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling (ICAPS 2020), pp. 263–271. 2020.

   Abs Bib PDF Poster

   Symbolic search has proven to be a competitive approach to cost-optimal planning, as it compactly represents sets of states by symbolic data structures. While heuristics for symbolic search exist, symbolic bidirectional blind search empirically outperforms its heuristic counterpart and is therefore the dominant search strategy. This prompts the question of why heuristics do not seem to pay off in symbolic search. As a first step in answering this question, we investigate the search behaviour of symbolic heuristic search by means of BDDA*. Previous work identified the partitioning of state sets according to their heuristic values as the main bottleneck. We theoretically and empirically evaluate the search behaviour of BDDA* and reveal another fundamental problem: we prove that the use of a heuristic does not always improve the search performance of BDDA*. In general, even the perfect heuristic can exponentially deteriorate search performance.

   @inproceedings{speck-et-al-icaps2020,
     title = {When Perfect is not Good Enough: On the Search Behaviour of Symbolic Heuristic Search},
     author = {Speck, David and Gei{\ss}er, Florian and Mattm{\"u}ller, Robert},
     editor = {Beck, J. Christopher and Karpas, Erez and Sohrabi, Shirin},
     booktitle = {Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling (ICAPS 2020)},
     publisher = {AAAI Press},
     year = {2020},
     pages = {263--271}
   }

2. David Speck, Robert Mattmüller and Bernhard Nebel

   Symbolic Top-k Planning

   In Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI 2020), pp. 9967–9974. 2020.

   Abs Bib Code PDF Poster

   The objective of top-k planning is to determine a set of k different plans with lowest cost for a given planning task. In practice, such a set of best plans can be preferred to a single best plan generated by ordinary optimal planners, as it allows the user to choose between different alternatives and thus take into account preferences that may be difficult to model. In this paper we show that, in general, the decision problem version of top-k planning is PSPACE-complete, as is the decision problem version of ordinary classical planning. This does not hold for polynomially bounded plans for which the decision problem turns out to be PP-hard, while the ordinary case is NP-hard. We present a novel approach to top-k planning, called SYM-K, which is based on symbolic search, and prove that SYM-K is sound and complete. Our empirical analysis shows that SYM-K exceeds the current state of the art for both small and large k.

   @inproceedings{speck-et-al-aaai2020,
     title = {Symbolic Top-k Planning},
     author = {Speck, David and Mattm{\"u}ller, Robert and Nebel, Bernhard},
     editor = {Conitzer, Vincent and Sha, Fei},
     booktitle = {Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI 2020)},
     publisher = {AAAI Press},
     year = {2020},
     pages = {9967--9974}
   }

3. Florian Geißer,  David Speck and Thomas Keller

   Trial-based Heuristic Tree Search for MDPs with Factored Action Spaces

   In Proceedings of the 13th Annual Symposium on Combinatorial Search (SoCS 2020), pp. 38–47. 2020.

   Abs Bib Code Data PDF

   MDPs with factored action spaces, i.e. where actions are described as assignments to a set of action variables, allow reasoning over action variables instead of action states, yet most algorithms only consider a grounded action representation. This includes algorithms that are instantiations of the trial-based heuristic tree search (THTS) framework, such as AO* or UCT.

   To be able to reason over factored action spaces, we propose a generalisation of THTS where nodes that branch over all applicable actions are replaced with subtrees that consist of nodes that represent the decision for a single action variable. We show that many THTS algorithms retain their theoretical properties under the generalised framework, and show how to approximate any state-action heuristic to a heuristic for partial action assignments. This allows to guide a UCT variant that is able to create exponentially fewer nodes than the same algorithm that considers ground actions. An empirical evaluation on the benchmark set of the probabilistic track of the latest International Planning Competition validates the benefits of the approach.

   @inproceedings{geisser-et-al-socs2020,
     title = {Trial-based Heuristic Tree Search for {MDP}s with Factored Action Spaces},
     author = {Gei{\ss}er, Florian and Speck, David and Keller, Thomas},
     editor = {Harabor, Daniel and Vallati, Mauro},
     booktitle = {Proceedings of the 13th Annual Symposium on Combinatorial Search (SoCS 2020)},
     publisher = {AAAI Press},
     year = {2020},
     pages = {38--47}
   }

2019

1. David Speck, Florian Geißer, Robert Mattmüller and Álvaro Torralba

   Symbolic Planning with Axioms

   In Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling (ICAPS 2019), pp. 464–572. 2019.

   Abs Bib Code PDF

   Axioms are an extension for classical planning models that allow for modeling complex preconditions and goals exponentially more compactly. Although axioms were introduced in planning more than a decade ago, modern planning techniques rarely support axioms, especially in cost-optimal planning. Symbolic search is a popular and competitive optimal planning technique based on the manipulation of sets of states. In this work, we extend symbolic search algorithms to support axioms natively. We analyze different ways of encoding derived variables and axiom rules to evaluate them in a symbolic representation. We prove that all encodings are sound and complete, and empirically show that the presented approach outperforms the previous state of the art in cost-optimal classical planning with axioms.

   @inproceedings{speck-et-al-icaps2019,
     title = {Symbolic Planning with Axioms},
     author = {Speck, David and Gei{\ss}er, Florian and Mattm{\"u}ller, Robert and Torralba, {\'{A}lvaro}},
     editor = {Lipovetzky, Nir and Onaindia, Eva and Smith, David E.},
     booktitle = {Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling (ICAPS 2019)},
     year = {2019},
     publisher = {AAAI Press},
     pages = {464--572}
   }

2. Sumitra Corraya, Florian Geißer,  David Speck and Robert Mattmüller

   An Empirical Study of the Usefulness of State-Dependent Action Costs in Planning

   In Proceedings of the 42nd Annual German Conference on Artificial Intelligence (KI 2019), pp. 123–130. 2019.

   Abs Bib HTML PDF

   The vast majority of work in planning to date has focused on state-independent action costs. However, if a planning task features state-dependent costs, using a cost model with state-independent costs means either introducing a modeling error, or potentially sacrificing compactness of the model. In this paper, we investigate the conflicting priorities of modeling accuracy and compactness empirically, with a particular focus on the extent of the negative impact of reduced modeling accuracy on (a) the quality of the resulting plans, and (b) the search guidance provided by heuristics that are fed with inaccurate cost models. Our empirical results show that the plan suboptimality introduced by ignoring state-dependent costs can range, depending on the domain, from inexistent to several orders of magnitude. Furthermore, our results show that the impact on heuristic guidance additionally depends strongly on the heuristic that is used, the specifics of how exactly the costs are represented, and whether one is interested in heuristic accuracy, node expansions, or overall runtime savings.

   @inproceedings{corraya-et-al-ki2019,
     author = {Corraya, Sumitra and Geißer, Florian and Speck, David and Mattm{\"u}ller, Robert},
     title = {An Empirical Study of the Usefulness of State-Dependent Action Costs in Planning},
     editor = {Benzm{\"u}ller, Christoph and Stuckenschmidt, Heiner},
     booktitle = {Proceedings of the 42nd Annual German Conference on Artificial Intelligence (KI 2019)},
     publisher = {Springer-Verlag},
     series = {Lecture Notes in Artificial Intelligence},
     year = {2019},
     pages = {123--130}
   }

3. Florian Geißer,  David Speck and Thomas Keller

   An Analysis of the Probabilistic Track of the IPC 2018

   In ICAPS 2019 Workshop on the International Planning Competition (WIPC), pp. 27–35. 2019.

   Abs Bib Code Data PDF

   The International Planning Competition 2018 consisted of several tracks on classical, temporal and probabilistic planning. In this paper, we focus on the discrete MDP track of the probabilistic portion of the competition.

   We discuss the changes to the input language RDDL, which give rise to new challenges for planning systems, and analyze each of the eight competition domains separately and highlight unique properties. We demonstrate flaws of the used evaluation criterion, the IPC score, and discuss the need for optimal upper bounds. An evaluation of the three top-performers, including their post-competition versions, and a brief analysis of their performance highlights the strengths and weaknesses of the individual approaches.

   @inproceedings{geisser-et-al-icaps2019wsipc,
     title = {An Analysis of the Probabilistic Track of the {IPC} 2018},
     author = {Gei{\ss}er, Florian and Speck, David and Keller, Thomas},
     booktitle = {ICAPS 2019 Workshop on the International Planning Competition (WIPC)},
     year = {2019},
     pages = {27--35}
   }

4. Olga Speck, Rafael Horn,  David Speck, Johannes Gantner and Philip Leistner

   Biomimetics meets Sustainability

   In Bionik: Patente aus der Natur. Tagungsbeiträge zum 9. Bionik-Kongress, pp. 81–91. 2019.

   Abs Bib HTML

   Sustainable development is a challenge that needs to be tackled by social consensus. Learning from nature is linked to the hope of learning from biological solutions that have extraordinary qualities. One focus of the publication is to refine the discussion about technology-derived and biology-derived developments by taking descriptive, normative and emotional aspects into consideration. Descriptive aspects are presented on the basis of a straightforward classification tool (decision tree) to clearly describe, distinguish and identify biology-derived and technology-derived developments. A further focus of the article is the presentation of the concept of bioinspired sustainability and the presentation of an evaluation tree for Bioinspired Sustainability Assessment (BiSA).

   @inproceedings{speck-et-al-bk2019,
     author = {Speck, Olga and Horn, Rafael and Speck, David and Gantner, Johannes and Leistner, Philip},
     title = {Biomimetics meets Sustainability},
     booktitle = {Bionik: Patente aus der Natur. Tagungsbeiträge zum 9. Bionik-Kongress},
     year = {2019},
     pages = {81--91}
   }

2018

1. David Speck, Florian Geißer and Robert Mattmüller

   Symbolic Planning with Edge-Valued Multi-Valued Decision Diagrams

   In Proceedings of the Twenty-Eighth International Conference on Automated Planning and Scheduling (ICAPS 2018). 2018.

   Abs Bib Code PDF Poster Supp

   Symbolic representations have attracted significant attention in optimal planning. Binary Decision Diagrams (BDDs) form the basis for symbolic search algorithms. Closely related are Algebraic Decision Diagrams (ADDs), used to represent heuristic functions. Also, progress was made in dealing with models that take state-dependent action costs into account. Here, costs are represented as Edge-valued Multi-valued Decision Diagrams (EVMDDs), which can be exponentially more compact than the corresponding ADD representation. However, they were not yet considered for symbolic planning.

   In this work, we study EVMDD-based symbolic search for optimal planning. We define EVMDD-based representations of state sets and transition relations, and show how to compute the necessary operations required for EVMDD-A*. This EVMDD-based version of symbolic A* generalizes its BDD variant, and allows to solve planning tasks with state-dependent action costs. We prove theoretically that our approach is sound, complete and optimal. Additionally, we present an empirical analysis comparing EVMDD-A* to BDD-A* and explicit A* search. Our results underscore the usefulness of symbolic approaches and the feasibility of dealing with models that go beyond unit costs.

   @inproceedings{speck-et-al-icaps2018,
     title = {Symbolic Planning with Edge-Valued Multi-Valued Decision Diagrams},
     author = {Speck, David and Gei{\ss}er, Florian and Mattm{\"u}ller, Robert},
     editor = {de Weerdt, Mathijs and Koenig, Sven and R{\"o}ger, Gabriele and Spaan, Matthijs},
     booktitle = {Proceedings of the Twenty-Eighth International Conference on Automated Planning and Scheduling (ICAPS 2018)},
     year = {2018},
     publisher = {AAAI Press}
   }

2. Florian Geißer and David Speck

   Prost-DD – Utilizing Symbolic Classical Planning in THTS

   In Sixth International Probabilistic Planning Competition (IPPC-6): Planner Abstracts, pp. 13–16. 2018.

   Abs Bib Code PDF

   We describe PROST-DD, our submission to the International Probabilistic Planning Competition 2018. Like its predecessor PROST, which already participated with success at the previous IPPC, PROST-DD is based on the trial-based heuristic tree search framework and applies the UCT* algorithm. The novelty of our submission is the heuristic used to initialize newly encountered decision nodes. We apply an iterative symbolic backward planning approach based on the determinized task. Similarly to the SPUDD approach and recent work in symbolic planning with state-dependent action costs, we encode costs and reachability of states in a single decision diagram. During initialization, these diagrams are then used to query a state for its estimated expected reward. One benefit of this heuristic is that we can optionally interweave the standard heuristic of PROST, the IDS heuristic.

   @inproceedings{geisser-speck-ippc2018,
     author = {Gei{\ss}er, Florian and Speck, David},
     title = {{Prost-DD} -- Utilizing Symbolic Classical Planning in {THTS}},
     booktitle = {Sixth International Probabilistic Planning Competition ({IPPC}-6): Planner Abstracts},
     year = {2018},
     pages = {13--16}
   }

3. David Speck, Florian Geißer and Robert Mattmüller

   SYMPLE: Symbolic Planning based on EVMDDs

   In Ninth International Planning Competition (IPC-9): Planner Abstracts, pp. 82–85. 2018.

   Abs Bib Code PDF

   SYMPLE is a classical planner which performs bidirectional symbolic search. Symbolic search has proven to be a useful approach to optimal classical planning and is usually based on Binary Decision Diagrams (BDDs). Our approach is based on an alternative data structure called Edge-valued Multi-valued Decision Diagrams (EVMDDs), which have some structural advantages over BDDs.

   @inproceedings{speck-et-al-ipc2018,
     title = {{SYMPLE}: {S}ymbolic Planning based on {EVMDD}s},
     author = {Speck, David and Gei{\ss}er, Florian and Mattm{\"u}ller, Robert},
     booktitle = {Ninth International Planning Competition ({IPC}-9): Planner Abstracts},
     year = {2018},
     pages = {82--85}
   }

2017

1. David Speck, Christian Dornhege and Wolfram Burgard

   Shakey 2016 - How Much Does it Take to Redo Shakey the Robot?

   IEEE Robotics and Automation Letters (RA-L) 2.2, pp. 1203–1209. 2017.

   Abs Bib Code HTML PDF

   Shakey the robot was one of the first autonomous robots that showed impressive capabilities of navigation and mobile manipulation. Since then, robotics research has made great progress, showing more and more capable robotic systems for a large variety of application domains and tasks. In this letter, we look back on decades of research by rebuilding Shakey with modern robotics technology in the open-source Shakey 2016 system. Hereby, we demonstrate the impact of research by showing that ideas from the original Shakey are still alive in state-of-the-art systems, while robotics in general has improved to deliver more robust and more capable software and hardware. Our Shakey 2016 system has been implemented on real robots and leverages mostly open-source software. We experimentally evaluate the system in real-world scenarios on a PR2 robot and a Turtlebot-based robot and particularly investigate the development effort. The experiments documented in this letter demonstrate that results from robotics research are readily available for building complex robots such as Shakey within a short amount of time and little effort.

   @article{speck-et-al-ral2017,
     author = {Speck, David and Dornhege, Christian and Burgard, Wolfram},
     title = {Shakey 2016 - How Much Does it Take to Redo Shakey the Robot?},
     journal = {IEEE Robotics and Automation Letters (RA-L)},
     year = {2017},
     volume = {2},
     number = {2},
     pages = {1203--1209}
   }

2. Olga Speck,  David Speck, Rafael Horn, Johannes Gantner and Klaus Peter Sedlbauer

   Biomimetic bio-inspired biomorph sustainable? An attempt to classify and clarify biology-derived technical developments

   Bioinspiration and Biomimetics 12.1, pp. 011004. 2017.

   Abs Bib HTML PDF

   Over the last few decades, the systematic approach of knowledge transfer from biological concept generators to technical applications has received increasing attention, particularly because marketable bio-derived developments are often described as sustainable. The objective of this paper is to rationalize and refine the discussion about bio-derived developments also with respect to sustainability by taking descriptive, normative and emotional aspects into consideration. In the framework of supervised learning, a dataset of 70 biology-derived and technology-derived developments characterised by 9 different attributes together with their respective values and assigned to one of 17 classes was created. On the basis of the dataset a decision tree was generated which can be used as a straightforward classification tool to identify biology-derived and technology-derived developments. The validation of the applied learning procedure achieved an average accuracy of 90.0%. Additional extraordinary qualities of technical applications are generally discussed by means of selected biologyderived and technology-derived examples with reference to normative (contribution to sustainability) and emotional aspects(aesthetics and symbolic character). In the context of a case study from the building sector, all aspects are critically discussed.

   @article{speck-et-al-bandb2017,
     author = {Speck, Olga and Speck, David and Horn, Rafael and Gantner, Johannes and Sedlbauer, Klaus Peter},
     title = {Biomimetic bio-inspired biomorph sustainable? {A}n attempt to classify and clarify biology-derived technical developments},
     journal = {Bioinspiration and Biomimetics},
     year = {2017},
     volume = {12},
     number = {1},
     pages = {011004}
   }

2015

1. David Speck, Manuela Ortlieb and Robert Mattmüller

   Necessary Observations in Nondeterministic Planning

   In Proceedings of the 38th Annual German Conference on Artificial Intelligence (KI 2015), pp. 181–193. 2015.

   Abs Bib PDF

   An agent that interacts with a nondeterministic environment can often only partially observe the surroundings. This necessitates observations via sensors rendering more information about the current world state. Sensors can be expensive in many regards therefore it can be essential to minimize the amount of sensors an agent requires to solve given tasks. A limitation for sensor minimization is given by essential sensors which are always required to solve particular problems. In this paper we present an efficient algorithm which determines a set of necessary observation variables. More specifically, we develop a bottom-up algorithm which computes a set of variables which are always necessary to observe, in order to always reach a goal state. Our experimental results show that the knowledge about necessary observation variables can be used to minimize the number of sensors of an agent.

   @inproceedings{speck-et-al-ki2015,
     title = {Necessary Observations in Nondeterministic Planning},
     author = {Speck, David and Ortlieb, Manuela and Mattm{\"u}ller, Robert},
     editor = {H{\"o}lldobler, Steffen and Kr{\"o}tzsch, Markus and Pe{\~n}aloza-Nyssen, Rafael and Rudolph, Sebastian},
     booktitle = {Proceedings of the 38th Annual German Conference on Artificial Intelligence (KI 2015)},
     publisher = {Springer-Verlag},
     series = {Lecture Notes in Artificial Intelligence},
     volume = {9324},
     year = {2015},
     pages = {181--193}
   }

2024

1. David Speck and Daniel Gnad

   Decoupled Search for the Masses: A Novel Task Transformation for Classical Planning

   In Proceedings of the Thirty-Fourth International Conference on Automated Planning and Scheduling (ICAPS 2024). 2024.

   Abs Bib Code Data PDF

   Automated problem reformulation is a common technique in classical planning to identify and exploit problem structures. Decoupled search is an approach that automatically decomposes planning tasks based on their causal structure, often significantly reducing the search effort. However, its broad applicability is limited by the need for specialized algorithms. In this paper, we present an approach that embodies decoupled search for non-optimal planning through a novel task transformation. Specifically, given a task and a decomposition, we create a transformed task such that the state space of the transformed task is isomorphic to that of decoupled search on the original task. This eliminates the need for specialized algorithms and allows the use of various planning technology in the decoupled-search framework. Empirical evaluation shows that our method is empirically competitive with specialized decoupled algorithms and favorable to other related problem reformulation techniques.

   @inproceedings{speck-gnad-icaps2024,
     author = {Speck, David and Gnad, Daniel},
     title = {Decoupled Search for the Masses: A Novel Task Transformation for Classical Planning},
     editor = {Bernardini, Sara and Muise, Christian},
     booktitle = {Proceedings of the Thirty-Fourth International Conference on Automated Planning and Scheduling (ICAPS 2024)},
     year = {2024},
     publisher = {AAAI Press}
   }

2. Paul Höft,  David Speck, Florian Pommerening and Jendrik Seipp

   Versatile Cost Partitioning with Exact Sensitivity Analysis

   In Proceedings of the Thirty-Fourth International Conference on Automated Planning and Scheduling (ICAPS 2024). 2024.

   Abs Bib Code Data PDF

   Saturated post-hoc optimization is a powerful method for computing admissible heuristics for optimal classical planning. The approach solves a linear program (LP) for each state encountered during the search, which is computationally demanding. In this paper, we theoretically and empirically analyze to which extent we can reuse an LP solution of one state for another. We introduce a novel sensitivity analysis that can exactly characterize the set of states for which a unique LP solution is optimal. Furthermore, we identify two properties of the underlying LPs that affect reusability. Finally, we introduce an algorithm that optimizes LP solutions to generalize well to other states. Our new algorithms significantly reduce the number of necessary LP computations.

   @inproceedings{hoeft-et-al-icaps2024,
     author = {H{\"o}ft, Paul and Speck, David and Pommerening, Florian and Seipp, Jendrik},
     title = {Versatile Cost Partitioning with Exact Sensitivity Analysis},
     editor = {Bernardini, Sara and Muise, Christian},
     booktitle = {Proceedings of the Thirty-Fourth International Conference on Automated Planning and Scheduling (ICAPS 2024)},
     year = {2024},
     publisher = {AAAI Press}
   }

2023

1. Paul Höft,  David Speck and Jendrik Seipp

   Sensitivity Analysis for Saturated Post-hoc Optimization in Classical Planning

   In Proceedings of the Twenty-Sixth European Conference on Artificial Intelligence (ECAI 2023). 2023.

   Abs Bib Code Data PDF

   Cost partitioning is the foundation of today’s strongest heuristics for optimal classical planning. However, computing a cost partitioning for each evaluated state is prohibitively expensive in practice. Thus, existing approaches make an approximation and compute a cost partitioning only for a set of sampled states, and then reuse the resulting heuristics for all other states evaluated during the search. In this paper, we present exact methods for cost partitioning heuristics based on linear programming that fully preserve heuristic accuracy while minimizing computational cost. Specifically, we focus on saturated post-hoc optimization and establish several sufficient conditions for when reusing a cost partitioning computed for one state preserves the estimates for other states, mainly based on a sensitivity analysis of the underlying linear program. Our experiments demonstrate that our theoretical results transfer into practice, and that our exact cost partitioning algorithms are competitive with the strongest approximations currently available,while usually requiring fewer linear program evaluations.

   @inproceedings{hoeft-et-al-ecai2023,
     author = {H{\"o}ft, Paul and Speck, David and Seipp, Jendrik},
     title = {Sensitivity Analysis for Saturated Post-hoc Optimization in Classical Planning},
     editor = {Gal, Kobi},
     booktitle = {Proceedings of the Twenty-Sixth European Conference on Artificial Intelligence (ECAI 2023)},
     year = {2023},
     publisher = {IOS Press}
   }

2. Remo Christen, Salomé Eriksson, Michael Katz, Christian Muise, Alice Petrov, Florian Pommerening, Jendrik Seipp, Silvan Sievers and David Speck

   PARIS: Planning Algorithms for Reconfiguring Independent Sets

   In Proceedings of the Twenty-Sixth European Conference on Artificial Intelligence (ECAI 2023). 2023.

   Abs Bib Code Data PDF

   Combinatorial reconfiguration is the problem of transforming one solution of a combinatorial problem into another, where each transformation may only apply small changes to a solution and may not leave the solution space. An important example is the independent set reconfiguration (ISR) problem, where an independent set of a graph (a subset of its vertices without edges between them) has to be transformed into another by a sequence of transformations that can replace a vertex in the current subset such that the new subset is still an independent set. The 1st Combinatorial Reconfiguration Challenge (CoRe Challenge 2022) was a competition focused on the ISR problem. The PARIS team successfully participated with two solvers that model the ISR problem as a planning task and employ different planning techniques for solving it. In this work, we describe these models and solvers. For a fair comparison to competing ISR approaches, we re-run the entire competition under equal computational conditions. Besides showcasing the success of planning technology, we hope that this work will create a cross-fertilization of the two research fields.

   @inproceedings{christen-et-al-ecai2023,
     author = {Christen, Remo and Eriksson, Salom{\'e} and Katz, Michael and Muise, Christian and Petrov, Alice and Pommerening, Florian and Seipp, Jendrik and Sievers, Silvan and Speck, David},
     title = {{PARIS}: Planning Algorithms for Reconfiguring Independent Sets},
     editor = {Gal, Kobi},
     booktitle = {Proceedings of the Twenty-Sixth European Conference on Artificial Intelligence (ECAI 2023)},
     year = {2023},
     publisher = {IOS Press}
   }

3. David Speck, Paul Höft, Daniel Gnad and Jendrik Seipp

   Finding Matrix Multiplication Algorithms with Classical Planning

   In Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling (ICAPS 2023), pp. 411–416. 2023.

   Abs Bib Code Data PDF

   Matrix multiplication is a fundamental operation of linear algebra, with applications ranging from quantum physics to artificial intelligence. Given its importance, enormous resources have been invested in the search for faster matrix multiplication algorithms. Recently, this search has been cast as a single-player game. By learning how to play this game efficiently, the newly-introduced AlphaTensor reinforcement learning agent discovers many new faster algorithms. In this paper, we show that finding matrix multiplication algorithms can also be cast as a classical planning problem. Based on this observation, we introduce a challenging benchmark suite for classical planning and evaluate state-of-the-art planning techniques on it. We analyze the strengths and limitations of different planning approaches in this domain and show that we can use classical planning to find lower bounds and concrete algorithms for matrix multiplication.

   @inproceedings{speck-et-al-icaps2023,
     author = {Speck, David and H{\"o}ft, Paul and Gnad, Daniel and Seipp, Jendrik},
     title = {Finding Matrix Multiplication Algorithms with Classical Planning},
     editor = {Koenig, Sven and Stern, Roni and Vallati, Mauro},
     booktitle = {Proceedings of the Thirty-Third International Conference on
                       Automated Planning and Scheduling (ICAPS 2023)},
     year = {2023},
     publisher = {AAAI Press},
     pages = {411--416}
   }

4. Gregor Behnke,  David Speck, Michael Katz and Shirin Sohrabi

   On Partial Satisfaction Planning with Total-Order HTNs

   In Proceedings of the Thirty-Third International Conference on Automated Planning and Scheduling (ICAPS 2023), pp. 42–51. 2023.

   Abs Bib Code Data PDF

   Since its introduction, partial satisfaction planning (PSP), including both oversubscription (OSP) and net-benefit, has received significant attention in the classical planning community. However, hierarchical aspects have been mostly ignored in this context, although several problem domains that form the main motivation for PSP, such as the rover domain, have an inherent hierarchical structure. In this paper, we are taking the necessary steps for facilitating this research direction. First, we formally define hierarchical partial satisfaction planning problems and discuss the usefulness and necessity of this formalism. Second, we present a carefully structured set of benchmarks consisting of OSP and net-benefit problems with hierarchical structure. We describe and analyze the different domains of the benchmark set and the desiderata that are met to provide an interesting and challenging starting point for upcoming research. Third, we introduce various planning techniques that can solve hierarchical OSP problems and investigate their empirical behaviour on our proposed benchmark.

   @inproceedings{behnke-et-al-icaps2023,
     author = {Behnke, Gregor and Speck, David and Katz, Michael and Sohrabi, Shirin},
     title = {On Partial Satisfaction Planning with Total-Order HTNs},
     editor = {Koenig, Sven and Stern, Roni and Vallati, Mauro},
     booktitle = {Proceedings of the Thirty-Third International Conference on
                       Automated Planning and Scheduling (ICAPS 2023)},
     year = {2023},
     publisher = {AAAI Press},
     pages = {42--51}
   }

5. Dominik Drexler, Daniel Gnad, Paul Höft, Jendrik Seipp,  David Speck and Simon Ståhlberg

   Ragnarok

   In Tenth International Planning Competition (IPC-10): Planner Abstracts. 2023.

   Abs Bib Code PDF

   Ragnarok is a sequential portfolio planner that uses several classical planners developed by members of the Representation, Learning and Planning Lab at Linköping University in Sweden. Much like the Norse saga Ragnarök, from whom our portfolio planner takes its name, our component planners battled each other in a training phase, from which we obtained the time slices for each component to create a portfolio that combines their individual strengths. This portfolio participated in and won the Optimal Track of the International Planning Competition 2023. The Ragnarok source code is published online and we recommend to use the latest version with some post-competition fixes, available at https://github.com/ipc2023-classical/planner17/tree/latest.

   @inproceedings{drexler-et-al-ipc2023a,
     title = {Ragnarok},
     author = {Drexler, Dominik and Gnad, Daniel and H{\"o}ft, Paul and Seipp, Jendrik and Speck, David and St{\aa}hlberg, Simon},
     booktitle = {Tenth {I}nternational {P}lanning {C}ompetition ({IPC}-10):
                       Planner Abstracts},
     year = {2023}
   }

6. Dominik Drexler, Jendrik Seipp and David Speck

   Odin: A Planner Based on Saturated Transition Cost Partitioning

   In Tenth International Planning Competition (IPC-10): Planner Abstracts. 2023.

   Abs Bib Code PDF

   This planner abstract describes an optimal classical planner called Odin. Odin uses A* search (Hart, Nilsson, and Raphael 1968) with an admissible heuristic (Pearl 1984) based on abstraction heuristics and saturated transition cost partitioning (Keller et al. 2016) to find optimal plans. Odin’s main strength is in tasks where optimal plans contain the same actions multiple times, which is often the case in transportation domains.

   @inproceedings{drexler-et-al-ipc2023b,
     title = {Odin: A Planner Based on Saturated Transition Cost Partitioning},
     author = {Drexler, Dominik and Seipp, Jendrik and Speck, David},
     booktitle = {Tenth {I}nternational {P}lanning {C}ompetition ({IPC}-10):
                       Planner Abstracts},
     year = {2023}
   }

7. David Speck

   SymK – A Versatile Symbolic Search Planner

   In Tenth International Planning Competition (IPC-10): Planner Abstracts. 2023.

   Abs Bib Code PDF

   SymK is a planner that performs symbolic search using Binary Decision Diagrams to find a single optimal or the best k plans. It is designed to be a versatile planner by supporting several important and expressive extensions to the classical planning formalism. Our planner, SymK, therefore natively supports features relevant for compact modeling of planning tasks, such as conditional effects and derived predicates with axioms.

   @inproceedings{speck-ipc2023,
     title = {{SymK} -- {A} Versatile Symbolic Search Planner},
     author = {Speck, David},
     booktitle = {Tenth {I}nternational {P}lanning {C}ompetition ({IPC}-10):
                       Planner Abstracts},
     year = {2023}
   }

8. Paul Höft,  David Speck and Jendrik Seipp

   Dofri: Planner Abstract

   In Tenth International Planning Competition (IPC-10): Planner Abstracts. 2023.

   Abs Bib Code PDF

   Cost partitioning is the foundation of today’s strongest heuristics for optimal classical planning. Many cost partitioning algorithms use linear programs (LPs) to compute the heuristic value. In practice, it is often too time-consuming to solve a separate LP for each state, so it is necessary to approximate the heuristic. Our planner, Dofri, uses a refined version of the Saturated Post-hoc Optimization heuristic that reduces the computational cost without approximating the heuristic. This is done by simplifying the LPs and avoiding duplicate computations so that we can precisely compute the heuristics for each state without sacrificing heuristic quality.

   @inproceedings{hoeft-et-al-ipc2023,
     title = {Dofri: Planner Abstract},
     author = {H{\"o}ft, Paul and Speck, David and Seipp, Jendrik},
     booktitle = {Tenth {I}nternational {P}lanning {C}ompetition ({IPC}-10):
                       Planner Abstracts},
     year = {2023}
   }

1. Remo Christen, Salomé Eriksson, Michael Katz, Christian Muise, Alice Petrov, Florian Pommerening, Jendrik Seipp, Silvan Sievers and David Speck

   PARIS: Planning Algorithms for Reconfiguring Independent Sets

   In ICAPS 2023 Scheduling and Planning Applications woRKshop (SPARK). 2023.

   Superseded by the ECAI 2023 paper with the same name.

   Abs Bib PDF

   Combinatorial reconfiguration studies how one solution of a combinatorial problem can be transformed into another. The transformation can only make small local changes and may not leave the solution space. An important example is the independent set reconfiguration (ISR) problem, where an independent set of a graph (a subset of its vertices without edges between them) has to be transformed into another one by a sequence of modifications that remove a vertex or add another that is not adjacent to any vertex in the set. The 1st Combinatorial Reconfiguration Challenge (CoRe Challenge 2022) was a competition focused on the ISR problem. Our team participated with two solvers that model the ISR problem as a planning problem and employ different planning techniques for solving it. They successfully competed in the challenge and were awarded 4 first, 3 second, and 3 third places across 9 tracks. In this work, we present the ISR problem as a new problem to the planning community and describe the planning techniques used in our solvers. We re-ran the entire competition under equal computational conditions to allow for a fair comparison. Besides showcasing the success of planning technology, we hope that this work will create a cross-fertilization of the two research fields.

   @inproceedings{christen-et-al-icaps2023wsspark,
     author = {Christen, Remo and Eriksson, Salom{\'e} and Katz, Michael and Muise, Christian and Petrov, Alice and Pommerening, Florian and Seipp, Jendrik and Sievers, Silvan and Speck, David},
     title = {{PARIS}: Planning Algorithms for Reconfiguring Independent Sets},
     booktitle = {ICAPS 2023 Scheduling and Planning Applications woRKshop (SPARK)},
     year = {2023},
   }

2. Remo Christen, Salomé Eriksson, Michael Katz, Christian Muise, Alice Petrov, Florian Pommerening, Jendrik Seipp, Silvan Sievers and David Speck

   PARIS: Planning Algorithms for Reconfiguring Independent Sets

   In ICAPS 2023 Workshop on Heuristics and Search for Domain-independent Planning (HSDIP). 2023.

   Superseded by the ECAI 2023 paper with the same name.

   Abs Bib PDF

   Combinatorial reconfiguration studies how one solution of a combinatorial problem can be transformed into another. The transformation can only make small local changes and may not leave the solution space. An important example is the independent set reconfiguration (ISR) problem, where an independent set of a graph (a subset of its vertices without edges between them) has to be transformed into another one by a sequence of modifications that remove a vertex or add another that is not adjacent to any vertex in the set. The 1st Combinatorial Reconfiguration Challenge (CoRe Challenge 2022) was a competition focused on the ISR problem. Our team participated with two solvers that model the ISR problem as a planning problem and employ different planning techniques for solving it. They successfully competed in the challenge and were awarded 4 first, 3 second, and 3 third places across 9 tracks. In this work, we show how to model ISR problems as planning tasks and describe the planning techniques used in our solvers. For a fair comparison of ISR approaches, we re-run the entire competition under equal computational conditions. Besides showcasing the success of planning technology, we hope that this work will create a cross-fertilization of the two research fields.

   @inproceedings{christen-et-al-icaps2023wshsdip,
     author = {Christen, Remo and Eriksson, Salom{\'e} and Katz, Michael and Muise, Christian and Petrov, Alice and Pommerening, Florian and Seipp, Jendrik and Sievers, Silvan and Speck, David},
     title = {{PARIS}: Planning Algorithms for Reconfiguring Independent Sets},
     booktitle = {ICAPS 2023 Workshop on Heuristics and Search for Domain-independent Planning (HSDIP)},
     year = {2023},
   }

3. David Speck, Paul Höft, Daniel Gnad and Jendrik Seipp

   Finding Matrix Multiplication Algorithms with Classical Planning - Extended Abstract

   In The 35th Annual Workshop of the Swedish Artificial Intelligence Society (SAIS). 2023.

   Superseded by the ICAPS 2023 paper with the same name.

   Abs Bib Code Data PDF

   Matrix multiplication is a fundamental operation of linear algebra, with applications ranging from quantum physics to artificial intelligence. Given its importance, enormous resources have been invested in the search for faster matrix multiplication algorithms. Recently, this search has been cast as a single-player game. By learning how to play this game efficiently, the newly-introduced AlphaTensor reinforcement learning agent discovers many new faster algorithms. In this paper, we show that finding matrix multiplication algorithms can also be cast as a classical planning problem. Based on this observation, we introduce a challenging benchmark suite for classical planning and evaluate state-of-the-art planning techniques on it. We analyze the strengths and limitations of different planning approaches in this domain and show that we can use classical planning to find lower bounds and concrete algorithms for matrix multiplication.

   @inproceedings{speck-et-al-sais2023,
     author = {Speck, David and H{\"o}ft, Paul and Gnad, Daniel and Seipp, Jendrik},
     title = {Finding Matrix Multiplication Algorithms with Classical Planning - Extended Abstract},
     booktitle = {The 35th Annual Workshop of the Swedish Artificial Intelligence Society (SAIS)},
     year = {2023},
   }

2022

1. Kilian Hu and David Speck

   On Bidirectional Heuristic Search in Classical Planning: An Analysis of BAE*

   In Proceedings of the 15th Annual Symposium on Combinatorial Search (SoCS 2022), pp. 91–99. 2022.

   Abs Bib Code Data PDF

   Heuristic search is a successful approach to cost-optimal planning. Bidirectional heuristic search algorithms have been around for a long time, but only recent advances have led to algorithms like BAE* that have the potential to outperform unidirectional heuristic search algorithms like A* in practice. In this work, we analyze BAE* for classical planning and the challenges associated with the underlying assumption of an explicit state representation. We show that it is crucial to use mutexes and reachability analysis to reduce the potentially exponential number of goal states, which makes it possible to create an explicit representation of a reversed planning task that can be used for the backward search of BAE*. Our empirical evaluation shows that BAE* solves more instances than A* in multiple domains with significantly fewer node expansions, demonstrating the usefulness of BAE* in planning.

   @inproceedings{hu-speck-socs2022,
     author = {Hu, Kilian and Speck, David},
     title = {On Bidirectional Heuristic Search in Classical Planning: An Analysis of BAE*},
     editor = {Chrpa, Luk{\'a}{\v{s}} and Saetti, Alessandro},
     booktitle = {Proceedings of the 15th Annual Symposium on Combinatorial Search (SoCS 2022)},
     year = {2022},
     publisher = {AAAI Press},
     pages = {91--99}
   }

2. Remo Christen, Salomé Eriksson, Michael Katz, Emil Keyder, Christian Muise, Alice Petrov, Florian Pommerening, Jendrik Seipp, Silvan Sievers and David Speck

   (PARIS) Planning Algorithms for Reconfiguring Independent Sets – Solver Description

   In First CoRe Challenge: Solver and Graph Descriptions, pp. 15–22. 2022.

   Abs Bib PDF

   The general approach to all of the solver tracks was to model the ISR problem as one of automated planning, and use a selection of state-of-the-art solvers to solve these instances. Throughout this document, we describe the encoding, solvers, and overall search setup.

   @inproceedings{christen-et-al-core2022,
     author = {Christen, Remo and Eriksson, Salom{\'e} and Katz, Michael and Keyder, Emil and Muise, Christian and Petrov, Alice and Pommerening, Florian and Seipp, Jendrik and Sievers, Silvan and Speck, David},
     title = {({PARIS}) Planning Algorithms for Reconfiguring Independent Sets -- Solver Description},
     year = {2022},
     editor = {Soh, Takehide and Okamoto, Yoshio and Ito, Takehiro},
     booktitle = {First {CoRe} Challenge: Solver and Graph Descriptions},
     pages = {15--22}
   }

3. André Biedenkapp,  David Speck, Silvan Sievers, Frank Hutter, Marius Lindauer and Jendrik Seipp

   Learning Domain-Independent Policies for Open List Selection

   In ICAPS 2022 Workshop on Bridging the Gap Between AI Planning and Reinforcement Learning (PRL). 2022.

   Abs Bib PDF

   Since its proposal over a decade ago, LAMA has been considered one of the best-performing satisficing classical planners. Its key component is heuristic search with multiple open lists, each using a different heuristic function to order states. Even with a very simple, ad-hoc policy for open list selection, LAMA achieves state-of-the-art results. In this paper, we propose to use dynamic algorithm configuration to learn such policies in a principled and data-driven manner. On the learning side, we show how to train a reinforcement learning agent over several heterogeneous environments, aiming at zero-shot generalization to new related domains. On the planning side, our experimental results show that the trained policies often reach the performance of LAMA, and sometimes even perform better. Furthermore, our analysis of different policies shows that prioritizing states reached via preferred operators is crucial, explaining the strong performance of LAMA.

   @inproceedings{biedenkapp-et-al-icaps2022wsprl,
     title = {Learning Domain-Independent Policies for Open List Selection},
     author = {Biedenkapp, Andr{\'e} and Speck, David and Sievers, Silvan and Hutter, Frank and Lindauer, Marius and Seipp, Jendrik},
     booktitle = {ICAPS 2022 Workshop on Bridging the Gap Between AI Planning and Reinforcement Learning (PRL)},
     year = {2022}
   }

4. David Speck and Jendrik Seipp

   New Refinement Strategies for Cartesian Abstractions

   In Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling (ICAPS 2022), pp. 348–352. 2022.

   Abs Bib Code Data PDF

   Cartesian counterexample-guided abstraction refinement (CEGAR) yields strong heuristics for optimal classical planning. CEGAR repeatedly finds counterexamples, i.e., abstract plans that fail for the concrete task. Although there are usually many such abstract plans to choose from, the refinement strategy from previous work is to choose an arbitrary optimal one. In this work, we show that an informed refinement strategy is critical in theory and practice. We demonstrate that it is possible to execute all optimal abstract plans in the concrete task simultaneously, and present methods to minimize the time and number of refinement steps until we find a concrete solution. The resulting algorithm solves more tasks than the previous state of the art for Cartesian CEGAR, both during refinement and when used as a heuristic in an A* search.

   @inproceedings{speck-seipp-icaps2022,
     author = {Speck, David and Seipp, Jendrik},
     title = {New Refinement Strategies for Cartesian Abstractions},
     editor = {Thi{\'e}baux, Sylvie and Yeoh, William},
     booktitle = {Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling (ICAPS 2022)},
     year = {2022},
     publisher = {AAAI Press},
     pages = {348--352}
   }

5. Julian von Tschammer, Robert Mattmüller and David Speck

   Loopless Top-K Planning

   In Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling (ICAPS 2022), pp. 380–384. 2022.

   Abs Bib Code PDF

   In top-k planning, the objective is to determine a set of k cheapest plans that provide several good alternatives to choose from. Such a solution set often contains plans that visit at least one state more than once. Depending on the application, plans with such loops are of little importance because they are dominated by a loopless representative and can prevent more meaningful plans from being found.

   In this paper, we motivate and introduce loopless top-k planning. We show how to enhance the state-of-the-art symbolic top-k planner, symK, to obtain an efficient, sound and complete algorithm for loopless top-k planning. An empirical evaluation shows that our proposed approach has a higher k-coverage than a generate-and-test approach that uses an ordinary top-k planner, which we show to be incomplete in the presence of zero-cost loops.

   @inproceedings{vontschammer-et-al-icaps2022,
     author = {{von Tschammer}, Julian and Mattm{\"u}ller, Robert and Speck, David},
     title = {Loopless Top-K Planning},
     editor = {Thi{\'e}baux, Sylvie and Yeoh, William},
     booktitle = {Proceedings of the Thirty-Second International Conference on Automated Planning and Scheduling (ICAPS 2022)},
     year = {2022},
     publisher = {AAAI Press},
     pages = {380--384}
   }

6. David Speck

   Symbolic Search for Optimal Planning with Expressive Extensions

   PhD thesis, University of Freiburg, Germany, 2022.

   Abs arXiv Bib HTML PDF

   In classical planning, the goal is to derive a course of actions that allows an intelligent agent to move from any situation it finds itself in to one that satisfies its goals. Classical planning is considered domain-independent, i.e., it is not limited to a particular application and can be used to solve different types of reasoning problems. In practice, however, some properties of a planning problem at hand require an expressive extension of the standard classical planning formalism to capture and model them. Although the importance of many of these extensions is well known, most planners, especially optimal planners, do not support these extended planning formalisms. The lack of support not only limits the use of these planners for certain problems, but even if it is possible to model the problems without these extensions, it often leads to increased effort in modeling or makes modeling practically impossible as the required problem encoding size increases exponentially.

   In this thesis, we propose to use symbolic search for cost-optimal planning for different expressive extensions of classical planning, all capturing different aspects of the problem. In particular, we study planning with axioms, planning with state- dependent action costs, oversubscription planning, and top-k planning. For all formalisms, we present complexity and compilability results, highlighting that it is desirable and even necessary to natively support the corresponding features. We analyze symbolic heuristic search and show that the search performance does not always benefit from the use of a heuristic and that the search performance can exponentially deteriorate even under the best possible circumstances, namely the perfect heuristic. This reinforces that symbolic blind search is the dominant symbolic search strategy nowadays, on par with other state-of-the-art cost-optimal planning strategies. Based on this observation and the lack of good heuristics for planning formalisms with expressive extensions, symbolic search turns out to be a strong approach. We introduce symbolic search to support each of the formalisms individually and in combination, resulting in optimal, sound, and complete planning algorithms that empirically compare favorably with other approaches.

   @phdthesis{speck-phd2022,
     author = {Speck, David},
     title = {Symbolic Search for Optimal Planning with Expressive Extensions},
     school = {University of Freiburg, Germany},
     year = {2022}
   }

2021

1. David Speck, David Borukhson, Robert Mattmüller and Bernhard Nebel

   On the Compilability and Expressive Power of State-Dependent Action Costs

   In Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling (ICAPS 2021), pp. 358–366. 2021.

   Abs Bib PDF Poster

   While state-dependent action costs are practically relevant and have been studied before, it is still unclear if they are an essential feature of planning tasks. In this paper, we study to what extent state-dependent action costs are an essential feature by analyzing under which circumstances they can be compiled away. We give a comprehensive classification for combinations of action cost functions and possible cost measures for the compilations.

   Our theoretical results show that if both task sizes and plan lengths are to be preserved polynomially, then the boundary between compilability and non-compilability lies between FP and FPSPACE computable action cost functions (under a mild assumption on the polynomial hierarchy). Preserving task sizes polynomially and plan lengths linearly at the same time is impossible.

   @inproceedings{speck-et-al-icaps2021a,
     author = {Speck, David and Borukhson, David and Mattm{\"u}ller, Robert and Nebel, Bernhard},
     title = {On the Compilability and Expressive Power of State-Dependent Action Costs},
     editor = {Goldman, Robert P. and Biundo, Susanne and Katz, Michael},
     booktitle = {Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling (ICAPS 2021)},
     year = {2021},
     publisher = {AAAI Press},
     pages = {358--366}
   }

2. David Speck, André Biedenkapp, Frank Hutter, Robert Mattmüller and Marius Lindauer

   Learning Heuristic Selection with Dynamic Algorithm Configuration

   In Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling (ICAPS 2021), pp. 597–605. 2021.

   Abs arXiv Bib Code PDF Poster

   A key challenge in satisficing planning is to use multiple heuristics within one heuristic search. An aggregation of multiple heuristic estimates, for example by taking the maximum, has the disadvantage that bad estimates of a single heuristic can negatively affect the whole search. Since the performance of a heuristic varies from instance to instance, approaches such as algorithm selection can be successfully applied. In addition, alternating between multiple heuristics during the search makes it possible to use all heuristics equally and improve performance. However, all these approaches ignore the internal search dynamics of a planning system, which can help to select the most useful heuristics for the current expansion step. We show that dynamic algorithm configuration can be used for dynamic heuristic selection which takes into account the internal search dynamics of a planning system. Furthermore, we prove that this approach generalizes over existing approaches and that it can exponentially improve the performance of the heuristic search. To learn dynamic heuristic selection, we propose an approach based on reinforcement learning and show empirically that domain-wise learned policies, which take the internal search dynamics of a planning system into account, can exceed existing approaches.

   @inproceedings{speck-et-al-icaps2021b,
     author = {Speck, David and Biedenkapp, Andr{\'e} and Hutter, Frank and Mattm{\"u}ller, Robert and Lindauer, Marius},
     title = {Learning Heuristic Selection with Dynamic Algorithm Configuration},
     editor = {Goldman, Robert P. and Biundo, Susanne and Katz, Michael},
     booktitle = {Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling (ICAPS 2021)},
     year = {2021},
     publisher = {AAAI Press},
     pages = {597--605}
   }

3. Dominik Drexler, Jendrik Seipp and David Speck

   Subset-Saturated Transition Cost Partitioning

   In Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling (ICAPS 2021), pp. 131–139. 2021.

   Abs Bib Code Data PDF Poster

   Cost partitioning admissibly combines the information from multiple heuristics for optimal state-space search. One of the strongest cost partitioning algorithms is saturated cost partitioning. It considers the heuristics in sequence and assigns to each heuristic the minimal fraction of the remaining costs that are needed for preserving all heuristic estimates. Saturated cost partitioning has recently been generalized in two directions: first, by allowing to use different costs for the transitions induced by the same operator, and second, by preserving the heuristic estimates for only a subset of states. In this work, we unify these two generalizations and show that the resulting subset-saturated transition cost partitioning algorithm usually yields stronger heuristics than the two generalizations by themselves.

   @inproceedings{drexler-et-al-icaps2021,
     author = {Drexler, Dominik and Seipp, Jendrik and Speck, David},
     title = {Subset-Saturated Transition Cost Partitioning},
     editor = {Goldman, Robert P. and Biundo, Susanne and Katz, Michael},
     booktitle = {Proceedings of the Thirty-First International Conference on Automated Planning and Scheduling (ICAPS 2021)},
     year = {2021},
     publisher = {AAAI Press},
     pages = {131--139}
   }

4. David Speck and Michael Katz

   Symbolic Search for Oversubscription Planning

   In Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI 2021), pp. 11972–11980. 2021.

   Abs Bib Code PDF Poster

   The objective of optimal oversubscription planning is to find a plan that yields an end state with a maximum utility while keeping plan cost under a certain bound. In practice, the situation occurs whenever a large number of possible, often competing goals of varying value exist, or the resources are not sufficient to achieve all goals. In this paper, we investigate the use of symbolic search for optimal oversubscription planning. Specifically, we show how to apply symbolic forward search to oversubscription planning tasks and prove that our approach is sound, complete and optimal. An empirical analysis shows that our symbolic approach favorably competes with explicit state-space heuristic search, the current state of the art for oversubscription planning.

   @inproceedings{speck-katz-aaai2021,
     title = {Symbolic Search for Oversubscription Planning},
     author = {Speck, David and Katz, Michael},
     editor = {Leyton-Brown, Kevin and Mausam},
     booktitle = {Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI 2021)},
     publisher = {AAAI Press},
     year = {2021},
     pages = {11972--11980}
   }

5. Gregor Behnke and David Speck

   Symbolic Search for Optimal Total-Order HTN Planning

   In Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI 2021), pp. 11744–11754. 2021.

   Abs Bib Code PDF Poster

   Symbolic search has proven to be a useful approach to optimal classical planning. In Hierarchical Task Network (HTN) planning, however, there is little work on optimal planning. One reason for this is that in HTN planning, most algorithms are based on heuristic search, and admissible heuristics have to incorporate the structure of the task network in order to be informative. In this paper, we present a novel approach to optimal (totally-ordered) HTN planning, which is based on symbolic search. An empirical analysis shows that our symbolic approach outperforms the current state of the art for optimal totally-ordered HTN planning.

   @inproceedings{behnke-speck-aaai2021,
     title = {Symbolic Search for Optimal Total-Order HTN Planning},
     author = {Behnke, Gregor and Speck, David},
     editor = {Leyton-Brown, Kevin and Mausam},
     booktitle = {Proceedings of the Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI 2021)},
     publisher = {AAAI Press},
     year = {2021},
     pages = {11744--11754}
   }

2020

1. David Speck, Florian Geißer and Robert Mattmüller

   When Perfect is not Good Enough: On the Search Behaviour of Symbolic Heuristic Search

   In Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling (ICAPS 2020), pp. 263–271. 2020.

   Abs Bib PDF Poster

   Symbolic search has proven to be a competitive approach to cost-optimal planning, as it compactly represents sets of states by symbolic data structures. While heuristics for symbolic search exist, symbolic bidirectional blind search empirically outperforms its heuristic counterpart and is therefore the dominant search strategy. This prompts the question of why heuristics do not seem to pay off in symbolic search. As a first step in answering this question, we investigate the search behaviour of symbolic heuristic search by means of BDDA*. Previous work identified the partitioning of state sets according to their heuristic values as the main bottleneck. We theoretically and empirically evaluate the search behaviour of BDDA* and reveal another fundamental problem: we prove that the use of a heuristic does not always improve the search performance of BDDA*. In general, even the perfect heuristic can exponentially deteriorate search performance.

   @inproceedings{speck-et-al-icaps2020,
     title = {When Perfect is not Good Enough: On the Search Behaviour of Symbolic Heuristic Search},
     author = {Speck, David and Gei{\ss}er, Florian and Mattm{\"u}ller, Robert},
     editor = {Beck, J. Christopher and Karpas, Erez and Sohrabi, Shirin},
     booktitle = {Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling (ICAPS 2020)},
     publisher = {AAAI Press},
     year = {2020},
     pages = {263--271}
   }

2. David Speck, Robert Mattmüller and Bernhard Nebel

   Symbolic Top-k Planning

   In Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI 2020), pp. 9967–9974. 2020.

   Abs Bib Code PDF Poster

   The objective of top-k planning is to determine a set of k different plans with lowest cost for a given planning task. In practice, such a set of best plans can be preferred to a single best plan generated by ordinary optimal planners, as it allows the user to choose between different alternatives and thus take into account preferences that may be difficult to model. In this paper we show that, in general, the decision problem version of top-k planning is PSPACE-complete, as is the decision problem version of ordinary classical planning. This does not hold for polynomially bounded plans for which the decision problem turns out to be PP-hard, while the ordinary case is NP-hard. We present a novel approach to top-k planning, called SYM-K, which is based on symbolic search, and prove that SYM-K is sound and complete. Our empirical analysis shows that SYM-K exceeds the current state of the art for both small and large k.

   @inproceedings{speck-et-al-aaai2020,
     title = {Symbolic Top-k Planning},
     author = {Speck, David and Mattm{\"u}ller, Robert and Nebel, Bernhard},
     editor = {Conitzer, Vincent and Sha, Fei},
     booktitle = {Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence (AAAI 2020)},
     publisher = {AAAI Press},
     year = {2020},
     pages = {9967--9974}
   }

3. Florian Geißer,  David Speck and Thomas Keller

   Trial-based Heuristic Tree Search for MDPs with Factored Action Spaces

   In Proceedings of the 13th Annual Symposium on Combinatorial Search (SoCS 2020), pp. 38–47. 2020.

   Abs Bib Code Data PDF

   MDPs with factored action spaces, i.e. where actions are described as assignments to a set of action variables, allow reasoning over action variables instead of action states, yet most algorithms only consider a grounded action representation. This includes algorithms that are instantiations of the trial-based heuristic tree search (THTS) framework, such as AO* or UCT.

   To be able to reason over factored action spaces, we propose a generalisation of THTS where nodes that branch over all applicable actions are replaced with subtrees that consist of nodes that represent the decision for a single action variable. We show that many THTS algorithms retain their theoretical properties under the generalised framework, and show how to approximate any state-action heuristic to a heuristic for partial action assignments. This allows to guide a UCT variant that is able to create exponentially fewer nodes than the same algorithm that considers ground actions. An empirical evaluation on the benchmark set of the probabilistic track of the latest International Planning Competition validates the benefits of the approach.

   @inproceedings{geisser-et-al-socs2020,
     title = {Trial-based Heuristic Tree Search for {MDP}s with Factored Action Spaces},
     author = {Gei{\ss}er, Florian and Speck, David and Keller, Thomas},
     editor = {Harabor, Daniel and Vallati, Mauro},
     booktitle = {Proceedings of the 13th Annual Symposium on Combinatorial Search (SoCS 2020)},
     publisher = {AAAI Press},
     year = {2020},
     pages = {38--47}
   }

1. David Speck, André Biedenkapp, Frank Hutter, Robert Mattmüller and Marius Lindauer

   Learning Heuristic Selection with Dynamic Algorithm Configuration

   In ICAPS 2020 Workshop on Bridging the Gap Between AI Planning and Reinforcement Learning (PRL), pp. 61–69. 2020.

   Superseded by the ICAPS 2021 paper with the same name.

   Abs arXiv Bib Code PDF

   A key challenge in satisficing planning is to use multiple heuristics within one heuristic search. An aggregation of multiple heuristic estimates, for example by taking the maximum, has the disadvantage that bad estimates of a single heuristic can negatively affect the whole search. Since the performance of a heuristic varies from instance to instance, approaches such as algorithm selection can be successfully applied. In addition, alternating between multiple heuristics during the search makes it possible to use all heuristics equally and improve performance. However, all these approaches ignore the internal search dynamics of a planning system, which can help to select the most helpful heuristics for the current expansion step. We show that dynamic algorithm configuration can be used for dynamic heuristic selection which takes into account the internal search dynamics of a planning system. Furthermore, we prove that this approach generalizes over existing approaches and that it can exponentially improve the performance of the heuristic search. To learn dynamic heuristic selection, we propose an approach based on reinforcement learning and show empirically that domain-wise learned policies, which take the internal search dynamics of a planning system into account, can exceed existing approaches in terms of coverage.

   @inproceedings{speck-et-al-icaps2020wsprl,
     title = {Learning Heuristic Selection with Dynamic Algorithm Configuration},
     author = {Speck, David and Biedenkapp, Andr{\'e} and Hutter, Frank and Mattm{\"u}ller, Robert and Lindauer, Marius},
     booktitle = {ICAPS 2020 Workshop on Bridging the Gap Between AI Planning and Reinforcement Learning (PRL)},
     year = {2020},
     pages = {61--69},
   }

2. Dominik Drexler,  David Speck and Robert Mattmüller

   Subset-Saturated Transition Cost Partitioning for Optimal Classical Planning

   In ICAPS 2020 Workshop on Heuristics and Search for Domain-Independent Planning (HSDIP), pp. 23–31. 2020.

   Superseded by the ICAPS 2021 paper "Subset-Saturated Transition Cost Partitioning".

   Abs Bib Code Data PDF

   Cost partitioning admissibly combines the information from multiple heuristics for state-space search. We use a greedy method called saturated cost partitioning that considers the heuristics in sequence and assigns the minimal fraction of the remaining costs that it needs to preserve the heuristic estimates. In this work, we address the problem of using more expressive transition cost functions with saturated cost partitioning to obtain stronger heuristics. Our contribution is subset-saturated transition cost partitioning that combines the concepts of using transition cost functions and prioritizing states that look more important during the search. Our empirical evaluation shows that this approach still causes too much computational overhead but leads to more informed heuristics.

   @inproceedings{drexler-et-al-icaps2020wshsdip,
     title = {Subset-Saturated Transition Cost Partitioning for Optimal Classical Planning},
     author = {Drexler, Dominik and Speck, David and Mattm{\"u}ller, Robert},
     booktitle = {ICAPS 2020 Workshop on Heuristics and Search for Domain-Independent Planning (HSDIP)},
     year = {2020},
     pages = {23--31},
   }

2019

1. David Speck, Florian Geißer, Robert Mattmüller and Álvaro Torralba

   Symbolic Planning with Axioms

   In Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling (ICAPS 2019), pp. 464–572. 2019.

   Abs Bib Code PDF

   Axioms are an extension for classical planning models that allow for modeling complex preconditions and goals exponentially more compactly. Although axioms were introduced in planning more than a decade ago, modern planning techniques rarely support axioms, especially in cost-optimal planning. Symbolic search is a popular and competitive optimal planning technique based on the manipulation of sets of states. In this work, we extend symbolic search algorithms to support axioms natively. We analyze different ways of encoding derived variables and axiom rules to evaluate them in a symbolic representation. We prove that all encodings are sound and complete, and empirically show that the presented approach outperforms the previous state of the art in cost-optimal classical planning with axioms.

   @inproceedings{speck-et-al-icaps2019,
     title = {Symbolic Planning with Axioms},
     author = {Speck, David and Gei{\ss}er, Florian and Mattm{\"u}ller, Robert and Torralba, {\'{A}lvaro}},
     editor = {Lipovetzky, Nir and Onaindia, Eva and Smith, David E.},
     booktitle = {Proceedings of the Twenty-Ninth International Conference on Automated Planning and Scheduling (ICAPS 2019)},
     year = {2019},
     publisher = {AAAI Press},
     pages = {464--572}
   }

2. Sumitra Corraya, Florian Geißer,  David Speck and Robert Mattmüller

   An Empirical Study of the Usefulness of State-Dependent Action Costs in Planning

   In Proceedings of the 42nd Annual German Conference on Artificial Intelligence (KI 2019), pp. 123–130. 2019.

   Abs Bib HTML PDF

   The vast majority of work in planning to date has focused on state-independent action costs. However, if a planning task features state-dependent costs, using a cost model with state-independent costs means either introducing a modeling error, or potentially sacrificing compactness of the model. In this paper, we investigate the conflicting priorities of modeling accuracy and compactness empirically, with a particular focus on the extent of the negative impact of reduced modeling accuracy on (a) the quality of the resulting plans, and (b) the search guidance provided by heuristics that are fed with inaccurate cost models. Our empirical results show that the plan suboptimality introduced by ignoring state-dependent costs can range, depending on the domain, from inexistent to several orders of magnitude. Furthermore, our results show that the impact on heuristic guidance additionally depends strongly on the heuristic that is used, the specifics of how exactly the costs are represented, and whether one is interested in heuristic accuracy, node expansions, or overall runtime savings.

   @inproceedings{corraya-et-al-ki2019,
     author = {Corraya, Sumitra and Geißer, Florian and Speck, David and Mattm{\"u}ller, Robert},
     title = {An Empirical Study of the Usefulness of State-Dependent Action Costs in Planning},
     editor = {Benzm{\"u}ller, Christoph and Stuckenschmidt, Heiner},
     booktitle = {Proceedings of the 42nd Annual German Conference on Artificial Intelligence (KI 2019)},
     publisher = {Springer-Verlag},
     series = {Lecture Notes in Artificial Intelligence},
     year = {2019},
     pages = {123--130}
   }

3. Florian Geißer,  David Speck and Thomas Keller

   An Analysis of the Probabilistic Track of the IPC 2018

   In ICAPS 2019 Workshop on the International Planning Competition (WIPC), pp. 27–35. 2019.

   Abs Bib Code Data PDF

   The International Planning Competition 2018 consisted of several tracks on classical, temporal and probabilistic planning. In this paper, we focus on the discrete MDP track of the probabilistic portion of the competition.

   We discuss the changes to the input language RDDL, which give rise to new challenges for planning systems, and analyze each of the eight competition domains separately and highlight unique properties. We demonstrate flaws of the used evaluation criterion, the IPC score, and discuss the need for optimal upper bounds. An evaluation of the three top-performers, including their post-competition versions, and a brief analysis of their performance highlights the strengths and weaknesses of the individual approaches.

   @inproceedings{geisser-et-al-icaps2019wsipc,
     title = {An Analysis of the Probabilistic Track of the {IPC} 2018},
     author = {Gei{\ss}er, Florian and Speck, David and Keller, Thomas},
     booktitle = {ICAPS 2019 Workshop on the International Planning Competition (WIPC)},
     year = {2019},
     pages = {27--35}
   }

4. Olga Speck, Rafael Horn,  David Speck, Johannes Gantner and Philip Leistner

   Biomimetics meets Sustainability

   In Bionik: Patente aus der Natur. Tagungsbeiträge zum 9. Bionik-Kongress, pp. 81–91. 2019.

   Abs Bib HTML

   Sustainable development is a challenge that needs to be tackled by social consensus. Learning from nature is linked to the hope of learning from biological solutions that have extraordinary qualities. One focus of the publication is to refine the discussion about technology-derived and biology-derived developments by taking descriptive, normative and emotional aspects into consideration. Descriptive aspects are presented on the basis of a straightforward classification tool (decision tree) to clearly describe, distinguish and identify biology-derived and technology-derived developments. A further focus of the article is the presentation of the concept of bioinspired sustainability and the presentation of an evaluation tree for Bioinspired Sustainability Assessment (BiSA).

   @inproceedings{speck-et-al-bk2019,
     author = {Speck, Olga and Horn, Rafael and Speck, David and Gantner, Johannes and Leistner, Philip},
     title = {Biomimetics meets Sustainability},
     booktitle = {Bionik: Patente aus der Natur. Tagungsbeiträge zum 9. Bionik-Kongress},
     year = {2019},
     pages = {81--91}
   }

2018

1. David Speck, Florian Geißer and Robert Mattmüller

   Symbolic Planning with Edge-Valued Multi-Valued Decision Diagrams

   In Proceedings of the Twenty-Eighth International Conference on Automated Planning and Scheduling (ICAPS 2018). 2018.

   Abs Bib Code PDF Poster Supp

   Symbolic representations have attracted significant attention in optimal planning. Binary Decision Diagrams (BDDs) form the basis for symbolic search algorithms. Closely related are Algebraic Decision Diagrams (ADDs), used to represent heuristic functions. Also, progress was made in dealing with models that take state-dependent action costs into account. Here, costs are represented as Edge-valued Multi-valued Decision Diagrams (EVMDDs), which can be exponentially more compact than the corresponding ADD representation. However, they were not yet considered for symbolic planning.

   In this work, we study EVMDD-based symbolic search for optimal planning. We define EVMDD-based representations of state sets and transition relations, and show how to compute the necessary operations required for EVMDD-A*. This EVMDD-based version of symbolic A* generalizes its BDD variant, and allows to solve planning tasks with state-dependent action costs. We prove theoretically that our approach is sound, complete and optimal. Additionally, we present an empirical analysis comparing EVMDD-A* to BDD-A* and explicit A* search. Our results underscore the usefulness of symbolic approaches and the feasibility of dealing with models that go beyond unit costs.

   @inproceedings{speck-et-al-icaps2018,
     title = {Symbolic Planning with Edge-Valued Multi-Valued Decision Diagrams},
     author = {Speck, David and Gei{\ss}er, Florian and Mattm{\"u}ller, Robert},
     editor = {de Weerdt, Mathijs and Koenig, Sven and R{\"o}ger, Gabriele and Spaan, Matthijs},
     booktitle = {Proceedings of the Twenty-Eighth International Conference on Automated Planning and Scheduling (ICAPS 2018)},
     year = {2018},
     publisher = {AAAI Press}
   }

2. Florian Geißer and David Speck

   Prost-DD – Utilizing Symbolic Classical Planning in THTS

   In Sixth International Probabilistic Planning Competition (IPPC-6): Planner Abstracts, pp. 13–16. 2018.

   Abs Bib Code PDF

   We describe PROST-DD, our submission to the International Probabilistic Planning Competition 2018. Like its predecessor PROST, which already participated with success at the previous IPPC, PROST-DD is based on the trial-based heuristic tree search framework and applies the UCT* algorithm. The novelty of our submission is the heuristic used to initialize newly encountered decision nodes. We apply an iterative symbolic backward planning approach based on the determinized task. Similarly to the SPUDD approach and recent work in symbolic planning with state-dependent action costs, we encode costs and reachability of states in a single decision diagram. During initialization, these diagrams are then used to query a state for its estimated expected reward. One benefit of this heuristic is that we can optionally interweave the standard heuristic of PROST, the IDS heuristic.

   @inproceedings{geisser-speck-ippc2018,
     author = {Gei{\ss}er, Florian and Speck, David},
     title = {{Prost-DD} -- Utilizing Symbolic Classical Planning in {THTS}},
     booktitle = {Sixth International Probabilistic Planning Competition ({IPPC}-6): Planner Abstracts},
     year = {2018},
     pages = {13--16}
   }

3. David Speck, Florian Geißer and Robert Mattmüller

   SYMPLE: Symbolic Planning based on EVMDDs

   In Ninth International Planning Competition (IPC-9): Planner Abstracts, pp. 82–85. 2018.

   Abs Bib Code PDF

   SYMPLE is a classical planner which performs bidirectional symbolic search. Symbolic search has proven to be a useful approach to optimal classical planning and is usually based on Binary Decision Diagrams (BDDs). Our approach is based on an alternative data structure called Edge-valued Multi-valued Decision Diagrams (EVMDDs), which have some structural advantages over BDDs.

   @inproceedings{speck-et-al-ipc2018,
     title = {{SYMPLE}: {S}ymbolic Planning based on {EVMDD}s},
     author = {Speck, David and Gei{\ss}er, Florian and Mattm{\"u}ller, Robert},
     booktitle = {Ninth International Planning Competition ({IPC}-9): Planner Abstracts},
     year = {2018},
     pages = {82--85}
   }

2017

1. David Speck, Christian Dornhege and Wolfram Burgard

   Shakey 2016 - How Much Does it Take to Redo Shakey the Robot?

   IEEE Robotics and Automation Letters (RA-L) 2.2, pp. 1203–1209. 2017.

   Abs Bib Code HTML PDF

   Shakey the robot was one of the first autonomous robots that showed impressive capabilities of navigation and mobile manipulation. Since then, robotics research has made great progress, showing more and more capable robotic systems for a large variety of application domains and tasks. In this letter, we look back on decades of research by rebuilding Shakey with modern robotics technology in the open-source Shakey 2016 system. Hereby, we demonstrate the impact of research by showing that ideas from the original Shakey are still alive in state-of-the-art systems, while robotics in general has improved to deliver more robust and more capable software and hardware. Our Shakey 2016 system has been implemented on real robots and leverages mostly open-source software. We experimentally evaluate the system in real-world scenarios on a PR2 robot and a Turtlebot-based robot and particularly investigate the development effort. The experiments documented in this letter demonstrate that results from robotics research are readily available for building complex robots such as Shakey within a short amount of time and little effort.

   @article{speck-et-al-ral2017,
     author = {Speck, David and Dornhege, Christian and Burgard, Wolfram},
     title = {Shakey 2016 - How Much Does it Take to Redo Shakey the Robot?},
     journal = {IEEE Robotics and Automation Letters (RA-L)},
     year = {2017},
     volume = {2},
     number = {2},
     pages = {1203--1209}
   }

2. Olga Speck,  David Speck, Rafael Horn, Johannes Gantner and Klaus Peter Sedlbauer

   Biomimetic bio-inspired biomorph sustainable? An attempt to classify and clarify biology-derived technical developments

   Bioinspiration and Biomimetics 12.1, pp. 011004. 2017.

   Abs Bib HTML PDF

   Over the last few decades, the systematic approach of knowledge transfer from biological concept generators to technical applications has received increasing attention, particularly because marketable bio-derived developments are often described as sustainable. The objective of this paper is to rationalize and refine the discussion about bio-derived developments also with respect to sustainability by taking descriptive, normative and emotional aspects into consideration. In the framework of supervised learning, a dataset of 70 biology-derived and technology-derived developments characterised by 9 different attributes together with their respective values and assigned to one of 17 classes was created. On the basis of the dataset a decision tree was generated which can be used as a straightforward classification tool to identify biology-derived and technology-derived developments. The validation of the applied learning procedure achieved an average accuracy of 90.0%. Additional extraordinary qualities of technical applications are generally discussed by means of selected biologyderived and technology-derived examples with reference to normative (contribution to sustainability) and emotional aspects(aesthetics and symbolic character). In the context of a case study from the building sector, all aspects are critically discussed.

   @article{speck-et-al-bandb2017,
     author = {Speck, Olga and Speck, David and Horn, Rafael and Gantner, Johannes and Sedlbauer, Klaus Peter},
     title = {Biomimetic bio-inspired biomorph sustainable? {A}n attempt to classify and clarify biology-derived technical developments},
     journal = {Bioinspiration and Biomimetics},
     year = {2017},
     volume = {12},
     number = {1},
     pages = {011004}
   }

2015

1. David Speck, Manuela Ortlieb and Robert Mattmüller

   Necessary Observations in Nondeterministic Planning

   In Proceedings of the 38th Annual German Conference on Artificial Intelligence (KI 2015), pp. 181–193. 2015.

   Abs Bib PDF

   An agent that interacts with a nondeterministic environment can often only partially observe the surroundings. This necessitates observations via sensors rendering more information about the current world state. Sensors can be expensive in many regards therefore it can be essential to minimize the amount of sensors an agent requires to solve given tasks. A limitation for sensor minimization is given by essential sensors which are always required to solve particular problems. In this paper we present an efficient algorithm which determines a set of necessary observation variables. More specifically, we develop a bottom-up algorithm which computes a set of variables which are always necessary to observe, in order to always reach a goal state. Our experimental results show that the knowledge about necessary observation variables can be used to minimize the number of sensors of an agent.

   @inproceedings{speck-et-al-ki2015,
     title = {Necessary Observations in Nondeterministic Planning},
     author = {Speck, David and Ortlieb, Manuela and Mattm{\"u}ller, Robert},
     editor = {H{\"o}lldobler, Steffen and Kr{\"o}tzsch, Markus and Pe{\~n}aloza-Nyssen, Rafael and Rudolph, Sebastian},
     booktitle = {Proceedings of the 38th Annual German Conference on Artificial Intelligence (KI 2015)},
     publisher = {Springer-Verlag},
     series = {Lecture Notes in Artificial Intelligence},
     volume = {9324},
     year = {2015},
     pages = {181--193}
   }