Publications
2024

David Speck and Daniel GnadDecoupled Search for the Masses: A Novel Task Transformation for Classical PlanningIn Proceedings of the ThirtyFourth International Conference on Automated Planning and Scheduling (ICAPS 2024). 2024.
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 nonoptimal 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 decoupledsearch framework. Empirical evaluation shows that our method is empirically competitive with specialized decoupled algorithms and favorable to other related problem reformulation techniques.

Paul Höft, David Speck, Florian Pommerening and Jendrik SeippVersatile Cost Partitioning with Exact Sensitivity AnalysisIn Proceedings of the ThirtyFourth International Conference on Automated Planning and Scheduling (ICAPS 2024). 2024.
Saturated posthoc 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.

Daniel Gnad and David SpeckOn an Attempt at Casting Orbit Search as a Task TransformationIn ICAPS 2024 Workshop on Echoing (failed) Efforts in Planning (WEEP). 2024.
Statespace reduction techniques are a powerful means to enhancing the performance of searchbased planners. Recent work has shown that decoupled search, which compactly represents sets of states, can be cast as a task reformulation. Concretely, it is possible to exactly simulate the behavior and reduction of (nonoptimal) decoupled search by applying a transformation to the input task and running regular search on the transformed task. In this work, we investigate if the same approach is feasible for symmetry breaking, in particular orbit space search (OSS). One of the challenges in this endeavor is that OSS dynamically computes a canonical representative of every state generated during search. To represent this computation as a task transformation, however, we need to fix the procedure at transformation time. This leads to reduced pruning potential, which we discuss in detail and verify empirically. We also discuss an approach that can fully simulate OSS, at the cost of vastly blowingup the task size.
2023

Paul Höft, David Speck and Jendrik SeippSensitivity Analysis for Saturated Posthoc Optimization in Classical PlanningIn Proceedings of the TwentySixth European Conference on Artificial Intelligence (ECAI 2023). 2023.
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 posthoc 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.

Remo Christen, Salomé Eriksson, Michael Katz, Christian Muise, Alice Petrov, Florian Pommerening, Jendrik Seipp, Silvan Sievers and David SpeckPARIS: Planning Algorithms for Reconfiguring Independent SetsIn Proceedings of the TwentySixth European Conference on Artificial Intelligence (ECAI 2023). 2023.
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 rerun the entire competition under equal computational conditions. Besides showcasing the success of planning technology, we hope that this work will create a crossfertilization of the two research fields.

David Speck, Paul Höft, Daniel Gnad and Jendrik SeippFinding Matrix Multiplication Algorithms with Classical PlanningIn Proceedings of the ThirtyThird International Conference on Automated Planning and Scheduling (ICAPS 2023), pp. 411–416. 2023.
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 singleplayer game. By learning how to play this game efficiently, the newlyintroduced 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 stateoftheart 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.

Gregor Behnke, David Speck, Michael Katz and Shirin SohrabiOn Partial Satisfaction Planning with TotalOrder HTNsIn Proceedings of the ThirtyThird International Conference on Automated Planning and Scheduling (ICAPS 2023), pp. 42–51. 2023.
Since its introduction, partial satisfaction planning (PSP), including both oversubscription (OSP) and netbenefit, 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 netbenefit 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.

Dominik Drexler, Daniel Gnad, Paul Höft, Jendrik Seipp, David Speck and Simon StåhlbergRagnarokIn Tenth International Planning Competition (IPC10): Planner Abstracts. 2023.
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 postcompetition fixes, available at https://github.com/ipc2023classical/planner17/tree/latest.

Dominik Drexler, Jendrik Seipp and David SpeckOdin: A Planner Based on Saturated Transition Cost PartitioningIn Tenth International Planning Competition (IPC10): Planner Abstracts. 2023.
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.

David SpeckSymK – A Versatile Symbolic Search PlannerIn Tenth International Planning Competition (IPC10): Planner Abstracts. 2023.
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.

Paul Höft, David Speck and Jendrik SeippDofri: Planner AbstractIn Tenth International Planning Competition (IPC10): Planner Abstracts. 2023.
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 timeconsuming 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 Posthoc 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.
2022

