Multi-UAS minimum time search in dynamic and uncertain environments

Resumo

Esta tesis se engloba en el proyecto de innovación SAVIER (Situational Awareness Virtual EnviRonment) propuesto por Airbus en colaboración con varias universidades españolas, cuyo principal objetivo es investigar los beneficios de distintas tecnologías y automatismos en las estaciones de control de tierra (Ground Control Station, GCS) de múltiples UAVs (Unmaned Aerial Vehicle, UAV). En concreto esta tesis se engloba dentro de la teoría de la búsqueda óptima, que modela probabilísticamente la información disponible sobre el escenario de búsqueda y propone trayectorias de búsqueda teniendo en cuenta los modelos probabilísticos y el tipo de misión de búsqueda. En el caso de algoritmos probabilísticos que tratan con misiones MTS (Minimum Time Search, MTS), su propósito es minimizar el tiempo de detección del objetivo perdido. Debido a esta importancia crítica del tiempo, algunas de sus aplicaciones son las misiones de búsqueda de supervivientes o que impliquen cierto peligro. El principal objetivo de la tesis es proponer nuevos algoritmos MTS y modelos probabilísticos realistas. Esta tesis resuelve el problema MTS desde un nuevo enfoque basado en la metaheurística de optimización de colonias de hormigas (Ant Colony Optimization, ACO), seleccionada debido a su aplicación satisfactoria en una gran variedad de problemas de optimización y a su capacidad para incluir información específica del problema mediante el uso de heurísticas constructivas, lo cual puede ser beneficioso en problemas de gran complejidad como MTS. Se proponen dos tipos de soluciones algorítmicas. Por un lado, se proponen dos algoritmos MTS basados en el algoritmo de optimización ACO para problemas de optimización discretos (Max-Min Ant Colony System), que optimiza las trayectorias de alto nivel de múltiples UAVs, especificadas como secuencias de celdas adyacentes de la red utilizada para discretizar el área de búsqueda. Por lo tanto, debido a la consideración de un modelo dinámico de UAV simple y que requiere una alta maniobrabilidad, estos algoritmos son adecuados para los UAVs de ala rotatoria y tienen la ventaja de requerir tiempos de computación bajos. Los experimentos realizados muestran que, gracias a la heurística MTS propuesta, los algoritmos de MTS pueden encontrar soluciones de mejor calidad en tiempos de computación menores que otros algoritmos del estado del arte. Por otro lado, se propone un algoritmo MTS basado en la metaheurística ACO para problemas de optimización continuos (Ant Colony Optimization for Real Domains, ACOR), que realiza la optimización de múltiples objetivos (minimiza el tiempo de detección del objetivo y el valor una heurística propuesta para evitar caer en soluciones locales, mientras evita que los UAVs sobrevuelen áreas de vuelo prohibidas y posibles colisiones entre UAVs). Gracias a la consideración de un modelo dinámico de UAV complejo, las rutas propuestas quedan definidas por curvas suaves adecuadas para las restricciones de maniobrabilidad de los UAVs de ala fija. Además, alentados por los buenos resultados obtenidos en la versión discreta del problema, se incluye un porcentaje de hormigas que usan información de una heurística constructiva específica del problema MTS para determinar su camino. De las simulaciones realizadas podemos concluir que la inclusión de hormigas heurísticas aumenta la calidad de las soluciones y la velocidad de convergencia del algoritmo, logrando mejores resultados que el algoritmo MTS basado en algoritmos genéticos también propuesto durante esta tesis. Por último, con el objetivo de probar que las técnicas propuestas en esta tesis pueden incorporarse a la funcionalidad de un sistema aéreo no tripulado real, los algoritmos y contribuciones propuestos se han integrado y testeado con una GCS desarrollada por Airbus para controlar el UAV ATLANTE.