Cost Partitioning Heuristics for Stochastic Shortest Path Problems


  • Thorsten Klößner Saarland University
  • Florian Pommerening University of Basel
  • Thomas Keller University of Basel
  • Gabriele Röger University of Basel



Stochastic Shortest-Path Problems, Cost-Partitioning, Heuristic Search, Approximate Linear Programming, Occupation Measures


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.




How to Cite

Klößner, T., Pommerening, F., Keller, T., & Röger, G. (2022). Cost Partitioning Heuristics for Stochastic Shortest Path Problems. Proceedings of the International Conference on Automated Planning and Scheduling, 32(1), 193-202.