Sintesi Tecnica: GraphChase: Una Piattaforma e un Benchmark per i Giochi di Sicurezza nelle Reti Urbane

Definizione del Problema

I Giochi di Sicurezza nelle Reti Urbane (UNSG - Urban Network Security Games) modellano scenari in cui le forze dell'ordine (inseguitori) devono allocare strategicamente risorse limitate per intercettare criminali (evasori) che fuggono attraverso reti stradali urbane. Sebbene siano stati fatti progressi significativi nei giochi a somma zero a due giocatori, la risoluzione degli UNSG presenta sfide uniche a causa della loro natura di giochi multiplayer che coinvolgono cooperazione, competizione e informazioni imperfette.

Il settore affronta attualmente tre limitazioni primarie:

1. Mancanza di Standardizzazione: L'assenza di una piattaforma sperimentale unificata porta a implementazioni incompatibili, strutture dati incoerenti e difficoltà nella valutazione incrociata degli algoritmi.
2. Compromesso tra Realismo e Scalabilità: I metodi basati sull'ottimizzazione spesso si affidano alla Programmazione Lineare Intera Mista (MILP) per modellare i tempi di percorrenza pesati, ma non riescono a scalare su reti ampie. Al contrario, i metodi di apprendimento allo stato dell'arte (SOTA) tipicamente semplificano gli ambienti in grafi non pesati per facilitare l'addestramento, ignorando l'eterogeneità dei segmenti stradali reali (ad esempio, variazioni di lunghezza e limiti di velocità).
3. Gap Sim-to-Real: Gli approcci esistenti faticano in termini di robustezza e scalabilità quando vengono distribuiti su reti pesate, evidenziando un gap di generalizzazione tra ambienti di addestramento semplificati e condizioni realistiche.

Metodologia: La Piattaforma GraphChase

Per affrontare queste sfide, gli autori introducono GraphChase, una piattaforma open-source progettata per standardizzare la ricerca sugli UNSG e supportare simulazioni in ambienti realistici. La piattaforma impiega un'architettura modulare che disaccoppia l'ambiente, gli agenti e i solver.

Componenti Core

1. Modulo di Gioco (Ambiente):

   • Rappresentazione del Grafo: Modella le reti stradali come grafi $G=(V, E, \omega)$, supportando archi diretti e non diretti. Gestisce archi pesati dove $\omega(u, v)$ rappresenta il tempo di percorrenza continuo.
   • Rappresentazione dello Stato: Gli agenti sono localizzati o sui vertici o lungo gli archi, rappresentati come tuple $(u, v, \delta)$, dove $\delta$ è la distanza dal vertice $u$. Ciò consente il movimento continuo all'interno di un framework a tempo discreto.
   • Dinamica: Utilizza un meccanismo decisionale ibrido in cui gli agenti prendono decisioni all'inizio dei passi temporali e istantaneamente al raggiungimento dei vertici. Il gioco termina con la cattura (distanza $\le \epsilon$), la fuga (raggiungimento dei nodi di uscita) o il timeout ($T$).
   • Strutture Informative: Supporta quattro scenari informativi che vanno dalla piena osservabilità alla parziale osservabilità sia per gli inseguitori che per gli evasori, e consente il processo decisionale indipendente o coordinato tra gli inseguitori.

2. Modulo Agente:

   • Fornisce un'interfaccia unificata per la rappresentazione delle policy (neurale o euristica) e la raccolta di traiettorie.
   • Introduce i Runner per incapsulare l'interazione con l'ambiente, il pre-processing e la costruzione dei batch, supportando rollout vettorizzati per una raccolta dati efficiente.
   • Supporta l'apprendimento game-teorico iterativo, inclusa la clonazione della policy e la persistenza per framework come i Policy-Space Response Oracles (PSRO).

3. Modulo Solver:

   • Implementa ottimizzatori plug-and-play (es. PPO, MAPPO) per l'addestramento della best-response.
   • Supporta framework di apprendimento game-teorico, specificamente PSRO, decomponendolo in Best Response Oracles (RL o euristica) e Meta-Solver (es. Projected Replicator Dynamics).
   • Permette l'implementazione di solver personalizzati senza modificare la logica di gioco centrale.

Protocollo di Benchmark

GraphChase stabilisce un protocollo di benchmark standardizzato che include:

• Algoritmi: Integrazione di algoritmi SOTA tra cui CFR-MIX, NSG-NFSP, NSGZero, Pretrained PSRO e Grasper.
• Modalità di Esecuzione: Supporta l'esecuzione basata su percorsi (gli evasori selezionano un obiettivo di uscita e un percorso prima del gioco) e l'esecuzione step-wise (gli agenti campionano le azioni ad ogni punto decisionale).
• Metriche di Valutazione:
  • Utilità del Caso Peggiore (Worst-Case Utility): Enumera tutti i percorsi degli evasori per trovare l'utilità minima dell'inseguitore.
  • Pseudo Worst-Case Utility: Approssima il caso peggiore campionando i percorsi per ogni uscita per gestire grafi di grandi dimensioni.
  • Visualizzazione: Strumenti per analizzare le traiettorie e i processi decisionali.

