Resumo Técnico: Busca em Árvore Guiada por Primitivas em Jogos de Perseguição-Evasão Multiagente

1. Formulação do Problema

O artigo aborda o desafio de computar políticas de equilíbrio de Nash em jogos de Perseguição-Evasão (PEGs) multiagentes em grafos. Nestes jogos, uma equipe de Perseguidores (Vermelho) tenta capturar uma equipe de Evadidores (Azul) antes que os Evadidores alcancem nós de saída designados. A dificuldade central reside no crescimento exponencial dos espaços de estados e ações conjuntas à medida que o número de agentes aumenta.

Abordagens existentes enfrentam um compromisso (trade-off):

• Métodos offline (ex: PSRO, MAPPO) treinam políticas offline, mas frequentemente carecem de adaptabilidade a comportamentos adversariais não vistos durante o treinamento e sofrem com alta complexidade de treinamento.
• Métodos de planejamento online (ex: MCTS) adaptam-se aos estados atuais, mas lutam contra os massivos fatores de ramificação inerentes aos jogos simultâneos de múltiplos agentes, tornando a busca profunda computacionalmente inviável.
• Métodos híbridos (ex: variantes de AlphaZero) frequentemente dependem da aprendizagem de aproximações precisas de valor/política, exigindo dados extensos, ou são limitados a cenários de dois jogadores.

O objetivo é desenvolver um framework escalável e robusto que combine a profundidade estratégica da computação de equilíbrio offline com a adaptabilidade da busca online.

2. Metodologia: Busca em Árvore Guiada por Primitivas (PGTS)

Os autores propõem a Busca em Árvore Guiada por Primitivas (PGTS), um framework híbrido que decompõe o complexo jogo multiagente em subjogos tratáveis offline e integra essas soluções em uma Busca em Árvore Monte Carlo de Movimentos Simultâneos (SM-MCTS) online.

2.1 Fase Offline: Subjogos Primitivos de Subequipes

Em vez de resolver o jogo completo diretamente, o PGTS pré-computa equilíbrios de Nash exatos para pequenos subjogos representativos envolvendo subconjuntos de agentes:

• 1v1: Um Perseguidor contra um Evadidor.
• 2v1: Dois Perseguidores contra um Evadidor.
  Estes são resolvidos usando iteração de valor de Shapley nos espaços de estados restritos ($V \times V$ e $V^2 \times V$). O resultado inclui políticas mistas ótimas ($\pi^*$) e funções de valor ($V^*$) para estas primitivas, que são armazenadas em cache para uso em tempo de execução.

2.2 Fase Online: Busca em Árvore

Em cada passo de tempo, o PGTS realiza uma busca em árvore a partir do estado conjunto atual. O algoritmo modifica o SM-MCTS padrão de duas maneiras críticas:

1. Expansão Guiada por Primitivas:
   Para mitigar o fator de ramificação exponencial, o algoritmo não expande todas as possíveis ações conjuntas. Em vez disso, utiliza as políticas primitivas offline para guiar a busca:

   • Para cada Evador, o algoritmo identifica seus $k_r$ Perseguidores mais próximos.
   • Ele amostra ações conjuntas para interações locais (grupos 1v1 e 2v1) baseando-se nas políticas de Nash pré-computadas ($\pi^*_{1v1}, \pi^*_{2v1}$).
   • Estas amostras formam um conjunto de ações candidatas restrito, aumentado com ações heurísticas de caminho mais curto e exploração aleatória para evitar o comprometimento excessivo com os priors.

2. Estimativa de Valor de Folha via Surrogates de Subequipes:
   Em vez de executar simulações (rollouts) de Monte Carlo custosas até o horizonte, o algoritmo estima o valor dos nós folha utilizando as funções de valor primitivas offline.

   • O algoritmo aproxima o valor do jogo completo decompondo o estado atual em um conjunto de subequipes primitivas.
   • Emprega uma estratégia de correspondência sequencial: Primeiro, ele associa agentes de forma gananciosa (greedy) para formar interações 2v1 (capturando coordenação de ordem superior, como o cerco conjunto) usando o algoritmo de Hungariana na matriz de valor 2v1.
   • Os agentes restantes são combinados em interações 1v1.
   • O valor da folha é a soma agregada destes valores primitivos, permitindo que a busca termine em profundidades menores enquanto mantém estimativas de resultados precisas.

