Riepilogo Tecnico: FALCON per Problemi di Equilibrio di Nash Generalizzato Non Convesso Parzialmente Disaccoppiati

Formulazione del Problema

Il documento affronta la sfida di risolvere problemi di controllo ottimo multi-agente in ambito aerospaziale e robotico, modellandoli come giochi differenziali non convessi. Gli autori si concentrano su una sottoclasse specifica di Problemi di Equilibrio di Nash Generalizzato (GNEP) denominata Problemi di Equilibrio di Nash Generalizzato Parzialmente Disaccoppiati (PDGNEP).

In questa formulazione, $N$ agenti cercano di minimizzare le singole funzioni di costo $J_i$ soggetti a:

1. Dinamiche Separabili: Ogni agente $i$ evolve secondo la propria dinamica $\dot{x}_i(t) = f(x_i(t), u_i(t))$, indipendente dai controlli o dagli stati degli altri agenti.
2. Vincoli Accoppiati: Gli agenti sono accoppiati attraverso vincoli di uguaglianza e disuguaglianza condivisi $C(X, \Upsilon) \leq 0$, che possono dipendere dalle traiettorie di tutti gli agenti.
3. Obiettivo: Trovare un Equilibrio di Nash in Open-Loop, definito come un insieme di strategie in cui nessun agente può migliorare unilateralmente il proprio costo deviando, date le strategie degli altri.

I metodi esistenti presentano limitazioni: gli Iterative LQ Games (iLQGames) mancano di una gestione nativa dei vincoli; gli Augmented Lagrangian Games (ALGAMES) mostrano prestazioni migliorate ma faticano con non-convessità marcate; e il Differential Games Sequential Quadratic Programming (DG-SQP) offre garanzie di convergenza ma spesso soffre di elevati costi computazionali e instabilità numerica in scenari altamente non convessi.

Metodologia: L'Algoritmo FALCON

Gli autori propongono FALCON (Fast Augmented Lagrangian Convexification for Open-loop Nash equilibria), un algoritmo che combina la Programmazione Convessa Sequenziale (SCP) con un framework Augmented Lagrangian. La metodologia centrale procede come segue:

1. Applicazione dei Vincoli nel Tempo Continuo

Per affrontare il problema delle violazioni dei vincoli tra i campioni, comune nei solver SCP discretizzati, gli autori riformulano i vincoli utilizzando un approccio a penalità esterna.

• Una misura del tempo continuo della violazione del vincolo, $\Lambda_i(t)$, è definita utilizzando una funzione di penalità cubica $q(z) = [z]_+^3$ (scelta per la sua regolarità $C^2$).
• Una variabile di stato aumentata $y_i(t)$ accumula questa violazione nel tempo.
• I vincoli sono imposti non solo ai nodi di discretizzazione, ma durante l'intero orizzonte continuo, limitando l'accumulo di $y_i$ tra i nodi, garantendo la soddisfazione puntuale del vincolo entro un limite teorico $\delta(\varepsilon)$.

2. Formulazione Augmented Lagrangian ed Epigrafica

Per gestire obiettivi e vincoli non convessi:

• Forma Epigrafica: La funzione di costo non convessa $J_i$ viene spostata nei vincoli tramite una variabile epigrafica $\tau_i$, minimizzando $\tau_i$ soggetto a $J_i \leq \tau_i$. Ciò consente di linearizzare l'obiettivo mantenendo la non-convessità nei vincoli.
• Augmented Lagrangian: Viene costruito una funzione Augmented Lagrangian $L_i$, che incorpora moltiplicatori di Lagrange ($\lambda, \mu$) e pesi di penalità ($\omega$) sia per la dinamica che per i vincoli di accoppiamento.

3. Convessificazione Sequenziale (SCvx*)

Il gioco non convesso viene approssimato iterativamente risolvendo una sequenza di sottoproblemi convessi:

• Linearizzazione: Dinamiche e vincoli vengono linearizzati attorno a una traiettoria di riferimento $\bar{z}$.
• Rilassamento: Vengono introdotte variabili di controllo virtuale ($\xi$) e di buffer virtuale ($\zeta$) per mitigare l'infeasibilità artificiale causata dalla linearizzazione.
• Regione di Fiducia (Trust Region): Un vincolo di regione di fiducia $\|z - \bar{z}\|_\infty \leq r$ assicura che l'approssimazione rimanga valida.
• Riformulazione come Gioco Potenziale: Il sottoproblema convesso risultante è strutturato come un Equilibrio di Nash Generalizzato Variazionale (v-GNE). Costruendo una funzione potenziale fortemente convessa $\Phi_k$ (somma delle singole funzioni di costo penalizzate), il sottoproblema viene risolto efficientemente come un Programma di Ottimizzazione Conica Secondaria (SOCP).

