Solving Urban Network Security Games: Learning Platform, Benchmark, and Challenge for AI Research

Questions:

• To Question 2: Thank you for this important observation regarding the termination patterns in Figures 7 and 8. We acknowledge that this requires clarification.

  For all experiments, including both GraphChase and baseline implementations, we set a large maximum iteration count at the start of training. The earlier termination of the red lines in the figures is a direct result of GraphChase's improved computational efficiency as we explain above, allowing it to complete the whole iterations more rapidly than the baseline implementations.

  Regarding the specific cases presented in the first panels of Figures 7 and 8, we acknowledge that the data shown in our original submission only covered the results up to the point of convergence. Data after this point, which would have depicted a more stable convergence curve, was not included. We recognize that it may not have provided a complete view of the algorithms’ convergence trajectories. To address this, we have updated our results to include a more comprehensive depiction of the convergence process. We apologize for any confusion this omission may have caused and appreciate the opportunity to present more complete and accurate experimental results in Figures 7 and 8.

• To Question 3: We added experiments based on a $15\times 15$ grid graph and the Singapore map. The $15\times 15$ grid graph has been previously tested in CFR-MIX (Li et al., 2021), NSG-NFSP (Xue et al., 2021) and NSGZero (Xue et al., 2022). The Singapore map has been tested in NSG-NFSP (Xue et al., 2021), NSGZero (Xue et al., 2022), Pretrained PSRO (Li et al., 2023a) and Grasper (Li et al., 2024). These additional experiments can show the significance of GraphChase. The experimental results are detailed in Table 3 of the appendix.

We appreciate the reviewer's thoughtful critique and the opportunity to clarify our platform's contributions.

To Weaknesses:

The primary goal of GraphChase is not to propose a novel algorithm or demonstrate superior performance than existing work, but rather to provide a unified, open-source environment for training and testing for UNSGs. Our platform enables researchers to efficiently utilize existing algorithms, including NSGZero, NSG-NFSP, PretrainPSRO, and Grasper, for performance evaluation. This addresses a critical gap in solving UNSGs, which is why we submitted to the Datasets and Benchmarks track.

Since GraphChase aims to provide a unified simulation environment for existing algorithms, we focused on reproduction rather than algorithmic improvements. That's the reason GraphChase does not have significant improvements over the original algorithm. We optimized code structure and implementation, resulting in faster wall-clock convergence compared to the original implementations. This aligns with our objective of achieving comparable performance to the original implementations.

Concerning the systematic comparisons to the existing literature, we deliberately matched the experimental settings of the original papers to validate GraphChase's ability to reproduce their results. As our primary goal is to demonstrate equivalent performance to original implementations rather than surpassing them, we suppose our current experiments sufficiently validate this objective.

Our experiments also show that current algorithms still suffer performance and scalability issues in real-world settings. It suggests that substantial efforts are still required to develop effective and efficient algorithms for solving real-world UNSGs.

GraphChase supports a wide range of equilibrium concepts, including, but not limited to Nash Equilibrium. The platform allows researchers to explore and analyze diverse equilibrium types by integrating their custom solution algorithms. This flexibility distinguishes GraphChase from existing platforms, which typically lack support for such extensibility.

We look forward to the research community utilizing GraphChase as a collaborative tool for advancing UNSG research. Furthermore, we will provide more details about why it is faster and when to terminate in response to your subsequent questions.

Questions:

