# HyP-DESPOT: A Hybrid Parallel Algorithm for Online Planning under Uncertainty

arXiv: https://arxiv.org/abs/1802.06215 · HTML: https://mlsanity.com/paper/1802.06215/

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Feb 2018.

## Built on by (most cited first, 18 of 18)

- [Partially Observable Markov Decision Processes in Robotics: A Survey](https://mlsanity.com/paper/2209.10342/) (2022)
- [BetaZero: Belief-State Planning for Long-Horizon POMDPs using Learned Approximations](https://mlsanity.com/paper/2306.00249/) (2023)
- [Closing the Planning-Learning Loop with Application to Autonomous Driving](https://mlsanity.com/paper/2101.03834/) (2021)
- [LEADER: Learning Attention over Driving Behaviors for Planning under Uncertainty](https://mlsanity.com/paper/2209.11422/) (2022)
- [Pedestrian-Robot Interactions on Autonomous Crowd Navigation: Reactive Control Methods and Evaluation Metrics](https://mlsanity.com/paper/2208.02121/) (2022)
- [Intention-Aware Navigation in Crowds with Extended-Space POMDP Planning](https://mlsanity.com/paper/2206.10028/) (2022)
- [Quantum Artificial Intelligence: A Brief Survey](https://mlsanity.com/paper/2408.10726/) (2024)
- [Active Inference Tree Search in Large POMDPs](https://mlsanity.com/paper/2103.13860/) (2021)
- [Hi-Drive: Hierarchical POMDP Planning for Safe Autonomous Driving in Diverse Urban Environments](https://mlsanity.com/paper/2409.18411/) (2024)
- [Previous Knowledge Utilization In Online Anytime Belief Space Planning](https://mlsanity.com/paper/2412.13128/) (2024)
- [Vectorized Online POMDP Planning](https://mlsanity.com/paper/2510.27191/) (2025)
- [Constrained Bayesian Experimental Design via Online Planning](https://mlsanity.com/paper/2605.26990/) (2026)
- [Belief-Conditioned One-Step Diffusion: Real-Time Trajectory Planning with Just-Enough Sensing](https://mlsanity.com/paper/2508.12166/) (2025)
- [Factored Online Planning in Many-Agent POMDPs](https://mlsanity.com/paper/2312.11434/) (2023)
- [MEXGEN: An Effective and Efficient Information Gain Approximation for Information Gathering Path Planning](https://mlsanity.com/paper/2405.02605/) (2024)
- [Array-Based Monte Carlo Tree Search](https://mlsanity.com/paper/2508.20140/) (2025)
- [Neural Value Iteration](https://mlsanity.com/paper/2511.08825/) (2025)
- [Vec-QMDP: Vectorized POMDP Planning on CPUs for Real-Time Autonomous Driving](https://mlsanity.com/paper/2602.08334/) (2026)

## Abstract (arXiv)

Planning under uncertainty is critical for robust robot performance in uncertain, dynamic environments, but it incurs high computational cost. State-of-the-art online search algorithms, such as DESPOT, have vastly improved the computational efficiency of planning under uncertainty and made it a valuable tool for robotics in practice. This work takes one step further by leveraging both CPU and GPU parallelization in order to achieve near real-time online planning performance for complex tasks with large state, action, and observation spaces. Specifically, we propose Hybrid Parallel DESPOT (HyP-DESPOT), a massively parallel online planning algorithm that integrates CPU and GPU parallelism in a multi-level scheme. It performs parallel DESPOT tree search by simultaneously traversing multiple independent paths using multi-core CPUs and performs parallel Monte-Carlo simulations at the leaf nodes of the search tree using GPUs. Experimental results show that HyP-DESPOT speeds up online planning by up to several hundred times, compared with the original DESPOT algorithm, in several challenging robotic tasks in simulation.