Generating Admissible Heuristics by Abstraction for Search in Stochastic Domains
Natalia Beliaeva
Shlomo Zilberstein
Abstract
Search in abstract spaces has been shown to produce useful admissible
heuristic estimates in deterministic domains. We show in this paper how
to generalize these results to search in stochastic domains. Solving
stochastic optimization problems is significantly harder than solving
their deterministic counterparts. Designing admissible heuristics for
stochastic domains is also much harder. Therefore, deriving such
heuristics automatically using abstraction is particularly beneficial.
We analyze this approach both theoretically and empirically and show
that it produces significant computational savings when used in
conjunction with the heuristic search algorithm LAO*.
Download
[pdf]