Resumo Técnico: GraphChase: Uma Plataforma e Benchmark para Jogos de Segurança em Redes Urbanas

Definição do Problema

Os Jogos de Segurança em Redes Urbanas (UNSGs) modelam cenários onde o cumprimento da lei (perseguidores) deve alocar estrategicamente recursos limitados para interceptar criminosos (evadidores) que escapam através de redes viárias urbanas. Embora progressos significativos tenham sido feitos em jogos de soma zero entre dois jogadores, resolver UNSGs apresenta desafios únicos devido à sua natureza como jogos multiplayer envolvendo cooperação, competição e informação imperfeita.

O campo enfrenta atualmente três limitações primárias:

1. Falta de Padronização: A ausência de uma plataforma experimental unificada leva a implementações incompatíveis, estruturas de dados inconsistentes e dificuldade na avaliação cruzada de algoritmos.
2. Compromisso entre Realismo e Escalabilidade: Métodos baseados em otimização frequentemente dependem de Programação Linear Inteira Mista (MILP) para modelar tempos de viagem ponderados, mas falham em escalar para redes grandes. Por outro lado, os métodos de aprendizado de última geração (SOTA) tipicamente simplificam os ambientes para grafos não ponderados para facilitar o treinamento, ignorando a heterogeneidade dos segmentos de estrada do mundo real (ex: variações de comprimento e limites de velocidade).
3. Lacuna Sim-to-Real: As abordagens existentes lutam com robustez e escalabilidade quando implantadas em redes ponderadas, destacando uma lacuna de generalização entre ambientes de treinamento simplificados e condições realistas.

Metodologia: A Plataforma GraphChase

Para enfrentar esses desafios, os autores introduzem o GraphChase, uma plataforma de código aberto projetada para padronizar a pesquisa em UNSG e suportar simulações em ambientes realistas. A plataforma emprega uma arquitetura modular que desacopla o ambiente, os agentes e os solvers.

Componentes Principais

1. Módulo de Jogo (Ambiente):

   • Representação de Grafo: Modela redes viárias como grafos $G=(V, E, \omega)$, suportando arestas direcionadas e não direcionadas. Lida com arestas ponderadas onde $\omega(u, v)$ representa o tempo de viagem contínuo.
   • Representação de Estado: Os agentes estão localizados em vértices ou ao longo de arestas, representados como tuplas $(u, v, \delta)$, onde $\delta$ é a distância do vértice $u$. Isso permite o movimento contínuo dentro de um framework de tempo discreto.
   • Dinâmica: Utiliza um mecanismo de tomada de decisão híbrido onde os agentes tomam decisões no início dos passos de tempo e instantaneamente ao atingir vértices. O jogo termina após captura (distância $\le \epsilon$), fuga (atingir nós de saída) ou timeout ($T$).
   • Estruturas de Informação: Suporta quatro cenários de informação, variando de observabilidade total a observabilidade parcial para perseguidores e evadidores, e permite a tomada de decisão independente ou coordenada entre perseguidores.

2. Módulo de Agente:

   • Fornece uma interface unificada para representação de política (neural ou heurística) e coleta de trajetórias.
   • Introduz Runners para encapsular a interação com o ambiente, pré-processamento e construção de lotes (batches), suportando rollouts vetorizados para coleta eficiente de dados.
   • Suporta aprendizado teórico-dos-jogos iterativo, incluindo clonagem de política e persistência para frameworks como Policy-Space Response Oracles (PSRO).

3. Módulo de Solver:

   • Implementa otimizadores plug-and-play (ex: PPO, MAPPO) para treinamento de melhor resposta (best-response).
   • Suporta frameworks de aprendizado teórico-dos-jogos, especificamente o PSRO, decompondo-o em Oráculos de Melhor Resposta (RL ou heurística) e Meta-Solvers (ex: Dinâmica de Replicador Projetado).
   • Permite a implementação de solvers customizados sem modificar a lógica central do jogo.

Protocolo de Benchmark

O GraphChase estabelece um protocolo de benchmark padronizado incluindo:

• Algoritmos: Integração de algoritmos SOTA incluindo CFR-MIX, NSG-NFSP, NSGZero, Pretrained PSRO e Grasper.
• Modos de Execução: Suporta execução baseada em caminhos (evadidores selecionam um alvo de saída e um caminho antes do jogo) e execução passo a passo (agentes amostram ações em cada ponto de decisão).
• Métricas de Avaliação:
  • Utilidade do Pior Caso: Enumera todos os caminhos do evadidor para encontrar a utilidade mínima do perseguidor.
  • Utilidade Pseudo Pior Caso: Aproxima o pior caso amostrando caminhos para cada saída para lidar com grafos grandes.
  • Visualização: Ferramentas para analisar trajetórias e processos de decisão.

