Dynamic Decentralized 3D Urban Coverage and Patrol with UAVs

Resumen Técnico: Cobertura y Patrullaje Urbano 3D Descentralizado y Dinámico con UAV

Formulación del Problema
El artículo aborda el desafío de coordinar un enjambre de Vehículos Aéreos No Tripulados (UAV) para realizar una cobertura y patrullaje cooperativo y periódico en un entorno urbano 3D tras desastres naturales o provocados por el hombre (por ejemplo, incendios, inundaciones, terremotos). El entorno se modela como un conjunto de edificios representados por prismas rectos, donde el objetivo es cubrir todas las fachadas verticales y las superficies de los techos con restricciones específicas de calidad de imagen para la detección de objetos.

Las principales restricciones y suposiciones incluyen:

• Recursos Limitados: No hay suficientes agentes para proporcionar una cobertura continua; por lo tanto, el sistema debe proporcionar una cobertura periódica.
• Complejidad 3D: Los agentes deben navegar alrededor de obstáculos (los propios edificios) y gestionar la inclinación de la cámara (pitch) para observar tanto las fachadas como los techos.
• Requisitos del Sistema: La solución debe ser descentralizada (sin controlador central), escalable, robusta ante la falla de agentes, adaptable a cambios dinámicos y capaz de operar con ancho de banda y alcance de comunicación limitados (conectividad periódica).
• Objetivo: Minimizar la "inactividad" máxima ($i_v$), definida como el intervalo de tiempo entre visitas consecutivas a cualquier punto de observación específico en la superficie de un edificio.

Metodología
Los autores proponen un marco modular y descentralizado que descompone el problema en cuatro etapas distintas: Generación de Puntos de Observación, Generación de Tareas, Asignación de Tareas y Estrategia de Patrullaje.

1. Generación de Puntos de Observación:
   Las superficies 3D de los edificios (fachadas y techos) se discretizan en un conjunto de puntos de observación ($V$). Cada punto de observación representa una posición y orientación 3D específica donde un UAV puede capturar un área rectangular de la superficie que coincida con el Campo de Visión (FOV) de su cámara a una distancia específica ($c_d$) para asegurar una resolución óptima para la detección de objetos.

2. Generación de Tareas:
   Los puntos de observación asociados con un solo edificio se conectan para formar una trayectoria cerrada ($H_j$). La generación de esta trayectoria se modela como un Problema del Viajante (TSP) en 3D. Para evitar la complejidad NP-duro de encontrar una solución óptima, los autores emplean el algoritmo de Christofides, un heurístico que garantiza una longitud de trayectoria dentro de 1.5 veces la óptima. La trayectoria tiene en cuenta la evitación de obstáculos (por ejemplo, no volar a través del edificio) utilizando grafos de visibilidad 3D. Cada edificio constituye una "tarea" con una capacidad definida ($c_j$) para el número de agentes que puede soportar.

3. Asignación de Tareas:
   Los agentes se asignan a tareas (edificios) utilizando el Enfoque de Paquete Basado en Consenso (CBBA) y su extensión, el Algoritmo de Agrupación Basado en Consenso (CBGA). Este método de subasta descentralizado permite que los agentes pujen por las tareas basándose en una función de puntuación. La puntuación considera la distancia al cuadrado al edificio y un factor de prioridad ($p_j$), permitiendo el manejo de tareas heterogéneas (por ejemplo, priorizar edificios de alta importancia o reasignar agentes para tareas de seguimiento dinámico). Esto asegura la escalabilidad y la tolerancia a fallas sin requerir un grafo de comunicación totalmente conectado.

4. Estrategia de Patrullaje:
   Una vez asignados a una trayectoria cerrada, los agentes ejecutan una estrategia de patrullaje mínima y descentralizada.