Kilian Hu and David SpeckOn 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.
Heuristic search is a successful approach to costoptimal 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.

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 DescriptionIn First CoRe Challenge: Solver and Graph Descriptions, pp. 15–22. 2022.
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 stateoftheart solvers to solve these instances. Throughout this document, we describe the encoding, solvers, and overall search setup.

André Biedenkapp, David Speck, Silvan Sievers, Frank Hutter, Marius Lindauer and Jendrik SeippLearning DomainIndependent Policies for Open List SelectionIn ICAPS 2022 Workshop on Bridging the Gap Between AI Planning and Reinforcement Learning (PRL). 2022.
Since its proposal over a decade ago, LAMA has been considered one of the bestperforming 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, adhoc policy for open list selection, LAMA achieves stateoftheart results. In this paper, we propose to use dynamic algorithm configuration to learn such policies in a principled and datadriven manner. On the learning side, we show how to train a reinforcement learning agent over several heterogeneous environments, aiming at zeroshot 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.

David Speck and Jendrik SeippNew Refinement Strategies for Cartesian AbstractionsIn Proceedings of the ThirtySecond International Conference on Automated Planning and Scheduling (ICAPS 2022), pp. 348–352. 2022.
Cartesian counterexampleguided 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.

Julian von Tschammer, Robert Mattmüller and David SpeckLoopless TopK PlanningIn Proceedings of the ThirtySecond International Conference on Automated Planning and Scheduling (ICAPS 2022), pp. 380–384. 2022.
In topk 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 topk planning. We show how to enhance the stateoftheart symbolic topk planner, symK, to obtain an efficient, sound and complete algorithm for loopless topk planning. An empirical evaluation shows that our proposed approach has a higher kcoverage than a generateandtest approach that uses an ordinary topk planner, which we show to be incomplete in the presence of zerocost loops.

David SpeckSymbolic Search for Optimal Planning with Expressive ExtensionsPhD thesis, University of Freiburg, Germany, 2022.
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 domainindependent, 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 costoptimal planning for different expressive extensions of classical planning, all capturing different aspects of the problem. In particular, we study planning with axioms, planning with statedependent action costs, oversubscription planning, and topk 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 stateoftheart costoptimal 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.
2021

David Speck, David Borukhson, Robert Mattmüller and Bernhard NebelOn the Compilability and Expressive Power of StateDependent Action CostsIn Proceedings of the ThirtyFirst International Conference on Automated Planning and Scheduling (ICAPS 2021), pp. 358–366. 2021.
While statedependent 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 statedependent 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 noncompilability 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.

David Speck, André Biedenkapp, Frank Hutter, Robert Mattmüller and Marius LindauerLearning Heuristic Selection with Dynamic Algorithm ConfigurationIn Proceedings of the ThirtyFirst International Conference on Automated Planning and Scheduling (ICAPS 2021), pp. 597–605. 2021.
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 domainwise learned policies, which take the internal search dynamics of a planning system into account, can exceed existing approaches.

Dominik Drexler, Jendrik Seipp and David SpeckSubsetSaturated Transition Cost PartitioningIn Proceedings of the ThirtyFirst International Conference on Automated Planning and Scheduling (ICAPS 2021), pp. 131–139. 2021.
Cost partitioning admissibly combines the information from multiple heuristics for optimal statespace 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 subsetsaturated transition cost partitioning algorithm usually yields stronger heuristics than the two generalizations by themselves.

David Speck and Michael KatzSymbolic Search for Oversubscription PlanningIn Proceedings of the ThirtyFifth AAAI Conference on Artificial Intelligence (AAAI 2021), pp. 11972–11980. 2021.
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 statespace heuristic search, the current state of the art for oversubscription planning.

Gregor Behnke and David SpeckSymbolic Search for Optimal TotalOrder HTN PlanningIn Proceedings of the ThirtyFifth AAAI Conference on Artificial Intelligence (AAAI 2021), pp. 11744–11754. 2021.
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 (totallyordered) 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 totallyordered HTN planning.
2020

David Speck, Florian Geißer and Robert MattmüllerWhen Perfect is not Good Enough: On the Search Behaviour of Symbolic Heuristic SearchIn Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling (ICAPS 2020), pp. 263–271. 2020.
Symbolic search has proven to be a competitive approach to costoptimal 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.

