Cost Partitioning Heuristics for Stochastic Shortest Path Problems

Klößner, Thorsten and Pommerening, Florian and Keller, Thomas and Röger, Gabriele. (2022) Cost Partitioning Heuristics for Stochastic Shortest Path Problems. In: Proceedings of the 32nd International Conference on Automated Planning and Scheduling (ICAPS 2022). pp. 193-202.

[img] PDF - Accepted Version

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

Downloads: Statistics Overview


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.
Faculties and Departments:05 Faculty of Science > Departement Mathematik und Informatik > Informatik > Artificial Intelligence (Helmert)
UniBasel Contributors:Pommerening, Florian and Keller, Thomas and Röger, Gabriele
Item Type:Conference or Workshop Item, refereed
Conference or workshop item Subtype:Conference Paper
Publisher:AAAI Press
Note:Publication type according to Uni Basel Research Database: Conference paper
Identification Number:
edoc DOI:
Last Modified:15 Feb 2023 09:50
Deposited On:15 Feb 2023 09:50

Repository Staff Only: item control page