Anytime Point-Based Approximations for Large POMDPs

Abstract

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.

References in corpus (6)

• Decision-Theoretic Planning: Structural Assumptions and Computational Leverage
• Value-Function Approximations for Partially Observable Markov Decision Processes
• Tractable Inference for Complex Stochastic Processes
• Incremental Pruning: A Simple, Fast, Exact Method for Partially Observable Markov Decision Processes
• Speeding Up the Convergence of Value Iteration in Partially Observable Markov Decision Processes
• Value-Directed Belief State Approximation for POMDPs

Cited by in corpus (40)

• Online Planning Algorithms for POMDPs
• A Survey of Multi-Objective Sequential Decision-Making
• Partially Observable Markov Decision Processes in Robotics: A Survey
• Planning for robotic exploration based on forward simulation
• Monte Carlo Sampling Methods for Approximating Interactive POMDPs
• Optimal adaptive inspection and maintenance planning for deteriorating structural systems
• Optimal Value of Information in Graphical Models
• Anytime Planning for Decentralized POMDPs using Expectation Maximization
• Deterministic POMDPs Revisited
• Deep reinforcement learning for the olfactory search POMDP: a quantitative benchmark
• Exploiting Submodular Value Functions For Scaling Up Active Perception
• Optimal policies for Bayesian olfactory search in turbulent flows
• Simplified decision making in the belief space using belief sparsification
• Modelling Observation Correlations for Active Exploration and Robust Object Detection
• Automated Attack Planning
• Topological Information-Theoretic Belief Space Planning with Optimality Guarantees
• FHHOP: A Factored Hybrid Heuristic Online Planning Algorithm for Large POMDPs
• General Purpose Incremental Covariance Update and Efficient Belief Space Planning via Factor-Graph Propagation Action Tree
• Joint Policy Search for Multi-agent Collaboration with Imperfect Information
• Counterexample-guided Abstraction Refinement for POMDPs
• Structure in the Value Function of Two-Player Zero-Sum Games of Incomplete Information
• Near Optimality of Finite Memory Feedback Policies in Partially Observed Markov Decision Processes
• Optimal Sensing via Multi-armed Bandit Relaxations in Mixed Observability Domains
• Linear programming-based solution methods for constrained partially observable Markov decision processes
• Supervisor Synthesis of POMDP based on Automata Learning
• Robust Active Perception via Data-association aware Belief Space planning
• Efficient Online Learning for Optimizing Value of Information: Theory and Application to Interactive Troubleshooting
• Open Problem: Approximate Planning of POMDPs in the class of Memoryless Policies
• A Fenchel-Moreau-Rockafellar type theorem on the Kantorovich-Wasserstein space with Applications in Partially Observable Markov Decision Processes
• Computational Techniques for Reachability Analysis of Partially Observable Discrete Time Stochastic Hybrid Systems
• Finite Model Approximations for Partially Observed Markov Decision Processes with Discounted Cost
• Approximate Safety Verification and Control of Partially Observable Stochastic Hybrid Systems
• Efficient Planning under Partial Observability with Unnormalized Q Functions and Spectral Learning
• TurKPF: TurKontrol as a Particle Filter
• Combining Offline Models and Online Monte-Carlo Tree Search for Planning from Scratch
• iX-BSP: Incremental Belief Space Planning
• Planning with Submodular Objective Functions
• Deep Synoptic Monte Carlo Planning in Reconnaissance Blind Chess
• Reinforcement Learning in Reward-Mixing MDPs
• Memory Bounded Open-Loop Planning in Large POMDPs using Thompson Sampling