Parallel Algorithm for the Path Planning of Multiple Unmanned Aerial Vehicles

This paper presents a parallel algorithm for the path planning of multiple unmanned aerial vehicles (UAVs) in the context of a surveillance mission. The UAVs are tasked to visit a set of points of interest (POIs) dispersed in a 3D environment and the algorithm allocates the POIs to the UAVs and computes optimal paths in between the POIs. The algorithm following a four-step approach and relies on a single source shortest path (SSSP) algorithm to compute the optimal paths between the POIs and a genetic algorithm to assign the POIs to the UAVs and find the order in which the POIs are visited. The algorithm is parallelized on a graphics processing unit and a multicore CPU to reduce the computing time and to allow for in-flight planning. The proposed algorithm is able to calculate paths for 3 UAVs and 10 POIs in just 0.6 seconds which represents a speedup of 48x compared to a sequential implementation on CPU.