• To Question 1: We can detail the specific technical factors contributing to the improved performance:

  Our platform incorporates several technical enhancements that contribute to its faster performance in terms of the wall-clock time. First, GraphChase is developed based on Gymnasium, replacing the custom class implementations found in the original papers. This change results in faster simulation processes and eliminates redundant data copying operations, leading to improved efficiency.

  Additionally, we have implemented various code optimizations to enhance the platform's performance. These include improved data type conversions, such as using numpy-to-tensor conversions instead of list-to-tensor operations, which reduces processing time. We have also focused on enhancing memory management throughout the platform, resulting in more efficient resource utilization.

  Currently, different algorithms (such as NSGZero, PretrainPSRO, and Grasper) each implement their simulation environments differently. This requires researchers to rewrite substantial code to adapt their algorithms for comparison with existing methods. When using the original code to test games, we rewrote game-related code to fit the input data requirements of each algorithm. However, we did not make any modifications to the algorithmic implementations from the original papers.

  The algorithms implemented in our platform are direct reproductions of the original code provided by the respective papers, with no changes or improvements made to the algorithms themselves. The key difference is that in GraphChase, researchers only need to input graph adjacency list as parameters into the game generation function to enable the application of different algorithms. Therefore, the primary contribution of GraphChase lies in providing a standardized and unified testing environment, addressing the lack of platforms for UNSG research.

  To address the reviewer's concern about performance improvements, we added a detailed discussion in Appendix E comparing GraphChase's simulation speed with original implementations. The results show that GraphChase truly accelerates a single episode of simulation and the data-saving process for each algorithm.

  Hope our reply will clarify your concerns.

Questions:

3. To Question 3: The extensive training times are primarily due to the limitations of the current algorithms rather than platform inefficiencies. Let me elaborate on some factors contributing to these computational demands:

   • Grasper and Pretrained PSRO: These algorithms require extensive training to generate the best responses in each iteration. Our platform's current implementations require $10^5$ episode simulations(same as the original paper) to gather sufficient data for RL training. This sampling requirement is inherent to the PSRO methodology.

   • NSGZero: Similar to AlphaGo's approach, it employs Monte Carlo Tree Search. Requires extensive tree exploration to generate effective policies. The computational intensity is intrinsic to the search-based nature of the algorithm.

   Other implemented algorithms similarly require substantial data sampling for effective training.

   We also note that the significant training time requirements, even for relatively small games (e.g., $5\times 5$ grid), represent a broader challenge in the field of UNSGs. Actually, it is one of the reasons that we develop the GraphChase platform.

   In addition, our new Appendix E shows that our platform GraphChase runs faster than existing implemented environments.

   We aim to provide researchers with a standardized environment for algorithm development and testing. We hope that our platform can enable researchers to focus on algorithmic design that could potentially reduce these training times and improve computational efficiency, rather than spending time on environment implementation details.

4. To Question 4: The simplified assumptions about criminal strategies primarily serve to facilitate convergence analysis due to the hardness of computing the evader's best response. Modeling both criminals and pursuers as learning agents presents a practical challenge: As demonstrated in NSG-NFSP (Xue et al., 2021), when criminals are modeled as learning agents, they tend to spend considerable time exploring invalid paths (those not leading to targets) before discovering optimal strategies. This results in:

   • Training inefficiency due to pursuers learning against suboptimal opponents
   • System instability during the learning process

   These findings have influenced subsequent works, including NSGZero, Pretrained PSRO, and Grasper, to adopt similar modeling approaches for criminal strategies. That's the reason that our current testing algorithms follow the same settings.

   However, our platform fully supports the implementation of criminals as learning agents, a feature that is not supported in the original papers. Researchers can integrate their own training algorithm and criminal agent designs into our simulator. We truly hope that our GraphChase is a useful tool for advancing UNSG research by enabling the development and testing of more sophisticated criminal strategy models.

Questions:

1. To Question 1: Let us explain how we arrived at the probability of 0.5 under the Nash equilibrium:

   On the left side of Figure 5, the evader has four potential exit nodes. The calculation considers several key factors:

   Exit Node Accessibility:

   • Two exit nodes (bottom-left and bottom-right) have the shortest paths longer than 3 steps for the evader
   • These same exits can be reached by pursuers in exactly 3 steps
   • Due to rational decision-making, the evader will avoid these exits as capture would be certain

   Viable Exit Options:

   • This leaves two viable exit nodes for the evader
   • Only the pursuer in the top-left corner can reach either of these exits within 3 steps
   • Both exits have equal utility for both the evader and the pursuer

   Probability Calculation:

   • The evader rationally chooses between the two viable exits with equal probability (1/2 for each)
   • For each exit, the probability of being caught depends on the pursuer choosing the same exit (1/2)
   • The total probability is calculated as: 2 exits × (1/2 probability of choosing each exit) × (1/2 probability of pursuer choosing the same exit) = 0.5

   Hope our reply will clarify your concerns.

