DESPOT: Online POMDP Planning with Regularization

By Adhiraj Somani, Nan Ye, David Hsu, Wee Sun Lee. Neural Information Processing Systems, 2013

558 citations recorded by the source corpus.

POMDPs provide a principled framework for planning under uncertainty, but are computationally intractable, due to the "curse of dimensionality" and the "curse of history". This paper presents an online POMDP algorithm that alleviates these difficulties by focusing the search on a set of randomly sampled scenarios. A Determinized Sparse Partially Observable Tree (DESPOT) compactly captures the execution of all policies on these scenarios. Our Regularized DESPOT (R-DESPOT) algorithm searches the DESPOT for a policy, while optimally balancing the size of the policy and its estimated value obtained under the sampled scenarios. We give an output-sensitive performance bound for all policies derived from a DESPOT, and show that R-DESPOT works well if a small optimal policy exists. We also give an anytime algorithm that approximates R-DESPOT. Experiments show strong results, compared with two of the fastest online POMDP algorithms. Source code along with experimental settings are available at http://bigbird.comp.nus.edu.sg/pmwiki/farm/appl/.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

View Paper: https://www.semanticscholar.org/paper/270722c0233562d6c423d16d36b2c4adc5ed0829

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 Computer Vision and Pattern Recognition

Citations in the corpus

Adaptive Information Gathering via Imitation Learning (2017, methodology): “Although there exists fast solvers such as POMCP (Silver and Veness [34]) and DESPOT (Somani et al. [37]), the product space of world maps and observation space is too large for online planning.”
Online Replanning in Belief Space for Partially Observable Task and Motion Problems (2019, methodology): “One approach to online planning is to use Monte-Carlo sampling [17], [18] to explore likely outcomes of various actions.”
Robust Opponent Modeling via Adversarial Ensemble Reinforcement Learning in Asymmetric Imperfect-Information Games (2019, methodology): “ls for single agent, multiagent fully cooperative and multiagent general sum scenarios, respectively. Model-based planning is the most prevalent technique for solving POMDP and Dec-POMDP (e.g., [15], [26], [22]). In POMDP, a value function satisfying Bellmen equation can be defined on the belief spa”
Rational quantitative attribution of beliefs, desires and percepts in human mentalizing (2017, background): “optimal POMDP solutions can be tractably approximated in certain cases [19], and modern solvers can scale to problems with millions of states [44, 45].”
Intention-aware online POMDP planning for autonomous driving in a crowd (2015, methodology): “In contrast, online planning interleaves planning and plan execution (see, e.g., [6], [12], [15], [17]).”
Potential-based reward shaping for finite horizon online POMDP planning (2016, methodology): “This is a very interesting result as on the one hand, AUVNavigation requires long sequences of actions to accomplish its goal, so depth-focused planning approaches like AEMS2 or the MCTS algorithms (ABDESPOT, ARDESPOT) should have an inherent advantage.”
Research Advances and Challenges of Autonomous and Connected Ground Vehicles (2019, background): “Other studies, which use online policy to solve the POMDP for decision making, can be found in [364]– [366].”