GPU-based Global Path Planning Using Genetic Algorithm with Near Corner Initialization

This paper presents a global path planning framework and method that utilizes genetic algorithm (GA) optimization on a highly parallelized Graphics Processing Unit (GPU) platform to achieve salient computing performance. A method to randomly initialize waypoints in the free space near obstacle corners is proposed, which in conjunction with mutation in the free space shows great advantages over other methods in reaching low fitness value. Furthermore, the migration process is introduced into the GA to mitigate the issue of premature convergence. To determine best GA configurations, a tradeoff analysis is conducted, and it is found that the runtime is minimized and optimization accuracy is preserved when the number of populations and individuals are selected as 640 and 64. The number of generations is selected as 1,000 based on the convergence rate of GA optimization. An objective function enabling differential consideration of the path length, smoothness, safety, and feasibility through individual weights is also presented. Numerical experiments demonstrate that different optimal paths can be obtained from the same terrain by tuning the weights. Compared to its serial CPU counterpart, the average speedup achieved by GPU is 83x .