Algorithmic and combinatorial problems on multi-UAV systems

摘要

espanolLas matematicas siempre han sido una pieza fundamental en el desarrollo de la robotica, asi como los problemas de robotica han jugado un importante papel en el desarrollo de las matematicas. Esta tesis esta motivada por el creciente interes en problemas que aparecen en aplicaciones de robotica aerea, especificamente, esta enfocada en sistemas cooperativos de multiples robots aereos o drones. La mayoria de los trabajos de investigacion en sistemas de robots se han centrado en la construccion y validacion de arquitecturas desde un enfoque empirico. Por el contrario, esta tesis enfoca el estudio de problemas relacionados con tareas para equipos de robots aereos desde el punto de vista de la optimizacion discreta y combinatoria. Inspirada en problemas de este campo, esta memoria plantea nuevos modelos teoricos y problemas de interes para las matematicas aplicadas y la ciencia computacional. Enestatesisse abordanlostemassiguientes: (1) sincronizacion: disenodeuna estrategia de coordinacion que permita comunicacion periodica entre los miembros de un equipo cooperativo mientras ejecutan una tarea sobre trayectorias fijadas, (2) robustez: analisis del efecto que produce el fallo de los agentes en un sistema sincronizado, (3)estrategias estocasticas: analisisdelfuncionamientodeunsistema sincronizado cuando se utilizan drones con toma de decisiones aleatorias, y (4) asignacion de tareas: coordinacion no centralizada usando asignacion periodica de tareas que permita mantener una carga de trabajo balanceada. En la primera parte, se estudia teoricamente el problema de la sincronizacion, dando condiciones necesarias y suficientes para la existencia de solucion 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 comunicacion entre los miembros del equipo. Se estudian de forma rigurosa problemas combinatorios que surgen cuando se requiere saber como de robusto es un sistema con respecto a fallos. Se muestran conexiones con areas matematicas como la teoria de numeros, la teoria de grafos, los grafos circulantes o multiplicacion 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 relacion de este problema con la teoria de caminatas aleatorias y se muestra que el uso de estrategias estocasticas supone una mejora de la robustez del sistema sincronizado. Por ultimo, se propone la estrategia de coordinacion por bloques para la asignacion balanceada de tareas. Se prueba la convergencia del metodo a una asignacion optima y se realiza un estudio de caso para la construccion 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 metodos propuestos. EnglishMathematics 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 pe