2. To Question 2: Our platform incorporates several technical enhancements that contribute to its faster performance in terms of the wall-clock time. First, we have adopted the Gymnasium for game simulation, replacing the custom class implementations found in the original papers. This change results in faster simulation processes and eliminates redundant data copying operations, leading to improved efficiency.

   Additionally, we have implemented various code optimizations to enhance the platform's performance. These include improved data type conversions, such as using numpy-to-tensor conversions instead of list-to-tensor operations, which reduces processing time. We have also focused on enhancing memory management throughout the platform, resulting in more efficient resource utilization.

   From the perspective of wall-clock time, this indeed accelerates the convergence speed. However, it's crucial to note that in terms of the number of training iterations required for convergence, there is no significant improvement. For instance, if the original code necessitates sampling $10^4$ episodes to initiate convergence, our platform's reproduced algorithms similarly require approximately the same number of training iterations. This consistency in training iterations is attributable to the fact that we have not altered the underlying algorithms themselves.

   This distinction highlights an important nuance: while GraphChase offers improved computational efficiency in the environment, it does not change the sample efficiency or learning process of the implemented algorithms. Our platform's primary contribution lies in providing a more efficient simulation environment, rather than enhancing the algorithmic performance itself.

Weaknesses:

To Weakness 3: We would like to clarify the scope and positioning of UNSGs within the pursuit-evasion games domain.

While pursuit-evasion games encompass various scenarios, UNSGs represent a specific subset with distinct characteristics. UNSGs are specifically focused on scenarios with discrete observation and action spaces, chasing within a finite time horizon. In contrast, existing pursuit-evasion game benchmarks like Avalon, mentioned in our related work, are designed to simulate biological survival skills (from basic actions like eating to complex behaviors like hunting and navigation). In the revised version, we added more details about existing platforms SIMPE and Avalon, and highlighted the difference between them and our platform. Its problem settings do not belong to UNSGs.

Our related work discussion (L437-460) examines various pursuit-evasion scenarios that can be modeled as UNSGs. These works, while valuable, do not provide a platform for UNSGs. So we do not conduct experimental comparisons with GraphChase.

Regarding existing benchmarks (discussed in L462-478), we provide a brief overview of these benchmarks and explain why they are not suitable for UNSGs. For instance, MARBLER primarily simulates real-world robot behavior, while SIMPE operates in continuous state space and imposes restrictions on the behavior patterns of both pursuers and evaders. These limitations make existing benchmarks unsuitable for studying UNSGs.

So the motivation behind developing GraphChase is precisely to address this gap by providing a platform and benchmark tailored for research on UNSGs. Thank you for your suggestion. We added more comparisons in the related work to clarify the differences between GraphChase and the current platforms for pursuit-evasion games, which we believe will aid in the readers' understanding.

To Weakness 4: We appreciate the reviewer's comment about platform usability and interaction documentation.

We deliberately chose Gymnasium as the foundational framework for GraphChase because it is widely recognized and utilized in the DRL community. This design choice significantly reduces the learning curve for researchers who are already familiar with Gymnasium's interfaces and conventions.

Regarding platform usage and interaction details, we have provided comprehensive documentation and examples in our GitHub repository. We added a brief introduction about how to use our platform to Appendix F.

Thank you for bringing this to our attention. These additions will make the paper more complete and useful for potential users of our platform.

Thank you for your thoughtful review! Please find point-by-point replies below:

Weaknesses:

To Weakness 1: We would like to clarify two key aspects of GraphChase:

Regarding information levels, our platform allows researchers to configure game environments according to their algorithmic requirements. This flexibility is demonstrated in our current implementations: CFR-MIX makes decisions without considering evader history, while PretrainPSRO incorporates historical evader information. This exemplifies GraphChase's capability to support varying information levels. That is the information level requirements are determined by the algorithms themselves. Currently, there are only a few learning algorithms for UNSGs and the results of them are shown in our work.

Concerning graph structures, GraphChase supports the removal of edges between any connected nodes to simulate different real-world scenarios. This feature has been tested with the Grasper algorithm, as it requires the generation of diverse graph structures. Furthermore, GraphChase allows researchers to customize various graph structures by providing an adjacency list as a parameter to our game generation function.

