A Surveillance Evasion Game with Continuous Sensor Redeployment via Bilevel Optimization

Resumo Técnico: Um Jogo de Evasão de Vigilância com Redeployamento Contínuo de Sensores via Otimização Bilevel

Formulação do Problema
O artigo aborda o desafio crítico de segurança de Sistemas Aéreos Não Tripulados (UASs) explorando lacunas espaço-temporais em perímetros de sensores para infiltrar-se em espaço aéreo restrito sem detecção. Os autores modelam essa interação como um jogo diferencial de soma zero entre dois jogadores: um UAS adversário (atacante) e uma rede heterogênea de sensores (defensora) composta por sensores direcionais e omnidirecionais.

Diferentemente de abordagens anteriores que frequentemente restringem os defensores a grafos de colocação discretos, configurações fixas ou assumem cobertura omnidirecional estática, este trabalho formula o problema sobre espaços de estratégia contínuos. O atacante busca uma trajetória espaço-temporal livre de colisões de um ponto de partida a um ponto de destino que minimize a probabilidade cumulativa de detecção. Por outro lado, o defensor visa maximizar essa probabilidade otimizando a colocação espacial dos sensores. Uma complexidade chave surge do uso de sensores direcionais rotativos pelo defensor, que criam regiões de cobertura variantes no tempo e não convexas, bem como lacunas previsíveis que um adversário inteligente pode explorar. Os autores observam que encontrar um ponto de sela global é intratável devido à natureza de alta dimensão e não convexa dos espaços de estratégia conjuntos e às descontinuidades introduzidas pelos campos de visão (FOV) rotativos dos sensores. Consequentemente, o objetivo é calcular um Equilíbrio de Nash Local (LNE), um estado em que nenhum jogador pode melhorar seu payoff através de desvios unilaterais infinitesimais.

Metodologia
A solução proposta emprega um framework de otimização bilevel iterativo que alterna entre a resolução dos subproblemas de melhor resposta do atacante e do defensor até que a convergência para um LNE seja alcançada.

1. Melhor Resposta do Atacante:
   Dada uma colocação fixa de sensores, o atacante resolve um problema de programação não linear (NLP) para minimizar a probabilidade de detecção. Para lidar com a paisagem de detecção não convexa, os autores utilizam uma abordagem em duas etapas:

   • Inicialização: O algoritmo Space-Time Probabilistic Rapidly-exploring Random Tree (STP-RRT*) gera uma trajetória inicial viável e livre de colisões, navegando ao redor de regiões de cobertura de sensores dinâmicas.
   • Refinamento: Um solver NLP baseado em gradiente (IPOPT) refina essa trajetória para minimizar a probabilidade cumulativa de detecção. O modelo de detecção utiliza uma função sigmoid suave para aproximar a visibilidade, garantindo diferenciabilidade para otimização baseada em gradiente.

2. Melhor Resposta do Defensor:
   Dada a trajetória otimizada do atacante, o defensor resolve um problema de redeployamento contínuo de sensores para maximizar a probabilidade de detecção.

   • Redeployamento Contínuo: Diferentemente de métodos baseados em grafos discretos, os sensores são permitidos deslizar livremente ao longo das fronteiras de edifícios poligonais convexos.
   • Restrições Suaves: Para permitir otimização baseada em gradiente nessas fronteiras, os autores impõem restrições de colocação usando uma aproximação suave log-sum-exp da distância assinada à borda do edifício mais próxima. Essa técnica preserva a diferenciabilidade nos vértices do polígono, superando a não diferenciabilidade de restrições de fronteira rígidas.

3. Esquema Iterativo:
   O framework alterna entre a minimização do atacante e a maximização do defensor. O processo termina quando os resíduos de gradiente para ambos os jogadores caem abaixo de uma tolerância prescrita, satisfazendo as condições de estacionariedade de primeira ordem para um LNE. Se o algoritmo entrar em um ciclo limite (oscilação não decrescente), o defensor é reinicializado a partir de uma nova colocação aleatória para recuperar a convergência.

Contribuições Principais
O artigo faz três contribuições primárias:

• Formulação do Jogo: Uma formulação de jogo diferencial de soma zero entre dois jogadores que modela regiões de detecção variantes no tempo e não convexas de sensores direcionais rotativos sobre espaços de estratégia contínuos.
• Redeployamento Contínuo: Uma formulação inovadora para o defensor permitindo que sensores deslizem continuamente ao longo de fronteiras físicas de edifícios, imposta via uma restrição diferenciável log-sum-exp, habilitando otimização baseada em gradiente.
• Otimização Bilevel Iterativa: Um framework algorítmico que converge para um Equilíbrio de Nash Local ao otimizar alternadamente a colocação de sensores e trajetórias de atacantes, com condições analíticas de estacionariedade de primeira ordem derivadas para ambos os jogadores.

Resultados e Validação
O framework foi avaliado através de simulações numéricas e uma demonstração experimental física:

• Simulação de Monte Carlo: Uma simulação de 500 ensaios demonstrou que o framework proposto alcança uma melhoria de 4× na probabilidade de detecção do defensor em comparação com a colocação aleatória de sensores (a linha de base natural). O método alcançou uma taxa de convergência de 96,8% para um Equilíbrio de Nash Local. No estado convergido, a probabilidade de detecção do defensor aumentou significativamente (de uma média de ~0,103 para ~0,419), enquanto a taxa de sucesso do atacante diminuiu.
• Comportamento de Convergência: A otimização alternada tipicamente estabilizou-se em um platô, com resíduos numéricos decaindo para perto de $10^{-6}$. Comportamento de ciclo limite foi observado em apenas 1 de 500 ensaios (2%), o que foi resolvido com sucesso por reinicialização.
• Demonstração Experimental: O framework foi testado em um ambiente físico em escala reduzida simulando um cenário de defesa de aeroporto com um cânion urbano. Usando um Crazyflie 2.1 como atacante e câmeras PTZ como defensores, os experimentos validaram que a otimização bilevel produz melhorias consistentes na estratégia. A estratégia LNE ($a^*, d^*$) resultou em um custo de detecção ($J$) de 0,9451, significativamente maior que a colocação heurística inicial ($J=0,6847$) e superior a cenários onde apenas um jogador otimizava sua estratégia.

Significado e Alegações
Os autores posicionam este trabalho como uma linha de base implantável para colocações heterogêneas de sensores em missões de Contra-UAS (CUAS). Eles afirmam que o significado reside em preencher três lacunas na literatura existente: a falta de redeployamento contínuo de sensores ao longo de fronteiras de edifícios, a ausência de modelagem probabilística de FOV direcional em contextos de teoria dos jogos, e a transição de espaços de estratégia discretos para otimização bilevel baseada em gradiente.

O artigo enquadra modestamente sua contribuição como estabelecer um primeiro passo necessário ao isolar a contribuição da topologia de implantação, reconhecendo que o problema mais complexo de acoplamento de agendamento e colocação permanece para trabalhos futuros. Os resultados confirmam que otimizar a colocação de sensores em um espaço contínuo, levando em conta a natureza dinâmica de sensores direcionais, melhora significativamente a segurança do perímetro contra adversários inteligentes em comparação com linhas de base estáticas ou aleatórias.