Reach-avoid games for players with damped double integrator dynamics

Titel: Bereik-ontwijk-spellen voor spelers met gedempte dubbel-integrator-dynamica

Auteurs: Mengxin Lyu, Ruiliang Deng, Zongying Shi, Yisheng Zhong (Tsinghua Universiteit)

1. Probleemstelling

Het artikel onderzoekt een reach-avoid-differentiëelspel (bereik-ontwijk-spel) tussen twee spelers: een aanvaller (A) en een verdediger (D).

• Dynamica: Beide spelers volgen een gedempte dubbel-integrator-dynamica. Dit is een realistischer model dan de gebruikelijke "simple motion" (constante snelheid) modellen, omdat het rekening houdt met traagheid en demping. De bewegingsvergelijkingen zijn:
  $$\dot{x}_i = v_i, \quad \dot{v}_i = -\mu v_i + u_i \begin{bmatrix} \cos \theta_i \\ \sin \theta_i \end{bmatrix}$$
  waarbij $u_i$ de grootte van de versnelling is (beperkt tot $[0, u_{im}]$), $\theta_i$ de richting, en $\mu > 0$ de dempingsfactor.
• Doelstellingen:
  • De aanvaller probeert een doelwit (gelegen in de oorsprong $[0,0]^T$) te bereiken zonder gevangen te worden.
  • De verdediger probeert de aanvaller te vangen op het punt dat zo ver mogelijk van het doelwit verwijderd is.
• Winning Scenarios: Het spel eindigt wanneer de aanvaller het doel bereikt (aanvaller wint) of wanneer de verdediger de aanvaller vangt (verdediger wint, waarbij de afstand tot het doel gemaximaliseerd wordt).
• Uitdaging: Bestaande methoden voor reach-avoid-spellen zijn vaak gebaseerd op simpele bewegingsmodellen of vereisen complexe numerieke oplossingen van de Hamilton-Jacobi-Isaacs (HJI) vergelijking. De aanwezigheid van demping ($\mu$) maakt de trajecten niet-lineair en niet-strak, wat de geometrische analyse aanzienlijk verandert.

2. Methodologie

De auteurs combineren de theorie van differentiële spellen met geometrische analyse om optimale strategieën af te leiden.

• Hamilton-Jacobi-Isaacs (HJI) Framework: Er wordt een Hamiltoniaan opgesteld om de co-toestanden (costates) en de optimale besturingsstrategieën ($u^*, \theta^*$) te bepalen. Het wordt aangetoond dat de optimale strategieën bestaan uit een constante versnellingsgrootte ($u_{im}$) en een constante richting ($\theta^*$), wat wordt gedefinieerd als een "Normal strategy".
• Isochrones en Meerdere Bereikbare Gebieden (MRR):
  • Een isochrone is de set punten die een speler op een bepaald tijdstip $t$ kan bereiken met een normale strategie.
  • Vanwege de gedempte dynamica zijn deze isochrones geen concentrische cirkels (zoals bij simpele beweging), maar vormen ze complexe vormen die zichzelf kunnen overlappen.
  • De auteurs introduceren het concept van het Multiple Reachable Region (MRR): een gebied waar een punt kan worden bereikt via meerdere verschillende normale strategieën (meestal 1, 2 of 3 manieren).
  • Er worden drie tijdstippen gedefinieerd om een punt te bereiken: $t_1 < t_2 < t_3$. Het tijdstip $t_2$ correspondeert met een lokaal maximum van de reistijd binnen het MRR, terwijl $t_1$ en $t_3$ lokale minima zijn.
• Dominantiegebieden van de Aanvaller:
  • Traditioneel is het dominante gebied het gebied waar de aanvaller sneller is dan de verdediger.
  • De auteurs definiëren een nieuwe typologie voor het dominante gebied van de aanvaller, bestaande uit drie delen:
    1. $R_I$: Gebied waar de aanvaller sneller is dan de verdediger en veilig kan bereiken.
    2. $R_{II}$: Gebied waar de verdediger de aanvaller kan vangen, zelfs als de aanvaller sneller is (vanwege de kromming van de trajecten door demping).
    3. $R_{III}$ (Nieuw): Een gebied binnen het bereikbare domein van de verdediger, waar de aanvaller toch veilig kan bereiken door zijn versnelling $u_A$ te verlagen. Door $u_A$ te verlagen, verandert de vorm van de isochrones zodanig dat de aanvaller het punt op een tijdstip kan bereiken dat tussen de tweede en derde reistijd van de verdediger ligt ($t_{D2} < t_{A} < t_{D3}$), waardoor hij de verdediger "ontsnapt" ondanks dat hij theoretisch langzamer is.

