Solving Markov Decision Problems Using Heuristic Search

Eric A. Hansen and Shlomo Zilberstein

We describe a heuristic search algorithm for Markov decision problems, called LAO*, that is derived from the classic heuristic search algorithm AO*. LAO* shares the advantage heuristic search has over dynamic programming for simpler classes of problems: it can find optimal solutions without evaluating all problem states. The derivation of LAO* from AO* makes it easier to generalize refinements of heuristic search developed for simpler classes of problems for use in solving Markov decision problems more efficiently.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.