Multiplayer Reach-Avoid Differential Games with Defender-Side Information Delay

Technische Samenvatting: Multiplayer Reach-Avoid Differentieel Spel met Informatievertraging aan de Verdedigerszijde

Probleemformulering
Dit artikel onderzoekt een klasse van reach-avoid differentiele spelen waarbij meerdere verdedigers en meerdere aanvallers betrokken zijn die bewegen in een tweedimensionaal vlak met begrensde snelheden. De kernuitdaging die wordt aangepakt, is de aanwezigheid van informatievertraging aan de verdedigerszijde. In deze setting, terwijl aanvallers beschikken over realtime staat-informatie, observeert elke verdediger $D_i$ de toestanden van andere agenten (zowel andere verdedigers als aanvallers) met een constante tijdsvertraging $\tau_i$. Bijgevolg baseren verdedigers hun controlebeslissingen op de verleden posities van aanvallers ($t-\tau_i$) in plaats van op hun huidige posities.

Het spel betreft $N$ verdedigers en $M$ aanvallers. Aanvallers beogen een convexe gesloten doelregio $T$ te bereiken, terwijl verdedigers proberen aanvallers te onderscheppen (binnen een straal $r_i$) voordat zij $T$ bereiken. Als een aanvaller wordt onderschept, streven de verdedigers ernaar om de afstand van het onderscheppingspunt tot $T$ te maximaliseren, terwijl de aanvaller ernaar streeft deze afstand te minimaliseren. Het spel eindigt wanneer alle aanvallers ofwel zijn onderschept ofwel de doelregio zijn binnengegaan. De auteurs gaan uit van specifieke begincondities om te garanderen dat het spel goed gedefinieerd is: verdedigers zijn aanvankelijk stationair tijdens het vertragingsinterval, aanvallers starten buiten de doelregio, verdedigers zijn sneller dan aanvallers ($\bar{v}_D > \bar{v}_A$), en de initiële afstanden zijn voldoende groot om onmiddellijke onderschepping vóór het einde van de vertragingsperiode te voorkomen.

Methodologie
De auteurs maken gebruik van een geometrische benadering gecombineerd met convexe analyse en speltheoretische evenwichtsbegrippen om het probleem op te lossen.

1. Analyse van Eén-Aanvaller-Eén-Verdediger:

   • Karakterisering van het Aanvalgebied: De auteurs leiden eerst een expliciete analytische karakterisering af van het "vertraagde aanvalgebied" ($R_{total}^A$). Dit gebied vertegenwoordigt de verzameling punten die een aanvaller gegarandeerd kan bereiken niet later dan de verdediger, rekening houdend met de reactievertraging van de verdediger.
   • Convexiteitbewijs: Met behulp van een specifieke krommingsanalyse van de grens, gedefinieerd door de afstandbeperkingen en vertragingsparameters, bewijzen de auteurs dat dit aanvalgebied een convexe verzameling is onder milde aannames.
   • Optimale Strategieën: Op basis van het convexe aanvalgebied formuleren de auteurs een convex optimalisatieprobleem om het onderscheppingspunt te vinden (het punt in het aanvalgebied dat het dichtst bij de doelregio ligt). De optimale strategieën voor beide spelers worden afgeleid als het bewegen met maximale snelheid in een rechte lijn naar dit onderscheppingspunt.
   • Evenwichtsverificatie: Het artikel stelt vast dat deze strategieën een subgame-perfect Nash-evenwicht (SPNE) vormen. Dit wordt bewezen door het spel te verdelen in twee stadia (vóór en na het betreden van het spel door de verdediger) en door middel van backward induction aan te tonen dat de strategieën in elke fase optimaal zijn.

