Technische Samenvatting: GraphChase: Een Platform en Benchmark voor Urban Network Security Games

Probleemdefinitie

Urban Network Security Games (UNSGs) modelleren scenario's waarin wetshandhaving (achtervolgers) strategisch beperkte middelen moet toewijzen om criminelen (ontwijkers) te onderscheppen die via stedelijke wegennetwerken vluchten. Hoewel er aanzienlijke vooruitgang is geboekt in twee-speler zero-sum games, vormt het oplossen van UNSGs unieke uitdagingen vanwege hun aard als multiplayer-games die samenwerking, competitie en imperfecte informatie inhouden.

Het vakgebied staat momenteel voor drie primaire beperkingen:

1. Gebrek aan Standaardisatie: Het ontbreken van een verenigd experimenteel platform leidt tot incompatibele implementaties, inconsistente datastructuren en moeilijkheden bij het kruisgewijs evalueren van algoritmen.
2. Realiteits-Schaalbaarheidstussenruimte: Optimalisatiemethoden vertrouwen vaak op Mixed-Integer Linear Programming (MILP) om gewogen reistijden te modelleren, maar slagen er niet in op te schalen naar grote netwerken. Daarentegen vereenvoudigen state-of-the-art (SOTA) leergebaseerde methoden omgevingen doorgaans tot ongewogen grafen om training te vergemakkelijken, waarbij de heterogeniteit van realistische wegsegmenten (bijv. variërende lengtes en snelheidslimieten) wordt genegeerd.
3. Sim-to-Real Gap: Bestaande benaderingen worstelen met robuustheid en schaalbaarheid bij implementatie op gewogen grafen, wat wijst op een generalisatiekloof tussen vereenvoudigde trainingsomgevingen en realistische condities.

Methodologie: Het GraphChase Platform

Om deze uitdagingen aan te pakken, introduceren de auteurs GraphChase, een open-source platform ontworpen om UNSG-onderzoek te standaardiseren en simulaties in realistische omgevingen te ondersteunen. Het platform maakt gebruik van een modulaire architectuur die de omgeving, agenten en solvers ontkoppelt.

Kerncomponenten

1. Game Module (Omgeving):

   • Graafrepresentatie: Modelleert wegennetwerken als grafen $G=(V, E, \omega)$, waarbij zowel gerichte als ongerichte randen worden ondersteund. Het verwerkt gewogen randen waarbij $\omega(u, v)$ de continue reistijd representeert.
   • Toestandsrepresentatie: Agenten bevinden zich ofwel op vertices of langs randen, gerepresenteerd als tupels $(u, v, \delta)$, waarbij $\delta$ de afstand is vanaf vertex $u$. Dit maakt continue beweging mogelijk binnen een discrete tijdstap-framework.
   • Dynamiek: Gebruikt een hybride besluitvormingsmechanisme waarbij agenten beslissingen nemen aan het begin van tijdstappen en onmiddellijk bij het bereiken van vertices. Het spel eindigt bij capture (afstand $\le \epsilon$), escape (bereiken van exit-nodes), of timeout ($T$).
   • Informatiestructuren: Ondersteunt vier informatiescenario's variërend van volledige observabiliteit tot partiële observabiliteit voor zowel achtervolgers als ontwijkers, en staat onafhankelijke of gecoördineerde besluitvorming tussen achtervolgers toe.

2. Agent Module:

   • Biedt een uniforme interface voor beleidsrepresentatie (neuraal of heuristisch) en trajectverzameling.
   • Introduceert Runners om interactie met de omgeving, preprocessing en batchconstructie te encapsuleren, wat ondersteuning biedt voor vectorized rollouts voor efficiënte dataverzameling.
   • Ondersteunt iteratief speltheoretisch leren, inclus$\ef$ policy cloning en persistentie voor frameworks zoals Policy-Space Response Oracles (PSRO).

3. Solver Module:

   • Implementeert plug-and-play optimalisatoren (bijv. PPO, MAPPO) voor best-response training.
   • Ondersteunt speltheoretische leerframeworks, specifiek PSRO, waarbij het wordt gedecomposed in Best Response Oracles (RL of heuristisch) en Meta-Solvers (bijv. Projected Replicator Dynamics).
   • Maakt custom solver-implementaties mogelijk zonder de kern van de game-logica te wijzigen.

Benchmark Protocol

GraphChase stelt een gestandaardiseerd benchmarkprotocol vast, inclusief:

• Algoritmen: Integratie van SOTA-algoritmen waaronder CFR-MIX, NSG-NFSP, NSGZero, Pretrained PSRO, en Grasper.
• Executiemodi: Ondersteunt zowel path-based execution (ontwijkers selecteren een doel-exit en een pad vóór het spel) als step-wise execution (agenten bepalen acties op elk beslispunt).
• Evaluatiemetrieken:
  • Worst-Case Utility: Evalueert alle paden van de ontwijker om de minimale utility van de achtervolger te vinden.
  • Pseudo Worst-Case Utility: Benadert het slechtste geval door paden voor elke exit te samplen om grote grafen te verwerken.
  • Visualisatie: Tools voor het analyseren van trajecten en besluitvormingsprocessen.

