This is a research project intended to overcome barriers that have limited the usefulness of partially-observable Markov decision process algorithms. In the area of planning under uncertainty, the Markov decision process (MDP) has emerged as a powerful and elegant framework for solving problems in a wide range of application domains such as mobile robot control, machine maintenance, gesture recognition, medical diagnosis and treatment, and policy making. For situations in which the decision maker can fully observe the intermediate state of the domain, there are many effective algorithms that can solve large problems. However, in many applications, it is unrealistic to assume that perfect state information is available. The more general, partially-observable MDP (POMDP) addresses this difficulty, but in this case the computational complexity of planning makes it hard to apply existing solution techniques to practical applications.
This project will study new ways to address the key computational bottlenecks in POMDP algorithms. To achieve this, it will (a) Identify and examine new types of belief-space structures that can be used to accelerate significantly each of the key components of POMDP solution techniques; (b) Evaluate the impact of these improvements on a wide range of exact and approximate algorithms with the goal of demonstrating exponential acceleration; (c) Integrate the new approach with previously identified methods for accelerating MDP and POMDP algorithms using search, symbolic representations, and parallelization; (d) Develop a new set of challenging test problems and benchmarks that are significantly harder than the existing toy problems and perform a rigorous evaluation and comparison of the developed techniques; and (e) Increase the interaction between the artificial intelligence community and other communities that employ POMDP solution techniques such as operations research and management sciences, and exploit the synergy that arises when the best solution techniques from these communities are brought together.
The approach is based on exploring new types of structures in the belief space that make it possible to decompose the main computational components into faster, region-based operations. A theoretical analysis of the new approach and a preliminary implementation show that it can significantly increase the efficiency of both exact and approximate algorithms and thus it can improve the scalability of POMDP algorithms and increase their applicability. The newly designed technique is particularly suitable for parallel implementation on grid computers, offering significant additional opportunities for performance gains.
The technical impact of this project involves fundamental contributions to the understanding of the complexity of planning in stochastic domains as well as the development of efficient planning algorithms that provide exponential savings in computing time. The new approach improves several computational operations that are often used as components of existing algorithms - both exact and approximate. Therefore, the benefits of the approach transfer easily to many existing solution techniques. The broader impact of the project stems from the broad applicability of the resulting technology in several scientific and engineering disciplines, the immediate educational impact at the University of Massachusetts Amherst, an extensive plan for non-traditional dissemination efforts, making the experimental testbed available to the research community, and enhancing an existing alliance between the principal investigator and an international research team at INRIA, France.