We designed GraphChase to offer maximum flexibility through user-defined graph structures and customizable information levels. We hope that our platform serves as a versatile tool for researchers, enabling them to efficiently implement and evaluate various algorithms.

To Weakness 2: We would like to clarify several aspects of our platform's implementation and evaluation methodology:

Regarding finding the evader's optimal strategy, our current implementations follow the simplified evader modeling approach used in existing UNSG research. This simplification means that it only considers finding the optimal strategy for the pursuer, and directly computes the criminals' best responses as evaluation.

The computational complexity of UNSGs presents significant challenges, as the strategy space of players cannot be enumerated even under simplified conditions where the time dynamics are ignored (Jain et al., 2011). That is, even if the evader's strategy is simplified, the problem of solving UNSGs is still NP-hard (Jain et al., 2011), which is discussed in Section 2.3 of the paper.

We also note the limitations of solely computing the pursuer's optimal strategy during training, as evidenced by the experimental results in Table 1. The pursuer's performance notably deteriorates when confronting evader strategies not encountered during training. This observation was one of the key motivations behind developing GraphChase. So our platform enables researchers to model evaders with any strategy. Specifically, GraphChase allows researchers to customize evader decision-making mechanisms such as implementing them as learning algorithms to find optimal strategies.

Due to the computational complexity in evaluation, we sample 1000 episodes to calculate the pursuers' worst case utility. At the beginning of each episode, the evader selects an available path based on the best response i.e., enumerate all paths to select the best path. During each time step, the evader moves according to this predetermined path. The pursuer's performance is evaluated based on the average success rate across these 1000 episodes.

As we discussed in Section 2.3, scalability is the key challenge for solving UNSGs. Our GraphChase platform has been designed to facilitate and address these challenges by providing a large-scale game environment.

Thank you for your review. We would appreciate your feedback on whether our response has adequately addressed your concerns. If there are any remaining questions or points that need further clarification, we would be happy to provide additional information.

Thank you for your insightful question regarding strategy evaluation methods. We appreciate the opportunity to elaborate on our approach to assessing pursuer strategies and equilibrium computation.

Our platform supports the pursuer's strategy evaluation through four methods:

1. Pseudo Worst-Case Utility

This method evaluates the performance of the pursuer's strategy by first selecting an exit according to the best response and then choosing a path within that exit. Due to the randomness in path selection, it is referred to as pseudo worst-case utility.

2. Worst Case Utility

This method evaluates the performance of the pursuer's strategy by enumerating every feasible path and using the path with the lowest reward as the worst-case utility. When the number of paths is vast and difficult to enumerate, it will use the first method to approximate worst-case utility.

3. Strategy Robustness Testing

We assess strategy robustness by varying the maximum time horizon, which enables a comprehensive examination of the pursuer strategy's performance against diverse evader behaviors. As demonstrated in our experimental setup, this approach provides insights into the strategy's adaptability across different scenario complexities.

4. Exploitability Testing

This method systematically evaluates the pursuer strategy's vulnerability by training an adversarial evader strategy using reinforcement learning while maintaining a fixed pursuer strategy.

Regarding equilibrium assessment, our platform supports calculating the NashConv metric to measure convergence. This metric is calculated as:

, where pursuer_br_value and evader_br_value denote the values of their respective best response strategies. Since we provided the aforementioned methods for strategy evaluation, there are several ways to assess NashConv. Users can utilize (Pseudo) Worst-Case Utility or various training algorithms to calculate the value of best response strategies. The detailed usage methods can be found on GraphChase repository.

The evaluation method outlined in Section 3.2 of our paper is consistent with prior works on UNSG, including CFR-MIX (Li et al., 2021), NSG-NFSP (Xue et al., 2021), NSGZero (Xue et al., 2022), Pretrained PSRO (Li et al., 2023a), and Grasper (Li et al., 2024). To ensure a fair and direct comparison with these previous studies, we did not include alternative evaluation methods in the paper.

However, our platform fully supports additional evaluation methods as mentioned above. These methods have been implemented at the code level, so we have provided detailed example instructions in the usage guide available on GraphChase Platform. The guide provides detailed instructions on how users can leverage these various assessment techniques to evaluate strategies and analyze equilibrium characteristics.

