David Speck – Publications

2024

• David Speck and Daniel Gnad.
  Decoupled Search for the Masses: A Novel Task Transformation for Classical Planning.
  In Proceedings of the 34th International Conference on Automated Planning and Scheduling (ICAPS 2024), pp. 546-554. 2024.
  (Show abstract) (Hide abstract) (PDF) (appendix, code, scripts and data)
  

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

• Paul Höft, David Speck, Florian Pommerening and Jendrik Seipp.
  Versatile Cost Partitioning with Exact Sensitivity Analysis.
  In Proceedings of the 34th International Conference on Automated Planning and Scheduling (ICAPS 2024), pp. 276-280. 2024.
  (Show abstract) (Hide abstract) (PDF) (code, scripts and data)
  

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

• Daniel Gnad and David Speck.
  On an Attempt at Casting Orbit Search as a Task Transformation.
  In Proceedings of the ICAPS 2024 Workshop on Echoing (failed) Efforts in Planning (WEEP 2024). 2024.
  (Show abstract) (Hide abstract) (PDF)
  

  State-space reduction techniques are a powerful means to enhancing the performance of search-based 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 (non-optimal) 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 blowing-up the task size.