Silvan Sievers

ECAI Conference 2024 Conference Paper

Merge-and-Shrink Heuristics for SSPs with Prune Transformations

• Thorsten Klößner
• Álvaro Torralba
• Marcel Steinmetz
• Silvan Sievers

The merge-and-shrink framework is a powerful tool for constructing state-of-the-art admissible heuristics in classical planning. Recent work has begun generalizing the complex theory behind this framework to probabilistic planning in forms of stochastic shortest-path problems (SSPs). There however remain two important gaps. Firstly, although the previous work makes substantial efforts, the probabilistic merge-and-shrink theory is still incomplete, lacking in particular prune transformations, i. e. , transformations discarding uninteresting states, effectively reducing the size of the abstraction without losing relevant information. Secondly, an actual implementation and experimental evaluation of the merge-and-shrink framework for SSPs is so far missing. Here, we round off the previous work by contributing both a theoretical analysis of prune transformations, as well as an empirical evaluation of merge-and-shrink heuristics. Our results show that merge-and-shrink heuristics outperform previous single abstraction heuristics, but do not quite reach the performance of state-of-the-art additive combinations of such heuristics yet.

ICAPS Conference 2024 Conference Paper

Merging or Computing Saturated Cost Partitionings? A Merge Strategy for the Merge-and-Shrink Framework

• Silvan Sievers
• Thomas Keller 0001
• Gabriele Röger

The merge-and-shrink framework is a powerful tool for computing abstraction heuristics for optimal classical planning. Merging is one of its name-giving transformations. It entails computing the product of two factors of a factored transition system. To decide which two factors to merge, the framework uses a merge strategy. While there exist many merge strategies, it is generally unclear what constitutes a strong merge strategy, and a previous analysis shows that there is still lots of room for improvement with existing merge strategies. In this paper, we devise a new scoring function for score-based merge strategies based on answering the question whether merging two factors has any benefits over computing saturated cost partitioning heuristics over the factors instead. Our experimental evaluation shows that our new merge strategy achieves state-of-the-art performance on IPC benchmarks.

ICAPS Conference 2023 Conference Paper

A Theory of Merge-and-Shrink for Stochastic Shortest Path Problems

• Thorsten Klößner
• Álvaro Torralba
• Marcel Steinmetz
• Silvan Sievers

The merge-and-shrink framework is a powerful tool to construct state space abstractions based on factored representations. One of its core applications in classical planning is the construction of admissible abstraction heuristics. In this paper, we develop a compositional theory of merge-and-shrink in the context of probabilistic planning, focusing on stochastic shortest path problems (SSPs). As the basis for this development, we contribute a novel factored state space model for SSPs. We show how general transformations, including abstractions, can be formulated on this model to derive admissible and/or perfect heuristics. To formalize the merge-and-shrink framework for SSPs, we transfer the fundamental merge-and-shrink transformations from the classical setting: shrinking, merging, and label reduction. We analyze the formal properties of these transformations in detail and show how the conditions under which shrinking and label reduction lead to perfect heuristics can be extended to the SSP setting.

ICAPS Conference 2023 Conference Paper

Computing Domain Abstractions for Optimal Classical Planning with Counterexample-Guided Abstraction Refinement

• Raphael Kreft
• Clemens Büchner
• Silvan Sievers
• Malte Helmert

Abstraction heuristics are the state of the art in optimal classical planning as heuristic search. A popular method for computing abstractions is the counterexample-guided abstraction refinement (CEGAR) principle, which has successfully been used for projections, which are the abstractions underlying pattern databases, and Cartesian abstractions. While projections are simple and fast to compute, Cartesian abstractions subsume projections and hence allow more fine-grained abstractions, however at the expense of efficiency. Domain abstractions are a third class of abstractions between projections and Cartesian abstractions in terms of generality. Yet, to the best of our knowledge, they are only briefly considered in the planning literature but have not been used for computing heuristics yet. We aim to close this gap and compute domain abstractions by using the CEGAR principle. Our empirical results show that domain abstractions compare favorably against projections and Cartesian abstractions.

