Distributed management and coordination of UAV swarms based on infrastructureless wireless networks

Abstract

[ES] Los Vehículos Aéreos no Tripulados (o drones) ya han demostrado su utilidad en una gran variedad de aplicaciones. Hoy en día, se utilizan para fotografía, cinematografía, inspecciones y vigilancia, entre otros. Sin embargo, en la mayoría de los casos todavía son controlados por un piloto, que como máximo suele estar volando un solo dron cada vez. En esta tesis, tratamos de avanzar en paso más allá en esta tecnología al permitir que múltiples drones con capacidad para despegue y aterrizaje vertical trabajen de forma sincronizada, como una sola entidad. La principal ventaja de realizar vuelos en grupo, comúnmente denominado enjambre, es que se pueden realizar tareas más complejas que utilizando un solo dron. De hecho, un enjambre permite cubrir más área en el mismo tiempo, ser más resistente, tener una capacidad de carga más alta, etc. Esto puede habilitar el uso de nuevas aplicaciones, o una mejor eficiencia para las aplicaciones existentes. Sin embargo, una parte clave es que los miembros del enjambre deben organizarse correctamente, ya que, durante el vuelo, diferentes perturbaciones pueden provocar que sea complicado mantener el enjambre como una unidad coherente. Una vez que se pierde esta coherencia, todos los beneficios previamente mencionados de un enjambre se pierden también. Incluso, aumenta el riesgo de colisiones entre los elementos del enjambre. Por lo tanto, esta tesis se centra en resolver algunos de estos problemas, proporcionando un conjunto de algoritmos que permitan a otros desarrolladores crear aplicaciones de enjambres de drones.

Para desarrollar los algoritmos propuestos hemos incorporado mejoras al llamado ArduSim. Este simulador nos permite simular tanto la física de un dron como la comunicación entre drones con un alto grado de precisión. ArduSim nos permite implementar protocolos y algoritmos (bien probados) en drones reales con facilidad. Durante toda la tesis, ArduSim ha sido utilizado ampliamente. Su utilización ha permitido que las pruebas fueran seguras, y al mismo tiempo nos permitió ahorrar mucho tiempo, dinero y esfuerzo de investigación.

Comenzamos nuestra investigación sobre enjambres asignando posiciones aéreas para cada dron en el suelo. Suponiendo que los drones están ubicados aleatoriamente en el suelo, y que necesitan alcanzar una formación aérea deseada, buscamos una solución que minimice la distancia total recorrida por todos los drones. Para ello se empezó con un método de fuerza bruta, pero rápidamente nos dimos cuenta de que, dada su alta complejidad, este método funciona mal cuando el número de drones aumenta. Por lo tanto, propusimos una heurística. Como en todas las heurísticas, se realizó un compromiso entre complejidad y precisión. Al simplificar el problema, encontramos que nuestra heurística era capaz de calcular una solución muy rápidamente sin aumentar sustancialmente la distancia total recorrida. Además, implementamos el algoritmo de Kuhn-Munkres (KMA), un algoritmo que ha demostrado proporcionar la respuesta exacta (es decir, reducir la distancia total recorrida) en el menor tiempo posible. Después de muchos experimentos, llegamos a la conclusión de que nuestra heurística es más rápida, pero que la solución proporcionada por el KMA es ligeramente más eficiente. En particular, aunque la diferencia en la distancia total recorrida es pequeña, el uso de KMA reduce el número de trayectorias de vuelo que se cruzan entre sí, lo cual es una métrica importante para las siguientes propuestas.[...]