Contribuições Principais

1. Plataforma Unificada: Desenvolvimento do GraphChase, que desacopla o ambiente dos algoritmos, resolvendo problemas de incompatibilidade e permitindo a avaliação cruzada justa de estratégias em tarefas idênticas.
2. Estabelecimento de Benchmark: Integração de múltiplos algoritmos baseados em aprendizado profundo dentro de um framework unificado, fornecendo bases confiáveis e estabelecendo métricas de desempenho através de diversas configurações de jogo.
3. Revelação da Lacuna Sim-to-Real: Experimentos extensos demonstrando que as abordagens atuais enfrentam limitações significativas em escalabilidade e robustez, sofrendo particularmente de degradação de desempenho quando implantadas em redes viárias ponderadas em comparação com as não ponderadas.

Resultados Experimentais

Os autores conduziram experimentos em um servidor com CPUs de 48 núcleos e 8 GPUs NVIDIA A30 para validar a plataforma e avaliar algoritmos.

• Reprodutibilidade e Correção: O GraphChase reproduziu com sucesso os resultados da literatura original (Pretrained PSRO, Grasper, NSGZero, NSG-NFSP, CFR-MIX) em grafos de grade 5x5 e 7x7. A plataforma resolveu ineficiências nos códigos originais (ex: Grasper), resultando em melhor desempenho de treinamento enquanto mantém a lógica consistente.
• Eficiência Computacional: O GraphChase melhorou a taxa de amostragem geral em 1.38x e acelerou a computação de melhor resposta para evadidores (1.96x) e perseguidores (1.72x) em comparação com as implementações originais, atribuído ao design de ambiente vetorizado.
• Benchmarks de Topologia do Mundo Real: Testes em seis mapas do mundo real (Singapura, Manhattan, Mumbai, etc.) revelaram variação de desempenho. Os algoritmos alcançaram alta utilidade em algumas topologias, mas tiveram dificuldades em ambientes complexos como Manhattan e Times Square, caracterizados por altos números de nós/arestas e horizontes de tempo estendidos.
• Avaliação de Robustez:
  • Deslocamento de Horizonte: Políticas treinadas em $T=4$ mostraram quedas significativas de utilidade quando testadas em $T=8$, indicando robustez limitada a mudanças no horizonte de tempo.
  • Variações de Peso de Aresta: Políticas treinadas em grafos não ponderados sofreram degradação significativa de desempenho quando testadas em grafos ponderados, ressaltando a falta de robustez à heterogeneidade de custos de aresta.
• Escalabilidade: Algoritmos existentes falharam ao treinar em uma grade 100x100, e até mesmo grades 30x30 estagnaram devido à explosão exponencial de enumeração de caminhos necessária para a tomada de decisão. Isso destaca uma barreira de escalabilidade para os solvers atuais.
• Execução de Política Passo a Passo: Experimentos no mapa de Mumbai (não ponderado e ponderado) demonstraram que o GraphChase pode treinar e avaliar políticas PPO passo a passo. Enquanto defensores heurísticos performaram bem contra atacantes heurísticos, eles tiveram dificuldades contra atacantes PPO, e defensores PPO mostraram baixas taxas de captura em grafos ponderados, confirmando a dificuldade de aprender em topologias ponderadas realistas.

Significância e Alegações

O artigo afirma que o GraphChase fornece a primeira plataforma de código aberto dedicada a UNSGs, oferecendo um ambiente de jogo multiplayer flexível que preenche a lacuna entre a resolução teórica de jogos e aplicações de segurança urbana realistas.

• Padronização: Reduz a barreira de entrada para a pesquisa em UNSG ao fornecer uma interface unificada, fomentando uma comunidade focada em desafios de segurança escaláveis e realistas.
• Modelagem Realista: Ao suportar grafos ponderados e tomada de decisão híbrida, a plataforma captura a natureza dinâmica de cenários reais (ex: padrões de tráfego) melhor do que os modelos tradicionais não ponderados.
• Testbed para Jogos Multiplayer: A plataforma serve como um banco de testes para computar Equilíbrios de Nash (NE) e Equilíbrios de Team-Maxmin (TME) em cenções multiplayer complexas, aplicáveis a domínios mais amplos como combate à caça ilegal e jogos de equipe adversariais.
• Identificação de Limitações: O trabalho quantifica explicitamente a lacuna de generalização "sim-to-real", mostrando que os algoritmos SOTA atuais não são robustos a custos de aresta ponderados ou redes de grande escala, motivando o desenvolvimento de novas abordagens que se afastem da travessia de espaço de ação global.

Os autores posicionam o GraphChase como uma ferramenta de planejamento defensivo e avaliação, destinada a melhorar as estratégias de segurança pública em vez de auxiliar no planejamento de fuga.