Autor: FUERTES COIRAS, Daniel

Título: Multi-agent Route Planning using Deep Reinforcement Learning Techniques and Transformer Networks for Graph Analysis

Fecha: 2025

Materia: ---

Escuela: E.T.S. DE INGENIEROS DE TELECOMUNICACION

Departamento: SEÑALES, SISTEMAS Y RADIOCOMUNICACIONES

Acceso electrónico: https://oa.upm.es/91225/

Director/a(s):

• Director/a: BLANCO ADÁN, Carlos Roberto del

Resumen: Autonomous navigation has become an important challenge in our days, with applications such as package delivery, transportation, search-and-rescue, etc. In these scenarios, autonomous vehicles are tasked with visiting designated locations to perform specific actions. Historically, these vehicles have relied on human operators to navigate complex environments and complete mission objectives. However, having the necessary skills to control them in complex environments is complicated, especially in multi-agent systems where collaboration and simultaneous operations are essential. This complexity highlights the need for advanced navigation systems that can efficiently coordinate and ensure cooperation among fleets of vehicles. To address these challenges, researchers have traditionally modeled the problem as different vehicle routing problems, focusing on determining the most efficient routes for one or more vehicles. This work introduces FCM-Transformer, a novel system designed to coordinate multiple agents cooperatively. FCM-Transformer employs a two-step approach: first, it groups and assigns regions to individual agents in an initial planning phase, and second, it predicts efficient routes for each agent in the route solving phase. At the heart of this model is a Transformer-based neural network, trained with deep reinforcement learning, that analyzes the environment and predicts high-quality routes. FCM-Transformer introduces a novel region-sharing strategy that encourages cooperation among agents and helps overcome the suboptimality of the initial clustering. After this, NaviFormer neural network is presented as an evolution of FCM-Transformer. Contrary to FCM-Transformer, NaviFormer considers trajectory generation and obstacle avoidance to solve the common subproblems of route planning (waypoint sequencing) and path planning (trajectory prediction) as a unique and holistic navigation planning problem. This integrated approach enables NaviFormer to predict not only the best sequence of regions to visit, but also the precise, collision-free trajectories that connect them. By eliminating the need for separate solvers, NaviFormer offers a more direct and efficient solution to the navigation problem. The final model introduced in this work is TOP-Former, which offers a straight solution to the well-known Team Orienteering Problem for multiple agents. Unlike FCM-Transformer, which divides the environment into clusters, TOP-Former considers the state of all agents simultaneously, ensuring robust coordination and collaboration. By analyzing the global context of all agents, TOP-Former can predict high-quality routes that enable agents to collaborate effectively and achieve near-optimal performance. This direct approach ensures that the model can handle complex multi-agent scenarios more efficiently than previous methods. A series of experiments were conducted to evaluate the performance of the proposed models, including variations in scenario conditions, ablation studies, and comparative analyzes with other state-of-the-art algorithms. The findings demonstrate the competitive performance of the models presented, showcasing their ability to achieve an excellent balance between solution quality and computational efficiency. The results reflect the robustness of the models under various conditions, highlighting their suitability for practical applications. However, certain open issues, common across the state of the art, remain unresolved, such as scalability problems. This is related to an increase of the complexity of the problem due to greater number of nodes, obstacles, or agents, which is often manifested as a degradation in the quality and the computational cost of the solutions. Although some efforts have been made to address these limitations, the scalability problem still remains a critical barrier to achieve near-optimal performance in large-scale complex problems. RESUMEN La navegación autónoma es un desafío moderno importante, con aplicaciones como entrega de paquetes, transporte, búsqueda y rescate, etc. En estos escenarios, los vehículos autónomos deben visitar regiones en las que realizar ciertas acciones. Históricamente, estos vehículos han dependido de operadores humanos para navegar y cumplir con las misiones. Sin embargo, tener las habilidades necesarias para controlarlos en entornos complejos es complicado, especialmente en sistemas multiagente donde la colaboración simultánea es esencial. Esta complejidad resalta la necesidad de sistemas de navegación capaces de garantizar la cooperación entre vehículos. Para abordar este reto, los investigadores han modelado tradicionalmente el desafío como diversos problemas de enrutamiento de vehículos, centrados en determinar las rutas más eficientes para uno o más vehículos. Este trabajo presenta FCM-Transformer, un sistema novedoso para coordinar múltiples agentes. FCM-Transformer funciona en dos etapas: primero, agrupa regiones y las asigna los a agentes en la fase de planificación inicial y, después, genera rutas eficientes para cada agente en la fase de predicción de rutas. El núcleo de este modelo se basada en una red Transformer, entrenada con aprendizaje por refuerzo profundo, que analiza el entorno y predice rutas de alta calidad. FCM-Transformer introduce una novedosa estrategia de compartición de regiones que fomenta la cooperación entre agentes y ayuda a subsanar los rasgos subóptimos de la planificación inicial. A continuación, se presenta la red NaviFormer como una evolución de FCM-Transformer. A diferencia de FCM-Transformer, NaviFormer genera trayectorias y evita posibles obstáculos para resolver los problemas de planificación de rutas (secuenciación de regiones) y planificación de caminos (predicción de trayectorias) como un problema de navegación único y holístico. Este enfoque permite a NaviFormer predecir no solo la mejor secuencia de regiones a visitar, sino también las trayectorias libres de colisiones que las conectan. Al eliminar la necesidad de emplear soluciones separadas, NaviFormer ofrece un enfoque más directo y eficiente al problema de navegación. El modelo final presentado es TOP-Former, que ofrece una solución directa al conocido Team Orienteering Problem (Problema de Orientación en Equipo) para múltiples agentes. A diferencia de FCM-Transformer, que divide el entorno en clústeres, TOP-Former considera el estado de todos los agentes simultáneamente, asegurando una coordinación robusta. Al analizar el contexto global de todos los agentes, TOP-Former predice rutas de alta calidad que permiten a los agentes colaborar y lograr un rendimiento cercano al óptimo. Este enfoque directo asegura que el modelo pueda manejar escenarios complejos multiagente de manera más eficiente que los métodos anteriores. Se realizaron una serie de experimentos para evaluar el rendimiento de los modelos propuestos, incluyendo variaciones en las condiciones de entorno, estudios de ablación y análisis comparativos con otros algoritmos del estado del arte. Los hallazgos demuestran un rendimiento competitivo de los modelos presentados, destacando su capacidad para lograr un excelente equilibrio entre calidad de solución y eficiencia computacional. Los resultados reflejan la robustez de los modelos en diversas condiciones, lo que resalta su idoneidad para aplicaciones prácticas. Sin embargo, ciertos problemas, comunes en el estado del arte, permanecen sin resolver, como la escalabilidad. Esta está relacionada con el aumento de la complejidad de los escenarios (ya sea por el incremento del número de nodos, obstáculos o agentes) y suele manifestarse como una degradación en la calidad de las soluciones y el tiempo de computación. Aunque se han realizado esfuerzos para abordar estas limitaciones, el problema de escalabilidad sigue siendo una barrera para lograr un rendimiento casi óptimo en problemas complejos y de gran escala.