Forecast-Aware Cooperative Planning on Temporal Graphs under Stochastic Adversarial Risk

Título: Planejamento Cooperativo Consciente de Previsão em Grafos Temporais sob Risco Adversarial Estocástico

1. Problema Abordado

O artigo aborda o desafio de coordenar missões de múltiplos robôs em ambientes onde os custos de travessia evoluem dinamicamente devido à presença de adversários (ou perigos) com movimentos estocásticos.

• Contexto: Em missões como busca e resgate ou proteção de comboios, os robôs devem navegar por grafos onde certas arestas (rotas) tornam-se perigosas dependendo da localização de adversários que se movem aleatoriamente.
• Mecanismo de Suporte: Para mitigar riscos, os robôs podem realizar ações de "suporte", onde um robô fica temporariamente em uma posição designada para cobrir/assistir um companheiro que atravessa uma aresta de alto risco, reduzindo o custo de penalidade da travessia.
• Limitação das Abordagens Atuais: A maioria dos métodos existentes assume um cenário de risco estático ou determinístico. Eles falham em antecipar tendências temporais previsíveis na evolução do risco. Isso leva a ações de suporte mal posicionadas (muito cedo, muito tarde ou em locais que deixaram de ser perigosos), resultando em desvios desnecessários e aumento do custo total da missão.
• Objetivo: Desenvolver um framework que integre a previsão de riscos estocásticos com a alocação proativa de suporte em grafos temporais, permitindo que a equipe antecipe onde e quando o risco aparecerá.

2. Metodologia

Os autores propõem um framework de planejamento em três estágios principais, operando sobre um grafo temporal onde os custos das arestas mudam ao longo do tempo.

A. Modelagem do Ambiente e Dinâmica do Adversário

• Grafo Temporal: O ambiente é modelado como um grafo $G=(V, E)$ com custos dependentes do tempo.
• Dinâmica Estocástica: Os adversários seguem um processo de Markov de primeira ordem do tipo "permanecer-mover" (stay-move). Em cada passo de tempo, um adversário pode permanecer na aresta atual ou mover-se para uma aresta adjacente com probabilidades definidas.
• Previsão de Risco: Ao propagar essas transições para frente no tempo, o sistema gera previsões de probabilidade de ocupação das arestas ($\rho_{uv}(t)$), indicando a probabilidade de haver pelo menos um adversário em uma aresta específica em um tempo futuro.

B. Alocação de Suporte Consciente de Previsão

Diferente de métodos estáticos que fixam posições de suporte baseadas apenas no risco inicial, este método aloca suporte com base na evolução futura do risco:

1. Identificação de Candidatos: Para arestas previstas como perigosas no horizonte de planejamento, identifica-se nós vizinhos (dentro de um raio $k$) que podem atuar como posições de suporte.
2. Pontuação de Nós (Scoring): Cada nó candidato recebe uma pontuação baseada em dois fatores:
   • Sobreposição de Caminho ($\hat{P}$): Quantos robôs passarão por esse nó em seus caminhos mais curtos (garantindo que o suporte esteja em corredores de alto tráfego).
   • Potencial de Risco ($\hat{R}$): A intensidade do risco acumulado previsto na aresta que o nó pode cobrir, ponderada pela distância.
   • A fórmula de pontuação combina tráfego e risco para selecionar as posições mais eficazes.
3. Mapeamento: Gera-se um mapeamento $\Gamma$ que associa arestas de risco previstas a nós de suporte específicos antes da execução do planejamento de caminho.

C. Planejamento de Equipe Baseado em Previsão

• Objetivo Aproximado: Como o estado real dos adversários é desconhecido no momento do planejamento, o objetivo de minimizar o custo é aproximado usando os valores esperados (previsões de risco) em vez de realizações reais.
• Algoritmo de Busca: Utiliza-se uma variação do algoritmo Lazy A* (A* Preguiçoso) sobre o grafo temporal expandido. O algoritmo adia a avaliação de riscos até que uma aresta seja considerada na busca, mantendo a eficiência computacional e a admissibilidade da heurística.

3. Contribuições Principais

1. Formulação do Problema: Formalização da travessia cooperativa em grafos temporais sob risco adversarial estocástico, onde os custos evoluem dinamicamente.
2. Mecanismo de Alocação Proativa: Introdução de um mecanismo de alocação de suporte que utiliza transições de "permanecer-mover" para antecipar riscos e alocar posições de suporte de forma proativa, em vez de reativa.
3. Validação Experimental: Demonstração de que a abordagem reduz consistentemente o custo esperado da equipe em comparação com bases não antecipatórias (como alocação aleatória ou baseada apenas no estado inicial), aproximando-se do desempenho de um "planejador oráculo" (que conhece o futuro).

4. Resultados Experimentais

Os experimentos foram realizados em grafos aleatórios com tamanhos variados (5 a 20 nós) e diferentes configurações de robôs (2-4) e adversários (4).

• Desempenho de Custo: O método "Forecast-aware" (consciente de previsão) consistentemente obteve o menor custo esperado de equipe entre todas as estratégias de suporte (incluindo Random, TCGRE e sem suporte).
• Comparação com Baselines:
  • Superou o método TCGRE (que aloca suporte apenas para riscos iniciais) porque considera riscos que surgem mais tarde no horizonte.
  • Superou a alocação Aleatória, especialmente em grafos maiores, onde a seleção aleatória frequentemente posiciona suporte em locais de baixo impacto.
  • Em cenários estáticos (probabilidade de permanência = 1.0), o método converge para o comportamento de métodos determinísticos existentes, validando sua correção.
• Eficiência Computacional: O método foi o único a encontrar soluções viáveis dentro do limite de tempo (90s) em configurações complexas (muitos robôs e grafos grandes), enquanto outras abordagens frequentemente falharam (timeout) devido à incapacidade de encontrar trajetórias seguras sem suporte coordenado.
• Calibração: A diferença entre o custo esperado ($J_{exp}$) e o custo realizado (via simulação de Monte Carlo) foi pequena e bounded, confirmando que o modelo de previsão é bem calibrado.
• Ganhos Qualitativos: Em exemplos visuais, o método permitiu que os robôs atravessassem corredores de risco mais cedo com suporte coordenado, reduzindo o tempo de espera e o custo total em até ~42% em comparação com a estratégia sem suporte.

5. Significado e Conclusão

Este trabalho representa um avanço significativo na coordenação de multi-robôs ao integrar previsão temporal com ação cooperativa.

• Inovação: A principal inovação é a transição de um paradigma reativo (responder ao risco atual) para um paradigma proativo (antecipar o risco futuro), permitindo que a equipe tome decisões de suporte que maximizam a eficiência a longo prazo.
• Aplicabilidade: O framework é crucial para missões em ambientes dinâmicos onde a informação é incerta, mas segue padrões estocásticos conhecidos.
• Limitações e Futuro: O trabalho atual assume dinâmica adversarial conhecida e planejamento centralizado. Trabalhos futuros visam integrar estimativa online de riscos (aprendizado durante a execução) e estender o framework para coordenação descentralizada e adversários reativos.

Em resumo, o artigo demonstra que a antecipação inteligente da evolução do risco, combinada com a alocação estratégica de suporte baseada no tráfego de robôs, é essencial para otimizar missões cooperativas em ambientes hostis e dinâmicos.