• Movimiento: Los agentes entran en la trayectoria en su punto de observación más cercano y se mueven en una dirección aleatoria (sentido horario o antihorario).
• Interacción: Los agentes intercambian información de estado local (posición, índice del punto de observación actual, último punto de observación servido y dirección) solo cuando están dentro del rango de comunicación.
• Mecanismo de "Rebote" (Bouncing): Cuando los agentes se encuentran (ya sea en el mismo punto de observación o pasándose el uno al otro), aplican reglas específicas para revertir la dirección ("rebotar").
  • Si dos agentes se mueven en direcciones opuestas hacia el mismo punto de observación, el agente más cercano lo atiende y revierte su dirección, mientras que el agente más lejano revierte inmediatamente.
  • Si se mueven en la misma dirección, el agente más lejano revierte para evitar el adelantamiento.
  • Si los agentes pasan sus respectivos últimos puntos de observación servidos, ambos revierten.
• Comportamiento Emergente: Esta interacción local conduce a una oscilación emergente donde los agentes particionan la trayectoria dinámicamente. El sistema no busca una partición igualitaria de la trayectoria, sino que asegura que todos los puntos de observación sean visitados periódicamente.

Contribuciones Clave

• Marco Modular: El artículo introduce un enfoque estructurado que separa la planificación de la trayectoria de cobertura de la estrategia de patrullaje, permitiendo que los componentes individuales se optimicen o modifiquen de forma independiente.
• Estrategia de Patrullaje Mínima: A diferencia de otros trabajos que dependen de un consenso global o de una coordinación compleja para particionar un perímetro continuo, este enfoque utiliza reglas locales simples ("rebote") para lograr la cobertura periódica en trayectorias cerradas 3D discretas.
• Discretización 3D: El método maneja explícitamente la naturaleza 3D de los entornos urbanos mediante la generación de puntos de observación tanto para fachadas como para techos, teniendo en cuenta la inclinación de la cámara y la evitación de obstáculos en la planificación de la trayectoria.
• Eficiencia de Recursos: La estrategia minimiza la carga computacional y de comunicación, lo que la hace adecuada para plataformas con recursos limitados que operan en entornos con conectividad esporádica.

Resultados de la Simulación
Los autores validaron el marco utilizando un Simulador de Investigación de Enjambres con un escenario que involucra 7 edificios y 401 puntos de observación.

• Configuración: Se asignaron 100 UAVs a los 7 edificios. Los agentes se movían a 2 m/s y hacían una pausa de 3 segundos en cada punto de observación.
• Desempeño: El sistema se ejecutó en tiempo real (1 Hz para la lógica de asignación/patrullaje, 10 Hz para la dinámica de los UAV) El algoritmo de Christofides promedió 3 ms por edificio, y el algoritmo de patrullaje tomó menos de 2 ms por agente.
• Cobertura: A lo largo de 10 ejecuciones experimentales (1800 segundos cada una), el enjambre logró con éxito la cobertura completa de todos los puntos de observación.
• Inactividad: La inactividad máxima para los puntos de observación estuvo acotada y convergió con el tiempo. Los resultados demostraron que la estrategia mínima efectivamente restringe el límite superior de la inactividad y asegura la cobertura periódica sin necesidad de coordinación global.

Significado y Reivindicaciones
El artículo afirma que el enfoque propuesto resuelve con éxito el problema de la cobertura urbana 3D multi-agente aprovechando el comportamiento emergente derivado de reglas locales simples. El significado reside en el compromiso: el sistema sacrifica la optimalidad de una partición igualitaria de la trayectoria (que requiere consenso global) para lograr una alta escalabilidad, robustez y adaptabilidad en entornos urbanos dinámicos y con limitaciones de comunicación. Los autores sostienen que esta estrategia mínima es particularmente adecuada para escenarios de respuesta ante desastres, donde las señales de comunicación pueden ser limitadas o esporádicas, y donde el sistema debe seguir siendo funcional incluso si los agentes individuales fallan o se pierden. Se identifica como trabajo futuro la mejora de la generación de puntos de observación para manejar cámaras heterogéneas y oclusiones complejas, pero la contribución actual se centra en la viabilidad del mecanismo de patrullaje descentralizado en un entorno urbano 3D estructurado.