ICAPS Conference 2023 Conference Paper

Efficient Evaluation of Large Abstractions for Decoupled Search: Merge-and-Shrink and Symbolic Pattern Databases

• Daniel Gnad 0001
• Silvan Sievers
• Álvaro Torralba

Abstraction heuristics are a state-of-the-art technique to solve classical planning problems optimally. A common approach is to precompute many small abstractions and combine them admissibly using cost partitioning. Recent work has shown that this approach does not work out well when using such heuristics for decoupled state space search, where search nodes represent potentially large sets of states. This is due to the fact that admissibly combining the estimates of several heuristics without sacrificing accuracy is NP-hard for decoupled states. In this work we propose to use a single large abstraction instead. We focus on merge-and-shrink and symbolic pattern database heuristics, which are designed to produce such abstractions. For these heuristics, we prove that the evaluation of decoupled states is NP-hard in general, but we also identify conditions under which it is polynomial. We introduce algorithms for both the general and the polynomial case. Our experimental evaluation shows that single large abstraction heuristics lead to strong performance when the heuristic evaluation is polynomial.

ECAI Conference 2023 Conference Paper

PARIS: Planning Algorithms for Reconfiguring Independent Sets

• Remo Christen
• Salomé Eriksson
• Michael Katz 0001
• Christian J. Muise
• Alice Petrov
• Florian Pommerening
• Jendrik Seipp
• Silvan Sievers

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

SoCS Conference 2022 Conference Paper

Additive Pattern Databases for Decoupled Search

• Silvan Sievers
• Daniel Gnad 0001
• Álvaro Torralba

Abstraction heuristics are the state of the art in optimal classical planning as heuristic search. Despite their success for explicit-state search, though, abstraction heuristics are not available for decoupled state-space search, an orthogonal reduction technique that can lead to exponential savings by decomposing planning tasks. In this paper, we show how to compute pattern database (PDB) heuristics for decoupled states. The main challenge lies in how to additively employ multiple patterns, which is crucial for strong search guidance of the heuristics. We show that in the general case, for arbitrary collections of PDBs, computing the heuristic for a decoupled state is exponential in the number of leaf components of decoupled search. We derive several variants of decoupled PDB heuristics that allow to additively combine PDBs avoiding this blow-up and evaluate them empirically.

ICAPS Conference 2022 Conference Paper

On the Complexity of Heuristic Synthesis for Satisficing Classical Planning: Potential Heuristics and Beyond

• Malte Helmert
• Silvan Sievers
• Alexander Rovner
• Augusto B. Corrêa

Potential functions are a general class of heuristics for classical planning. For satisficing planning, previous work suggested the use of descending and dead-end avoiding (DDA) potential heuristics, which solve planning tasks by backtrack-free search. In this work we study the complexity of devising DDA potential heuristics for classical planning tasks. We show that verifying or synthesizing DDA potential heuristics is PSPACE-complete, but suitable modifications of the DDA properties reduce the complexity of these problems to the first and second level of the polynomial hierarchy. We also discuss the implications of our results for other forms of heuristic synthesis in classical planning.

ICAPS Conference 2021 Conference Paper

Automatic Instance Generation for Classical Planning

• Álvaro Torralba
• Jendrik Seipp
• Silvan Sievers

The benchmarks from previous International Planning Competitions (IPCs) are the de-facto standard for evaluating planning algorithms. The IPC set is both a collection of planning domains and a selection of instances from these domains. Most of the domains come with a parameterized generator that generates new instances for a given set of parameter values. Due to the steady progress of planning research some of the instances that were generated for past IPCs are inadequate for evaluating current planners. To alleviate this problem, we introduce Autoscale, an automatic tool that selects instances for a given domain. Autoscale takes into account constraints from the domain designer as well as the performance of current planners to generate an instance set of appropriate difficulty, while avoiding too much bias with respect to the considered planners. We show that the resulting benchmark set is superior to the IPC set and has the potential of improving empirical evaluation of planning research.

