Robotics: Science and Systems XIV
HyP-DESPOT: A Hybrid Parallel Algorithm for Online Planning under Uncertainty
Panpan Cai, Yuanfu Luo, David Hsu, Wee Sun LeeAbstract:
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 hundreds of times, compared with the original DESPOT, in several challenging robotic tasks in simulation.
Bibtex:
@INPROCEEDINGS{Cai-RSS-18, AUTHOR = {Panpan Cai AND Yuanfu Luo AND David Hsu AND Wee Sun Lee}, TITLE = {HyP-DESPOT: A Hybrid Parallel Algorithm for Online Planning under Uncertainty}, BOOKTITLE = {Proceedings of Robotics: Science and Systems}, YEAR = {2018}, ADDRESS = {Pittsburgh, Pennsylvania}, MONTH = {June}, DOI = {10.15607/RSS.2018.XIV.004} }