DESPOT: Online POMDP Planning with Regularization

Abstract

The partially observable Markov decision process (POMDP) provides a principled general framework for planning under uncertainty, but solving POMDPs optimally is computationally intractable, due to the "curse of dimensionality" and the "curse of history". To overcome these challenges, we introduce the Determinized Sparse Partially Observable Tree (DESPOT), a sparse approximation of the standard belief tree, for online planning under uncertainty. A DESPOT focuses online planning on a set of randomly sampled scenarios and compactly captures the "execution" of all policies under these scenarios. We show that the best policy obtained from a DESPOT is near-optimal, with a regret bound that depends on the representation size of the optimal policy. Leveraging this result, we give an anytime online planning algorithm, which searches a DESPOT for a policy that optimizes a regularized objective function. Regularization balances the estimated value of a policy under the sampled scenarios and the policy size, thus avoiding overfitting. The algorithm demonstrates strong experimental results, compared with some of the best online POMDP algorithms available. It has also been incorporated into an autonomous driving system for real-time vehicle control. The source code for the algorithm is available online.

36 pages

References in corpus (8)

• Online Planning Algorithms for POMDPs
• PEGASUS: A Policy Search Method for Large MDPs and POMDPs
• Bandit Algorithms for Tree Search
• Speeding Up the Convergence of Value Iteration in Partially Observable Markov Decision Processes
• Nonapproximability Results for Partially Observable Markov Decision Processes
• Point-Based POMDP Algorithms: Improved Analysis and Implementation
• Efficient Planning under Uncertainty with Macro-actions
• Monte Carlo Bayesian Reinforcement Learning

Cited by in corpus (22)

• Motion Planning for Autonomous Driving: The State of the Art and Future Perspectives
• Perception-aware Autonomous Mast Motion Planning for Planetary Exploration Rovers
• QMDP-Net: Deep Learning for Planning under Partial Observability
• Stochastic Motion Planning under Partial Observability for Mobile Robots with Continuous Range Measurements
• Particle Filter Networks with Application to Visual Localization
• FABRIC: A Framework for the Design and Evaluation of Collaborative Robots with Extended Human Adaptation
• Simplified decision making in the belief space using belief sparsification
• Optimality Guarantees for Particle Belief Approximation of POMDPs
• Learning to Plan Hierarchically from Curriculum
• EPSILON: An Efficient Planning System for Automated Vehicles in Highly Interactive Environments
• Efficient Uncertainty-aware Decision-making for Automated Driving Using Guided Branching
• Learning Logic Specifications for Policy Guidance in POMDPs: an Inductive Logic Programming Approach
• A Model-Based, Decision-Theoretic Perspective on Automated Cyber Response
• Active Inference Tree Search in Large POMDPs
• POMDPs in Continuous Time and Discrete Spaces
• Adaptive Belief Discretization for POMDP Planning
• Integrating Algorithmic Planning and Deep Learning for Partially Observable Navigation
• Simplified Belief-Dependent Reward MCTS Planning with Guaranteed Tree Consistency
• PODDP: Partially Observable Differential Dynamic Programming for Latent Belief Space Planning
• Explanation through Reward Model Reconciliation using POMDP Tree Search
• Combining Offline Models and Online Monte-Carlo Tree Search for Planning from Scratch
• Rollout Heuristics for Online Stochastic Contingent Planning