Contributi Chiave

1. Piattaforma Unificata: Sviluppo di GraphChase, che disaccoppia l'ambiente dagli algoritmi, risolvendo i problemi di incompatibilità e consentendo una valutazione incrociata equa delle strategie su compiti identici.
2. Stabilimento del Benchmark: Integrazione di molteplici algoritmi basati sul deep learning in un framework unificato, fornendo baseline affidabili e stabilendo metriche di prestazione attraverso diverse configurazioni di gioco.
3. Rivelazione del Gap Sim-to-Real: Esperimenti estesi che dimostrano come gli approcci attuali affrontino limitazioni significative in termini di scalabilità e robustezza, soffrendo particolarmente di una degradazione delle prestazioni quando distribuiti su reti stradali pesate rispetto a quelle non pesate.

Risultati Sperimentali

Gli autori hanno condotto esperimenti su un server con CPU a 48 core e 8 GPU NVIDIA A30 per validare la piattaforma e valutare gli algoritmi.

• Riproducibilità e Correttezza: GraphChase ha riprodotto con successo i risultati della letteratura originale (Pretrained PSRO, Grasper, NSGZero, NSG-NFSP) su grafi a griglia 5x5 e 7x7. La piattaforma ha risolto le inefficienze dei codebase originali (es. Grasper), ottenendo prestazioni di addestramento migliori pur mantenendo una logica coerente.
• Efficienza Computazionale: GraphChase ha migliorato il throughput complessivo di campionamento del 1.38x e ha accelerato il calcolo della best-response per gli evasori (1.96x) e per gli inseguitori (1.72x) rispetto alle implementazioni originali, grazie al design dell'ambiente vettorizzato.
• Benchmark di Topologia del Mondo Reale: I test su sei mappe del mondo reale (Singapore, Manhattan, Mumbai, ecc.) hanno rivelato una varianza nelle prestazioni. Gli algoritmi hanno ottenuto un'alta utilità in alcune topologie, ma hanno faticato in ambienti complessi come Manhattan e Times Square, caratterizzati da un alto numero di nodi/archi e orizzonti temporali estesi.
• Valutazione della Robustezza:
  • Shift dell'Orizzonte Temporale: Le policy addestrate su $T=4$ hanno mostrato cali significativi di utilità quando testate su $T=8$, indicando una robustezza limitata ai cambiamenti dell'orizzonte temporale.
  • Variazioni del Peso degli Archi: Le policy addestrate su grafi non pesati hanno subito una significativa degradazione delle prestazioni quando testate su grafi pesati, sottolineando una mancanza di robustezza all'eterogeneità dei costi degli archi.
• Scalabilità: Gli algoritmi esistenti non sono riusciti ad addestrarsi su una griglia 100x100, e persino le griglie 30x30 si sono bloccate a causa dell'esplosione esponenziale della enumerazione dei percorsi necessaria per il processo decisionale. Ciò evidenzia una barriera di scalabilità per gli attuali solver.
• Esecuzione della Policy Step-wise: Gli esperimenti sulla mappa di Mumbai (non pesata e pesata) hanno dimostato che GraphChase può addestrare e valutare policy PPO step-wise. Mentre i difensori euristici hanno performato bene contro gli attaccanti euristici, hanno faticato contro gli attaccanti PPO, e i difensori PPO hanno mostrato bassi tassi di cattura su grafi pesati, confermando la difficoltà di apprendere su topologie pesate realistiche.

Significato e Rivendicazioni

L'articolo afferma che GraphChase fornisce la prima piattaforma open-source dedicata agli UNSG, offrendo un ambiente di gioco multiplayer flessibile che colma il divario tra la risoluzione teorica dei giochi e le applicazioni di sicurezza urbana reali.

• Standardizzazione: Abbassa la barriera d'ingresso per la ricerca sugli UNSG fornendo un'interfaccia unificata, favorendo una comunità focalizzata su sfide di sicurezza scalabili e realistiche.
• Modellazione Realistica: Supportando grafi pesati e decisioni ibride, la piattaforma cattura meglio la natura dinamica dei casi reali (es. schemi di traffico) rispetto ai modelli tradizionali non pesati.
• Testbed per Giochi Multiplayer: La piattaforma funge da banco di prova per il calcolo di Nash Equilibria (NE) e Team-Maxmin Equilibria (TME) in contesti multiplayer complessi, applicabili a domini più ampi come l'antibracconaggio e i giochi di squadra avversariali.
• Identificazione delle Limitazioni: Il lavoro quantifica esplicitamente il gap di generalizzazione "sim-to-real", mostrando che gli attuali algoritmi SOTA non sono robusti rispetto ai costi degli archi pesati o alle reti su larga scala, motivando così lo sviluppo di nuovi approcci che si allontanino dalla traversata globale dello spazio delle azioni.

Gli autori posizionano GraphChase come uno strumento di pianificazione e valutazione difensiva, destinato a migliorare le strategie di pubblica sicurezza piuttosto che ad aiutare la pianificazione della fuga.