⚡ electrical engineering

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

Diese Arbeit analysiert Multiplayer-Reach-Avoid-Differenzialspiele mit Informationsverzögerungen auf der Verteidigerseite, leitet explizite analytische Charakterisierungen verzögerter Angriffsregionen ab, formuliert konvexe Optimierungsprobleme für optimale Abfangstrategien, die ein Subgame-Perfect-Nash-Gleichgewicht bilden, und erweitert das Framework auf Multi-Agenten-Szenarien mittels verzögerungsbewusster Zuweisungsformulierungen, welche durch numerische Simulationen validiert werden.

Ursprüngliche Autoren: Zehua Zhao, Rui Yan, Jianping He, Xiaoming Duan

Veröffentlicht 2026-06-24

📖 4 Min. Lesezeit☕ Kaffeepausen-Lektüre

CC BY 4.0

Ursprüngliche Autoren: Zehua Zhao, Rui Yan, Jianping He, Xiaoming Duan

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich ein hochkarätiges Fangspiel auf einem flachen Feld vor, aber mit einem Twist: Die „Fänger“ (Verteidiger) spielen mit einer langsamen Internetverbindung.

Hier ist die Geschichte der Arbeit, unterteilt in einfache Konzepte:

Das Setup: Ein Fangspiel mit einem Glitch

Stellen Sie sich ein Spiel vor, bei dem eine Gruppe von Angreifern (den Läufern) versucht, eine Sicherheitszone (ein Zielgebiet) zu erreichen, ohne gefasst zu werden. Eine Gruppe von Verteidigern (den Fängern) versucht, sie zu stoppen. Jeder hat eine maximale Geschwindigkeit, und wenn ein Verteidiger nah genug an einen Angreifer herankommt, „fängt“ er ihn.

Der Haken: Die Verteidiger leiden unter Informationsverzögerung.
Denken Sie an Folgendes: Die Verteidiger tragen VR-Headsets, die ihnen die Welt zeigen, aber der Video-Feed verzögert um einige Sekunden. Wenn ein Verteidiger auf einen Angreifer blickt, sieht er nicht, wo der Angreifer jetzt gerade ist; er sieht, wo der Angreifer vor einem Moment war. Die Angreifer hingegen haben eine perfekte Echtzeit-Sicht.

Die große Frage

Wenn die Verteidiger auf alte Daten schauen, können die Angreifer dies ausnutzen? Können die Angreifer in einem Zickzack-Muster laufen, das die Verteidiger nicht vorhersagen können, weil sie auf die Vergangenheit reagieren? Oder können die Verteidiger sie trotzdem fangen?

Die Lösung: Die „Sicherheitszone“ zeichnen

Die Autoren haben einen Weg gefunden, eine perfekte Karte für die Verteidiger zu zeicheln.

Die „Angriffszone“ (der Spielplatz des Läufers):
Stellen Sie sich vor, man zeichnet eine Form auf den Boden. Innerhalb dieser Form kann der Läufer garantieren, dass er einen bestimmten Punkt bevor der Fänger dort ankommt, erreicht – selbst mit der Verzögerung. Das Papier beweist, dass diese Form immer ein glatter, solider Klumpen (mathematisch als „konvex“ bezeichnet) ist. Es ist kein gezacktes, verwirrendes Chaos; es ist ein sauberer, berechenbarer Bereich.
Die Gewinnstrategie:
- Wenn der Läufer innerhalb der Angriffszone ist: Er kann geradeaus auf die Sicherheitszone laufen. Egal wie sich der Fänger bewegt, der Läufer gewinnt, weil der Fänger der Vergangenheit hinterherhinkt.
- Wenn der Läufer außerhalb der Angriffszone ist: Der Fänger kann einen Sieg garantieren. Das Papier liefert eine mathematische Formel (ein „konvexes Optimierungsproblem“), um genau den Punkt zu finden, an dem der Fänger den Läufer fangen wird.

Die Geheimwaffe: „Subgame-Perfect“ Denken

In der Spieltheorie ist ein „Nash-Gleichgewicht“ ein Zustand, in dem niemand seine Strategie ändern möchte, weil er bereits das Beste aus seiner Situation macht. Dieses Papier geht einen Schritt weiter.

