Resumen Técnico: FALCON para Problemas de Equilibrio de Nash Generalizado No Convexos y Parcialmente Desacoplados

Formulación del Problema

El artículo aborda el desafío de resolver problemas de control óptimo multi-agente en el ámbito aeroespacial y robótico, modelándolos específicamente como juegos diferenciales no convexos. Los autores se centran en una subclase específica de Problemas de Equilibrio de Nash Generalizado (GNEP), denominada Problemas de Equilibrio de Nash Generalizado Parcialmente Desacoplados (PDGNEP).

En esta formulación, $N$ agentes buscan minimizar sus funciones de costo individuales $J_i$ sujetos a:

1. Dinámicas Separables: Cada agente $i$ evoluciona según su propia dinámica $\dot{x}_i(t) = f(x_i(t), u_i(t))$, de forma independiente a los controles o estados de otros agentes.
2. Restricciones Acopladas: Los agentes están acoplados mediante restricciones de igualdad e desigualdad compartidas $C(X, \Upsilon) \leq 0$, las cuales pueden depender de las trayectorias de todos los agentes.
3. Objetivo: Encontrar un Equilibrio de Nash de Lazo Abierto (Open-Loop), definido como un conjunto de estrategias donde ningún agente puede mejorar unilateralmente su costo desviándose, dadas las estrategias de los demás.

Los métodos existentes enfrentan limitaciones: los Juegos de iLQ (iLQGames) carecen de un manejo nativo de restricciones; los Juegos de Lagrangiano Aumentado (ALGAMES) muestran un rendimiento mejorado pero tienen dificultades ante no convexidades estrictas; y el Programación Cuadrática Secuencial para Juegos Diferenciales (DG-SQP) ofrece garantías de convergencia, pero a menudo sufre de altos costos computacionales e inestabilidad numérica en escenarios altamente no convexos.

Metodología: El Algoritmo FALCON

Los autores proponen FALCON (Fast Augmented Lagrangian Convexification for Open-loop Nash equilibria), un algoritmo que combina la Programación Convexa Secuencial (SCP) con un marco de Lagrangiano Aumentado. La metodología central procede de la siguiente manera:

1. Cumplimiento de Restricciones en Tiempo Continuo

Para abordar el problema de las violaciones de restricciones entre muestras, común en los resolvedores de SCP discretizados, los autores reformulan las restricciones utilizando un enfoque de penalización exterior.

• Se define una medida de violación de restricción en tiempo continuo, $\Lambda_i(t)$, utilizando una función de penalización cúbica $q(z) = [z]_+^3$ (elegida por su suavidad $C^2$).
• Una variable de estado aumentada $y_i(t)$ acumula esta violación a lo largo del tiempo.
• Las restricciones se cumplen no solo en los nodos de discretización, sino a lo largo de todo el horizonte continuo mediante el acotamiento de la acumulación de $y_i$ entre nodos, asegurando el cumplimiento puntual de la restricción dentro de un límite teórico $\delta(\varepsilon)$.

2. Lagrangiano Aumentado y Reformulación de Epígrafo

Para manejar objetivos y restricciones no convexos:

• Forma de Epígrafo: La función de costo no convexa $J_i$ se desplaza hacia las restricciones mediante una variable de epígrafo $\tau_i$, minimizando $\tau_i$ sujeto a $J_i \leq \tau_i$. Esto permite linealizar el objetivo manteniendo la no convexidad en las restricciones.
• Lagrangiano Aumentado: Se construye una función de Lagrangiano aumentado $L_i$, que incorpora multiplicadores de Lagrange ($\lambda, \mu$) y pesos de penalización ($\omega$) tanto para la dinámica como para las restricciones de acoplamiento.

3. Convexificación Secuencial (SCvx*)

El juego no convexo se aproxima iterativamente mediante la resolución de una secuencia de subproblemas convexos:

• Linealización: Las dinámicas y restricciones se linealizan alrededor de una trayectoria de referencia $\bar{z}$.
• Relajación: Se introducen variables de control virtual ($\xi$) y de búfer virtual ($\zeta$) para mitar la inviabilidad artificial causada por la linealización.
• Región de Confianza: Una restricción de región de confianza $\|z - \bar{z}\|_\infty \leq r$ asegura que la aproximación siga siendo válida.
• Reformulación de Juego de Potencial: El subproblema convexo resultante se estructura como un Equilibrio de Nash Generalizado Variacional (v-GNE). Mediante la construcción de una función de potencial fuertemente convexa $\Phi_k$ (suma de los objetivos penalizados individuales), el subproblema se resuelve eficientemente como un Programa de Cono de Segundo Orden (SOCP).

