Quad-RRT: A real-time GPU-based global path planner in large-scale real environments. (1st June 2018)

• Record Type: Journal Article
• Authors: Hidalgo-Paniagua, Alejandro; Bandera, Juan Pedro; Ruiz-de-Quintanilla, Manuel; Bandera, Antonio
• Is Part Of: Expert systems with applications. Volume 99(2018)
• Page Start: 141
• Page End: 154
• Publication Date: 2018-06-01
• Subjects: Global path planning -- Large-scale environment -- Rapidly-exploring random trees -- Graphics processing unit; Expert systems (Computer science) -- Periodicals; Systèmes experts (Informatique) -- Périodiques; Electronic journals; 006.33
• DOI: 10.1016/j.eswa.2018.01.035
• Languages: English
• ISSNs: 0957-4174

Abstract

Highlights: Unlike B-RRT, quad-RRT builds four RRT-trees over the map to speed up the process. A complete study of parallelism has been made to analyze the quad-RRT performance. Quad-RRT parameters have been tuned up in order to optimize computation time. Quad-RRT is 10x faster than the best existing RRT-based approaches. Abstract: During the last decade, sampling based methods for motion and path planning have gained more interest. Specifically, in the field of robotics, approaches based on the Rapidly-exploring Random Tree (RRT) algorithm have become the customary technique for solving the single-query motion planning problem. However, dynamic large maps still represent a challenging scenario for these methods to produce fast enough results. Taking advantage of an NVidia CUDA-enabled Graphic Processing Unit (GPU), we present quad-RRT, an extension of the bi-directional strategy to speed up the RRT when dealing with large-scale, bidimensional (2D) maps. Designed for modern GPUs, quad-RRT computes four trees instead of the two ones built by the bidirectional approaches. This modification aims balancing the direct searching ability of these methods with the parallel exploration of those parts of the map at both sides of the path joining the initial and goal poses. Experimental results demonstrate that the proposed algorithm provides a significant speedup dealing with large-scale maps densely populated by obstacles, when compared to other implementations of the RRT. Hence, the algorithm can have a high impact in the field of inspection path planning for distributed infrastructure. It is also a promising approach to allow new generation robots, designed to work in unconstrained environments, dynamically plan large-scale paths.