Author name cluster

Thorsten Klößner

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

1 author row

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.

Details

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.

Details

ECAI Conference 2023 Conference Paper

Cartesian Abstractions and Saturated Cost Partitioning in Probabilistic Planning

Thorsten Klößner
Jendrik Seipp
Marcel Steinmetz

Stochastic shortest path problems (SSPs) capture probabilistic planning tasks with the objective of minimizing expected cost until reaching the goal. One of the strongest methods to solve SSPs optimally is heuristic search guided by an admissible (lower-bounding) heuristic function. Recently, probability-aware pattern database (PDB) abstractions have been highlighted as an efficient way of generating such lower bounds, with significant advantages over traditional determinization-based approaches. Here, we follow this work, yet consider a more general type, Cartesian abstractions, which have been used successfully in the classical setting. We show how to construct probability-aware Cartesian abstractions via a counterexample-guided abstraction refinement (CEGAR) loop akin to classical planning. This method is complete, meaning it guarantees convergence to the optimal expected cost if not terminated prematurely. Furthermore, we investigate the admissible combination of multiple such heuristics using saturated cost partitioning (SCP), marking its first application in the probabilistic setting. In our experiments, we show that probability-aware Cartesian abstractions yield much more informative heuristics than their determinization-based counterparts. Finally, we show that SCP yields probability-aware abstraction heuristics that are superior to the previous state of the art.

Details

ICAPS Conference 2022 Conference Paper

Cost Partitioning Heuristics for Stochastic Shortest Path Problems

Thorsten Klößner
Florian Pommerening
Thomas Keller 0001
Gabriele Röger

In classical planning, cost partitioning is a powerful method which allows to combine multiple admissible heuristics while retaining an admissible bound. In this paper, we extend the theory of cost partitioning to probabilistic planning by generalizing from deterministic transition systems to stochastic shortest path problems (SSPs). We show that fundamental results related to cost partitioning still hold in our extended theory. We also investigate how to optimally partition costs for a large class of abstraction heuristics for SSPs. Lastly, we analyze occupation measure heuristics for SSPs as well as the theory of approximate linear programming for reward-oriented Markov decision processes. All of these fit our framework and can be seen as cost-partitioned heuristics.

Details

ICAPS Conference 2022 Conference Paper

Pattern Selection Strategies for Pattern Databases in Probabilistic Planning

Thorsten Klößner
Marcel Steinmetz
Álvaro Torralba
Jörg Hoffmann 0001

Recently, pattern databases have been extended to probabilistic planning, to derive heuristics for the objectives of goal probability maximization and expected cost minimization. While this approach yields both theoretical and practical advantages over techniques relying on determinization, the problem of selecting the patterns in the first place has only been scantily addressed as yet, through a method that systematically enumerates patterns up to a fixed size. Here we close this gap, extending pattern generation techniques known from classical planning to the probabilistic case. We consider hill-climbing as well as counter-example guided abstraction refinement (CEGAR) approaches, and show how they need to be adapted to obtain desired properties such as convergence to the perfect value function in the limit. Our experiments show substantial improvements over systematic pattern generation and the previous state of the art.

Details

ICAPS Conference 2021 Conference Paper

Pattern Databases for Goal-Probability Maximization in Probabilistic Planning

Thorsten Klößner
Jörg Hoffmann 0001
Marcel Steinmetz
Álvaro Torralba

Heuristic search algorithms for goal-probability maximization (MaxProb) have been known since a decade. Yet prior work on heuristic functions for MaxProb relies on determinization, not actually taking the probabilities into account. Here we begin to fix this, by introducing MaxProb pattern databases (PDB). We show that, for the special case of PDBs in contrast to more general abstractions, abstract transitions have a unique probability so that the abstract planning task is still an MDP. The resulting heuristic functions are admissible, i. e. , they upper-bound the real goal probability. We identify conditions allowing to admissibly multiply heuristic values across several PDBs. Our experiments show that even non-probabilistic PDB heuristics often outperform previous MaxProb heuristics, and that our new probabilistic PDBs can in turn yield significant performance gains over non-probabilistic ones.

Details

SoCS Conference 2021 Conference Paper

Pattern Databases for Stochastic Shortest Path Problems

Thorsten Klößner
Jörg Hoffmann 0001

Stochastic shortest-path problems (SSP) are an important subclass of MDPs for which heuristic search algorithms exist since over a decade. Yet most known heuristic functions rely on determinization so do not actually take the transition probabilities into account. The only exceptions are Trevizan et al.

Details