Solving Markov Decision Problems Using Heuristic Search

Search Techniques for Problem Solving Under Uncertainty and Incomplete Information

Volume

Search Techniques for Problem Solving Under Uncertainty and Incomplete Information

Contents

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.