ICAPS Conference 2021 Conference Paper

Dantzig-Wolfe Decomposition for Cost Partitioning

• Florian Pommerening
• Thomas Keller 0001
• Valentina Halasi
• Jendrik Seipp
• Silvan Sievers
• Malte Helmert

Optimal cost partitioning can produce high quality heuristic estimates even from small abstractions. It can be computed with a linear program (LP) but the size of this LP often makes this impractical. Recent work used Lagrangian decomposition to speed up the computation. Here we use a different decomposition technique called Dantzig-Wolfe decomposition to tackle the problem. This gives new insights into optimal cost partitioning and has several advantages over Lagrangian decomposition: our method detects when a cost partition is optimal; it can deal with general cost functions; and it does not consider abstractions in the linear program that do not contribute to the heuristic value. We also show the advantage of the method empirically and investigate several improvements that are useful for all cost partitioning methods.

JAIR Journal 2021 Journal Article

Merge-and-Shrink: A Compositional Theory of Transformations of Factored Transition Systems

• Silvan Sievers
• Malte Helmert

The merge-and-shrink framework has been introduced as a general approach for defining abstractions of large state spaces arising in domain-independent planning and related areas. The distinguishing characteristic of the merge-and-shrink approach is that it operates directly on the factored representation of state spaces, repeatedly modifying this representation through transformations such as shrinking (abstracting a factor of the representation), merging (combining two factors), label reduction (abstracting the way in which different factors interact), and pruning (removing states or transitions of a factor). We provide a novel view of the merge-and-shrink framework as a “toolbox” or “algebra” of transformations on factored transition systems, with the construction of abstractions as only one possible application. For each transformation, we study desirable properties such as conservativeness (overapproximating the original transition system), inducedness (absence of spurious states and transitions), and refinability (reconstruction of paths in the original transition system from the transformed one). We provide the first complete characterizations of the conditions under which these desirable properties can be achieved. We also provide the first full formal account of factored mappings, the mechanism used within the merge-and-shrink framework to establish the relationship between states in the original and transformed factored transition system. Unlike earlier attempts to develop a theory for merge-and-shrink, our approach is fully compositional: the properties of a sequence of transformations can be entirely understood by the properties of the individual transformations involved. This aspect is key to the use of merge-and-shrink as a general toolbox for transforming factored transition systems. New transformations can easily be added to our theory, with compositionality taking care of the seamless integration with the existing components. Similarly, new properties of transformations can be integrated into the theory by showing their compositionality and studying under which conditions they are satisfied by the building blocks of merge-and-shrink.

IJCAI Conference 2021 Conference Paper

On Weak Stubborn Sets in Classical Planning

• Silvan Sievers
• Martin Wehrle

Stubborn sets are a pruning technique for state-space search which is well established in optimal classical planning. In this paper, we show that weak stubborn sets introduced in recent work in planning are actually not weak stubborn sets in Valmari's original sense. Based on this finding, we introduce weak stubborn sets in the original sense for planning by providing a generalized definition analogously to generalized strong stubborn sets in previous work. We discuss the relationship of strong, weak and the previously called weak stubborn sets, thus providing a further step in getting an overall picture of the stubborn set approach in planning.

SoCS Conference 2020 Conference Paper

An Atom-Centric Perspective on Stubborn Sets

• Gabriele Röger
• Malte Helmert
• Jendrik Seipp
• Silvan Sievers

Stubborn sets are an optimality-preserving pruning technique for factored state-space search, for example in classical planning. Their applicability is limited by their computational overhead. We describe a new algorithm for computing stubborn sets that is based on the state variables of the state space, while previous algorithms are based on its actions. Typical factored state spaces tend to have far fewer state variables than actions, and therefore our new algorithm is much more efficient than the previous state of the art, making stubborn sets a viable technique in many cases where they previously were not.

IJCAI Conference 2020 Conference Paper

Cost-Partitioned Merge-and-Shrink Heuristics for Optimal Classical Planning

