Pattern Selection Strategies for Pattern Databases in Probabilistic Planning
Thorsten Klößner, Marcel Steinmetz, Álvaro Torralba and Jörg Hoffmann
Abstract: 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.
*This password protected talk video will only be available after it was presented at the conference.
