Pattern Selection Strategies for Pattern Databases in Probabilistic Planning


  • Thorsten Klößner Saarland University
  • Marcel Steinmetz Saarland University
  • Álvaro Torralba Aalborg University
  • Jörg Hoffmann Saarland University


Probabilistic Planning, Pattern Databases, Stochastic Shortest-Path Problems, Goal Probability Maximization, Heuristic Search


Recently, pattern databases have been extended to probabilistic planning, to derive heuristics for the objectives of goal probability maximization and expected cost minimization. While this approach yields both theoretical and practical advantages over techniques relying on determinization, the problem of selecting the patterns in the first place has only been scantily addressed as yet, through a method that systematically enumerates patterns up to a fixed size. Here we close this gap, extending pattern generation techniques known from classical planning to the probabilistic case. We consider hill-climbing as well as counter-example guided abstraction refinement (CEGAR) approaches, and show how they need to be adapted to obtain desired properties such as convergence to the perfect value function in the limit. Our experiments show substantial improvements over systematic pattern generation and the previous state of the art.




How to Cite

Klößner, T., Steinmetz, M., Torralba, Álvaro, & Hoffmann, J. (2022). Pattern Selection Strategies for Pattern Databases in Probabilistic Planning. Proceedings of the International Conference on Automated Planning and Scheduling, 32(1), 184-192. Retrieved from