• Silvan Sievers
• Florian Pommerening
• Thomas Keller
• Malte Helmert

Cost partitioning is a method for admissibly combining admissible heuristics. In this work, we extend this concept to merge-and-shrink (M&S) abstractions that may use labels that do not directly correspond to operators. We investigate how optimal and saturated cost partitioning (SCP) interact with M&S transformations and develop a method to compute SCPs during the computation of M&S. Experiments show that SCP significantly improves M&S on standard planning benchmarks.

ICAPS Conference 2019 Conference Paper

Counterexample-Guided Abstraction Refinement for Pattern Selection in Optimal Classical Planning

• Alexander Rovner
• Silvan Sievers
• Malte Helmert

We describe a new algorithm for generating pattern collections for pattern database heuristics in optimal classical planning. The algorithm uses the counterexample-guided abstraction refinement (CEGAR) principle to guide the pattern selection process. Our experimental evaluation shows that a single run of the CEGAR algorithm can compute informative pattern collections in a fairly short time. Using multiple CEGAR algorithm runs, we can compute much larger pattern collections, still in shorter time than existing approaches, which leads to a planner that outperforms the state-of-the-art pattern selection methods by a significant margin.

AAAI Conference 2019 Conference Paper

Deep Learning for Cost-Optimal Planning: Task-Dependent Planner Selection

• Silvan Sievers
• Michael Katz
• Shirin Sohrabi
• Horst Samulowitz
• Patrick Ferber

As classical planning is known to be computationally hard, no single planner is expected to work well across many planning domains. One solution to this problem is to use online portfolio planners that select a planner for a given task. These portfolios perform a classification task, a well-known and wellresearched task in the field of machine learning. The classification is usually performed using a representation of planning tasks with a collection of hand-crafted statistical features. Recent techniques in machine learning that are based on automatic extraction of features have not been employed yet due to the lack of suitable representations of planning tasks. In this work, we alleviate this barrier. We suggest representing planning tasks by images, allowing to exploit arguably one of the most commonly used and best developed techniques in deep learning. We explore some of the questions that inevitably rise when applying such a technique, and present various ways of building practically useful online portfoliobased planners. An evidence of the usefulness of our proposed technique is a planner that won the cost-optimal track of the International Planning Competition 2018.

IJCAI Conference 2019 Conference Paper

Merge-and-Shrink Task Reformulation for Classical Planning

• Álvaro Torralba
• Silvan Sievers

The performance of domain-independent planning systems heavily depends on how the planning task has been modeled. This makes task reformulation an important tool to get rid of unnecessary complexity and increase the robustness of planners with respect to the model chosen by the user. In this paper, we represent tasks as factored transition systems (FTS), and use the merge-and-shrink (M&S) framework for task reformulation for optimal and satisficing planning. We prove that the flexibility of the underlying representation makes the M&S reformulation methods more powerful than the counterparts based on the more popular finite-domain representation. We adapt delete-relaxation and M&S heuristics to work on the FTS representation and evaluate the impact of our reformulation.

ICAPS Conference 2019 Conference Paper

Theoretical Foundations for Structural Symmetries of Lifted PDDL Tasks

• Silvan Sievers
• Gabriele Röger
• Martin Wehrle
• Michael Katz 0001

We transfer the notion of structural symmetries to lifted planning task representations, based on abstract structures which we define to model planning tasks. We show that symmetries are preserved by common grounding methods and we shed some light on the relation to previous symmetry concepts used in planning. Using a suitable graph representation of lifted tasks, our experimental analysis of common planning benchmarks reveals that symmetries occur in the lifted representation of many domains. Our work establishes the theoretical ground for exploiting symmetries beyond their previous scope, such as for faster grounding and mutex generation, as well as for state space transformations and reductions.

SoCS Conference 2018 Conference Paper

Merge-and-Shrink Heuristics for Classical Planning: Efficient Implementation and Partial Abstractions

• Silvan Sievers

