Applications of best-first heuristic search to finite-horizon partially observed markov decision processes
Chelsea C. White, James W. Lark · 1990
This dissertation considers solution techniques for the finite-horizon partially observed Markov decision process (POMDP). We develop methods for solving finite-horizon POMDPs based upon best-first heuristic search theory, an area in Artificial Intelligence research. We also develop methods which improve substantially the performance of some POMDP solution procedures based upon dynamic programming. Chapter 1 provides background information concerning the POMDP and heuristic search. Chapter 2 provides details of best-first heuristic search in the context of AND/OR trees. The objective is to find solution subtrees which are nondominated with respect to a special order relation defined on real-valued vectors. We devise a best-first heuristic search algorithm for this purpose, and prove results which guarantee that algorithm will discover all nondominated solutions. In Chapter 3, we show the equivalence between the POMDP and a specially constructed finite AND/OR tree. Each nondominated strategy for the POMDP corresponds to a nondominated vector-cost subtree in the AND/OR tree. We define a heuristic function for the AND/OR tree and prove that the algorithm, with this heuristic, will find all solution subtrees corresponding to nondominated strategies for the POMDP. We also discuss POMDP solution procedures based on dynamic programming, such as the one-pass algorithm of Sondik and its modification by Monahan. We develop a modification of the Monahan procedure which is usually significantly faster than other dynamic programming-based procedures. We provide an exploratory numerical investigation of the performance of all solution procedures under consideration. Chapter 4 deals with the finite-horizon multiobjective Markov decision process (MOMDP). We develop both heuristic search and dynamic programming approaches for this problem, based upon ideas from Chapter 3. Also, we use an idea of C. C. White and K. W. Kim to reformulate the MOMDP as a POMDP. We employ techniques from Chapter 3 to solve the MOMDP, and provide an exploratory numerical investigation of the solution procedures. We also discuss some technical points concerning definitions of nondominated strategies in the MOMDP context. Chapter 5 provides a discussion of future research and extensions of the results within the dissertation.