Technische Samenvatting: FALCON voor Niet-Convexe Gedeeltelijk Ontkoppelde Generalized Nash Equilibrium Problemen

Probleemformulering

Het artikel behandelt de uitdaging van het oplossen van multi-agent optimal besturingsproblemen in de luchtvaart en robotica, specifiek door deze te modelleren als niet-convexe differentiële spelen. De auteurs richten zich op een specifieke subklasse van Generalized Nash Equilibrium Problems (GNEP's) genaamd Partially-Decoupled Generalized Nash Equilibrium Problems (PDGNEP's).

In deze formulering streven $N$ agenten ernaar om individuele kostenfuncties $J_i$ te minimaliseren onder de volgende voorwaarden:

1. Scheidbare Dynamica: Elke agent $i$ evolueert volgens zijn eigen dynamica $\dot{x}_i(t) = f(x_i(t), u_i(t))$, onafhankelijk van de controles of toestanden van andere agenten.
2. Gekoppelde Constraints: Agenten zijn gekoppeld via gedeelde gelijkheids- en ongelijkheidsconstraints $C(X, \Upsilon) \leq 0$, die afhankelijk kunnen zijn van de trajecten van alle agenten.
3. Doelstelling: Het vinden van een Open-Loop Nash Equilibrium, gedefinieerd als een verzameling strategieën waarbij geen enkele agent eenzijdig zijn kosten kan verbeteren door af te wijken van de strategieën van anderen.

Bestaande methoden kampen met beperkingen: Iterative LQ Games (iLQGames) missen natuurlijke ondersteuning voor constraints; Augmented Lagrangian Games (ALGAMES) vertonen verbeterde prestaties maar hebben moeite met sterke niet-convexiteiten; en Differential Games Sequential Quadratic Programming (DG-SQP) biedt convergentiegaranties, maar lijdt vaak aan hoge computationele kosten en numerieke instabiliteit in sterk niet-convexe scenario's.

Methodologie: Het FALCON-algoritme

De auteurs stellen FALCON voor (Fast Augmented Lagrangian Convexification for Open-loop Nash equilibria), een algoritme dat Sequential Convex Programming (SCP) combineert met een Augmented Lagrangian framework. De kernmethodologie verloopt als volt volgt:

1. Continu-tijd Constraint Handhaving

Om het probleem van inter-sample constraint schendingen aan te pakken, die gebruikelijk zijn bij gediscretiseerde SCP-solvers, herformuleren de auteurs de constraints met behulp van een exterior-penalty benadering.

• Een continu-tijd maatstaf voor de constraint schending, $\Lambda_i(t)$, wordt gedefinieerd met behulp van een cubische penalty functie $q(z) = [z]_+^3$ (gekozen vanwege $C^2$ gladheid).
• Een uitgebreide toestandsvariabele $y_i(t)$ accumuleert deze schending over de tijd.
• Constraints worden niet alleen afgedwongen op discretisatiepunten, maar door de gehele continue horizon door de accumulatie van $y_i$ tussen de punten te begrenzen, waardoor puntgewijze constraint voldoening binnen een theoretische grens $\delta(\varepsilon)$ wordt gegarandeerd.

2. Augmented Lagrangian en Epigraph Herformulering

Om niet-convexe doelstellingen en constraints aan te pakken:

• Epigraph Vorm: De niet-convexe kostenfunctie $J_i$ wordt verschoven naar de constraints via een epigraph variabele $\tau_i$, waarbij $\tau_i$ wordt geminimaliseerd onder de voorwaarde $J_i \leq \tau_i$. Dit maakt het mogelijk de doelstelling te lineariseren terwijl de niet-convexiteit in de constraints blijft.
• Augmented Lagrangian: Een augmented lagrangiaan functie $L_i$ wordt geconstrueerd, die Lagrange vermenigvuldigers ($\lambda, \mu$) en penalty gewichten ($\omega$) bevat voor zowel de dynamica als de koppelingsconstraints.

3. Sequential Convexification (SCvx*)

Het niet-convexe spel wordt iteratief benaderd door een reeks convexe sub-problemen op te lossen:

• Linearisatie: Dynamica en constraints worden gelineariseerd rond een referentietraject $\bar{z}$.
• Relaxatie: Virtuele controle ($\xi$) en virtuele buffer ($\zeta$) variabelen worden geïntroduceerd om kunstmatige onhaalbaarheid veroorzaakt door linearisatie te mitigeren.
• Trust Region: Een trust region constraint $\|z - \bar{z}\|_\infty \leq r$ zorgt ervoor dat de benadering geldig blijft.
• Potential Game Herformulering: Het resulterende convexe sub-probleem wordt gestructureerd als een Variational Generalized Nash Equilibrium (v-GNE). Door een sterk convexe potentiaal functie $\Phi_k$ (som van individuele gepenaliseerde doelstellingen) te construeren, kan het sub-probleem efficiënt worden opgelost als een Second-Order Cone Program (SOCP).

