Finding Approximate POMDP solutions Through Belief Compression

By Nicholas A. Roy, Geoffrey J. Gordon, Sebastian Thrun. 2011

358 citations recorded by the source corpus.

Standard value function approaches to finding policies for Partially Observable Markov Decision Processes (POMDPs) are generally considered to be intractable for large models. The intractability of these algorithms is to a large extent a consequence of computing an exact, optimal policy over the entire belief space. However, in real-world POMDP problems, computing the optimal policy for the full belief space is often unnecessary for good control even for problems with complicated policy classes. The beliefs experienced by the controller often lie near a structured, low-dimensional subspace embedded in the high-dimensional belief space. Finding a good approximation to the optimal value function for only this subspace can be much easier than computing the full value function. We introduce a new method for solving large-scale POMDPs by reducing the dimensionality of the belief space. We use Exponential family Principal Components Analysis (Collins, Dasgupta, & Schapire, 2002) to represent sparse, high-dimensional belief spaces using small sets of learned features of the belief state. We then plan only in terms of the low-dimensional belief features. By planning in this low-dimensional space, we can find policies for POMDP models that are orders of magnitude larger than models that can be handled by conventional techniques. We demonstrate the use of this algorithm on a synthetic problem and on mobile robot navigation tasks.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Learned Belief Search: Efficiently Improving Policies in Partially Observable Settings (2021, background): “Roy et al. (2005) attempt to scale to large belief spaces by learning a compressed representation of the beliefs and then performing Bayesian updates in this space.”
Deep Reinforcement Learning amidst Continual Structured Non-Stationarity (2021, methodology): “While exact solution methods are tractable only for tiny state and actions spaces (Kaelbling et al., 1998), methods based (primarily) on approximate Bayesian inference have enabled scaling to larger problems over the course of the past two decades (Kurniawati et al., 2008; Roy et al., 2005).”
Simultaneous Localization, Mapping and Moving Object Tracking (2007, background): “A few studies such as (Crisan and Doucet, 2002; Verma et al., 2003; Pineau and Thrun, 2002; Roy, 2003) on applying suboptimal approximations to beat the curse of dimensionality and history need to be further studied.”
Search and pursuit-evasion in mobile robotics (2011, background): “Roy et al. (2005) showed how belief compression can be used to make the POMDP search problem tractable for a single pursuer, but the increased state space makes this approach infeasible as the environment and team size scales up.”
Learning omnidirectional path following using dimensionality reduction (2007, methodology): “[28] use dimensionality reduction to compactly represent belief states in a Partially Observable MDP.”
Point-Based Value Iteration for Continuous POMDPs (2006, methodology): “Given the numerous optimization techniques for discrete models, a common approach for continuous models consists of discretizing or approximating the continuous components with a grid (Thrun, 2000; Roy et al., 2005).”
Poisson Noise Reduction with Non-local PCA (2012, methodology): “We propose to update the rows of U and columns of V as proposed in [35].”
Perseus: Randomized Point-based Value Iteration for POMDPs (2005, background): “Roy, Gordon, and Thrun (2005) apply Exponential family PCA to a sample set of beliefs to ﬁnd a low-dimensional representation, based on which an approximate solution is sought.”
Planning under Uncertainty for Robotic Tasks with Mixed Observability (2010, methodology): “There are several approaches to overcome this difficulty, including sampling B, building lower-dimensional approximations of B [19], and employing structured value function representations [4, 6, 18].”
A Multitask Representation Using Reusable Local Policy Templates (2012, positive): “More general approaches, such as belief space compression (Roy, Gordon, and Thrun 2005), suggest that such structure exists more fundamentally as an underlying manifold in many decision problems.”
Discovering latent causes in reinforcement learning (2015, background): “, [4–6]), but research on how the brain solves this problem is still in its infancy.”
Deep Reinforcement Learning amidst Lifelong Non-Stationarity (2020, methodology): “While exact solution methods are tractable only for tiny state and actions spaces [27], methods based (primarily) on approximate Bayesian inference have enabled scaling to larger problems over the course of the past two decades [31, 44].”
SARSOP: Efficient Point-Based POMDP Planning by Approximating Optimally Reachable Belief Spaces (2008, result): “Along with other reports in literature [2, 3, 10, 11, 14, 19], our results indicate that with the advances in POMDP solution algorithms, the POMDP approach is gradually becoming practical for non-trivial robotic tasks.”