AAPP: An Accelerative and Adaptive Path Planner for Robots on GPU

摘要

Optimal path planning is one of the major bottlenecks for the effective navigation of robots working towards accomplishing complex missions. To overcome the bottleneck and support efficient applications, this paper presents <monospace>AAPP</monospace> , an accelerative and adaptive path planner based on RRT*, a popular path planning algorithm, on GPU, to alleviate four main performance limitations, i.e., bandwidth limitation, load imbalance, high computing complexity, and the choice of parameters. First, <monospace>AAPP</monospace> employs a data storage structure, named simplified compressed sparse rows (SCSR), to compress the large-scale map data and increase the utilization of bandwidth. Second, to exploit the computing performance of GPU, we propose a two-layer parallel framework for RRT* based on SCSR format, named TLRRT*, by using the dynamic parallelism technique. Third, aiming at the problems of parallel load imbalance and high computing complexity in TLRRT*, we further design a two-stage parallel framework, named TSRRT*, that fully exploits hardware heterogeneity (CPU/GPU) by scheduling tasks on CPU and GPU adaptively. Finally, we present optimizations for <monospace>AAPP</monospace> to adaptively select execution schemes and parameters. Experimental results on a heterogeneous CPU/GPU machine show that <monospace>AAPP</monospace> yields the speedup up to <inline-formula><tex-math notation="LaTeX">$22.72\times$</tex-math></inline-formula> over the RRT* algorithm. Compared to the state-of-the-art, <monospace>AAPP</monospace> can handle large-scale datasets and obtain feasible solutions with shorter trajectory lengths.