A Heuristic Search Algorithm for Markov Decision Problems

Eric A. Hansen and Shlomo Zilberstein. A Heuristic Search Algorithm for Markov Decision Problems. Proceedings of the Bar-Ilan Symposium on the Foundation of Artificial Intelligence (BISFAI), Ramat Gan, Israel, 1999.

Abstract

LAO* is a heuristic search algorithm for Markov decision problems that is derived from the classic heuristic search algorithm AO* (Hansen and Zilberstein, 1998). It shares the advantage heuristic search has over dynamic programming for simpler classes of problems: it can find optimal solutions without evaluating all problem states. In this paper, we show that the derivation of LAO* from AO* makes it possible to generalize refinements of simpler heuristic search algorithms for use in solving Markov decision problems more efficiently. We also generalize some theoretical analyses of simpler search problems to Markov decision problems.

Bibtex entry:

@inproceedings{HZbisfai99,
  author	= {Eric A. Hansen and Shlomo Zilberstein},
  title		= {A Heuristic Search Algorithm for {M}arkov Decision Problems},
  booktitle     = {Proceedings of the Bar-Ilan Symposium on the Foundation of
                   Artificial Intelligence},
  year		= {1999},
  pages		= {},
  address       = {Ramat Gan, Israel,},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/HZbisfai99.html}
}

shlomo@cs.umass.edu