Pattern Databases for Goal-Probability Maximization in Probabilistic Planning

Authors

  • Thorsten Klößner Saarland University, Saarland Informatics Campus, Germany
  • Jörg Hoffmann Saarland University, Saarland Informatics Campus, Germany
  • Marcel Steinmetz Saarland University, Saarland Informatics Campus, Germany
  • Álvaro Torralba Aalborg University, Department of Computer Science, Denmark

Keywords:

Uncertainty And Stochasticity In Planning And Scheduling

Abstract

Heuristic search algorithms for goal-probability maximization (MaxProb) have been known since a decade. Yet prior work on heuristic functions for MaxProb relies on determinization, not actually taking the probabilities into account. Here we begin to fix this, by introducing MaxProb pattern databases (PDB). We show that, for the special case of PDBs in contrast to more general abstractions, abstract transitions have a unique probability so that the abstract planning task is still an MDP. The resulting heuristic functions are admissible, i.e., they upper-bound the real goal probability. We identify conditions allowing to admissibly multiply heuristic values across several PDBs. Our experiments show that even non-probabilistic PDB heuristics often outperform previous MaxProb heuristics, and that our new probabilistic PDBs can in turn yield significant performance gains over non-probabilistic ones.

Downloads

Published

2021-05-17

How to Cite

Klößner, T., Hoffmann, J., Steinmetz, M., & Torralba, Álvaro. (2021). Pattern Databases for Goal-Probability Maximization in Probabilistic Planning. Proceedings of the International Conference on Automated Planning and Scheduling, 31(1), 201-209. Retrieved from https://ojs.aaai.org/index.php/ICAPS/article/view/15963