4. Bucle Algorítmico

El algoritmo itera a través de:

1. Linealización Sucesiva: Creación del subproblema convexo.
2. Aceptación de Paso: Evaluación de la "calidad" del paso utilizando una razón de potencial conjunta $\rho_k$ (comparando la reducción de costo real frente a la reducción predicha). Los pasos se aceptan si $\rho_k$ supera un umbral.
3. Actualización de Multiplicadores: Los multiplicadores de Lagrange y los pesos de penalización se actualizan basándose en las violaciones de restricciones y una tolerancia definida por el usuario $\delta_k$.
4. Ajuste de la Región de Confianza: El radio de la región de confianza $r$ se ajusta dinámicamente (se contrae o expande) basándose en la razón de aceptación.

Contribuciones Clave

1. Desarrollo de Algoritmo: Introducción de FALCON, un nuevo algoritmo que resuelve PDGNEPs no convexos combinando la convexificación secuencial con técnicas de Lagrangiano aumentado.
2. Garantías Teóricas: Demostración de la convergencia global hacia un equilibrio de Nash de lazo abierto bajo supuestos moderados (aceleración acotada, continuidad Lipschitz, suavidad $C^2$). Se garantiza que la solución sea dinámicamente factible y aproximadamente factible de acoplamiento en un sentido de tiempo continuo.
3. Seguridad en Tiempo Continuo: Una formulación rigurosa para imponer restricciones continuamente entre los nodos de discretización, evitando violaciones de seguridad en los intervalos entre muestras.
4. Eficiencia: Demostración de que el subproblema convexo puede resolverse como un juego de potencial utilizando resolvedores SOCP eficientes, evitando los cuellos de botella computacionales de los métodos DG-SQP anteriores.

Resultados Numéricos

Los autores validan FALCON en tres escenarios distintos de juegos diferenciales no convexos:

1. F1 Austin Racing (2 Jugadores):

   • Escenario: Dos autos compitiendo en una curva cerrada de la pista de F1 en Austin.
   • Desempeño: FALCON logró una tasa de convergencia del 100% en diversas condiciones iniciales, mientras que DG-SQP convergió solo el 72% de las veces.
   • Velocidad: FALCON fue significativamente más rápido, con un tiempo de computación promedio de 0.873 segundos frente a los 50.021 segundos de DG-SQP. ALGAMES falló en converger en este caso difícil bajo los mismos estándares.

2. Pasillos Estrechos (3 Jugadores):

   • Escenario: Tres agentes tipo unicycle navegando por un pasillo con dos puntos de estrangulamiento mientras mantienen la evitación de colisiones y las restricciones de rango de comunicación.
   • Observación: El algoritmo manejó con éxito el entorno no convexo, demostrando comportamientos cooperativos emergentes (por ejemplo, agentes secuenciando su paso por los puntos de estrangulamiento) mientras cumple estrictamente con las restricciones de tiempo continuo.

3. Espacial Lady-Bandit-Guard (3 Jugadores):

   • Escenario: Un juego heterogéneo en $R^6$ (dinámicas de Clohessy-Wiltshire-Hill) que involucra a una "Lady" (activo de alto valor), un "Bandit" (atacante) y un "Guard" (defensor).
   • Observación: FALCON resolvió el complejo juego de persecución-evasión-defensa, simulando con éxito escenarios donde el guard bloqueaba al bandit para permitir la huida de la lady, manejando las no convexidades de la geometría de enfrentamiento.

Significado y Reivindicaciones

El artículo afirma que FALCON representa un avance significativo en la resolución de juegos diferenciales multi-agente al cerrar la brecha entre la eficiencia computacional y las garantías de convergencia teórica.

• Diferenciación: A diferencia de iLQGames, FALCON maneja de forma nativa las restricciones de estado y control. A diferencia de DG-SQP, ofrece un rendimiento numérico y una robustez superiores en entornos altamente no convexos sin sacrificar las garantías de convergencia.
• Seguridad: La formulación de restricciones en tiempo continuo se destaca como una característica crítica para aplicaciones aeroespaciales donde las violaciones entre muestras son inaceptables.
• Escalabilidad: Al reducir el bucle interno a un juego de potencial resoluble mediante SOCP, el método ofrece un enfoque escalable para sistemas multi-agente complejos.

Los autores concluyen que FALCON proporciona un marco robusto, rápido y teóricamente fundamentado para resolver juegos diferenciales no convexos, lo que lo hace adecuado para operaciones aeroespaciales complejas como la persecución-evasión, operaciones espaciales en entornos disputados y guía cooperativa.