David Speck – Publications

(Show all abstracts) (Hide all abstracts)

2022

David Speck and Jendrik Seipp.
New Refinement Strategies for Cartesian Abstractions.
In Proceedings of the 32nd International Conference on Automated Planning and Scheduling (ICAPS 2022). 2022.
(Show abstract) (Hide abstract) (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.
Julian von Tschammer, Robert Mattmüller and David Speck.
Loopless Top-k Planning.
In Proceedings of the 32nd International Conference on Automated Planning and Scheduling (ICAPS 2022). 2022.
(Show abstract) (Hide abstract) (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.
David Speck.
Symbolic Search for Optimal Planning with Expressive Extensions.
FreiDok plus 2022.
PhD Thesis.
(Show abstract) (Hide abstract) (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.

2021

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 31st International Conference on Automated Planning and Scheduling (ICAPS 2021), pp. 358-366. 2021.
(Show abstract) (Hide abstract) (PDF)

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.
David Speck, André Biedenkapp, Frank Hutter, Robert Mattmüller and Marius Lindauer.
Learning Heuristic Selection with Dynamic Algorithm Configuration.
In Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS 2021), pp. 597-605. 2021.
(Show abstract) (Hide abstract) (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 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.
Dominik Drexler, Jendrik Seipp and David Speck.
Subset-Saturated Transition Cost Partitioning.
In Proceedings of the 31st International Conference on Automated Planning and Scheduling (ICAPS 2021), pp. 131-139. 2021.
(Show abstract) (Hide abstract) (PDF)

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.
David Speck and Michael Katz.
Symbolic Search for Oversubscription Planning.
In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021), pp. 11972-11980. 2021.
(Show abstract) (Hide abstract) (PDF)

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.
Gregor Behnke and David Speck.
Symbolic Search for Optimal Total-Order HTN Planning.
In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI 2021), p. 11744–11754. 2021.
(Show abstract) (Hide abstract) (PDF)

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.

2020

David Speck, André Biedenkapp, Frank Hutter, Robert Mattmüller and Marius Lindauer.
Learning Heuristic Selection with Dynamic Algorithm Configuration.
In Proceedings of the Workshop on Bridging the Gap Between AI Planning and Reinforcement Learning (PRL 2020), p. 61–69. 2020.
Superseded by the ICAPS 2021 paper by the same authors.
(Show abstract) (Hide abstract) (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.
Dominik Drexler, David Speck and Robert Mattmüller.
Subset-Saturated Transition Cost Partitioning for Optimal Classical Planning.
In Proceedings of the 12th Workshop on Heuristics and Search for Domain-Independent Planning (HSDIP 2020), p. 23–31. 2020.
Superseded by the ICAPS 2021 paper "Subset-Saturated Transition Cost Partitioning".
(Show abstract) (Hide abstract) (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.
David Speck, André Biedenkapp, Frank Hutter, Robert Mattmüller and Marius Lindauer.
Learning Heuristic Selection with Dynamic Algorithm Configuration.
Technical Report arXiv:2006.08246, arxiv cs.AI, 2020.
Superseded by the PRL 2020 paper by the same authors.
(Show abstract) (Hide abstract) (PDF; Online)

A key challenge in satisfying 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.
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 30th International Conference on Automated Planning and Scheduling (ICAPS 2020), pp. 263-271. 2020.
(Show abstract) (Hide abstract) (PDF)

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.
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.
(Show abstract) (Hide abstract) (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.
David Speck, Robert Mattmüller and Bernhard Nebel.
Symbolic Top-k Planning.
In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI 2020), pp. 9967-9974. 2020.
(Show abstract) (Hide abstract) (PDF)

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.

2019

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 German Conference on Artificial Intelligence (KI 2019), pp. 123-130. 2019.
(Show abstract) (Hide abstract) (PDF) (PDF; Online)

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.
Florian Geißer, David Speck and Thomas Keller.
An Analysis of the Probabilistic Track of the IPC 2018.
In Proceedings of the ICAPS-2019 Workshop on the International Planning Competition (WIPC 2019), pp. 27-35. 2019.
(Show abstract) (Hide abstract) (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.
David Speck, Florian Geißer, Robert Mattmüller and Álvaro Torralba.
Symbolic Planning with Axioms.
In Proceedings of the 29th International Conference on Automated Planning and Scheduling (ICAPS 2019), pp. 464-572. 2019.
(Show abstract) (Hide abstract) (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.
Olga Speck, Rafael Horn, David Speck and Johannes Gantner and Philip Leistner.
Biomimetics meets Sustainability.
In Bionik: Patente aus der Natur. Tagungsbeiträge zum 9. Bionik-Kongress in Bremen, pp. 81-91. 2019.
(Show abstract) (Hide abstract) (PDF; Online)

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).

2018

David Speck, Florian Geißer and Robert Mattmüller.
Symbolic Planning with Edge-Valued Multi-Valued Decision Diagrams.
In Proceedings of the 28th International Conference on Automated Planning and Scheduling (ICAPS 2018). 2018.
(Show abstract) (Hide abstract) (PDF) (technical report with proofs; PDF)

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.
Florian Geißer and David Speck.
PROST-DD - Utilizing Symbolic Classical Planning in THTS.
In The 6th International Probabilistic Planning Competition (IPPC 2018), pp. 13-16. 2018.
(Show abstract) (Hide abstract) (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.
David Speck, Florian Geißer and Robert Mattmüller.
SYMPLE: Symbolic Planning based on EVMDDs.
In The 9th International Planning Competition (IPC 2018), pp. 82-85. 2018.
(Show abstract) (Hide abstract) (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.

2017

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.
(Show abstract) (Hide abstract) (PDF; Online)

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.
Olga Speck, David Speck, Rafael Horn and Johannes Gantner and Klaus Peter Sedlbauer.
Biomimetic bio-inspired biomorph sustainable? An attempt to classify and clarify biology-derived technical developments.
Bioinspiration & Biomimetics (B&B) 12 (1), p. 011004. 2017.
(Show abstract) (Hide abstract) (PDF; Online)

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.

2015

David Speck, Manuela Ortlieb and Robert Mattmüller.
Necessary Observations in Nondeterministic Planning.
In Proceedings of the 38th German Conference on Artificial Intelligence (KI 2015). 2015.
(Show abstract) (Hide abstract) (PDF) (BIB)

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.