Da die Verteidiger verzögert sind, läuft das Spiel in zwei deutlich unterscheidbaren Phasen ab:

Phase 1 (Die Verzögerung): Der Verteidiger ist eingefroren oder bewegt sich blind basierend auf alten Informationen. Der Läufer ist frei in seiner Bewegung.
Phase 2 (Das Aufholen): Der Verteidiger sieht den Läufer schließlich und beginnt die Verfolgung.

Die Autoren haben bewiesen, dass ihre Strategie „Subgame-Perfect“ ist. Das bedeutet, dass die Strategie nicht nur für das gesamte Spiel perfekt funktioniert, sondern für jeden einzelnen Moment des Spiels. Selbst wenn das Spiel mitten im Verlauf neu beginnt oder sich die Verzögerung ändert, bleibt die Strategie die beste Option für beide Seiten. Es ist wie ein GPS, das die perfekte Route sofort neu berechnet, egal wo man sich auf der Reise befindet.

Skalierung: Vom Eins-gegen-Eins zum Mannschaftssport

Das Papier blieb nicht bei einem Läufer gegen einen Fänger stehen. Sie erweiterten die Logik auf:

Ein Läufer gegen viele Fänger: Wenn ein Läufer von einem Team verzögerter Verteidiger umgeben ist, ist die „Angriffszone“ der Bereich, in dem der Läufer alle von ihnen schlagen kann. Das Papier zeigt, dass normalerweise nur die zwei schnellsten oder am besten positionierten Verteidiger tatsächlich relevant sind; der Rest dient nur als Backup.
Viele Läufer gegen viele Fänger: Dies wird zu einem Matching-Puzzle. Das Papier nutzt einen „Maximum Matching“-Algorithmus (wie ein Dating-App für Teams), um zu entscheiden, welcher Verteidiger welchen Läufer verfolgen soll. Das Ziel ist es, so viele Läufer wie möglich zu fangen, bevor sie die Sicherheitszone erreichen.

Die Simulationsergebnisse

Die Autoren ließen Computersimulationen laufen, um zu beweisen, dass ihre Mathematik funktioniert:

Eins-gegen-Eins: Sie zeigten, dass es dem Läufer sogar schlechter geht, wenn er versucht, die Verzögerung durch zufällige Richtungswechsel auszutricksen. Wenn der Verteidiger versucht, einfach auf die aktuelle sichtbare Position des Läufers zu laufen (oh-ne die Verzögerungs-Mathematik zu berücksichtre), schneidet er ebenfalls schlechter ab. Die „kluge“ mathematische Strategie gewinnt jedes Mal.
Mannschaftsspiel: Wenn mehrere Verteidiger unter Anwendung dieser Regeln zusammenarbeiten, fangen sie den Läufer effizienter als durch bloßes Raten.

Das Faz-Fazit

Dieses Papier löst ein komplexes mathematisches Rätsel über Verfolgung und Flucht, wenn eine Seite gegenüber der Gegenwart „blind“ ist. Es beweist, dass man selbst mit einer Verzögerung eine perfekte Karte davon zeichnen kann, wer gewinnt und wer verliert, und den exakten Pfad berechnen kann, den beide Seiten nehmen sollten, um optimal zu spielen. Es verwandelt ein chaotisches Fangspiel mit Lag in ein berechenbares, lösbares Geometrie-Problem.

Technische Zusammenfassung: Multiplayer-Reach-Avoid-Differenzialspiele mit Informationsverzögerung auf der Verteidigerseite

Problemformulierung
Dieses Paper untersucht eine Klasse von Reach-Avoid-Differenzialspielen, die mehrere Verteidiger und mehrere Angreifer involvieren, welche sich in einer zweidimensionalen Ebene mit begrenzten Geschwindigkeiten bewegen. Die zentrale Herausforderung ist das Vorhandensein einer Informationsverzögerung auf der Verteidigerseite. In diesem Szenario verfügen die Angreifer über Echtzeit-Zustandsinformationen, während jeder Verteidiger $D_i$ die Zustände anderer Agenten (sowohl anderer Verteidiger als auch Angreiger) mit einer konstanten Zeitverzögerung $\tau_i$ beobachtet. Folglich basieren die Entscheidungen der Verteidiger auf den vergangenen Positionen der Angreifer ( $t-\tau_i$ ) statt auf deren aktuellen Positionen.