David Speck, Robert Mattmüller and Bernhard NebelSymbolic Topk PlanningIn Proceedings of the ThirtyFourth AAAI Conference on Artificial Intelligence (AAAI 2020), pp. 9967–9974. 2020.
The objective of topk 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 topk planning is PSPACEcomplete, 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 PPhard, while the ordinary case is NPhard. We present a novel approach to topk planning, called SYMK, which is based on symbolic search, and prove that SYMK is sound and complete. Our empirical analysis shows that SYMK exceeds the current state of the art for both small and large k.

Florian Geißer, David Speck and Thomas KellerTrialbased Heuristic Tree Search for MDPs with Factored Action SpacesIn Proceedings of the 13th Annual Symposium on Combinatorial Search (SoCS 2020), pp. 38–47. 2020.
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 trialbased 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 stateaction 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.
2019

David Speck, Florian Geißer, Robert Mattmüller and Álvaro TorralbaSymbolic Planning with AxiomsIn Proceedings of the TwentyNinth International Conference on Automated Planning and Scheduling (ICAPS 2019), pp. 464–572. 2019.
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 costoptimal 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 costoptimal classical planning with axioms.

Sumitra Corraya, Florian Geißer, David Speck and Robert MattmüllerAn Empirical Study of the Usefulness of StateDependent Action Costs in PlanningIn Proceedings of the 42nd Annual German Conference on Artificial Intelligence (KI 2019), pp. 123–130. 2019.
The vast majority of work in planning to date has focused on stateindependent action costs. However, if a planning task features statedependent costs, using a cost model with stateindependent 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 statedependent 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.

Florian Geißer, David Speck and Thomas KellerAn Analysis of the Probabilistic Track of the IPC 2018In ICAPS 2019 Workshop on the International Planning Competition (WIPC), pp. 27–35. 2019.
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 topperformers, including their postcompetition versions, and a brief analysis of their performance highlights the strengths and weaknesses of the individual approaches.

Olga Speck, Rafael Horn, David Speck, Johannes Gantner and Philip LeistnerBiomimetics meets SustainabilityIn Bionik: Patente aus der Natur. Tagungsbeiträge zum 9. BionikKongress, pp. 81–91. 2019.
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 technologyderived and biologyderived 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 biologyderived and technologyderived 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).
2018

David Speck, Florian Geißer and Robert MattmüllerSymbolic Planning with EdgeValued MultiValued Decision DiagramsIn Proceedings of the TwentyEighth International Conference on Automated Planning and Scheduling (ICAPS 2018). 2018.
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 statedependent action costs into account. Here, costs are represented as Edgevalued Multivalued 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 EVMDDbased symbolic search for optimal planning. We define EVMDDbased representations of state sets and transition relations, and show how to compute the necessary operations required for EVMDDA*. This EVMDDbased version of symbolic A* generalizes its BDD variant, and allows to solve planning tasks with statedependent action costs. We prove theoretically that our approach is sound, complete and optimal. Additionally, we present an empirical analysis comparing EVMDDA* to BDDA* and explicit A* search. Our results underscore the usefulness of symbolic approaches and the feasibility of dealing with models that go beyond unit costs.

Florian Geißer and David SpeckProstDD – Utilizing Symbolic Classical Planning in THTSIn Sixth International Probabilistic Planning Competition (IPPC6): Planner Abstracts, pp. 13–16. 2018.
We describe PROSTDD, our submission to the International Probabilistic Planning Competition 2018. Like its predecessor PROST, which already participated with success at the previous IPPC, PROSTDD is based on the trialbased 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 statedependent 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.

David Speck, Florian Geißer and Robert MattmüllerSYMPLE: Symbolic Planning based on EVMDDsIn Ninth International Planning Competition (IPC9): Planner Abstracts, pp. 82–85. 2018.
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 Edgevalued Multivalued Decision Diagrams (EVMDDs), which have some structural advantages over BDDs.
2017

David Speck, Christian Dornhege and Wolfram BurgardShakey 2016 – How Much Does it Take to Redo Shakey the Robot?IEEE Robotics and Automation Letters (RAL) 2.2, pp. 1203–1209. 2017.
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 opensource Shakey 2016 system. Hereby, we demonstrate the impact of research by showing that ideas from the original Shakey are still alive in stateoftheart 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 opensource software. We experimentally evaluate the system in realworld scenarios on a PR2 robot and a Turtlebotbased 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.

