hansen~cs.msstate.edu

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 dy-namic programming for simpler classes of problems: it can find optimal solutions without evaluating all prob-lem 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