Title :
Parallelizing Broad Phase Collision Detection Algorithms for Sampling Based Path Planners
Author :
Geleri, F. ; Tosun, O. ; Topcuoglu, H.
Author_Institution :
Comput. Eng. Dept., Bogazici Univ., Istanbul, Turkey
fDate :
Feb. 27 2013-March 1 2013
Abstract :
Collision checking takes most of the time in sampling based path planning algorithms. When the scene gets crowded, more samples are needed and the probability decreases to find a collision free sample. Broad phase algorithms are designed to eliminate obviously collision free samples, so narrow phase algorithms can concentrate on fewer samples suspected to be in collision. In this study, we compare the performance of two broad phase algorithms implemented on both CPU and GPU. A novel technique is proposed to provide load balancing and efficient cache utilization on Bounding Sphere Collision Detection algorithm. Furthermore, Thrust library is extensively utilized on Sweep and Prune (SAP) algorithm. Our experimental results indicate speedups up to 103 times faster for GPU-based SAP algorithm and 134 times faster for GPU-based Bounding Sphere algorithm, compared to CPU implementations. This may allow using sampling based path planning algorithms for scenes with many robots.
Keywords :
application program interfaces; cache storage; graphics processing units; multiprocessing systems; parallel algorithms; parallel architectures; path planning; physics computing; resource allocation; sampling methods; CPU; GPU-based SAP algorithm; GPU-based bounding sphere algorithm; Thrust library; bounding sphere collision detection algorithm; broad phase collision detection algorithm parallelization; cache utilization; graphics processing units; load balancing; multicore central processing unit; narrow phase algorithms; probability; sampling based path planning algorithm; sweep and prune algorithm; Collision avoidance; Graphics processing units; Indexes; Instruction sets; Kernel; Load management; Robots; CUDA; OpenMP; broad phase; collision detection;
Conference_Titel :
Parallel, Distributed and Network-Based Processing (PDP), 2013 21st Euromicro International Conference on
Conference_Location :
Belfast
Print_ISBN :
978-1-4673-5321-2
Electronic_ISBN :
1066-6192
DOI :
10.1109/PDP.2013.62