Olga Speck, David Speck, Rafael Horn, Johannes Gantner and Klaus Peter SedlbauerBiomimetic bioinspired biomorph sustainable? An attempt to classify and clarify biologyderived technical developmentsBioinspiration and Biomimetics 12.1, pp. 011004. 2017.
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 bioderived developments are often described as sustainable. The objective of this paper is to rationalize and refine the discussion about bioderived 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 biologyderived and technologyderived 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 biologyderived and technologyderived 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 technologyderived 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.
2015

David Speck, Manuela Ortlieb and Robert MattmüllerNecessary Observations in Nondeterministic PlanningIn Proceedings of the 38th Annual German Conference on Artificial Intelligence (KI 2015), pp. 181–193. 2015.
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 bottomup 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.
2024

David Speck and Daniel GnadDecoupled Search for the Masses: A Novel Task Transformation for Classical PlanningIn Proceedings of the ThirtyFourth International Conference on Automated Planning and Scheduling (ICAPS 2024). 2024.
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 nonoptimal 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 decoupledsearch framework. Empirical evaluation shows that our method is empirically competitive with specialized decoupled algorithms and favorable to other related problem reformulation techniques.

Paul Höft, David Speck, Florian Pommerening and Jendrik SeippVersatile Cost Partitioning with Exact Sensitivity AnalysisIn Proceedings of the ThirtyFourth International Conference on Automated Planning and Scheduling (ICAPS 2024). 2024.
Saturated posthoc 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.

Daniel Gnad and David SpeckOn an Attempt at Casting Orbit Search as a Task TransformationIn ICAPS 2024 Workshop on Echoing (failed) Efforts in Planning (WEEP). 2024.
Statespace reduction techniques are a powerful means to enhancing the performance of searchbased planners. Recent work has shown that decoupled search, which compactly represents sets of states, can be cast as a task reformulation. Concretely, it is possible to exactly simulate the behavior and reduction of (nonoptimal) decoupled search by applying a transformation to the input task and running regular search on the transformed task. In this work, we investigate if the same approach is feasible for symmetry breaking, in particular orbit space search (OSS). One of the challenges in this endeavor is that OSS dynamically computes a canonical representative of every state generated during search. To represent this computation as a task transformation, however, we need to fix the procedure at transformation time. This leads to reduced pruning potential, which we discuss in detail and verify empirically. We also discuss an approach that can fully simulate OSS, at the cost of vastly blowingup the task size.
2023

Paul Höft, David Speck and Jendrik SeippSensitivity Analysis for Saturated Posthoc Optimization in Classical PlanningIn Proceedings of the TwentySixth European Conference on Artificial Intelligence (ECAI 2023). 2023.
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 posthoc 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.

Remo Christen, Salomé Eriksson, Michael Katz, Christian Muise, Alice Petrov, Florian Pommerening, Jendrik Seipp, Silvan Sievers and David SpeckPARIS: Planning Algorithms for Reconfiguring Independent SetsIn Proceedings of the TwentySixth European Conference on Artificial Intelligence (ECAI 2023). 2023.
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 rerun the entire competition under equal computational conditions. Besides showcasing the success of planning technology, we hope that this work will create a crossfertilization of the two research fields.

David Speck, Paul Höft, Daniel Gnad and Jendrik SeippFinding Matrix Multiplication Algorithms with Classical PlanningIn Proceedings of the ThirtyThird International Conference on Automated Planning and Scheduling (ICAPS 2023), pp. 411–416. 2023.
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 singleplayer game. By learning how to play this game efficiently, the newlyintroduced 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 stateoftheart 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.

Gregor Behnke, David Speck, Michael Katz and Shirin SohrabiOn Partial Satisfaction Planning with TotalOrder HTNsIn Proceedings of the ThirtyThird International Conference on Automated Planning and Scheduling (ICAPS 2023), pp. 42–51. 2023.
Since its introduction, partial satisfaction planning (PSP), including both oversubscription (OSP) and netbenefit, 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 netbenefit 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.

