Point-based value iteration: an anytime algorithm for POMDPs
Published 9 August 2003
Joëlle Pineau, Geoff Gordon, Sebastian Thrun
Citations934
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper introduces the Point-Based Value Iteration (PBVI) algorithm for POMDP planning, and presents results on a robotic laser tag problem as well as three test domains from the literature.
Abstract
This paper introduces the Point-Based Value Iteration (PBVI) algorithm for POMDP planning. PBVI approximates an exact value iteration solution by selecting a small set of representative belief points and then tracking the value and its derivative for those points only. By using stochastic trajectories to choose belief points, and by maintaining only one value hyper-plane per point, PBVI successfully solves large problems: we present results on a robotic laser tag problem as well as three test domains from the literature.
Keywords
Computer Science
Artificial IntelligencePlanning and acting in partially observable stochastic domains
4,129 Citations1998Leslie Pack Kaelbling, Michael L. Littman +1 more
A novel algorithm for solving pomdps off line and how, in some cases, a finite-memory controller can be extracted from the solution to a POMDP is outlined.
Elsevier eBooksLearning policies for partially observable environments: Scaling up
653 Citations1995Michael L. Littman, Anthony R. Cassandra +1 more
This paper discusses several simple solution methods and shows that all are capable of finding near- optimal policies for a selection of extremely small POMDP'S taken from the learning literature, but shows that none are able to solve a slightly larger and noisier problem based on robot navigation.
Journal of Artificial Intelligence ResearchValue-Function Approximations for Partially Observable Markov Decision Processes
536 Citations2000Miloš Hauskrecht
This work surveys various approximation methods, analyzes their properties and relations and provides some new insights into their differences, and presents a number of new approximation methods and novel refinements of existing techniques.
Munich Personal RePEc Archive (Ludwig Maximilian University of Munich)The optimal control of partially observable Markov processes
455 Citations1971Edward J. Sondik
A fluorescence spectrophotometer having a beam splitter placed between an exit slit of an excitation monochromator and a specimen and a reference photomultiplier provided for receiving fluorescence from said first light quantum meter.
arXiv (Cornell University)PEGASUS: A Policy Search Method for Large MDPs and POMDPs
369 Citations2013Andrew Y. Ng, Michael I. Jordan
This work proposes a new approach to the problem of searching a space of policies for a Markov decision process (MDP) or a partially observable Markov decisions process (POMDP), given a model, based on the following observation: Any (PO)MDP can be transformed into an "equivalent" POMDP in which all state transitions are deterministic.
arXiv (Cornell University)Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes
343 Citations2013Anthony R. Cassandra, Michael L. Littman +1 more
It is found that incremental pruning is presently the most efficient exact method for solving POMDPS.
Operations ResearchComputationally Feasible Bounds for Partially Observed Markov Decision Processes
310 Citations1991William S. Lovejoy
This paper explains how to approximate the state space by a finite grid of points, and use that grid to construct upper and lower value function bounds, generate approximate nonstationary and stationary policies, and bound the value loss relative to optimal for using these policies in the decision problem.
Approximate Planning in Large POMDPs via Reusable Trajectories
137 Citations1999Michael Kearns, Yishay Mansour +1 more
Upper bounds on the sample complexity are proved showing that, even for infinitely large and arbitrarily complex POMDPs, the amount of data needed can be finite, and depends only linearly on the complexity of the restricted strategy class II, and exponentially on the horizon time.
Journal of Artificial Intelligence ResearchSpeeding Up the Convergence of Value Iteration in Partially Observable Markov Decision Processes
126 Citations2001Nevin L. Zhang, Weixiong Zhang
This paper proposes a method for accelerating the convergence of value iteration, a well-known algorithm for finding optimal policies for POMDPs, and has been evaluated on an array of benchmark problems and was found to be very effective.
Exponential Family PCA for Belief Compression in POMDPs
117 Citations2002Nicholas Roy, Geoffrey J. Gordon
A new method for solving large-scale POMDPs by taking advantage of belief space sparsity by reducing the dimensionality of the belief space by exponential family Principal Components Analysis and planning directly on the low-dimensional belief features.
An improved grid-based approximation algorithm for POMDPs
99 Citations2001Rong Zhou, Eric A. Hansen
A novel approach to grid-based approximation that uses a variable-resolution regular grid, and it is shown that it outperforms previous grid- based approaches to approximation.
Value-Directed Compression of POMDPs
99 Citations2002Pascal Poupart, Craig Boutilier
It is observed that compressions that allow accurate policy evaluation (prediction of expected future reward) will not affect decision quality, and a set of sufficient conditions are derived that ensure accurate prediction in this respect.
A heuristic variable grid solution method for POMDPs
90 Citations1997Ronen I. Brafman
A simple variable-grid solution method which yields good results on relatively large problems with modest computational effort is described.
ArXiv.orgReinforcement Learning in POMDP's via Direct Gradient Ascent
88 Citations2025Jonathan Baxter, Peter L. Bartlett
GPOMDP, a REINFORCE-like algorithm for estimating an approximation to the gradient of the average reward as a function of the parameters of a stochastic policy, is introduced and it is proved convergence of GPOMDP.
Locating moving entities in indoor environments with teams of mobile robots
49 Citations2003Matthew Rosencrantz, Geoffrey J. Gordon +1 more
A new particle filter algorithm for tracking the location of many opponents in the presence of pervasive occlusion is presented, achieving efficient tracking principally through a clever factorization of the posterior into roles that can be dynamically added and merged.
A fast heuristic algorithm for decision-theoretic planning
32 Citations2001Kin Man Poon