Coordination on Systems of Multiple UAVs

Abstract

Esta tesis trata acerca de métodos para coordinar las trayectorias de un sistema de Vehículos Aéreos no Tripulados y Autónomos (en adelante UAVs). El primer conjunto de técnicas desarrolladas durante la tesis se agrupan dentro de las técnicas de planificación de trayectorias. En este caso, el objetivo es generar planes de vuelo para un conjunto de vehículos coordinadamente de forma que no se produzcan colisiones entre ellos. Además, este tipo de técnicas puede usarse para modificar el plan de vuelo de un subconjunto de UAVs en tiempo real. Entre los algoritmos desarrollados en la tesis podemos destacar la adaptación de algoritmos evolutivos como los Algoritmos Genéticos y el Particle Swarm (Enjambre de Partículas), la incorporación de nuevas formas de muestreo del espacio para la aplicación del algoritmo Optimal Rapidly Exploring Random Trees (RRT*) en sistemas multi-UAV usando técnicas de muestreo novedosas. También se ha estudiado el comportamiento de parte de estos algoritmos en situaciones variables de incertidumbre del estado del sistema. En particular, se propone el uso del Filtro de Partículas para estimar la posición relativa entre varios UAVs. Además, se estudia la aplicación de métodos reactivos para la resolución de colisiones en tiempo real. Esta tesis propone un nuevo algoritmo para la resolución de colisiones entre múltiples UAVs en presencia de obstáculos fijos llamado G-ORCA. Este algoritmo soluciona varios problemas que han surgido al aplicar el algoritmo ORCA en su variante 3D en sistemas compuestos por vehículos reales. Su seguridad se ha demostrado tanto analíticamente, como empíricamente en pruebas con sistemas reales. De hecho, durante esta tesis numerosos experimentos en sistemas multi-UAV reales compuestos hasta por 4 UAVs han sido ejecutados. En dichos experimentos, se realiza una coordinación autónoma de UAVs en las que se asegura la ejecución de trayectorias libres de colisiones garantizando por tanto la seguridad del sistema. Una característica reseñable de esta tesis es que los algoritmos desarrollados han sido probados e integrados en sistemas más complejos que son usados en aplicaciones reales. En primer lugar, se presenta un sistema para aumentar la duración del vuelo de planeadores aprovechando las corrientes ascendentes de viento generadas por el calor (térmicas). En segundo lugar, un sistema de detección y resolución de colisiones coordinado para sistemas con múltiples UAVs reactivo ha sido diseñado, desarrollado y probado experimentalmente. Este sistema ha sido integrado dentro de un sistema automático de construcción de estructuras mediante múltiples UAVs.

The aim of this thesis is to propose methods to coordinately generate trajectories for a system of Autonomous Unmanned Aerial Vehicles (UAVs). The first set of proposed techniques developed in this thesis can be defined as trajectory planning techniques. In this case, the objective is to generate coordinated flight plans for a system of UAVs in such a way that no collision are produced among each pair of UAVs. Besides, these techniques can be applied online in order to modify the original flight plan whenever a potential collision is detected. Amongst the developed algorithms in this thesis we can highlight the adaptation of evolutionary algorithms such as Genetic Algorithms and Particle Swarm, and the application of Optimal Rapidly Exploring Random Trees (RRT*) algorithm into a system of several UAVs with novel sampling techniques. In addition, many of these techniques have been adapted in order to be applicable when only uncertain knowledge of the state of the system is available. In particular, the use of the Particle Filter is proposed in order to estimate the relative position between UAVs. The estimation of the position as well as the uncertainty related to this estimation are then taken into account in the conflict resolution system. All techniques proposed in this thesis have been validated by performing several simulated and real tests. For this purpose, a method for randomly generating a huge test batch is presented in chapter 3. This will allow to test the behavior of the proposed methods in a great variety of situations. During the thesis, several real experimentations with fleets composed by up to four UAVs are presented. In these experiments, the UAVs in the system are automatically coordinated in order to ensure collision-free trajectories and thus guarantee the safety of the system. The other main topic of this thesis is the application of reactive methods for real-time conflict resolution. This thesis proposes a novel algorithm for collision resolution amongst multiple UAVs in the presence of static obstacles, which has been called Generalized-Optimal Reciprocal Collision Avoidance (G-ORCA). This algorithm overcomes several issues that have been detected into the algorithm 3D-ORCA in real applications. A remarkable characteristic of this thesis is that the developed algorithms have been applied as a part of more complex systems. First, a coordinated system for flight endurance extension of gliding aircrafts by profiting the ascending wind is presented. Second, a reactive collision avoidance block has been designed, developed and tested experimentally based in the aforementioned G-ORCA algorithm. This block has been integrated into a system for assembly construction with multiple UAVs.