Symbolic Dynamic Programming for Continuous State and Observation POMDPs
Zahra Zamani, Scott Sanner, Pascal Poupart, Kristian Kersting · 2012
Point-based value iteration (PBVI) methods have proven extremely effective for finding (approximately) optimal dynamic programming solutions to partially-observable Markov decision processes (POMDPs) when a set of initial belief states is known. However, no PBVI work has provided exact point-based back-ups for both continuous state and observation spaces, which we tackle in this paper. Our key insight is that while there may be an infinite number of observa-tions, there are only a finite number of continuous observation partitionings that are relevant for optimal decision-making when a finite, fixed set of reachable be-lief states is considered. To this end, we make two important contributions: (1) we show how previous exact symbolic dynamic programming solutions for continu-ous state MDPs can be generalized to continuous state POMDPs with discrete ob-servations, and (2) we show how recently developed symbolic integration methods allow this solution to be extended to PBVI for continuous state and observation POMDPs with potentially correlated, multivariate continuous observation spaces. 1