Resumen Técnico: GraphChase: Una Plataforma y Benchmark para Juegos de Seguridad en Redes Urbanas

Definición del Problema

Los Juegos de Seguridad en Redes Urbanas (UNSGs, por sus siglas en inglés) modelan escenarios donde las fuerzas del orden (perseguidores) deben asignar estratégicamente recursos limitados para interceptar criminales (evadidores) que escapan a través de redes de carreteras urbanas. Aunque se ha progresado significativamente en juegos de suma cero de dos jugadores, resolver los UNSGs presenta desafíos únicos debido a su naturaleza como juegos multijugador que involucran cooperación, competencia e información imperfecta.

El campo enfrenta actualmente tres limitaciones principales:

1. Falta de Estandarización: La ausencia de una plataforma experimental unificada conduce a implementaciones incompatibles, estructuras de datos inconsistentes y dificultad para la evaluación cruzada de algoritmos.
2. Compromiso entre Realismo y Escalabilidad: Los métodos basados en la optimización suelen depender de la Programación Lineal Entera Mixta (MILP) para modelar tiempos de viaje ponderados, pero no logran escalar a redes grandes. Por el contrario, los métodos de aprendizaje de vanguardia (SOTA) suelen simplificar los entornos a grafos no ponderados para facilitar el entrenamiento, ignorando la heterogeneidad de los segmentos de carretera del mundo real (por ejemplo, variaciones en longitudes y límites de velocidad).
3. Brecha Sim-to-Real: Los enfoques existentes tienen dificultades con la robustez y la escalabilidad cuando se despliegan en redes ponderadas, lo que resalta una brecha de generalización entre los entornos de entrenamiento simplificados y las condiciones realistas.

Metodología: La Plataforma GraphChase

Para abordar estos desafíos, los autores presentan GraphChase, una plataforma de código abierto diseñada para estandarizar la investigación en UNSG y soportar simulaciones en entornos realistas. La plataforma emplea una arquitectura modular que desacopla el entorno, los agentes y los solvers.

Componentes Principales

1. Módulo de Juego (Entorno):

   • Representación de Grafos: Modela las redes de carreteras como grafos $G=(V, E, \omega)$, soportando aristas dirigidas y no dirigidas. Gestiona aristas ponderadas donde $\omega(u, v)$ representa el tiempo de viaje continuo.
   • Representación de Estado: Los agentes se ubican ya sea en vértices o a lo largo de las aristas, representados como tuplas $(u, v, \delta)$, donde $\delta$ es la distancia desde el vértice $u$. Esto permite el movimiento continuo dentro de un marco de tiempo discreto.
   • Dinámica: Utiliza un mecanismo de toma de decisiones híbrido donde los agentes toman decisiones al inicio de los pasos de tiempo y de forma instantánea al alcanzar los vértices. El juego termina tras la captura (distancia $\le \epsilon$), la escape (alcanzar nodos de salida) o el tiempo límite ($T$).
   • Estructuras de Información: Soporta cuatro escenarios de información que van desde la observabilidad total hasta la observabilidad parcial tanto para perseguidores como para evadidores, y permite la toma de decisiones independiente o coordinada entre los perseguidores.

2. Módulo de Agente:

   • Proporciona una interfaz unificada para la representación de políticas (neuronal o heurística) y la recolección de trayectorias.
   • Introduce Runners para encapsular la interacción con el entorno, el preprocesamiento y la construcción de lotes, soportando rollouts vectorizados para una recolección de datos eficiente.
   • Soporta el aprendizaje iterativo de teoría de juegos, incluyendo el clonado de políticas y la persistencia para marcos como los Oráculos de Respuesta de Espacio de Políticas (PSRO).

3. Módulo de Solver:

   • Implementa optimizadores plug-and-play (por ejemplo, PPO, MAPPO) para el entrenamiento de mejor respuesta.
   • Soporta marcos de aprendizaje de teoría de juegos, específicamente PSRO, descomponiéndolo en Oráculos de Mejor Respuesta (RL o heurística) y Meta-Solvers (por ejemplo, Dinámica de Replicador Proyectada).
   • Permite la implementación de solvers personalizados sin modificar la lógica central del juego.

Protocolo de Benchmark

GraphChase establece un protocolo de benchmark estandarizado que incluye:

• Algoritmos: Integración de algoritmos SOTA incluyendo CFR-MIX, NSG-NFSP, NSGZero, Pretrained PSRO y Grasper.
• Modos de Ejecución: Soporta tanto la ejecución basada en rutas (los evadidores seleccionan una salida objetivo y una ruta antes del juego) como la ejecución paso a paso (los agentes muestrean acciones en cada punto de decisión).
• Métricas de Evaluación:
  • Utilidad del Peor Caso: Enumera todas las rutas de los evadidores para encontrar la utilidad mínima del perseguidor.
  • Utilidad Pseudo de Peor Caso: Aproxima el peor caso mediante el muestreo de rutas para cada salida para manejar grafos grandes.
  • Visualización: Herramientas para analizar trayectorias y procesos de decisión.

