Path Planning Algorithm for Multiple Unmanned Aerial Vehicles with Parallel Implementation on a Graphics Processing Unit

Abstract

The usage of unmanned aerial vehicles (UAVs) have been growing at increasing rates and primarily for the execution of surveillance and reconnaissance tasks. Motivations for their use pertain to their versatility, low cost, elimination of human risk, and potential autonomous capabilities. Intelligence, surveillance and reconnaissance (ISR) tasks for UAVs generally require the aircraft to overfly specified points of interest in an efficient manner while avoiding ter- rain and dangerous regions to gather data and information. A step towards autonomous UAV’s is a path planning module, capable of solving the com- plex optimization problem of computing the routing in a reliable and timely manner. This speed is essential to allow for rapid flight path updating due to variabilities in the environment and changing objectives. Deploying multiple UAVs on a mission allows for faster objective completion and provides a higher level of redundancy; however, adds complexity as the problem of resource al- location and coordination must be considered. This thesis work investigates a fast flight planning algorithm for an ISR scenario involving multiple UAV’s over a known geographical area. A path planning algorithm was developed, it consists of the setup and formatting of data, solving the routing problem for each POI using Bellman-Ford, and the distribution and assignment of the appropriate paths for multiple UAV’s using the Genetic Algorithm. The ac- celeration of this process was achieved using a Graphics Processing Unit and allowed for significant speed-up enabling rapid path planning and in-mission recalculations. The path planning program was tested and verified on a variety of real-world terrain scenario’s simulating an ISR type mission with varying number of UAVs.

L’utilisation de v ́ehicules a ́eriens sans pilote (UAV) augmente de plus en plus rapidement et sert principalement `a l’ex ́ecution de tˆaches de surveillance et de reconnaissance. Leur utilisation est motiv ́ee par leur polyvalence, leur faible couˆt, l’ ́elimination des risques pour l’homme et leur autonomie. Les tˆaches de renseignement, de surveillance et de reconnaissance (ISR) pour les UAV requi`ert de survoler des points d’int ́erˆet sp ́ecifi ́es de mani`ere efficace tout en ́evitant les terrains et les r ́egions dangereuses pour collecter des donn ́ees et de l’information. En marche vers leur autonomie, les UAV doivent disposer d’un module de planification de trajectoire capable de r ́esoudre le probl`eme complexe d’optimisation de calcul de mani`ere robuste et rapide. Cela permet une mise-`a-jour rapide de la trajectoire de vol en raison de la variabilit ́e de l’environnement et des objectifs changeants. Une complexit ́e suppl ́ementaire est introduite lors d’un sc ́enario ou` plusieurs UAV sont d ́eploy ́es. Cela permet d’accomplir les objectifs plus rapidement et offre un niveau de redondance plus ́elev ́e, mais l’affectation des ressources et la coordination des a ́eronefs doivent ˆetre prise en compte. Cette th`ese pr ́esente une solution de planification de vol pour un sc ́enario ISR ou` plusieurs UAV survolent une zone g ́eographique donn ́ee. Cela a ́et ́e accompli grˆace `a la configuration et au formatage des donn ́ees d’entr ́ee, `a la r ́esolution du probl`eme du chemin le plus court `a source unique pour chaque point d’int ́erˆet utilisant Bellman-Ford, ainsi qu’`a la distri- bution et `a l’attribution des chemins appropri ́es pour plusieurs UAV utilisant la m ́etaheuristique de l’algorithme g ́en ́etique. L’acc ́el ́eration de ce processus, obtenue `a l’aide d’un processeur graphique, a produit un gain significatif per- mettant la planification et le re calcul des trajectoires de mani`ere tr`es rapide. De plus, le programme de planification de trajectoire a ́et ́e test ́e et v ́erifi ́e pour divers sc ́enarios repr ́esentant un terrain r ́eel et simulant une mission de type ISR avec un nombre variable d’UAV.