Multiunmanned Aerial Vehicle Path Planner on Graphics Processing Unit.

Using multiple unmanned aerial vehicles (UAVs) improves the efficiency of reconnaissance, surveillance, and search and rescue missions. This article presents a path-planning software for a team of UAVs utilizing graphics processing units (GPUs). The UAVs are tasked to visit multiple points of interest (POIs) in a 3-D environment, and the software finds an optimized solution that assigns the POIs to the UAVs, selects the order in which the POIs are visited, and calculates the paths between the POIs. The software uses a multistep approach using a single-source-shortest-path algorithm to find the optimal paths between all combinations of POIs followed by a genetic algorithm to solve the multitraveling salesperson problem. The algorithm can minimize distance, time, or energy consumption depending on the setting selected by the user. The proposed GPU implementation is tested on eight different maps from around the world and executes in just 0.6 s, a $48.3\times $ speedup compared to a sequential execution on CPU. This performance improvement is a real asset in a mission-changing environment. [ABSTRACT FROM AUTHOR]