We hope this detailed explanation addresses your concerns and provides clarity on our approach to strategy and algorithm evaluation.

To C3: In team adversarial games, TMECom is NE discussed in Section 2. We have provided explanations in the relevant sections of the paper to prevent any misunderstandings for the readers.

To C4: Our platform is designed to be format-agnostic when it comes to graph data input. As long as users can obtain the adjacency list representation of their graph, regardless of the original format (e.g., GraphML, XML, or other standard graph formats), they can easily integrate it into our platform. Specifically, users only need to pass the adjacency list as parameters to our platform's game generation function, enabling them to customize their own games. To improve the clarity of our paper, we added a detailed explanation of supported data formats in Section 3.1.

To C5: Our platform incorporates several technical enhancements that contribute to its faster performance in terms of the wall-clock time. First, we have adopted the Gymnasium for game simulation, replacing the custom class implementations found in the original papers. This change results in faster simulation processes and eliminates redundant data copying operations, leading to improved efficiency.

Additionally, we have implemented various code optimizations to enhance the platform's performance. These include improved data type conversions, such as using numpy-to-tensor conversions instead of list-to-tensor operations, which reduces processing time. We have also focused on enhancing memory management throughout the platform, resulting in more efficient resource utilization.

To address the readers' concern about performance improvements, we added a detailed discussion in Appendix E comparing GraphChase's simulation speed with original implementations.

To C6: We agree that using "pursuer" and "evader" better reflects the abstract nature of our mathematical model and helps avoid potential misinterpretations about real-world applications.

We have revised the paper as follows: 1. Use "pursuer" and "evader" as the primary terminology throughout the theoretical discussions and model descriptions; 2. Maintain references to "police officers" and "criminals" only in specific illustrative examples where concrete scenarios help readers understand the practical applications of the abstract model.

Thank you for your thoughtful review! Please find point-by-point replies below:

Weaknesses:

To W1: We would like to clarify that our work primarily aims to provide a standardized platform for UNSG research and algorithm development, that's why we submitted to the Datasets and Benchmarks track.

Current UNSG-focused works (NSGZero, NSG-NFSP, Pretrained PSRO, Grasper, and CFR-MIX) implement environments differently, requiring researchers to rewrite substantial code to adapt to each algorithm's input requirements when conducting comparative studies. GraphChase addresses this challenge by integrating multiple into our platform. Researchers need only input the graph structure once to evaluate multiple algorithms' performance. This not only enhances research efficiency but also ensures fair algorithm comparisons by resolving implementation inconsistencies across different works.

One of the key features of GraphChase is its flexibility, allowing users to customize various game variants. We believe that the definition of game variants should be determined by the algorithm designers rather than by us, in order to support different algorithms training on the same graph structure. Our platform provides all state information at each simulation step, including all pursuer and evader observations. Researchers can freely define how their algorithms utilize this information. For instance, while CFR-MIX doesn't consider evader history, PretrainPSRO incorporates historical evader information in pursuer action selection. Despite these methodological differences, our platform requires only a single input of the game's topological structure to enable training and testing across different algorithms and game variants on the same game structure.

Furthermore, regarding graph topologies, our platform supports arbitrary graph structures for UNSG problems. Researchers can define any graph topology (grid-based or otherwise) by simply providing the adjacency list to our platform's game generation function. The platform architecture is intentionally designed to accommodate various equilibrium concepts as shown in the discussion. Researchers can leverage our platform to study different types of equilibria by implementing their own algorithms.

Our experiments show that current algorithms still suffer performance and scalability issues in real-world settings. It suggests that substantial efforts are still required to develop effective and efficient algorithms for solving real-world UNSGs.

We envision GraphChase as a unified and flexible platform that will advance research progress in UNSG problems.

To W2: We have revised the paper to adopt a more neutral and precise tone, removing subjective descriptors like "advanced" and "pivotal." Thank you for helping us maintain appropriate scientific writing standards.

Questions:

To C1: Thank you for your question regarding the definition of 'caught'. We acknowledge that we overlooked this definition in the original paper. To clarify: The evader is considered caught if the evader and any of the pursuers occupy the same point at any time within the maximum time horizon. We have now added this precise definition to Section 2.1.