4. Ciclo Algoritmico

L'algoritmo itera attraverso:

1. Linearizzazione Successiva: Creazione del sottoproblema convesso.
2. Accettazione del Passo: Valutazione della "qualità" del passo utilizzando un rapporto di potenziale congiunto $\rho_k$ (confrontando la riduzione del costo reale rispetto alla riduzione prevista). I passi sono accettati se $\rho_k$ supera una soglia.
3. Aggiornamento dei Moltiplicatori: I moltiplicatori di Lagrange e i pesi di penalità vengono aggiornati in base alle violazioni dei vincoli e a una tolleranza $\delta_k$ definita dall'utente.
4. Regolazione della Regione di Fiducia: Il raggio della regione di fiducia $r$ viene regolato dinamicamente (contratto o espanso) in base al rapporto di accettazione.

Contributi Chiave

1. Sviluppo dell'Algoritmo: Introduzione di FALCON, un nuovo algoritmo che risolve i PDGNEP non convessi combinando la convessificazione sequenziale con tecniche di Augmented Lagrangian.
2. Garanzie Teoriche: Dimostrazione della convergenza globale verso un equilibrio di Nash in open-loop sotto ipotesi moderate (accelerazione limitata, continuità Lipschitziana, regolarità $C^2$). La soluzione è garantita essere dinamicamente ammissibile e approssimativamente ammissibile per l'accoppiamento in senso di tempo continuo.
3. Sicurezza nel Tempo Continuo: Una formulazione rigorosa per l'applicazione dei vincoli continuamente tra i nodi di discretizzazione, prevenendo violazioni di sicurezza negli intervalli tra i campioni.
4. Efficienza: Dimostrazione che il sottoproblema convessificato può essere risolto come un gioco potenziale utilizzando efficienti solver SOCP, evitando i colli di bottiglia computazionali dei precedenti metodi DG-SQP.

Risultati Numerici

Gli autori validano FALCON su tre distinti scenari di gioco differenziale non convesso:

1. F1 Austin Racing (2 Giocatori):

   • Scenario: Due auto che corrono su una curva stretta del circuito F1 di Austin.
   • Prestazioni: FALCON ha raggiunto un tasso di convergenza del 100% in varie condizioni iniziali, mentre DG-SQP è convergente solo il 72% delle volte.
   • Velocità: FALCON è stato significativamente più veloce, con un tempo di calcolo medio di 0,873 secondi rispetto ai 50,021 secondi di DG-SQP. ALGAMES è fallito nel convergere su questo caso difficile sotto gli stessi standard.

2. Corridoi Stretti (3 Giocatori):

   • Scenario: Tre agenti unicycle che navigano in un corridoio con due punti di strozzatura, mantenendo l'evitamento delle collisioni e i vincoli di portata di comunicazione.
   • Osservazione: L'algoritmo ha gestito con successo l'ambiente non convesso, dimostrando comportamenti cooperativi emergenti (ad esempio, gli agenti che sequenziano il passaggio attraverso i punti di strozzatura) pur rispettando rigorosamente i vincoli di tempo continuo.

3. Spacecraft Lady-Bandit-Guard (3 Giocatori):

   • Scenario: Un gioco eterogeneo in $R^6$ (dinamiche di Clohessy-Wiltshire-Hill) che coinvolge una "Lady" (asset di alto valore), un "Bandit" (attaccante) e una "Guard" (difensore).
   • Osservazione: FALCON ha risolto il complesso gioco di inseguimento-evasione-difesa, simulando con successo scenari in cui la guardia blocca il bandit per permettere alla lady di fuggire, gestendo le non-convessità della geometria di ingaggio.

Significato e Rivendicazioni

Il documento afferma che FALCON rappresenta un avanzamento significativo nella risoluzione di giochi differenziali multi-agente colmando il divario tra efficienza computazionale e garanzie di convergenza teorica.

• Differenziazione: A differenza di iLQGames, FALCON gestisce nativamente i vincoli di stato e di controllo. A differenza di DG-SQP, offre prestazioni numeriche e robustezza superiori in scenari altamente non convessi senza sacrificare le garanzie di convergenza.
• Sicurezza: La formulazione dei vincoli nel tempo continuo è evidenziata come una caratteristica critica per le applicazioni aerospaziali critiche per la sicurezza, dove le violazioni tra i campioni sono inaccettabili.
• Scalabilità: Riducendo il ciclo interno a un gioco potenziale risolvibile tramite SOCP, il metodo offre un approccio scalabile per sistemi multi-agente complessi.

Gli autori concludono che FALCON fornisce un framework robusto, veloce e teoricamente fondato per risolvere giochi differenziali non convessi, rendendolo adatto a operazioni aerospaziali complesse come l'inseguimento-evasione, le operazioni spaziali contestate e la guida cooperativa.