AAPP: An Accelerative and Adaptive Path Planner for Robots on GPU
Juan Liu, Guoqing Xiao, Fan Wu, Xiangke Liao, Kenli Li · IEEE Transactions on Computers · 2023
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 presentsAAPP, 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,AAPPemploys 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 forAAPPto adaptively select execution schemes and parameters. Experimental results on a heterogeneous CPU/GPU machine show thatAAPPyields the speedup up to$22.72\times$over the RRT* algorithm. Compared to the state-of-the-art,AAPPcan handle large-scale datasets and obtain feasible solutions with shorter trajectory lengths.