Towards Unified Air Traffic Complexity Management through Graph Theory and Artificial Intelligence

Abstract

La Gestió del Trànsit Aeri (ATM) es defineix formalment com la gestió dinàmica i integrada del trànsit i l’espai aeri de forma segura, econòmica i eficient, mitjançant la disposició d’infraestructures i serveis integrats en col·laboració amb totes les parts i involucrant-hi funcionalitats del costat aire i del costat terra. Es tracta d’un sistema socio-tècnic complex estructurat en diferents nivells i subsistemes interrelacionats. El rendiment a cada nivell es mesura a través de diverses àrees clau de rendiment (KPA), d’entre les quals, algunes de les més importants són la seguretat, la capacitat, la rendibilitat i l’impacte ambiental. Tot i que formen part de la mateixa estructura ATM, cadascun dels nivells té diferents objectius que a la pràctica competeixen entre si, per maximitzar les seves pròpies metes. S’espera un escenari similar per als sistemes aeris no tripulats (UAS), on el desenvolupament de diferents sistemes de gestió de trànsit d’UAS obeeixen a un enfocament semblant al d’ATM. En aquesta tesi, concebem la complexitat del trànsit aeri com el marc de referència per tenir una comprensió única i compartida entre els actors que prenen decisions als diferents nivells del sistema ATM. D’altra banda, també hem treballat en la Detecció i Resolució de Conflictes (CD&R) automatitzada per investigar com l’Aprenentatge per Reforç de Múltiples Agents (MARL) pot facilitar avançar cap als sistemes autònoms de gestió de trànsit ATM i UAS. Per abordar tots dos objectius, primer definim la complexitat del trànsit aeri de manera que proporcioni eficientment una informació elaborada als diferents actors interessats. Com a primer pas, proporcionem una definició genèrica de les interdependències entre parells d’aeronaus, que es basa en la distància en temps discretitzats i s’adapta al cas d’ús i context. Hem utilitzat la teoria de grafs per modelar el trànsit aeri com un gràfic dinàmic i definim quatre indicadors de complexitat que combinen diferent informació topològica i la severitat de les interdependències per donar una evolució detallada i peculiar de la complexitat del trànsit en un espai aeri determinat. Aquests indicadors han estat ampliats per introduir el concepte de complexitat d’aeronau, a través del qual s’identifiquen àrees espai-temporals complexes en un espai aeri determinat. A més, s’ha investigat l’efectivitat d’aquests indicadors de complexitat al domini dels UAS, per mostrar com la mateixa definició de complexitat del trànsit aeri es pot utilitzar en diferents dominis. Centrant-nos en CD&R, abordem aquest problema a través de MARL, que és un paradigma d’aprenentatge automàtic (ML) on múltiples agents interactuen amb l’entorn i entre ells mateixos per maximitzar alguna noció de recompensa acumulada. Primer ampliem el treball existent en proposar un model que no sols resol conflictes, sinó que també mostra que és possible considerar diversos factors que afecten l’eficiència i l’impacte ambiental. Aquest enfocament és reforçat per l’ús de Graph Neural Networks (GNN), que faciliten la cooperació i la comunicació. Mostrem que a través de la cooperació és possible que els agents autònoms aprenguin estratègies de resolució que són semblants a les estratègies conegudes pels controladors humans. Aquests resultats no havien estat reportats a la literatura de GNN. Si bé aquests dos objectius poden semblar separats, en aquesta tesi argumentem que un sistema unificat de gestió de la complexitat del trànsit aeri amb aplicacions de la IA pot contribuir a avançar més en els sistemes autònoms al sector aeronàutic. Aquesta tesi conclou amb una visió de la IA a l’aviació que considera significatiu l’humà en el llaç de control i l’alineació de valors com a essència de les línies de recerca futura.