2. Extensie naar Multiplayer Scenario's:

   • Eén-Aanvaller-Meerdere-Verdedigers: Het aanvalgebied wordt gedefinieerd als de intersectie van de individuele aanvalsgebieden tussen de aanvaller en elke verdediger. Het onderscheppingspunt wordt bepaald door een convex optimalisatieprobleem op te lossen onder beperkingen van alle verdedigers. De auteurs merken op dat, in overeenstemming met eerder werk, maximaal twee verdedigers voldoende zijn om het onderscheppingspunt te bepalen onder optimaal spel.
   • Meerdere-Aanvallers-Meerdere-Verdedigers: Het probleem wordt uitgebreid naar een algemene $N$-tegen-$M$ setting. De auteurs integreren "vertragingsbewuste paarwijze winrelaties" (bepalen of een specifieke verdediger een specifieke aanvaller kan garanderen te onderscheppen) in een maximum matching-formulering. Dit maakt de optimale toewijzing van verdedigers aan aanvallers mogelijk om het aantal onderscheppingen te maximaliseren.

Belangrijkste Bijdragen
Het artikel levert de volgende specifieke bijdragen:

1. Wiskundige Formulering: Het stelt een rigoureuze formulering voor van reach-avoid spelen waarbij verdedigers opereren met vertraagde informatie over de posities van aanvallers.
2. Analytische Karakterisering: Voor de één-op-één casus leidt het een expliciete analytische representatie van het vertraagde aanvalgebied af en bewijst het de convexiteit ervan, een niet-triviaal resultaat gezien de tijdvertraging-dynamiek.
3. Optimale Strategieën en Evenwicht: Het leidt optimale strategieën af voor beide spelers en bewijst dat deze een subgame-perfect Nash-evenwicht vormen, waarbij rekening wordt gehouden met het sequentiële karakter van het spel veroorzaakt door de vertraging.
4. Schaalbaarheid: Het framework wordt uitgebreid naar één-aanvaller-meerdere-verdedigers en algemene multi-agent scenario's, waarbij strategieën worden geboden voor de berekening van het onderscheppingspunt en de toewijzing van verdediger aan aanvaller via maximum matching.

Resultaten
Numerieke simulaties zijn uitgevoerd met MATLAB om de theoretische bevindingen te valideren over drie scenario's:

• Eén-tegen-Eén: Simulaties bevestigden dat de voorgestelde optimale strategieën zowel pure-attack als pure-defense benchmark-policies overtreffen. Specifiek resulteerden unilaterale afwijkingen door een van beide spelers in slechtere uitkomsten voor de afwijkende speler, wat het evenwichtskarakter van de strategieën valideert.
• Eén-tegen-Meerdere: Simulaties met één aanvaller en twee verdedigers toonden aan dat coöperatieve strategieën onder verdedigers een betere prestatie kunnen leveren (het minimaliseren van de afstand van de aanvaller tot het doel) vergeleken met een enkele verdediger die alleen handelt.
• Multi-Agent: Een scenario met drie aanvallers en drie verdedigers illustreerde de effectiviteit van de maximum matching-benadering. De simulatie toonde aan dat verdedigers zichzelf succesvol toewijzen aan aanvallers die zij konden garanderen te onderscheppen, terwijl de niet-toegewezen aanvaller succesvol de doelregio bereikte.

Betekenis en Claims
Het artikel claimt de eerste te zijn die optimale strategieën biedt voor reach-avoid spelen specifal onder de conditie van informatievertraging aan de verdedigerszijde. Hoewel eerdere werken vertragingen bij aanvallers of standaard reach-avoid spelen hebben behandeld, vult dit werk een gat in de literatuur over hoe verdedigers optimaal kunnen reageren op de prestatieverslechtering wanneer hun informatie inherent vertraagd is.

De auteurs benadrukken dat hun benadering verder gaat dan de moeilijkheid van het direct oplossen van de hoog-dimensionale Hamilton-Jacobi-Isaacs (HJI) vergelijking. In plaats daarvan, door gebruik te maken van de geometrische structuur van het vertraagde aanvalgebied en de convexiteit ervan, bieden zij een hanteerbaar, verificatie-gebaseerd analytisch framework. Dit maakt de efficiënte berekening van winvoorwaarden en evenwichtsstrategieën mogelijk in scenario's die anders analytisch onhandelbaar zouden zijn. Het werk wordt gepositioneerd als een stap richting een realistischerere modellering van adversariële systemen (zoals militaire of lucht- en ruimtevaarttoepassingen) waarbij communicatie- en verwerkingslatenties onvermijdelijk zijn.