4. Algoritmische Loop

Het algoritme iterereert door:

1. Successieve Linearisatie: Het creëren van het convexe sub-probleem.
2. Stap Acceptatie: Het evalueren van de "kwaliteit" van de stap met behulp van een gezamenlijke potentiaal ratio $\rho_k$ (vergelijking van werkelijke kostenreductie versus voorspelde reductie). Stappen worden geaccepteerd als $\rho_k$ een drempelwaarde overschrijdt.
3. Multiplier Updates: Lagrange vermenigvuldigers en penalty gewichten worden bijgewerkt op basis van constraint schendingen en een gebruikersgedefinieerde tolerantie $\delta_k$.
4. Trust Region Aanpassing: De trust region straal $r$ wordt dynamisch aangepast (gecontracteerd of geëxpandeerd) op basis van de acceptatieratio.

Belangrijkste Bijdragen

1. Algoritme Ontwikkeling: Introductie van FALCON, een nieuw algoritme dat niet-convexe PDGNEP's oplost door sequential convexification te combineren met augmented Lagrangian technieken.
2. Theoretische Garanties: Bewijs van globale convergentie naar een open-loop Nash equilibrium onder milde aannames (begrensde versnelling, Lipschitz continuïteit, $C^2$ gladheid). De oplossing is gegarandeerd dynamisch haalbaar en benaderend koppelings-haalbaar in een continu-tijd zin.
3. Continu-tijd Veiligheid: Een rigoureuze formulering voor het afdwingen van constraints continu tussen discretisatiepunten, wat veiligheidschendingen in inter-sample intervallen voorkomt.
4. Efficiëntie: Demonstratie dat het geconvexifieerde sub-probleem kan worden opgelost als een potential game met behulp van efficiënte SOCP-solvers, waardoor de computationele bottlenecks van eerdere DG-SQP methoden worden vermeden.

Numerieke Resultaten

De auteurs valideren FALCON op drie verschillende niet-convexe differentiële spelscenario's:

1. F1 Austin Racing (2 Spelers):

   • Scenario: Twee auto's die racen op een scherpe bocht van het F1 Austin circuit.
   • Prestaties: FALCON bereikte een convergentiepercentage van 100% over diverse initiële condities, terwijl DG-SQP slechts 72% van de tijd convergeerde.
   • Snelheid: FALCON was aanzienlijk sneller, met een gemiddelde rekentijd van 0,873 seconden vergeleken met de 50,021 seconden van DG-SQP. ALGAMES slaagde er niet in om onder deze standaarden op deze moeilijke casus te convergeren.

2. Narrowing Hallways (3 Spelers):

   • Scenario: Drie unicycle agenten die door een gang navigeren met twee choke-points, terwijl ze botsingsvermijding en communicatiebereik-constraints handhaven.
   • Observatie: Het algoritme handelde de niet-convexe omgeving succesvol af, waarbij emergent coöperatief gedrag werd getoond (bijv. agenten die elkaar opeenvolgend door de choke-points laten passeren) terwijl strikt aan de continu-tijd constraints werd voldaan.

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

   • Scenario: Een heterogeen spel in $R^6$ (Clohessy-Wiltshire-Hill dynamica) bestaande uit een "Lady" (hoogwaardig bezit), een "Bandit" (aanvaller) en een "Guard" (verdediger).
   • Observatie: FALCON loste het complexe pursuit-evasion-defense spel op, waarbij het succesvol scenario's simuleerde waarin de guard de bandit blokkeerde om de lady te laten ontsnappen, waarbij de niet-convexiteiten van de engagement geometrie werden afgehandeld.

Betekenis en Claims

Het artikel claimt dat FALCON een significante vooruitgang vertegenwoordigt in het oplossen van multi-agent differentiële spelen door de kloof te overbruggen tussen computationele efficiëntie en theoretische convergentiegaranties.

• Differentiatie: In tegen tegenstelling tot iLQGames handelt FALCON inherent staat- en controle-constraints af. In tegenstelling tot DG-SQP biedt het superieure numerieke prestaties en robuustheid in sterk niet-convexe settings zonder de convergentiegaranties op te offeren.
• Veiligheid: De continu-tijd constraint formulering wordt benadrukt als een cruciaal kenmerk voor veiligheidskritische aerospace toepassingen waar inter-sample schendingen onacceptabel zijn.
• Schaalbaarheid: Door de inner loop te reduceren tot een potential game die via SOCP kan worden opgelost, biedt de methode een schaalbare aanpak voor complexe multi-agent systemen.

De auteurs concluderen dat FALCON een robuust, snel en theoretisch gefundeerd framework biedt voor het oplossen van niet-convexe differentiële spelen, wat het geschikt maakt voor complexe aerospace operaties zoals pursuit-evasion, betwiste ruimteoperaties en coöperatieve guidance.