3. Belangrijkste Bijdragen

1. Analyse van Gedempte Dynamica: Het artikel is de eerste die reach-avoid-spellen analyseert met gedempte dubbel-integrator-dynamica, in plaats van simpele bewegingsmodellen.
2. Invoering van MRR: Het concept van het Multiple Reachable Region wordt geïntroduceerd, wat laat zien dat spelers meerdere optimale paden hebben naar hetzelfde punt, afhankelijk van de gekozen versnelling en richting.
3. Nieuw Dominantiegebied ($R_{III}$): De auteurs identificeren een derde type dominante gebied ($R_{III}$) dat alleen bestaat door de complexiteit van de gedempte dynamica. Hierin kan de aanvaller een punt bereiken dat normaal gesproken door de verdediger wordt gedomineerd, door bewust minder versnelling te gebruiken om de timing van de isochrones te manipuleren.
4. Optimale Strategieën en Voorwaarde: Er worden specifieke strategieën afgeleid voor verschillende gebieden:
   • ADR-strategie: Voor punten in $R_I \cup R_{II}$, waarbij beide spelers maximale versnelling gebruiken.
   • MRR-strategie: Voor punten in $R_{III}$, waarbij de aanvaller een specifieke, lagere versnelling $\hat{u}_A$ kiest om exact op hetzelfde moment als de verdediger (op een specifiek tijdstip $t_{D2}$) het punt te bereiken, maar dan buiten het bereik van de verdediger.
   • Er wordt bewezen dat deze strategieën voldoen aan de noodzakelijke voorwaarden voor optimaliteit (via de HJI-vergelijking en de Maximum Principle).

4. Resultaten en Simulaties

Numerieke simulaties worden uitgevoerd om de theorie te valideren:

• Scenario 1 (Optimaal in $R_I$): Wanneer het optimale eindpunt in het traditionele dominante gebied ligt, presteert de voorgestelde ADR-strategie (maximale versnelling, constante richting) optimaal. Afwijken hiervan (bijv. puur-vervolg strategie) leidt tot een slechtere uitkomst.
• Scenario 2 (Optimaal in $R_{III}$): Wanneer het optimale punt in het nieuwe gebied $R_{III}$ ligt, faalt de standaard ADR-strategie. De simulatie toont aan dat de aanvaller door zijn versnelling te verlagen (MRR-strategie) het doel kan bereiken, terwijl de verdediger, die de standaard strategie blijft gebruiken, faalt om de aanvaller te vangen of een slechtere uitkomst behaalt.
• Scenario 3 (Vangst): Een scenario waarbij de aanvaller probeert door een "gevaarlijk" gebied ($R_{II}$) te gaan zonder de juiste aanpassing, resulteert in de vangst van de aanvaller voordat hij het doel bereikt.

5. Betekenis en Conclusie

Dit onderzoek is significant omdat het de kloof tussen theoretische differentiaal-spellen en realistische dynamische modellen overbrugt.

• Theoretische Impact: Het toont aan dat bij complexe dynamica (zoals demping) de intuïtie van "sneller is altijd beter" niet altijd opgaat. Het vermogen om versnelling te variëren om de timing van isochrones te manipuleren, creëert nieuwe strategische mogelijkheden.
• Praktische Toepassing: De resultaten zijn relevant voor toepassingen zoals botsingsvermijding, actieve verdediging van drones en robotica, waar systemen vaak te maken hebben met traagheid en demping.
• Toekomstig Werk: De auteurs wijzen erop dat de exacte vorm van $R_{III}$ nog niet volledig is bepaald en dat scenario's met meerdere aanvallers of niet-convexe dominante gebieden verdere studie vereisen.

Kortom, het paper biedt een rigoureuze wiskundige oplossing voor een complex spelprobleem en introduceert een nieuw inzicht in hoe spelers met gedempte dynamica strategisch kunnen manoeuvreren door hun versnelling dynamisch aan te passen.