Algorithmic and combinatorial problems on multi-UAV systems

Description

Las matemáticas siempre han sido una pieza fundamental en el desarrollo de la robótica, así como los problemas de robótica han jugado un importante papel en el desarrollo de las matemáticas. Esta tesis está motivada por el creciente interés en problemas que aparecen en aplicaciones de robótica aérea, específicamente, está enfocada en sistemas cooperativos de múltiples robots aéreos o drones. La mayoría de los trabajos de investigación en sistemas de robots se han centrado en la construcción y validación de arquitecturas desde un enfoque empírico. Por el contrario, esta tesis enfoca el estudio de problemas relacionados con tareas para equipos de robots aéreos desde el punto de vista de la optimización discreta y combinatoria. Inspirada en problemas de este campo, esta memoria plantea nuevos modelos teóricos y problemas de interés para las matemáticas aplicadas y la ciencia computacional. Enestatesisse abordanlostemassiguientes: (1) sincronización: diseñodeuna estrategia de coordinación que permita comunicación periódica entre los miembros de un equipo cooperativo mientras ejecutan una tarea sobre trayectorias fijadas, (2) robustez: análisis del efecto que produce el fallo de los agentes en un sistema sincronizado, (3)estrategias estocásticas: análisisdelfuncionamientodeunsistema sincronizado cuando se utilizan drones con toma de decisiones aleatorias, y (4) asignación de tareas: coordinación no centralizada usando asignación periódica de tareas que permita mantener una carga de trabajo balanceada. En la primera parte, se estudia teóricamente el problema de la sincronización, dando condiciones necesarias y suficientes para la existencia de solución y se presenta un algoritmo que construye un sistema sincronizado para un conjunto fijado de trayectorias de vuelo. La segunda parte de la tesis estudia la robustez de un sistema sincronizado teniendo en cuenta dos aspectos fundamentales: el cubrimiento del terreno y la comunicación entre los miembros del equipo. Se estudian de forma rigurosa problemas combinatorios que surgen cuando se requiere saber cómo de robusto es un sistema con respecto a fallos. Se muestran conexiones con áreas matemáticas como la teoría de números, la teoría de grafos, los grafos circulantes o multiplicación de polinomios. En la tercera parte de la tesis, se estudia la robustez del sistema cuando se introducen decisiones aleatorias de los drones. Se prueba la relación de este problema con la teoría de caminatas aleatorias y se muestra que el uso de estrategias estocásticas supone una mejora de la robustez del sistema sincronizado. Por último, se propone la estrategia de coordinación por bloques para la asignación balanceada de tareas. Se prueba la convergencia del método a una asignación óptima y se realiza un estudio de caso para la construcción de una estructura mediante un equipo cooperativo de drones. Todos los algoritmos desarrollados en esta tesis han sido implementados y se han llevado a cabo diversos experimentosque demuestran la validez de los métodos propuestos.

Abstract

Mathematics has always been a fundamental piece in robotics and, research in robotics has played an important role in the development of mathematics. This thesis is motivated by the growing interest on problems that appear in aerial robotics applications, specifically, on cooperative systems of multiple aerial robots or drones. Most of the research works in multi-robot systems have focused primarily on construction and validation of working systems, rather than more general and formal analysis of problems and solutions. By contrast, this thesis focuses on formally solving problems of aerial multi-robot systems from a discrete and combinatorial optimization perspective. Inspired on problems of this area, the thesis introduces some new theoretical models and problems of interest for mathematicians and computer scientists. The following topics are covered in this thesis: (1) synchronization: design of a coordination strategy to allow periodical communication between the members of a cooperative team while performing a task along fixed trajectories in a scenario with limited communication range, (2) robustness: analysis of the detrimental effects in the performance of a synchronized system when one or more robots fail, (3) stochastic strategies: performance analysis of a synchronized system using drones with stochastic decision making, and (4) task allocation: decentralized coordination to perform periodical task allocation in order to maintain a balanced work load for all members of a team with limited communication range. In the first part of the thesis, we study the synchronization problem giving a theoretical characterization of the solutions and, we present an algorithm to build a synchronized system for a given set of covering trajectories. The second part focuses on the study of the robustness in a synchronized system regarding to two key aspects: covering of the working area and communication between the members of the team. We rigorously study several combinatorial problems to measure how robust a system is to deal with drones failures. Connections of theseproblemswithnumbertheory, graphtheory, circulantgraphsandpolynomial multiplication are shown. The third part is devoted to an analysis of synchronized systems using random aerial robots. This topic is closely related to the random walk theory. It is shown that stochastic strategies increase the robustness of a synchronized system. Finally, this thesis introduces the block sharing strategy to addresstheproblemofmaintainingabalancedtaskallocationamongtherobotsby using periodical communications. A proof on the convergence to an optimal task allocation is given and, a case study for structure construction using a cooperative team of aerial robots is presented. All algorithms developed in this thesis have been implemented and extensive experiments have been conducted to analyze and validate the proposed methods.

Additional details