Anytime Point-Based Approximations for Large POMDPs

By Joelle Pineau, Geoffrey J. Gordon, Sebastian Thrun. Journal of Artificial Intelligence Research, 2006

436 citations recorded by the source corpus.

The Partially Observable Markov Decision Process has long been recognized as a rich framework for real-world planning and control problems, especially in robotics. However exact solutions in this framework are typically computationally intractable for all but the smallest problems. A well-known technique for speeding up POMDP solving involves performing value backups at specific belief points, rather than over the entire belief simplex. The efficiency of this approach, however, depends greatly on the selection of points. This paper presents a set of novel techniques for selecting informative belief points which work well in practice. The point selection procedure is combined with point-based value backups to form an effective anytime POMDP algorithm called Point-Based Value Iteration (PBVI). The first aim of this paper is to introduce this algorithm and present a theoretical analysis justifying the choice of belief selection technique. The second aim of this paper is to provide a thorough empirical comparison between PBVI and other state-of-the-art POMDP methods, in particular the Perseus algorithm, in an effort to highlight their similarities and differences. Evaluation is performed using both standard POMDP domains and realistic robotic tasks.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

View Paper: https://www.semanticscholar.org/paper/d3daa7072cde8acac8e241756729823db4bf94ae

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

In Computational Theory and Mathematics

Citations in the corpus

Sidekick agents for sequential planning problems (2013, methodology): “One popular set of more general-purpose approaches to POMDP solving use pointbased methods which sample points in belief space, compute the value function at those points via value iteration, and use them to form a value function estimate, such as PBVI [50] and SARSOP [37].”
Optimal Value of Information in Graphical Models (2009, methodology): “Hence, in principle, algorithms for planning in POMDPs, such as the anytime algorithm by Pineau, Gordon, and Thrun (2006), can be employed for optimizing value of information.”
Monte-Carlo Planning in Large POMDPs (2010, background): “The majority of online planners are based on point-based value iteration [12, 13].”
A Survey of Multi-Objective Sequential Decision-Making (2013, methodology): “Approximate point-based POMDP methods (Spaan & Vlassis, 2005; Pineau, Gordon, & Thrun, 2006) do not meet conditions (1) and (2) but could be adapted to compute an approximate convex hull, by choosing a prior distribution for the weights from which they could sample.”
Linear Fitted-Q Iteration with Multiple Reward Functions (2012, background): “Second, in POMDP planning, value is always a convex function of belief state, and this property is crucial in the development of exact and approximate (e.g., Pineau et al. 2006, Wang et al. 2006) methods.”
Autonomous driving in urban environments: approaches, lessons and challenges (2010, positive): “But, while the problem is cast in a formal way, these methods generally require discretization that does not scale well; recent results have attempted to overcome these challenges (Pineau et al. 2006).”
Online Planning Algorithms for POMDPs (2008, background): “Some recent publications provide a more comprehensive overview of offline approximate algorithms (Hauskrecht, 2000; Pineau, Gordon, & Thrun, 2006 ).”
From Bandits to Monte-Carlo Tree Search: The Optimistic Principle Applied to Optimization and Planning (2014, methodology): “Initial motivation in the context of clinical trials dates back to the works of Thompson [1933, 1935] and Robbins [1952]. In this chapter we consider the optimism in the face of uncertainty principle, which recommends following the optimal policy in the most favorable environment among all possible ”
Closing the learning-planning loop with predictive state representations (2009, background): “tate. Unfortunately, exact planning algorithms such as value iteration [27] are computationally intractable for most realistic POMDP planning problems. There are arguably two primary reasons for this [18]. The rst is the \curse of dimensionality": for a POMDP with nstates, the optimal policy is”
Joint Policy Search for Multi-agent Collaboration with Imperfect Information (2020, background): “Previous works also model belief space (e.g., Point-Based Value Iteration [31] in POMDP, BAD [16]) or model the behaviors of other agents (e.g., AWESOME [11], Hyper Q-learning [37], LOLA [15]).”