HyP-DESPOT: A hybrid parallel algorithm for online planning under uncertainty

P Cai, Y Luo, D Hsu, WS Lee - The International Journal of …, 2021 - journals.sagepub.com
P Cai, Y Luo, D Hsu, WS Lee
The International Journal of Robotics Research, 2021journals.sagepub.com
Robust planning under uncertainty is critical for robots in uncertain, dynamic environments,
but 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 real-time online planning
performance for complex tasks with large state, action, and observation spaces. Specifically …
Robust planning under uncertainty is critical for robots in uncertain, dynamic environments, but 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 real-time online planning performance for complex tasks with large state, action, and observation spaces. Specifically, Hybrid Parallel DESPOT (HyP-DESPOT) is 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; it performs parallel Monte Carlo simulations at the leaf nodes of the search tree using GPUs. HyP-DESPOT provably converges in finite time under moderate conditions and guarantees near-optimality of the solution. Experimental results show that HyP-DESPOT speeds up online planning by up to a factor of several hundred in several challenging robotic tasks in simulation, compared with the original DESPOT algorithm. It also exhibits real-time performance on a robot vehicle navigating among many pedestrians.
Sage Journals
以上显示的是最相近的搜索结果。 查看全部搜索结果