Combining Offline and Online Computation for Solving Partially Observable Markov Decision Process.

摘要

Partially observable Markov decision process (POMDP) provides a general and mathematically elegant way of formulating planning and control problems under uncertainty. Unfortunately, POMDPs are computationally intractable to solve in the worst case, prompting the development of approximation algorithms. In this project, they explored the use of online algorithms for approximately solving large-scale POMDPs. They developed a new online POMDP solver, DESPOT, with good theoretical and practical properties. The DESPOT algorithm was used as part of our entry that finished in first place at the ICAPS 2014 International Probabilistic Planning Competition (IPPC) POMDP track. They also applied the DESPOT algorithm on the problem of autonomous vehicle navigation through crowded locations, demonstrating its use in a real application. Although POMDPs are intractable in the worst case, there are subclasses of POMDPs that can be tractably approximated and are at the same time practically interesting. They applied online methods to two such special cases of POMDPs, specifically adaptive informative path planning and active learning, obtaining practical polynomial-time algorithms with guaranteed approximation bounds.