To C2: We appreciate your attention to detail.

1. Update $E_{xit}$ to $E_{exit}$.
2. N(v) specifically denotes the set of neighbours of node v. We have clarified this definition in the relevant sections of the paper to avoid any ambiguity.
3. Correct $R$ to $\mathbb{R}$.

Thank you for your valuable feedback!

We have expanded our experimental validation by incorporating a variety of scenarios used in the UNSG domain (Xue et al. 2021; 2022; Li et al. 2023a; 2024) in Section 4.2 (details are in Appendix D), which include larger $15\times 15$ grid structures and real-world maps based on Singapore and Manhattan. The $15\times 15$ grid network represents the randomly generated network, and two real-world networks represent different topological structures in real-world cities. To our knowledge, the Singapore and Manhattan maps represent the most realistic and complex graph structures currently used in the UNSG algorithm research. We believe that our extensive testing on Singapore and Manhattan maps demonstrates GraphChase's capability to handle real-world problems.

Regarding your point about testing communication between agents, to the best of our knowledge, no existing learning algorithms for solving UNSGs address this specific aspect. This limits our ability to conduct comparative experiments in this variant. However, GraphChase provides a standardized testing platform for researchers interested in exploring such scenarios. We hope that GraphChase will be a foundation to advance future UNSG research.

We thank the reviewer for constructive advice.

Weaknesses

1. To Weakness 1: We added user-controllable parameters in Appendix B.

2. To Weakness 2: As you correctly mentioned, our platform functions primarily as a simulator. While our current testing algorithms focus on Nash Equilibrium solutions, it's important to clarify that the platform itself is equilibrium-concept agnostic.

   The platform serves as a testing and training environment, providing researchers for algorithm development and evaluation. Researchers interested in studying Markov equilibrium or subgame perfect equilibrium would need to implement their own solution algorithms. The platform's role is to provide the environmental framework within which these various equilibrium concepts can be explored, rather than being tied to any specific equilibrium solution concept.

   One of our platform's aims is to allow researchers to implement and test different solution concepts according to their research needs. So the simulator's architecture is intentionally separated from the specifics of equilibrium computation, making it a versatile tool for studying various game-theoretic solution concepts.

3. To Weakness 3: Our platform is designed with extensibility as a core feature, allowing researchers to incorporate additional real-world elements into their models easily. The key to this flexibility lies in the method of generating games. Researchers can design and input their own adjacency list as parameters to our platform's game generation function, enabling customized environment modeling for specific research requirements.

   What's more, the graph implementation is based on the NetworkX library, so our platform enables researchers to incorporate diverse graph attributes, such as edge-specific travel times and other details to model real-world scenarios.

   The platform's modular design ensures that such modifications can be implemented without requiring changes to the core system architecture.

4. To Weakness 4: SIMPE is a Matlab-based platform for simulating Pursuit-Evasion games which has several limitations. First, it outputs the coordinates of the pursuer and evader in the x-y plane, with a continuous position space. So it is difficult to model the topological structure of actual UNSGs. Secondly, it does not take time information into account, overlooking the temporal constraints inherent in UNSG problems. Finally, it offers only three predefined strategies for pursuers and evaders, which substantially restricts the platform's extensibility.

   Avalon, on the other hand, is designed to simulate biological survival skills (from basic actions like eating to complex behaviors like hunting and navigation). It provides diverse procedural 3D environments where agents must survive which is not suitable for model UNSGs. We expanded our comparison of GraphChase with SIMPE and Avalon in the related work section.

   Our GraphChase platform is purposefully designed to model and simulate real-world criminal prevention scenarios, enabling the application of developed algorithms to urban security challenges. We deliberately choose Gymnasium to implement our platform, as many DRL researchers are already familiar with this environment, thus reducing the learning time. Additionally, our implementation of Gymnasium's SyncVector functions introduces parallel simulation capabilities, while Gymnasium's render functions enable researchers to better understand their algorithms' real-world performance. These features are not present in the other platforms. We hope that GraphChase can be a valuable tool for researchers to design their own algorithms.