La Gestión del Tráfico Aéreo(ATM) se define formalmente como la gestión dinámica e integrada del tráfico y el espacio aéreo de forma segura, económica y eficiente, mediante la disposición de infraestructuras y servicios integrados en colaboración con todas las partes e involucrando funcionalidades en el lado aire y en el lado tierra. Se trata de un sistema socio-técnico complejo estructurado en varios niveles y subsistemas interrelacionados. El rendimiento en cada nivel se mide a través de varias áreas clave de rendimiento (KPA), de entre las cuales, algunas de las más importantes son la seguridad, la capacidad, la rentabilidad y el impacto ambiental. Aunque forman parte de la misma estructura ATM, cada una de los niveles tiene diferentes objetivos que en la práctica compiten entre sí, para maximizar sus propias metas. Se espera un escenario similar para los sistemas aéreos no tripulados(UAS), donde el desarrollo de diferentes sistemas de gestión de tráfico de UAS obedecen a un enfoque similar al de ATM. En esta tesis, concebimos la complejidad del tráfico aéreo como el marco de referencia para tener una comprensión única y compartida entre los actores que toman decisiones en los diferentes niveles del sistema ATM. Por otro lado, también hemos trabajado en la Detección y Resolución de Conflictos(CD&R) automatizada para investigar cómo el Aprendizaje por Refuerzo de Múltiples Agentes(MARL) puede facilitar avanzar hacia los sistemas autónomos de gestión de tráfico ATM y UAS. Para abordar ambos objetivos, primero definimos la complejidad del tráfico aéreo de tal manera que proporcione eficientemente una información elaborada a los diferentes actores interesados.Como primer paso, proporcionamos una definición genérica de las interdependencias entre pares de aeronaves, que se basa en la distancia en tiempos discretizados y se adapta al caso de uso y al contexto. Hemos utilizado la teoría de grafos para modelar el tráfico aéreo como un gráfico dinámico y definimos cuatro indicadores de complejidad que combinan diferente información topológica y la severidad de las interdependencias para dar una evolución detallada y peculiar de la complejidad del tráfico en un espacio aéreo determinado. Estos indicadores se han ampliado para introducir el concepto de complejidad de aeronave, a través del cual se identifican áreas espacio-temporales complejas en un espacio aéreo determinado.Además, se ha investigado la efectividad de estos indicadores de complejidad en el dominio de los UAS, para mostrar cómo la misma definición de complejidad del tráfico aéreo se puede utilizar en diferentes dominios. Centrándonos en el CD&R, abordamos este problema a través de MARL, que es un paradigma de Aprendizaje Automático(ML) donde múltiples agentes interactúan con el entorno y entre ellos mismos para maximizar alguna noción de recompensa acumulada. Primero ampliamos el trabajo existente al proponer un modelo que no solo resuelve conflictos sino que también muestra que es posible considerar diversos factores que afectan la eficiencia y el impacto ambiental. Este enfoque se ve reforzado por el uso de Graph Neural Networks(GNN), que facilitan la cooperación y la comunicación. Mostramos que a través de la cooperación es posible que los agentes autónomos aprendan estrategias de resolución que son similares a las estrategias conocidas por los controladores humanos. Dichos resultados no habían sido reportados en la literatura de GNN. Si bien estos dos objetivos pueden parecer separados, en esta tesis argumentamos que un sistema unificado de gestión de la complejidad del tráfico aéreo con aplicaciones de la IA puede contribuir a avanzar mas en los sistemas autónomos en el sector aeronáutico. Esta tesis concluye con una visión de la IA en la aviación que considera significativo el humano en el lazo de control y la alineación de valores como esencia de las líneas de investigación futura.

Air Traffic Management (ATM) is formally defined as the dynamic, integrated management of air traffic and airspace safely, economically and efficiently, through the provision of facilities and seamless services in collaboration with all parties and involving airborne and ground-based functions. This implies a complex socio-technical system with several layers and sub-systems. The performance of these layers is measured through various Key Performance Areas (KPAs), of which some of the most important are safety, capacity, cost-efficiency and the environmental impact. Although part of ATM structure, each of the layers have different objectives which in practice compete to maximize their own goals. A similar situation can be expected for Unmanned Aerial Systems (UAS), where the development of different UAS traffic management systems is being guided with a similar approach to that of ATM. In this thesis, we envision air traffic complexity to be the framework through which a common understanding among stakeholders making decisions at the different ATM layers is enhanced. Furthermore, we focus on automated Conflict Detection and Resolution (CD&R) to investigate how Multi-Agent Reinforcement Learning (MARL) can facilitate the progress to autonomous ATM and UAS traffic management systems. To achieve these goals, we first define air traffic complexity in such a way that provides elaborate information efficiently to different stakeholders. As an initial step, we provide a generic definition of pairwise interdependencies between aircraft, which is based on the distance at a time step and is adaptive to the use-case and context. We use graph theory to model air traffic as a dynamic graph and define four complexity indicators that combine different topological information and the severity of the interdependencies to give a detailed and nuanced evolution of traffic complexity in a certain airspace. These indicators are extended to introduce the concept of single aircraft complexity, through which complex spatio-temporal areas in a given airspace are identified. Moreover, we investigate the effectiveness of these complexity indicators in the domain of UAS, to show how the same definition of air traffic complexity can be used in different domains. Focusing on CD&R, we approach this problem through MARL, which is a paradigm of Machine Learning (ML) where multiple agents interact with an environment and themselves to maximize some notion of accumulated reward. We first extend existing work by proposing a model that not only solves conflicts but also show that it is possible to consider several other factors that affect efficiency and the environmental impact. This approach is further enhanced by the use of Graph Neural Networks (GNNs), which facilitate cooperation and communication. We show that through cooperation it is possible for autonomous agents to learn resolution strategies that are similar to known strategies by human controllers, which existing work using GNNs has not been able to achieve. While these two goals might seem separate, in this thesis we argue that a unified air traffic complexity management system with the application of AI can move aviation further to its quest for autonomy. This thesis is concluded with a vision for AI in aviation that considers meaningful human control and value alignment as the most imperative directions for future research.