Robotics: Science and Systems XXII

Vec-QMDP: Vectorized POMDP Planning on CPUs for Real-Time Autonomous Driving

Jin Xuanjin, Yanxin Dong, Bin Sun, Huan Xu, Zhihui Hao, Xianpeng Lang, Panpan Cai

Abstract:

Planning under uncertainty for real-world robotics tasks, such as autonomous driving, requires reasoning in enormous high-dimensional belief spaces, rendering the problem computationally intensive. While parallelization offers scalability, existing hybrid CPU-GPU solvers face critical bottlenecks due to host-device synchronization latency and branch divergence on SIMT architectures, limiting their utility for real-time planning and hindering real-robot deployment. We present Vec-QMDP, a CPU-native parallel planner that aligns POMDP search with modern CPUs' SIMD architecture, achieving 227×--1073× speedup over state-of-the-art serial planners. Vec-QMDP adopts a Data-Oriented Design (DOD), refactoring scattered, pointer-based data structures into contiguous, cache-efficient memory layouts. We further introduce a hierarchical parallelism scheme: distributing sub-trees across independent CPU cores and SIMD lanes, enabling fully vectorized tree expansion and collision checking. Efficiency is maximized with the help of UCB load balancing across trees and a vectorized STR-tree for coarse-level collision checking. Evaluated on large-scale autonomous driving benchmarks, Vec-QMDP achieves state-of-the-art planning performance with millisecond-level latency, establishing CPUs as a high-performance computing platform for large-scale planning under uncertainty.

Download:

Bibtex:

  
@INPROCEEDINGS{XuanjinJ-RSS-26, 
    AUTHOR    = {Jin Xuanjin AND Yanxin Dong AND Bin Sun AND Huan Xu AND Zhihui Hao AND Xianpeng Lang AND Panpan Cai}, 
    TITLE     = {{Vec-QMDP: Vectorized POMDP Planning on CPUs for Real-Time Autonomous Driving}}, 
    BOOKTITLE = {Proceedings of Robotics: Science and Systems}, 
    YEAR      = {2026}, 
    ADDRESS   = {Sydney, Australia}, 
    MONTH     = {July}, 
    DOI       = {10.15607/RSS.2026.XXII.179} 
}