Dynamic Decentralized 3D Urban Coverage and Patrol with UAVs

Resumo Técnico: Cobertura e Patrulha Urbana 3D Descentralizada e Dinâmica com UAVs

Formulação do Problema
O artigo aborda o desafio de coordenar um enxame de Veículos Aéreos Não Tripulados (UAVs) para realizar cobertura e patrulha cooperativa e periódica em um ambiente urbano 3D após desastres naturais ou causados pelo homem (ex: incêndios, inundações, terremotos). O ambiente é modelado como um conjunto de edifícios representados por prismas retos, onde o objetivo é cobrir todas as fachadas verticais e superfícies de telhado com restrições específicas de qualidade de imagem para detecção de objetos.

As principais restrições e suposições incluem:

• Recursos Limitados: Há agentes insuficientes para fornecer cobertura contínua; portanto, o sistema deve fornecer cobertura periódica.
• Complexidade 3D: Os agentes devem navegar em torno de obstáculos (os próprios edifícios) e gerenciar a inclinação da câmera (pitch) para visualizar tanto as fachadas quanto os telhados.
• Requisitos do Sistema: A solução deve ser descentralizada (sem controlador central), escalável, robusta à falha de agentes, adaptável a mudanças dinâmicas e capaz de operar com largura de banda e alcance de comunicação limitados (conectividade periódica).
• Objetivo: Minimizar o "ócio" máximo ($i_v$), definido como o intervalo de tempo entre visitas consecutivas a qualquer ponto de observação específico na superfície de um edifício.

Metodologia
Os autores propõem uma estrutura modular e descentralizada que decompõe o problema em quatro estágios distintos: Geração de Pontos de Observação, Geração de Tarefas, Alocação de Tarefas e Estratégia de Patrulha.

1. Geração de Pontos de Observação:
   As superfícies 3D dos edifícios (fachadas e telhados) são discretizadas em um conjunto de pontos de observação ($V$). Cada ponto de observação representa uma posição e orientação 3D específica onde um UAV pode capturar uma área retangular da superfície correspondendo ao seu Campo de Visão (FOV) a uma distância específica ($c_d$) para garantir a resolução ideal para detecção de objetos.

2. Geração de Tarefas:
   Os pontos de observação associados a um único edifício são conectados para formar um caminho fechado ($H_j$). A geração deste caminho é modelada como um Problema do Caixeiro Viajante (TSP) 3D. Para evitar a complexidade NP-difícil de encontrar uma solução ótima, os autores utilizam o algoritmo de Christofides, um heurístico que garante um comprimento de caminho dentro de 1,5 vezes o ótimo. O caminho leva em conta a evasão de obstáculos (ex: não voar através do edifício) usando grafos de visibilidade 3D. Cada edifício constitui uma "tarefa" com uma capacidade definida ($c_j$) para o número de agentes que pode suportar.

3. Alocação de Tarefas:
   Os agentes são atribuídos a tarefas (edifícios) usando a Abordagem de Bundle Baseada em Consenso (CBBA) e sua extensão, o Algoritmo de Agrupamento Baseado em Consenso (CBGA). Este método baseado em leilão e descentralizado permite que os agentes deem lances em tarefas com base em uma função de pontuação. A pontuação considera a distância ao quadrado até o edifício e um fator de prioridade ($p_j$), permitindo o tratamento de tarefas heterogêneas (ex: priorizando edifícios de alta importância ou reatribuindo agentes para tarefas de rastreamento dinâmico). Isso garante escalabilidade e tolerância a falhas sem a necessidade de um grafo de comunicação totalmente conectado.

4. Estratégia de Patrulha:
   Uma vez atribuído a um caminho fechado, o agente executa uma estratégia de patrulha mínima e descentralizada.