Contribuciones Clave

1. Plataforma Unificada: Desarrollo de GraphChase, que desacopla el entorno de los algoritmos, resolviendo problemas de incompatibilidad y permitiendo una evaluación cruzada justa de estrategias en tareas idénticas.
2. Establecimiento de Benchmark: Integración de múltiples algoritmos de aprendizaje profundo dentro de un marco unificado, proporcionando bases fiables y estableciendo métricas de rendimiento a través de diversas configuraciones de juego.
3. Revelación de la Brecha Sim-to-Real: Experimentos extensos demuestran que los enfoques actuales enfrentan limitaciones significativas en escalabilidad y robustez, sufriendo particularmente una degradación de rendimiento cuando se despliegan en redes de carreteras ponderadas en comparación con las no ponderadas.

Resultados Experimentales

Los autores realizaron experimentos en un servidor con CPUs de 48 núcleos y 8 GPUs NVIDIA A30 para validar la plataforma y evaluar los algoritmos.

• Reproducibilidad y Corrección: GraphChase reprodujo con éxito los resultados de la literatura original (Pretrained PSRO, Grasper, NSGZero, NSG-NFSP, CFR-MIX) en grafos de rejilla de 5x5 y 7x7. La plataforma resolvió ineficiencias en los códigos originales (por ejemplo, Grasper), resultando en un mejor rendimiento de entrenamiento manteniendo una lógica consistente.
• Eficiencia Computacional: GraphChase mejoró la capacidad de muestreo general en un 1.38x y aceleró la computación de la mejor respuesta para evadidores (1.96x) y perseguidores (1.72x) en comparación con las implementaciones originales, debido al diseño de entorno vectorizado.
• Benchmarks de Topología del Mundo Real: Las pruebas en seis mapas del mundo real (Singapur, Manhattan, Mumbai, etc.) revelaron varianza en el rendimiento. Los algoritmos lograron una utilidad alta en algunas topologías, pero tuvieron dificultades en entornos complejos como Manhattan y Times Square, caracterizados por un alto número de nodos/aristas y horizontes de tiempo extendidos.
• Evaluación de Robustez:
  • Desplazamiento de Horizonte: Las políticas entrenadas con $T=4$ mostraron caídas significativas de utilidad cuando se probaron con $T=8$, indicando una robustez limitada ante cambios en el horizonte temporal.
  • Variaciones en el Peso de las Aristas: Las políticas entrenadas en grafos no ponderados sufrieron una degradación significativa de rendimiento al ser probadas en grafos ponderados, subrayando una falta de robustez ante la heterogeneidad de los costos de las aristas.
• Escalabilidad: Los algoritmos existentes fallaron al entrenar en una rejilla de 100x100, e incluso las rejillas de 30x30 se estancaron debido a la explosión exponencial de la enumeración de rutas requerida para la toma de decisiones. Esto resalta una barrera de escalabilidad para los solvers actuales.
• Ejecución de Política Paso a Paso: Los experimentos en el mapa de Mumbai (no ponderado y ponderado) demostraron que GraphChase puede entrenar y evaluar políticas PPO paso a paso. Mientras que los defensores heurísticos funcionaron bien contra atacantes heurísticos, tuvieron dificultades contra atacantes PPO, y los defensores PPO mostraron bajas tasas de captura en grafos ponderados, confirmando la dificultad de aprender en topologías ponderadas realistas.

Significación y Reivindicaciones

El artículo afirma que GraphChase proporciona la primera plataforma de código abierto dedicada a los UNSGs, ofreciendo un entorno de juego multijugador flexible que cierra la brecha entre la resolución de juegos teóricos y las aplicaciones de seguridad urbana realistas.

• Estandarización: Reduce la barrera de entrada para la investigación en UNSG al proporcionar una interfaz unificada, fomentando una comunidad centrada en desafíos de seguridad escalables y realistas.
• Modelado Realista: Al soportar grafos ponderados y toma de decisiones híbrida, la plataforma captura mejor la naturaleza dinámica de los escenarios reales (por ejemplo, patrones de tráfico) que los modelos tradicionales no ponderados.
• Banco de Pruebas para Juegos Multijugador: La plataforma sirve como banco de pruebas para computar Equilibrios de Nash (NE) y Equilibrios de Máximo-Equipo (TME) en entornos multijugador complejos, aplicables a dominios más amplios como la lucha contra la caza furtiva y los juegos de equipos adversarios.
• Identificación de Limitaciones: El trabajo cuantifica explícitamente la brecha de generalización "sim-to-real", mostrando que los algoritmos SOTA actuales no son robustos ante los costos de las aristas ponderadas o las redes de gran escala, lo que motiva el desarrollo de nuevos enfoques que se alejen del recorrido global del espacio de acciones.

Los autores posicionan a GraphChase como una herramienta de planificación y evaluación defensiva, destinada a mejorar las estrategias de seguridad pública en lugar de ayudar en la planificación de escapes.