Merge-and-shrink heuristics are a successful class of abstraction heuristics used for optimal classical planning. With the recent addition of generalized label reduction, merge-and-shrink can be understood as an algorithm framework that repeatedly applies transformations to a factored representation of a given planning task to compute an abstraction. In this paper, we describe an efficient implementation of the framework and its transformations, comparing it to its previous implementation in Fast Downward. We further discuss partial merge-and-shrink abstractions that do not consider all aspects of the concrete state space. To compute such partial abstractions, we stop the merge-and-shrink computation early by imposing simple limits on the resource consumption of the algorithm. Our evaluation shows that the efficient implementation indeed improves over the previous one, and that partial merge-and-shrink abstractions further push the efficiency of merge-and-shrink planners.

ICAPS Conference 2018 Conference Paper

Symmetry-Based Task Reduction for Relaxed Reachability Analysis

• Gabriele Röger
• Silvan Sievers
• Michael Katz 0001

Relaxed reachability analysis is relevant to efficient grounding, invariant synthesis as well as the computation of relaxation-based heuristics. Planning domains are typically specified in a lifted representation, where the size of the tasks grows exponentially with the number of objects in the world. This growth also affects the analysis of relaxed reachability. We present a task reduction based on symmetries of the lifted representation that allows to perform the same analysis on smaller tasks.

SoCS Conference 2017 Conference Paper

Strengthening Canonical Pattern Databases with Structural Symmetries

• Silvan Sievers
• Martin Wehrle
• Malte Helmert
• Michael Katz 0001

Symmetry-based state space pruning techniques have proved to greatly improve heuristic search based classical planners. Similarly, abstraction heuristics in general and pattern databases in particular are key ingredients of such planners. However, only little work has dealt with how the abstraction heuristics behave under symmetries. In this work, we investigate the symmetry properties of the popular canonical pattern databases heuristic. Exploiting structural symmetries, we strengthen the canonical pattern databases by adding symmetric pattern databases, making the resulting heuristic invariant under structural symmetry, thus making it especially attractive for symmetry-based pruning search methods. Further, we prove that this heuristic is at least as informative as using symmetric lookups over the original heuristic. An experimental evaluation confirms these theoretical results.

ICAPS Conference 2016 Conference Paper

An Analysis of Merge Strategies for Merge-and-Shrink Heuristics

• Silvan Sievers
• Martin Wehrle
• Malte Helmert

The merge-and-shrink framework provides a general basis for the computation of abstraction heuristics for factored transition systems. Recent experimental and theoretical research demonstrated the utility of non-linear merge strategies, which have not been studied in depth. We experimentally analyze the quality of state-of-the-art merge strategies by comparing them to random strategies and with respect to tie-breaking, showing that there is considerable room for improvement. We finally describe a new merge strategy that experimentally outperforms the current state of the art.

IJCAI Conference 2016 Conference Paper

Graph-Based Factorization of Classical Planning Problems

• Martin Wehrle
• Silvan Sievers
• Malte Helmert

In domain-independent planning, dependencies of operators and variables often prevent the effective application of planning techniques that rely on loosely coupled problems (like factored planning or partial order reduction). In this paper, we propose a generic approach for factorizing a classical planning problem into an equivalent problem with fewer operator and variable dependencies. Our approach is based on variable factorization, which can be reduced to the well-studied problem of graph factorization. While the state spaces of the original and the factorized problems are isomorphic, the factorization offers the potential to exponentially reduce the complexity of planning techniques like factored planning and partial order reduction.

AAAI Conference 2015 Conference Paper

Automatic Configuration of Sequential Planning Portfolios

• Jendrik Seipp
• Silvan Sievers
• Malte Helmert
• Frank Hutter

