Cost Partitioning Heuristics for Stochastic Shortest Path Problems

Authors

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

DOI:

https://doi.org/10.1609/icaps.v32i1.19802

Keywords:

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

Abstract

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.

Downloads

Published

2022-06-13

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. https://doi.org/10.1609/icaps.v32i1.19802