mlsanityData to 7 Oct 2026

DESPOT: Online POMDP Planning with Regularization

arXiv 1609.03250 ↗First posted 12 Sep 2016cs.AIcited by 105

Not on the map. Why?

Abstract (arXiv)

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.

Key facts. Cited by 105 papers in the map (data through 7 Oct 2026). First posted on arXiv 12 Sep 2016.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2018: 1; 2019: 0; 2020: 0; 2021: 16; 2022: 20; 2023: 24; 2024: 17; 2025: 15; 2026: 12.

105 papers.

Sort:

By area:

  1. 2023Motion Planning for Autonomous Driving: The State of the Art and Future Perspectivescited by 112
  2. 2022Partially Observable Markov Decision Processes in Robotics: A Surveycited by 81
  3. 2021Deep Multiagent Reinforcement Learning: Challenges and Directionscited by 42
  4. 2022Learning in Observable POMDPs, without Computationally Intractable Oraclescited by 30
  5. 2022Planning in Observable POMDPs in Quasipolynomial Timecited by 25
  6. 2023Machine Learning for Autonomous Vehicle's Trajectory Prediction: A comprehensive survey, Challenges, and Future Research Directionscited by 23
  7. 2022Optimality Guarantees for Particle Belief Approximation of POMDPscited by 20
  8. 2021Physical Interaction as Communication: Learning Robot Objectives Online from Human Correctionscited by 19
  9. 2023What Truly Matters in Trajectory Prediction for Autonomous Driving?cited by 17
  10. 2024Partially Observable Task and Motion Planning with Uncertainty and Risk Awarenesscited by 17
  11. 2024Equivariant Reinforcement Learning under Partial Observabilitycited by 17
  12. 2018An Efficient, Generalized Bellman Update For Cooperative Inverse Reinforcement Learningcited by 15
38 more
  1. 2021Solving Common-Payoff Games with Approximate Policy Iterationcited by 15
  2. 2021Towards Optimal Correlational Object Searchcited by 14
  3. 2023Active Uncertainty Reduction for Safe and Efficient Interaction Planning: A Shielding-Aware Dual Control Approachcited by 13
  4. 2023BetaZero: Belief-State Planning for Long-Horizon POMDPs using Learned Approximationscited by 13
  5. 2021Closing the Planning-Learning Loop with Application to Autonomous Drivingcited by 12
  6. 2023CAR-DESPOT: Causally-Informed Online POMDP Planning for Robots in Confounded Environmentscited by 11
  7. 2022Active Uncertainty Reduction for Human-Robot Interaction: An Implicit Dual Control Approachcited by 10
  8. 2022LEADER: Learning Attention over Driving Behaviors for Planning under Uncertaintycited by 9
  9. 2021Compositional Learning-based Planning for Vision POMDPscited by 8
  10. 2023Safe POMDP Online Planning via Shieldingcited by 8
  11. 2021SIDE: State Inference for Partially Observable Cooperative Multi-Agent Reinforcement Learningcited by 7
  12. 2023Learning Logic Specifications for Soft Policy Guidance in POMCPcited by 7
  13. 2021Simplified Belief-Dependent Reward MCTS Planning with Guaranteed Tree Consistencycited by 6
  14. 2022Adaptive Information Belief Space Planningcited by 6
  15. 2022Efficient Algorithms for Planning with Participation Constraintscited by 6
  16. 2022Multiagent Reinforcement Learning for Autonomous Routing and Pickup Problem with Adaptation to Variable Demandcited by 6
  17. 2023Combining Tree-Search, Generative Models, and Nash Bargaining Concepts in Game-Theoretic Reinforcement Learningcited by 6
  18. 2023Adaptive Discretization using Voronoi Trees for Continuous POMDPscited by 6
  19. 2024Task and Motion Planning for Execution in the Realcited by 6
  20. 2022Mask Atari for Deep Reinforcement Learning as POMDP Benchmarkscited by 5
  21. 2022Nonmyopic Distilled Data Association Belief Space Planning Under Budget Constraintscited by 5
  22. 2021Online POMDP Planning via Simplificationcited by 4
  23. 2022Intention-Aware Navigation in Crowds with Extended-Space POMDP Planningcited by 4
  24. 2023Weathering Ongoing Uncertainty: Learning and Planning in a Time-Varying Partially Observable Environmentcited by 4
  25. 2021Reinforcement Learning based Negotiation-aware Motion Planning of Autonomous Vehiclescited by 3
  26. 2022Risk Aware Adaptive Belief-dependent Probabilistically Constrained Continuous POMDP Planningcited by 3
  27. 2022Adaptive Discretization using Voronoi Trees for Continuous-Action POMDPscited by 3
  28. 2025Managing Geological Uncertainty in Critical Mineral Supply Chains: A POMDP Approach with Application to U.S. Lithium Resourcescited by 3
  29. 2025Generative AI for Autonomous Driving: A Reviewcited by 3
  30. 2021Active Inference Tree Search in Large POMDPscited by 2
  31. 2021Probabilistic Loss and its Online Characterization for Simplified Decision Making Under Uncertaintycited by 2
  32. 2021Efficient Sampling in POMDPs with Lipschitz Bandits for Motion Planning in Continuous Spacescited by 2
  33. 2021HARPS: An Online POMDP Framework for Human-Assisted Robotic Planning and Sensingcited by 2
  34. 2022Monte Carlo Planning in Hybrid Belief POMDPscited by 2
  35. 2023Online POMDP Planning with Anytime Deterministic Optimality Guaranteescited by 2
  36. 2023Rollout Heuristics for Online Stochastic Contingent Planningcited by 2
  37. 2023Simplifying Complex Observation Models in Continuous POMDP Planning with Probabilistic Guarantees and Practicecited by 2
  38. 2024The State of Robot Motion Generationcited by 2

50 most cited of 105 All 105 (JSON)