Pattern Databases for Stochastic Shortest Path Problems

Abstract

Stochastic shortest-path problems (SSP) are an important subclass of MDPs for which heuristic search algorithms exist since over a decade. Yet most known heuristic functions rely on determinization so do not actually take the transition probabilities into account. The only exceptions are Trevizan et al.'s heuristics hpom and hroc, which are geared at solving more complex (constrained) MDPs. Here we contribute pattern database (PDB) heuristics for SSPs, including an additivity criterion. These new heuristics turn out to be very competitive, even when using a simple systematic generation of pattern collections up to a fixed size. In our experiments, they beat determinization-based heuristics, and tend to yield better runtimes than hpom and hroc.