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


  • Thorsten Klößner Saarland University
  • Álvaro Torralba Aalborg University
  • Marcel Steinmetz Saarland University
  • Silvan Sievers University of Basel




Uncertainty and stochasticity in planning and scheduling, Heuristic search, Theoretical foundations of planning and scheduling


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.




How to Cite

Klößner, T., Torralba, Álvaro, Steinmetz, M., & Sievers, S. (2023). A Theory of Merge-and-Shrink for Stochastic Shortest Path Problems. Proceedings of the International Conference on Automated Planning and Scheduling, 33(1), 203-211. https://doi.org/10.1609/icaps.v33i1.27196