DOI:
Abstract:
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.