Pattern Databases for Goal-Probability Maximization in Probabilistic Planning

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.