Sequential planning portfolios exploit the complementary strengths of different planners. Similarly, automated algorithm configuration tools can customize parameterized planning algorithms for a given type of tasks. Although some work has been done towards combining portfolios and algorithm configuration, the problem of automatically generating a sequential planning portfolio from a parameterized planner for a given type of tasks is still largely unsolved. Here, we present Cedalion, a conceptually simple approach for this problem that greedily searches for the hparameter configuration, runtimei pair which, when appended to the current portfolio, maximizes portfolio improvement per additional runtime spent. We show theoretically that Cedalion yields portfolios provably within a constant factor of optimal for the training set distribution. We evaluate Cedalion empirically by applying it to construct sequential planning portfolios based on component planners from the highly parameterized Fast Downward (FD) framework. Results for a broad range of planning settings demonstrate that – without any knowledge of planning or FD – Cedalion constructs sequential FD portfolios that rival, and in some cases substantially outperform, manually-built FD portfolios.

AAAI Conference 2015 Conference Paper

Factored Symmetries for Merge-and-Shrink Abstractions

• Silvan Sievers
• Martin Wehrle
• Malte Helmert
• Alexander Shleyfman
• Michael Katz

Merge-and-shrink heuristics crucially rely on effective reduction techniques, such as bisimulation-based shrinking, to avoid the combinatorial explosion of abstractions. We propose the concept of factored symmetries for merge-andshrink abstractions based on the established concept of symmetry reduction for state-space search. We investigate under which conditions factored symmetry reduction yields perfect heuristics and discuss the relationship to bisimulation. We also devise practical merging strategies based on this concept and experimentally validate their utility.

AAAI Conference 2015 Conference Paper

Heuristics and Symmetries in Classical Planning

• Alexander Shleyfman
• Michael Katz
• Malte Helmert
• Silvan Sievers
• Martin Wehrle

Heuristic search is a state-of-the-art approach to classical planning. Several heuristic families were developed over the years to automatically estimate goal distance information from problem descriptions. Orthogonally to the development of better heuristics, recent years have seen an increasing interest in symmetry-based state space pruning techniques that aim at reducing the search effort. However, little work has dealt with how the heuristics behave under symmetries. We investigate the symmetry properties of existing heuristics and reveal that many of them are invariant under symmetries.

ICAPS Conference 2015 Conference Paper

On the Expressive Power of Non-Linear Merge-and-Shrink Representations

• Malte Helmert
• Gabriele Röger
• Silvan Sievers

We prove that general merge-and-shrink representations are strictly more powerful than linear ones by showing that there exist problem families that can be represented compactly with general merge-and-shrink representations but not with linear ones. We also give a precise bound that quantifies the necessary blowup incurred by conversions from general merge-and-shrink representations to linear representations or BDDs/ADDs. Our theoretical results suggest an untapped potential for non-linear merging strategies and for the use of non-linear merge-and-shrink-like representations within symbolic search.

ECAI Conference 2014 Conference Paper

Bounded Intention Planning Revisited

• Silvan Sievers
• Martin Wehrle
• Malte Helmert

AAAI Conference 2014 Conference Paper

Generalized Label Reduction for Merge-and-Shrink Heuristics

• Silvan Sievers
• Martin Wehrle
• Malte Helmert

Label reduction is a technique for simplifying families of labeled transition systems by dropping distinctions between certain transition labels. While label reduction is critical to the efficient computation of merge-and-shrink heuristics, current theory only permits reducing labels in a limited number of cases. We generalize this theory so that labels can be reduced in every intermediate abstraction of a merge-andshrink tree. This is particularly important for efficiently computing merge-and-shrink abstractions based on non-linear merge strategies. As a case study, we implement a nonlinear merge strategy based on the original work on mergeand-shrink heuristics in model checking by Dräger et al.

SoCS Conference 2012 Conference Paper

Efficient Implementation of Pattern Database Heuristics for Classical Planning

• Silvan Sievers
• Manuela Ortlieb
• Malte Helmert

Despite their general success in the heuristic search community, pattern database (PDB) heuristics have, until very recently, not been used by the most successful classical planning systems. We describe a new efficient implementation of pattern database heuristics within the Fast Downward planner. A planning system using this implementation is competitive with the state of the art in optimal planning, significantly improving over results from the previous best PDB heuristic implementation in planning.