Dominik Drexler, Daniel Gnad, Paul Höft, Jendrik Seipp, David Speck and Simon StåhlbergRagnarokIn Tenth International Planning Competition (IPC10): Planner Abstracts. 2023.
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 postcompetition fixes, available at https://github.com/ipc2023classical/planner17/tree/latest.

Dominik Drexler, Jendrik Seipp and David SpeckOdin: A Planner Based on Saturated Transition Cost PartitioningIn Tenth International Planning Competition (IPC10): Planner Abstracts. 2023.
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.

David SpeckSymK – A Versatile Symbolic Search PlannerIn Tenth International Planning Competition (IPC10): Planner Abstracts. 2023.
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.

Paul Höft, David Speck and Jendrik SeippDofri: Planner AbstractIn Tenth International Planning Competition (IPC10): Planner Abstracts. 2023.
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 timeconsuming 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 Posthoc 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.

Remo Christen, Salomé Eriksson, Michael Katz, Christian Muise, Alice Petrov, Florian Pommerening, Jendrik Seipp, Silvan Sievers and David SpeckPARIS: Planning Algorithms for Reconfiguring Independent SetsIn ICAPS 2023 Scheduling and Planning Applications woRKshop (SPARK). 2023.Superseded by the ECAI 2023 paper with the same name.
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 reran 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 crossfertilization of the two research fields.

Remo Christen, Salomé Eriksson, Michael Katz, Christian Muise, Alice Petrov, Florian Pommerening, Jendrik Seipp, Silvan Sievers and David SpeckPARIS: Planning Algorithms for Reconfiguring Independent SetsIn ICAPS 2023 Workshop on Heuristics and Search for Domainindependent Planning (HSDIP). 2023.Superseded by the ECAI 2023 paper with the same name.
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 rerun the entire competition under equal computational conditions. Besides showcasing the success of planning technology, we hope that this work will create a crossfertilization of the two research fields.

David Speck, Paul Höft, Daniel Gnad and Jendrik SeippFinding Matrix Multiplication Algorithms with Classical Planning  Extended AbstractIn The 35th Annual Workshop of the Swedish Artificial Intelligence Society (SAIS). 2023.Superseded by the ICAPS 2023 paper with the same name.
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 singleplayer game. By learning how to play this game efficiently, the newlyintroduced 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 stateoftheart 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.
2022

Kilian Hu and David SpeckOn 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.
Heuristic search is a successful approach to costoptimal 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.

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 DescriptionIn First CoRe Challenge: Solver and Graph Descriptions, pp. 15–22. 2022.
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 stateoftheart solvers to solve these instances. Throughout this document, we describe the encoding, solvers, and overall search setup.

André Biedenkapp, David Speck, Silvan Sievers, Frank Hutter, Marius Lindauer and Jendrik SeippLearning DomainIndependent Policies for Open List SelectionIn ICAPS 2022 Workshop on Bridging the Gap Between AI Planning and Reinforcement Learning (PRL). 2022.
Since its proposal over a decade ago, LAMA has been considered one of the bestperforming 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, adhoc policy for open list selection, LAMA achieves stateoftheart results. In this paper, we propose to use dynamic algorithm configuration to learn such policies in a principled and datadriven manner. On the learning side, we show how to train a reinforcement learning agent over several heterogeneous environments, aiming at zeroshot 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.

David Speck and Jendrik SeippNew Refinement Strategies for Cartesian AbstractionsIn Proceedings of the ThirtySecond International Conference on Automated Planning and Scheduling (ICAPS 2022), pp. 348–352. 2022.
Cartesian counterexampleguided 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.

Julian von Tschammer, Robert Mattmüller and David SpeckLoopless TopK PlanningIn Proceedings of the ThirtySecond International Conference on Automated Planning and Scheduling (ICAPS 2022), pp. 380–384. 2022.
In topk 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 topk planning. We show how to enhance the stateoftheart symbolic topk planner, symK, to obtain an efficient, sound and complete algorithm for loopless topk planning. An empirical evaluation shows that our proposed approach has a higher kcoverage than a generateandtest approach that uses an ordinary topk planner, which we show to be incomplete in the presence of zerocost loops.