2.3 Seleção de Ação

O framework suporta dois operadores de seleção para percorrer a árvore:

• Regret Matching (RM): Aplica o ajuste de arrependimento (regret matching) ao jogo de matriz estimada em cada nó para computar políticas mistas.
• Decoupled UCT (DUCT): Aplica limites de confiança superiores (Upper Confidence Bounds) independentemente para os valores de ação marginal de cada equipe.

3. Principais Contribuições

• Framework Híbrido: A introdução do PGTS, que integra de forma única soluções de Nash exatas de pequenos subjogos em uma busca em árvore online para coordenação multiagente.
• Expansão Estruturada: Um mecanismo para reduzir fatores de ramificação através da amostragem de ações baseada em priors estratégicos derivados de computações de equilíbrio offline, em vez de amostragem puramente heurística ou aleatória.
• Avaliação de Folha Escalável: Um método de estimativa de valor surrogate que aproveita funções de valor primitivas offline e um algoritmo de correspondência sequencial (priorizando 2v1 sobre 1v1) para avaliar nós folha sem rollouts profundos.
• Preservação de Coordenação: Diferente de métodos de decomposição simples que tratam subequipes de forma independente, o PGTS mantém a coordenação de nível de equipe ao realizar rollouts de ações conjuntas no espaço de ações total, guiados pelas primitivas.

4. Resultados Experimentais

Os autores avaliaram o PGTS em quatro topologias de grafos: duas grades 7x7 (Fácil/Difícil), um grafo de Scotland Yard de 200 nós e um grafo do mundo real de Atlanta com 151 nós. A equipe de Perseguidores foi testada contra vários comportamentos de Evadidores.

Baselines (Linhas de Base):

• MT-PSRO: Multi-Task Policy Space Response Oracles (baseado em aprendizagem).
• NSGZero: MCTS guiado por redes neurais para segurança de rede.
• Decomposition: Um baseline que utiliza apenas a decomposição de subequipes sem busca em árvore.
• Intercepting: Um baseline heurístico de caminho mais curto.

Descobertas:

• Robustez: O PGTS (ambas as variantes RM e DUCT) alcançou consistentemente a maior Utilidade de Pior Caso (WCU) em todas as topologias, superando significativamente os baselines de aprendizagem (MT-PSRO, NSGZero), que mostraram sinais de overfitting a Evadidores de caminho mais curto.
• Coordenação: O PGTS superou o baseline de "Decomposição" pura, demonstrando que o componente de busca em árvore captura efetivamente a coordenação de nível de equipe que a decomposição estática perde.
• Ablação: Remover a expansão guiada por primitivas ou as primitivas 2v1 resultou em quedas significativas de desempenho, particularmente em grafos maiores e complexos (Scotland Yard, Atlanta), confirmando a necessidade de ambos os componentes para uma exploração e estimativa de valor eficazes.

5. Significância e Alegações

O artigo afirma que o PGTS oferece uma solução escalável para a "maldição da dimensionalidade" em PEGs multiagentes. Ao alavancar soluções exatas para pequenas interações locais recorrentes (primitivas) para guiar uma busca global, o método alcança:

1. Tratabilidade Computacional: Gerencia o fator de ramificação e a profundidade de busca de forma eficaz.
2. Adaptabilidade: Mantém a capacidade de raciocinar sobre políticas coordenadas no espaço de ações conjuntas total, diferentemente da decomposição estática.
3. Robustez: Desempenha-se bem contra diversos estratégias adversariais, incluindo aquelas não vistas durante qualquer fase de treinamento, pois baseia-se em princípios da teoria dos jogos em vez de distribuições aprendidas.

Os autores concluem que esta abordagem preenche a lacuna entre a otimalidade teórica da computação de equilíbrio offline e a adaptabilidade prática do planejamento online, fornecendo um framework robusto para a tomada de decisão multiagente em ambientes adversariais. Sugere-se como trabalho futuro a extensão para observabilidade parcial e classes de jogos multiagentes mais amplas.