• Movimentação: Os agentes entram no caminho em seu ponto de observação mais próximo e movem-se em uma direção aleatória (horária ou anti-horária).
• Interação: Os agentes trocam informações de estado local (posição, índice do ponto de observação atual, último ponto de observação servido e direção) apenas quando estão dentro do alcance de comunicação.
• Mecanismo de "Bouncing" (Rebote): Quando os agentes se encontram (seja no mesmo ponto de observação ou passando uns pelos outros), eles aplicam regras específicas para inverter a direção ("bounce").
  • Se dois agentes estiverem se movendo em direções opostas em direção ao mesmo ponto de observação, o agente mais próximo atende o ponto e inverte a direção, enquanto o agente mais distante inverte imediatamente.
  • Se estiverem se movendo na mesma direção, o agente mais distante inverte para evitar ultrapassagens.
  • Se os agentes passarem pelos últimos pontos de observação servidos um do outro, ambos invertem a direção.
• Comportamento Emergente: Esta interação local leva a uma oscilação emergente onde os agentes particionam o caminho dinamicamente. O sistema não visa uma partição igual do caminho, mas garante que todos os pontos de observação sejam visitados periodicamente.

Principais Contribuições

• Estrutura Modular: O artigo introduz uma abordagem estruturada que separa o planejamento de caminho de cobertura da estratégia de patrulha, permitindo que componentes individuais sejam otimizados ou modificados independentemente.
• Estratégia de Patrulha Mínima: Ao contrário de trabalhos anteriores que dependem de consenso global ou coordenação complexa para particionar um perímetro contínuo, esta abordagem utiliza regras locais simples ("bouncing") para alcançar cobertura periódica em caminhos fechados 3D discretos.
• Discretização 3D: O método lida explicitamente com a natureza 3D dos ambientes urbanos ao gerar pontos de observação tanto para fachadas quanto para telhados, considerando a inclinação da câmera e a evasão de obstáculos no planejamento de caminho.
• Eficiência de Recursos: A estratégia minimiza o overhead computacional e de comunicação, tornando-a adequada para plataformas com recursos limitados operando em ambientes com conectividade esporádica.

Resultados de Simulação
Os autores validaram a estrutura usando um Simulador de Pesquisa de Enxame com um cenário envolvendo 7 edifícios e 401 pontos de observação.

• Configuração: 100 UAVs foram alocados aos 7 edifícios. Os agentes moviam-se a 2 m/s e faziam uma pausa de 3 segundos em cada ponto de observação.
• Desempenho: O sistema rodou em tempo real (1 Hz para lógica de alocação/patrulha, 10 Hz para dinâmica de UAV) . O algoritmo de Christofides levou em média 3 ms por edifício, e o algoritmo de patrulha levou menos de 2 ms por agente.
• Cobertura: Em 10 execuções experimentais (1800 segundos cada), o enxame alcançou com sucesso a cobertura completa de todos os pontos de observação.
• Ócio: O ócio máximo para os pontos de observação foi limitado e convergiu ao longo do tempo. Os resultados demonstraram que a estratégia mínima efetivamente restringe o limite superior do ócio e garante cobertura periódica sem coordenação global.

Significância e Alegações
O artigo afirma que a abordagem proposta resolve com sucesso o problema de cobertura urbana 3D multiagente ao alavancar o comportamento emergente derivado de regras locais simples. A significância reside no equilíbrio: o sistema sacrifica a otimalidade de uma partição igual do caminho (que requer consenso global) para alcançar alta escalabilidade, robustez e adaptabilidade em ambientes urbanos dinâmicos e com restrições de comunicação. Os autores afirmam que esta estratégia mínima é particularmente adequada para cenários de resposta a desastres, onde os sinais de comunicação podem ser limitados ou esporádicos, e onde o sistema deve permanecer funcional mesmo se agentes individuais falharem ou forem perdidos. O trabalho futuro é identificado como a melhoria da geração de pontos de observação para lidar com câmeras heterogêneas e oclusões complexas, mas a contribuição atual foca na viabilidade do mecanismo de patrulha descentralizado em um ambiente urbano 3D estruturado.