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

Klößner, Thorsten and Torralba, Álvaro and Steinmetz, Marcel and Sievers, Silvan. (2023) A Theory of Merge-and-Shrink for Stochastic Shortest Path Problems. In: Proceedings of the 33rd International Conference on Automated Planning and Scheduling (ICAPS 2023), 33. pp. 203-211.

[img] PDF - Accepted Version

Official URL: https://edoc.unibas.ch/95804/

Downloads: Statistics Overview


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.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Sievers, Silvan
Item Type:Conference or Workshop Item, refereed
Conference or workshop item Subtype:Conference Paper
Publisher:AAAI Press
Series Name:Proceedings of the International Conference on Automated Planning and Scheduling
Issue Number:1
Note:Publication type according to Uni Basel Research Database: Conference paper
Related URLs:
edoc DOI:
Last Modified:25 Sep 2023 11:39
Deposited On:25 Sep 2023 09:02

Repository Staff Only: item control page