Das Spiel umfasst $N$ Verteidiger und $M$ Angreifer. Die Angreifer versuchen, eine konvexe, geschlossene Zielregion $T$ zu erreichen, während die Verteidiger versuchen, die Angreifer (innerhalb eines Radius $r_i$ ) abzufangen, bevor diese $T$ erreichen. Wenn ein Angreifer abgefangen wird, versuchen die Verteidiger, den Abstand des Abfangpunktes zu $T$ zu maximieren, während der Angreifer versucht, diesen Abstand zu minimieren. Das Spiel endet, wenn alle Angreifer entweder abgefangen wurden oder in die Zielregion eingetreten sind. Die Autoren nehmen spezifische Anfangsbedingungen an, um sicherzustellen, dass das Spiel wohldefiniert ist: Die Verteidiger verharren während des Verzögerungsintervalls stationär, die Angreifer starten außerhalb der Zielregion, die Verteidiger sind schneller als die Angreifer ( $\bar{v}_D > \bar{v}_A$ ) und die Anfangsabstände sind ausreichend groß, um einen sofortigen Abfangvorgang vor Ende der Verzögerungsperiode zu verhindern.

Methodik
Die Autoren verwenden einen geometrischen Ansatz kombiniert mit konvexer Analyse und spieltheoretischen Gleichgewichtskonzepten, um das Problem zu lösen.

Analyse: Ein Angreifer gegen einen Verteidiger:
- Charakterisierung der Angriffsregion: Die Autoren leiten zunächst eine explizite analytische Charakterisierung der „verzögerten Angriffsregion“ ( $R_{total}^A$ ) her. Diese Region stellt die Menge der Punkte dar, die ein Angreifer garantierterweise nicht später erreichen kann als der Verteidiger, unter Berücksichtigung der Reaktionsverzögerung des Verteidigers.
- Konvexitätsbeweis: Mittels einer spezifischen Krümmungsanalyse der durch die Distanzbeschränkungen und Verzögerungsparameter definierten Grenze beweisen die Autoren, dass diese Angriffsregion unter milden Annahmen eine konvexe Menge ist.
- Optimale Strategien: Basierend auf der konvexen Angriffsregion formulieren die Autoren ein konvexes Optimierungsproblem, um den Abfangpunkt zu finden (den Punkt in der Angriffsregion, der der Zielregion am nächsten liegt). Die optimalen Strategien für beide Spieler werden als Bewegung mit maximaler Geschwindigkeit in einer geraden Linie auf diesen Abfangpunkt hin abgeleitet.
- Verifizierung des Gleichgewichts: Das Paper etabliert, dass diese Strategien ein Subgame-Perfect Nash Equilibrium (SPNE) bilden. Dies wird durch die Unterteilung des Spiels in zwei Phasen (vor und nach dem Eintritt des Verteidigers in das Spiel) und die Verwendung von Rückwärtsinduktion bewiesen, um die Optimalität in jeder Phase zu zeigen.
Erweiterung auf Multiplayer-Szenarien:
- Ein Angreifer gegen mehrere Verteidiger: Die Angriffsregion wird als der Schnittpunkt der individuellen Angriffsregionen zwischen dem Angreifer und jedem einzelnen Verteidiger definiert. Der Abfangpunkt wird durch das Lösen eines konvexen Optimierungsproblems unter Berücksichtigung der Beschränkungen aller Verteidiger bestimmt. Die Autoren merken an, dass – konsistent mit vorangegangener Arbeit – höchstens zwei Verteidiger ausreichen, um den Abfangpunkt zu bestimmen, sofern optimal gespielt wird.
- Mehrere Angreifer gegen mehrere Verteidiger: Das Problem wird auf ein allgemeines $N$ -gegen- $M$ -Szenario erweitert. Die Autoren integrieren „verzögerungsbewusste paarweise Gewinn-Relationen“ (die Bestimmung, ob ein spezifischer Verteidiger einen spezifischen Angreifer garantierterweise abfangen kann) in eine Maximum-Matching-Formulierung. Dies ermöglicht die optimale Zuweisung von Verteidigern zu Angreifern, um die Anzahl der Abfangvänge zu maximieren.

