Talk Sessions:

Poster Sessions:

June 21, Booth 41

June 23, Booth 38

Cost Partitioning Heuristics for Stochastic Shortest Path Problems

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

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.

*This password protected talk video will only be available after it was presented at the conference.