Technical Summary: GraphChase: A Platform and Benchmark for Urban Network Security Games

Problem Definition

Urban Network Security Games (UNSGs) model scenarios where law enforcement (pursuers) must strategically allocate limited resources to intercept criminals (evaders) escaping through urban road networks. While significant progress has been made in two-player zero-sum games, solving UNSGs presents unique challenges due to their nature as multiplayer games involving cooperation, competition, and imperfect information.

The field currently faces three primary limitations:

1. Lack of Standardization: The absence of a unified experimental platform leads to incompatible implementations, inconsistent data structures, and difficulty in cross-evaluating algorithms.
2. Realism-Scalability Trade-off: Optimization-based methods often rely on Mixed-Integer Linear Programming (MILP) to model weighted travel times but fail to scale to large networks. Conversely, state-of-the-art (SOTA) learning-based methods typically simplify environments to unweighted graphs to facilitate training, ignoring the heterogeneity of real-world road segments (e.g., varying lengths and speed limits).
3. Sim-to-Real Gap: Existing approaches struggle with robustness and scalability when deployed on weighted networks, highlighting a generalization gap between simplified training environments and realistic conditions.

Methodology: The GraphChase Platform

To address these challenges, the authors introduce GraphChase, an open-source platform designed to standardize UNSG research and support simulations in realistic environments. The platform employs a modular architecture decoupling the environment, agents, and solvers.

Core Components

1. Game Module (Environment):

   • Graph Representation: Models road networks as graphs $G=(V, E, \omega)$, supporting both directed and undirected edges. It handles weighted edges where $\omega(u, v)$ represents continuous travel time.
   • State Representation: Agents are located either at vertices or along edges, represented as tuples $(u, v, \delta)$, where $\delta$ is the distance from vertex $u$. This allows for continuous movement within a discrete-time step framework.
   • Dynamics: Uses a hybrid decision-making mechanism where agents make decisions at the start of time steps and instantaneously upon reaching vertices. The game terminates upon capture (distance $\le \epsilon$), escape (reaching exit nodes), or timeout ($T$).
   • Information Structures: Supports four information scenarios ranging from full observability to partial observability for both pursuers and evaders, and allows for independent or coordinated decision-making among pursuers.

2. Agent Module:

   • Provides a unified interface for policy representation (neural or heuristic) and trajectory collection.
   • Introduces Runners to encapsulate environment interaction, preprocessing, and batch construction, supporting vectorized rollouts for efficient data collection.
   • Supports iterative game-theoretic learning, including policy cloning and persistence for frameworks like Policy-Space Response Oracles (PSRO).

3. Solver Module:

   • Implements plug-and-play optimizers (e.g., PPO, MAPPO) for best-response training.
   • Supports game-theoretic learning frameworks, specifically PSRO, decomposing it into Best Response Oracles (RL or heuristic) and Meta-Solvers (e.g., Projected Replicator Dynamics).
   • Allows for custom solver implementation without modifying the core game logic.

Benchmark Protocol

GraphChase establishes a standardized benchmark protocol including:

• Algorithms: Integration of SOTA algorithms including CFR-MIX, NSG-NFSP, NSGZero, Pretrained PSRO, and Grasper.
• Execution Modes: Supports both path-based execution (evaders select a target exit and a path before the game) and step-wise execution (agents sample actions at each decision point).
• Evaluation Metrics:
  • Worst-Case Utility: Enumerates all evader paths to find the minimum pursuer utility.
  • Pseudo Worst-Case Utility: Approximates the worst case by sampling paths for each exit to handle large graphs.
  • Visualization: Tools for analyzing trajectories and decision processes.

Key Contributions

1. Unified Platform: Development of GraphChase, which decouples the environment from algorithms, resolving incompatibility issues and enabling fair cross-evaluation of strategies on identical tasks.
2. Benchmark Establishment: Integration of multiple deep learning-based algorithms within a unified framework, providing reliable baselines and establishing performance metrics across diverse game configurations.
3. Revealing the Sim-to-Real Gap: Extensive experiments demonstrating that current approaches face significant limitations in scalability and robustness, particularly suffering performance degradation when deployed on weighted road networks compared to unweighted ones.

Experimental Results

The authors conducted experiments on a server with 48-core CPUs and 8 NVIDIA A30 GPUs to validate the platform and evaluate algorithms.

• Reproducibility and Correctness: GraphChase successfully reproduced results from original literature (Pretrained PSRO, Grasper, NSGZero, NSG-NFSP, CFR-MIX) on 5x5 and 7x7 grid graphs. The platform resolved inefficiencies in original codebases (e.g., Grasper), resulting in better training performance while maintaining consistent logic.
• Computational Efficiency: GraphChase improved overall sampling throughput by 1.38x and accelerated best-response computation for evaders (1.96x) and pursuers (1.72x) compared to original implementations, attributed to vectorized environment design.
• Real-World Topology Benchmarks: Testing on six real-world maps (Singapore, Manhattan, Mumbai, etc.) revealed performance variance. Algorithms achieved high utility in some topologies but struggled in complex environments like Manhattan and Times Square, characterized by high node/edge counts and extended time horizons.
• Robustness Evaluation:
  • Horizon Shift: Policies trained on $T=4$ showed significant utility drops when tested on $T=8$, indicating limited robustness to time horizon changes.
  • Edge Weight Variations: Policies trained on unweighted graphs suffered significant performance degradation when tested on weighted graphs, underscoring a lack of robustness to edge-cost heterogeneity.
• Scalability: Existing algorithms failed to train on a 100x100 grid, and even 30x30 grids stalled due to the exponential explosion of path enumeration required for decision-making. This highlights a scalability barrier for current solvers.
• Step-wise Policy Execution: Experiments on the Mumbai map (unweighted and weighted) demonstrated that GraphChase can train and evaluate step-wise PPO policies. While heuristic defenders performed well against heuristic attackers, they struggled against PPO attackers, and PPO defenders showed low capture rates on weighted graphs, confirming the difficulty of learning on realistic weighted topologies.

Significance and Claims

The paper claims that GraphChase provides the first open-source platform dedicated to UNSGs, offering a flexible multiplayer game environment that bridges the gap between theoretical game solving and realistic urban security applications.

• Standardization: It lowers the entry barrier for UNSG research by providing a unified interface, fostering a community focused on scalable and realistic security challenges.
• Realistic Modeling: By supporting weighted graphs and hybrid decision-making, the platform captures the dynamic nature of real scenarios (e.g., traffic patterns) better than traditional unweighted models.
• Testbed for Multiplayer Games: The platform serves as a testbed for computing Nash Equilibria (NE) and Team-Maxmin Equilibria (TME) in complex multiplayer settings, applicable to broader domains like anti-poaching and adversarial team games.
• Identifying Limitations: The work explicitly quantifies the "sim-to-real" generalization gap, showing that current SOTA algorithms are not robust to weighted edge costs or large-scale networks, thereby motivating the development of new approaches that move away from global action space traversal.

The authors position GraphChase as a defensive planning and evaluation tool, intended to improve public safety strategies rather than aid in escape planning.