Pattern Databases for Goal-Probability Maximization in Probabilistic Planning
2021
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.
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
0
References
0
Citations
NaN
KQI