Zentrale Beiträge
Das Paper leistet die folgenden spezifischen Beiträge:

Mathematische Formulierung: Es schlägt eine rigorose Formulierung von Reach-Avoid-Spielen vor, bei denen die Verteidiger mit verzögerten Informationen bezüglich der Positionen der Angreifer operieren.
Analytische Charakterisierung: Für den Ein-gegen-Eins-Fall leitet es eine explizite analytische Repräsentation der verzögerten Angriffsregion her und beweist deren Konvexität – ein nicht triviales Ergebnis angesichts der Zeitverzögerungsdynamik.
Optimale Strategien und Gleichgewicht: Es leitet optimale Strategien für beide Spieler ab und beweist, dass diese ein Subgame-Perfect Nash Equilibrium bilden, wobei die durch die Verzögerung induzierte sequentielle Natur des Spiels berücksichtigt wird.
Skalierbarkeit: Das Framework wird auf Ein-Angreifer-gegen-mehrere-Verteidiger- sowie auf allgemeine Multi-Agenten-Szenarien erweitert und bietet Strategien zur Berechnung des Abfangpunktes sowie zur Zuweisung von Verteidiger zu Angreifer mittels Maximum-Matching.

Ergebnisse
Numerische Simulationen wurden mit MATLAB durchgeführt, um die theoretischen Erkenntnisse über drei Szenarien hinweg zu validieren:

Eins-gegen-Eins: Die Simulationen bestätigten, dass die vorgeschlagenen optimalen Strategien sowohl die „Pure-Attack“- als auch die „Pure-Defense“-Benchmark-Policys übertreffen. Insbesondere führten einseitige Abweichungen durch einen der Spieler zu schlechteren Ergebnissen für den abweichenden Spieler, was den Gleichgewichtscharakter der Strategien validiert.
Eins-gegen-Mehrere: Simulationen mit einem Angreifer und zwei Verteidigern zeigten, dass kooperative Strategien unter den Verteidigern eine bessere Leistung erzielen können (Minimierung des Abstand des Angreifers zum Ziel) als ein einzelner Verteidiger, der allein agiert.
Multi-Agenten: Ein Drei-Angreifer-gegen-Drei-Verteidiger-Szenario illustrierte die Effektivität des Maximum-Matching-Ansatzes. Die Simulation zeigte, dass die Verteidiger sich erfolgreich den Angreifern zuordneten, die sie garantierterweise abfangen konnten, während der nicht zugewiesene Angreifer erfolgreich das Ziel erreichte.

Bedeutung und Ansprüche
Das Paper behauptet, das erste zu sein, das optimale Strategien für Reach-Avoid-Spiele speziell unter der Bedingung einer Informationsverzögerung auf der Verteidigerseite bereitstellt. Während frühere Arbeiten Verzögerungen bei Angreifern oder Standard-Reach-Avoid-Spiele behandelt haben, füllt diese Arbeit eine Lücke in der Literatur hinsichtlich der Frage, wie Verteidiger die Leistungsdegradierung optimal abmildern können, wenn ihre Informationen inhärent verzögert sind.

Die Autoren betonen, dass ihr Ansatz über die Schwierigkeit hinausgeht, die hochdimensionale Hamilton-Jacobi-Isaacs-Gleichung (HJI) direkt zu lösen. Stattdessen bieten sie durch die Nutzung der geometrischen Struktur der verzögerten Angriffsregion und deren Konvexität einen handhabbaren, verifikationsbasierten analytischen Rahmen. Dies ermöglicht die effiziente Berechnung von Gewinnbedingungen und Gleichgewichtstrategien in Szenarien, die ansonsten analytisch nicht handhabbar wären. Die Arbeit positioniert sich als Schritt hin zu einer realistischeren Modellierung von adversen Systemen (wie etwa in militärischen oder luftfahrttechnischen Anwendungen), in denen Kommunikations- und Verarbeitungslatenzen unvermeidlich sind.