Belangrijkste Bijdragen

1. Verenigd Platform: Ontwikkeling van GraphChase, dat de omgeving ontkoppelt van algoritmen, wat incompatibiliteitsproblemen oplost en een eerlijke kruis-evaluatie van strategieën op identieke taken mogelijk maakt.
2. Vestiging van een Benchmark: Integratie van meerdere deep learning-gebaseerde algoritmen binnen een uniform framework, wat betrouwbare baselines biedt en prestatie-metrieken vaststelt over diverse game-configuraties.
3. Blootleggen van de Sim-to-Real Gap: Uitgebreide experimenten die aantonen dat huidige benaderingen significante beperkingen ervaren in schaalbaarheid en robuustheid, met name door prestatievermindering wanneer ze worden ingezet op gewogen wegennetwerken vergeleken met ongewogen netwerken.

Experimentele Resultaten

De auteurs hebben experimenten uitgevoerd op een server met 48-core CPU's en 8 NVIDIA A30 GPU's om het platform te valideren en algoritmen te evalueren.

• Reproduceerbaarheid en Correctheid: GraphChase heeft de resultaten uit de originele literatuur (Pretrained PSRO, Grasper, NSGZero, NSG-NFSP) succesvol gereproduceerd op 5x5 en 7x7 grid-grafen. Het platform loste inefficiënties in originele codebases op (bijv. Grasper op, wat resulteerde in betere trainingsprestaties terwijl de consistente logica behouden bleef.
• Computationele Efficiëntie: GraphChase verbeterde de algemene sampling-throughput met 1.38x en versnelde de best-response berekening voor ontwijkers (1.96x) en achtervolgers (1.72x) vergeleken met de originele implementaties, dankzij het gevectoriseerde environment-ontwerp.
• Real-World Topologie Benchmarks: Testen op zes real-world kaarten (Singapore, Manhattan, Mumbai, etc.) toonden variatie in prestaties aan. Algoritmen behaalden een hoge utility in sommige topologieën, maar hadden moeite met complexe omgevingen zoals Manhattan en Times Square, gekenmerkt door een hoog aantal nodes/edges en uitgebreide tijdshorizonten.
• Robuustheidsevaluatie:
  • Horizon Shift: Beleid getraind op $T=4$ vertoonde significante utility-dalingen wanneer getest op $T=8$, wat duidt op beperkte robuustheid tegen veranderingen in de tijdshorizont.
  • Edge Weight Variaties: Beleid getraind op ongewogen grafen leed onder significante prestatievermindering bij testen op gewogen grafen, wat het gebrek aan robuustheid tegen de heterogeniteit van edge-kosten onderstreept.
• Schaalbaarheid: Bestaande algoritmen faalden bij het trainen op een 100x100 grid, en zelfs 30x30 grids liepen vast door de exponentiële explosie van pad-enumeratie die nodig is voor besluitvorming. Dit benadrukt een schaalbaarheidsbarrière voor huidige solvers.
• Step-wise Policy Executie: Experimenten op de Mumbai-kaart (ongewogen en gewogen) toonden aan dat GraphChase step-wise PPO-beleid kan trainen en evalueren. Terwijl heuristische verdedigers goed presteerden tegen heuristische aanvallers, hadden zij moeite met PPO-aanvallers, en PVO-verdedigers vertoonden lage capture-rates op gewatteerde grafen, wat de moeilijkheid bevestigt van leren op realistische, gewogen topologieën.

Betekenis en Claims

Het artikel claimt dat GraphChase het eerste open-source platform is dat gewijd is aan UNSGs, en een flexibele multiplayer-game-omgeving biedt die de kloof overbrugt tussen theoretische game-solving en realistische stedelijke veiligheidstoepassingen.

• Standaardisatie: Het verlaagt de drempel voor UNSG-onderzoek door een uniforme interface te bieden, wat een gemeenschap stimuleert die gericht is op schaalbare en realistische beveiligingsuitdagingen.
• Realistische Modellering: Door gewogen grafen en hybride besluitvorming te ondersteunen, legt het platform de dynamische aard van real-world scenario's (bijv. verkeerspatronen) beter vast dan traditionele ongewogen modellen.
• Testbed voor Multiplayer Games: Het platform dient als een testbed voor het berekenen van Nash-evenwichten (NE) en Team-Maxmin Evenwichten (TME) in complexe multiplayer-settings, toepasbaar op bredere domeinen zoals anti-stroperij en adversarial team games.
• Identificatie van Beperkingen: Het werk kwantificeert expliciet de "sim-to-real" generalisatiekloof, waarbij wordt aangetoond dat huidige SOTA-algoritmen niet robuust zijn tegen gewogen edge-kosten of grootschalige netwerken, wat de ontwikkeling van nieuwe benaderingen stimuleert die afstappen van globale actieruimte-traversering.

De auteurs positioneren GraphChase als een instrument voor defensieve planning en evaluatie, bedoeld om publieke veiligheidsstrategieën te verbeteren in plaats van te helpen bij het plannen van ontsnappingen.