Title: Massively parallel hybrid algorithm on embedded graphics processing unit for unmanned aerial vehicle path planning
Authors: Vincent Roberge; Mohammed Tarbouchi
Addresses: Department of Electrical and Computer Engineering, Royal Military College of Canada, P.O. Box 17000, Station Forces, Kingston, ON K7K 7B4, Canada ' Department of Electrical and Computer Engineering, Royal Military College of Canada, P.O. Box 17000, Station Forces, Kingston, ON K7K 7B4, Canada
Abstract: To operate autonomously, military unmanned aerial vehicles (UAVs) must be equipped with a path planning module capable of calculating feasible trajectories. This is a highly complex and nonlinear optimisation problem that challenges state of the art methods. In this paper, we present a massively parallel hybrid algorithm to solve the path planning problem for fixed-wing military UAVs. The proposed solution combines the strengths of the genetic algorithm (GA) and the particle swarm optimisation and allows for the calculation of quasi-optimal paths in realistic 3D environments. To reduce the execution time, the proposed algorithm is parallelised on the NVIDIA Jetson TX1 embedded graphics processing unit (GPU). By exploiting the parallel architecture of the GPU, the runtime is reduced by a factor of 23.6× to just 4.3 seconds while requiring only 10 watts, making it an excellent solution for on-board path planning. The proposed system is tested in a simulation using 18 scenarios on six different terrains.
Keywords: hybrid metaheuristic; genetic algorithm; graphics processing units; GPU; NVIDIA Jetson TX1; particle swarm optimisation; PSO; path planning; parallel computing; unmanned aerial vehicle; UAV.
International Journal of Digital Signals and Smart Systems, 2018 Vol.2 No.1, pp.68 - 93
Received: 08 Aug 2017
Accepted: 19 Oct 2017
Published online: 27 Mar 2018 *