David SpeckSymbolic Search for Optimal Planning with Expressive ExtensionsPhD thesis, University of Freiburg, Germany, 2022.
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 domainindependent, 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 costoptimal planning for different expressive extensions of classical planning, all capturing different aspects of the problem. In particular, we study planning with axioms, planning with statedependent action costs, oversubscription planning, and topk 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 stateoftheart costoptimal 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.
2021

David Speck, David Borukhson, Robert Mattmüller and Bernhard NebelOn the Compilability and Expressive Power of StateDependent Action CostsIn Proceedings of the ThirtyFirst International Conference on Automated Planning and Scheduling (ICAPS 2021), pp. 358–366. 2021.
While statedependent 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 statedependent 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 noncompilability 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.

David Speck, André Biedenkapp, Frank Hutter, Robert Mattmüller and Marius LindauerLearning Heuristic Selection with Dynamic Algorithm ConfigurationIn Proceedings of the ThirtyFirst International Conference on Automated Planning and Scheduling (ICAPS 2021), pp. 597–605. 2021.
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 domainwise learned policies, which take the internal search dynamics of a planning system into account, can exceed existing approaches.

Dominik Drexler, Jendrik Seipp and David SpeckSubsetSaturated Transition Cost PartitioningIn Proceedings of the ThirtyFirst International Conference on Automated Planning and Scheduling (ICAPS 2021), pp. 131–139. 2021.
Cost partitioning admissibly combines the information from multiple heuristics for optimal statespace 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 subsetsaturated transition cost partitioning algorithm usually yields stronger heuristics than the two generalizations by themselves.

David Speck and Michael KatzSymbolic Search for Oversubscription PlanningIn Proceedings of the ThirtyFifth AAAI Conference on Artificial Intelligence (AAAI 2021), pp. 11972–11980. 2021.
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 statespace heuristic search, the current state of the art for oversubscription planning.

Gregor Behnke and David SpeckSymbolic Search for Optimal TotalOrder HTN PlanningIn Proceedings of the ThirtyFifth AAAI Conference on Artificial Intelligence (AAAI 2021), pp. 11744–11754. 2021.
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 (totallyordered) 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 totallyordered HTN planning.
2020

David Speck, Florian Geißer and Robert MattmüllerWhen Perfect is not Good Enough: On the Search Behaviour of Symbolic Heuristic SearchIn Proceedings of the Thirtieth International Conference on Automated Planning and Scheduling (ICAPS 2020), pp. 263–271. 2020.
Symbolic search has proven to be a competitive approach to costoptimal 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.

David Speck, Robert Mattmüller and Bernhard NebelSymbolic Topk PlanningIn Proceedings of the ThirtyFourth AAAI Conference on Artificial Intelligence (AAAI 2020), pp. 9967–9974. 2020.
The objective of topk 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 topk planning is PSPACEcomplete, 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 PPhard, while the ordinary case is NPhard. We present a novel approach to topk planning, called SYMK, which is based on symbolic search, and prove that SYMK is sound and complete. Our empirical analysis shows that SYMK exceeds the current state of the art for both small and large k.

Florian Geißer, David Speck and Thomas KellerTrialbased Heuristic Tree Search for MDPs with Factored Action SpacesIn Proceedings of the 13th Annual Symposium on Combinatorial Search (SoCS 2020), pp. 38–47. 2020.
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 trialbased 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 stateaction 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.

David Speck, André Biedenkapp, Frank Hutter, Robert Mattmüller and Marius LindauerLearning Heuristic Selection with Dynamic Algorithm ConfigurationIn 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.
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 domainwise learned policies, which take the internal search dynamics of a planning system into account, can exceed existing approaches in terms of coverage.

Dominik Drexler, David Speck and Robert MattmüllerSubsetSaturated Transition Cost Partitioning for Optimal Classical PlanningIn ICAPS 2020 Workshop on Heuristics and Search for DomainIndependent Planning (HSDIP), pp. 23–31. 2020.Superseded by the ICAPS 2021 paper "SubsetSaturated Transition Cost Partitioning".
Cost partitioning admissibly combines the information from multiple heuristics for statespace 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 subsetsaturated 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.
2019

