Generating Admissible Heuristics by Abstraction for Search in Stochastic Domains

Natalia Beliaeva and Shlomo Zilberstein. Generating Admissible Heuristics by Abstraction for Search in Stochastic Domains. Proceedings of the Symposium on Abstraction, Reformulation, and Approximation (SARA), 14-29, Airth Castle, Scotland, 2005.

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*.

Bibtex entry:

@inproceedings{BZsara05,
  author	= {Natalia Beliaeva and Shlomo Zilberstein},
  title		= {Generating Admissible Heuristics by Abstraction for Search 
                   in Stochastic Domains},
  booktitle     = {Proceedings of the Symposium on Abstraction, Reformulation,
                   and Approximation},
  year		= {2005},
  pages		= {14-29},
  address       = {Airth Castle, Scotland},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/BZsara05.html}
}

shlomo@cs.umass.edu