GPU-based motion planning under uncertainties using POMDP

We present a novel GPU-based parallel algorithm to solve continuous-state POMDP problems. We choose the MCVI (Monte Carlo Value Iteration) method as our base algorithm [1], and parallelize this algorithm using multi-level parallel formulation of MCVI. For each parallel level, we propose efficient algorithms to effectively utilize the massive data parallelism of GPUs. To obtain the maximum parallel performance at highest level, we introduce two workload distribution techniques such as data/compute interleaving and workload balancing. To the best of our knowledge, our algorithm is the first parallel algorithm that executes POMDP efficiently on GPUs. Our GPU-based algorithm outperforms the existing CPU-based algorithm by a factor of 75~90 on different benchmarks.