David Speck, Florian Geißer, Robert Mattmüller and Álvaro TorralbaSymbolic Planning with AxiomsIn Proceedings of the TwentyNinth International Conference on Automated Planning and Scheduling (ICAPS 2019), pp. 464–572. 2019.
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 costoptimal 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 costoptimal classical planning with axioms.

Sumitra Corraya, Florian Geißer, David Speck and Robert MattmüllerAn Empirical Study of the Usefulness of StateDependent Action Costs in PlanningIn Proceedings of the 42nd Annual German Conference on Artificial Intelligence (KI 2019), pp. 123–130. 2019.
The vast majority of work in planning to date has focused on stateindependent action costs. However, if a planning task features statedependent costs, using a cost model with stateindependent 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 statedependent 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.

Florian Geißer, David Speck and Thomas KellerAn Analysis of the Probabilistic Track of the IPC 2018In ICAPS 2019 Workshop on the International Planning Competition (WIPC), pp. 27–35. 2019.
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 topperformers, including their postcompetition versions, and a brief analysis of their performance highlights the strengths and weaknesses of the individual approaches.

Olga Speck, Rafael Horn, David Speck, Johannes Gantner and Philip LeistnerBiomimetics meets SustainabilityIn Bionik: Patente aus der Natur. Tagungsbeiträge zum 9. BionikKongress, pp. 81–91. 2019.
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 technologyderived and biologyderived 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 biologyderived and technologyderived 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).
2018

David Speck, Florian Geißer and Robert MattmüllerSymbolic Planning with EdgeValued MultiValued Decision DiagramsIn Proceedings of the TwentyEighth International Conference on Automated Planning and Scheduling (ICAPS 2018). 2018.
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 statedependent action costs into account. Here, costs are represented as Edgevalued Multivalued 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 EVMDDbased symbolic search for optimal planning. We define EVMDDbased representations of state sets and transition relations, and show how to compute the necessary operations required for EVMDDA*. This EVMDDbased version of symbolic A* generalizes its BDD variant, and allows to solve planning tasks with statedependent action costs. We prove theoretically that our approach is sound, complete and optimal. Additionally, we present an empirical analysis comparing EVMDDA* to BDDA* and explicit A* search. Our results underscore the usefulness of symbolic approaches and the feasibility of dealing with models that go beyond unit costs.

Florian Geißer and David SpeckProstDD – Utilizing Symbolic Classical Planning in THTSIn Sixth International Probabilistic Planning Competition (IPPC6): Planner Abstracts, pp. 13–16. 2018.
We describe PROSTDD, our submission to the International Probabilistic Planning Competition 2018. Like its predecessor PROST, which already participated with success at the previous IPPC, PROSTDD is based on the trialbased 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 statedependent 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.

David Speck, Florian Geißer and Robert MattmüllerSYMPLE: Symbolic Planning based on EVMDDsIn Ninth International Planning Competition (IPC9): Planner Abstracts, pp. 82–85. 2018.
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 Edgevalued Multivalued Decision Diagrams (EVMDDs), which have some structural advantages over BDDs.
2017

David Speck, Christian Dornhege and Wolfram BurgardShakey 2016 – How Much Does it Take to Redo Shakey the Robot?IEEE Robotics and Automation Letters (RAL) 2.2, pp. 1203–1209. 2017.
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 opensource Shakey 2016 system. Hereby, we demonstrate the impact of research by showing that ideas from the original Shakey are still alive in stateoftheart 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 opensource software. We experimentally evaluate the system in realworld scenarios on a PR2 robot and a Turtlebotbased 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.

Olga Speck, David Speck, Rafael Horn, Johannes Gantner and Klaus Peter SedlbauerBiomimetic bioinspired biomorph sustainable? An attempt to classify and clarify biologyderived technical developmentsBioinspiration and Biomimetics 12.1, pp. 011004. 2017.
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 bioderived developments are often described as sustainable. The objective of this paper is to rationalize and refine the discussion about bioderived 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 biologyderived and technologyderived 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 biologyderived and technologyderived 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 technologyderived 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.
2015

David Speck, Manuela Ortlieb and Robert MattmüllerNecessary Observations in Nondeterministic PlanningIn Proceedings of the 38th Annual German Conference on Artificial Intelligence (KI 2015), pp. 181–193. 2015.
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 bottomup 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.