[CA] Els vehicles aeris no tripulats (o drons) ja han demostrat la seua utilitat en una gran varietat d'aplicacions. Avui dia, s'utilitzen per a fotografia, cinematografia, inspeccions i vigilància, entre altres. No obstant això, en la majoria dels casos encara són controlats per un pilot, que com a màxim sol controlar el vol d'un sol dron cada vegada. En aquesta tesi, tractem d'avançar un pas més enllà en aquesta tecnologia, en permetre que múltiples drons amb capacitat per a l'enlairament i l'aterratge vertical treballen de forma sincronitzada, com una sola entitat. El principal avantatge de realitzar vols en grup, comunament denominats eixam, és que es poden fer tasques més complexes que utilitzant un sol dron. De fet, un eixam permet cobrir més àrea en el mateix temps, ser més resistent, tenir una capacitat de càrrega més alta, etc. Això pot habilitar l'ús de noves aplicacions, o una millor eficiència per a les aplicacions existents. No obstant això, una punt clau és que els membres de l'eixam han d'organitzar-se correctament, ja que, durant el vol, diferents pertorbacions poden provocar que siga complicat mantenir l'eixam com una unitat coherent. Una vegada que es perd aquesta coherència, tots els beneficis prèviament esmentats d'un eixam es perden també. Fins i tot, augmenta el risc de col·lisions entre els elements de l'eixam. Per tant, aquesta tesi se centra a resoldre alguns d'aquests problemes, proporcionant un conjunt d'algorismes que permeten a altres desenvolupadors crear aplicacions d'eixams de drons. Per a desenvolupar els algorismes proposats hem incorporat millores a l'anomenat ArduSim. Aquest simulador ens permet simular tant la física d'un dron com la comunicació entre drons amb un alt grau de precisió. ArduSim ens permet implementar protocols i algorismes (ben provats) en drons reals amb facilitat. Durant tota la tesi, ArduSim s'ha utilitzat àmpliament. El seu ús ha permès que les proves foren segures, i al mateix temps ens va permetre estalviar molt de temps, diners i esforç d'investigació. Per tant, es va utilitzar ArduSim per a cada bloc de construcció que vam desenvolupar. Comencem la nostra recerca sobre eixams assignant posicions aèries per a cada dron en terra. Suposant que els drons estan situats aleatòriament en terra i que necessiten assolir la formació aèria desitjada, cerquem una solució que minimitze la distància total recorreguda per tots els drons. Per a això, es va començar amb un mètode de força bruta, però ràpidament ens vam adonar que, atesa l'alta complexitat, aquest mètode funciona malament quan el nombre de drons augmenta. Per tant, vam proposar una heurística. Com en totes les heurístiques, es va fer un compromís entre complexitat i precisió. En simplificar el problema, trobem que la nostra heurística era capaç de calcular una solució molt ràpidament sense augmentar substancialment la distància total recorreguda. A més, vam implementar l'algorisme de Kuhn-Munkres (KMA), un algorisme que ha demostrat proporcionar la resposta exacta (és a dir, reduir la distància total recorreguda) en el menor temps possible. Després de molts experiments, arribem a la conclusió que la nostra heurística és més ràpida, però que la solució proporcionada pel KMA és lleugerament més eficient. En particular, encara que la diferència en la distància total recorreguda és xicoteta, l'ús de KMA redueix el nombre de trajectòries de vol que s'encreuen entre si, la qual cosa és una mètrica important per a les propostes següents.[...]

[EN] Unmanned Aerial Vehicles (UAVs) have already proven to be useful in many different applications. Nowadays, they are used for photography, cinematography, inspections, and surveillance. However, in most cases they are still controlled by a pilot, who at most is flying one UAV at a time. In this thesis, we try to take this technology one step further by allowing multiple Vertical Take-off and Landing (VTOL) UAVs to work together as one entity. The main advantage of this group, commonly referred to as a swarm, is that it can perform more complex tasks than a single UAV. When organized correctly, a swarm allows for: more area to be covered in the same time, more resilience, higher load capability, etc. A swarm can lead to new applications, or a better efficiency for existing applications. A key part, however, is that they should be organized correctly. During the flight, different disturbances will make it complicated to keep the swarm as one coherent unit. Once this coherency is lost, all the previously mentioned benefits of a swarm are lost as well. Even worse, the chance of a hazard increases. Therefore, this thesis focuses on solving some of these issues by providing a baseline of building blocks that enable other developers to create UAV swarm applications.

In order to develop these building blocks, we improve a multi-UAV simulator called ArduSim. This simulator allows us to simulate both the physics of a UAV, and the communication between UAVs with a high degree of accuracy. This is a crucial part because it allows us to deploy (well tested) protocols and algorithms on real UAVs with ease. During the entirety of this thesis, ArduSim has been used extensively. It made testing safe, and allowed us to save a lot of time, money and research effort.

We started by assigning airborne positions for each UAV on the ground. Assuming that the UAVs, are placed randomly on the ground, and that they need to reach a desired aerial formation, we searched for a solution that minimizes the total distance travelled by all the UAVs. We started with a brute-force method, but quickly realized that, given its high complexity, this method performs badly when the number of UAVs grows. Hence, we created a heuristic. As for all heuristics, a trade-off was made between complexity and accuracy. By simplifying the problem, we found that our heuristic was able to calculate a solution very quickly without increasing the total distance travelled substantially. Furthermore, we implemented the \ac{KMA}, an algorithm that has been proven to provide the exact answer (i.e. minimal total distance travelled) in the shortest time possible. After many experiments, we came to the conclusion that our heuristic is faster, but that the solution provided by the \ac{KMA} is slightly better. In particular, although the difference in total distance travelled is small, the \ac{KMA} reduces the numbers of flight paths crossing each other, which is an important metric in our next building block.

Once we developed algorithms to assign airborne positions to each UAV on the ground, we started developing algorithms to take off all those UAVs. The objective of these algorithms is to reduce the time it takes for all the UAVs to reach their aerial position, while ensuring that all UAVs maintain a safe distance. The easiest solution is a sequential take-off procedure, but this is also the slowest approach. Hence, we improved it by first proposing a semi-sequential and later a semi-simultaneous take-off procedure. With this semi-simultaneous take-off procedure, we are able to reduce the takeoff time drastically without introducing any risk to the aircraft. [..]