Obstacle-aware multi-UAV scheduling for plant-protection operations using an enhanced walrus optimizer

Resumen Técnico: Programación de Multi-UAV con Conciencia de Obstáculos para Operaciones de Protección de Cultivos mediante un Optimizador de Morsa Mejorado

Planteamiento del Problema
El artículo aborda el desafío de programar Vehículos Aéreos No Tripulados (UAV) cooperativos para la protección de cultivos en entornos de huertos caracterizados por terrenos complejos y obstáculos. A diferencia de la planificación de rutas de cobertura tradicional, este estudio se centra en el tratamiento dirigido de parches discretos de enfermedades o sitios de deficiencia de nutrientes. El problema central es una tarea de programación de múltiples salidas, múltiples UAV y un solo depósito, la cual está restringida por:

• Autonomía y Carga Útil: Alcance limitado de batería y capacidad de pesticida que requiere regresos repetidos a un depósito central.
• Evitación de Obstáculos: La presencia de árboles, edificios y zonas de no vuelo que hacen que las distancias euclidianas (en línea recta) sean inexactas para la planificación de rutas.
• Equilibrio de la Carga de Trabajo: La necesidad de distribuir las tareas de manera uniforme entre una flota homogénea para evitar la sobrecarga de UAVs específicos.
• Viabilidad 3D: El requisito de generar rutas ejecutables que respeten el despeje del terreno, los límites de ángulo de ascenso y las altitudes de trabajo específicas sobre la copa.

Los métodos existentes suelen evaluar las programaciones utilizando distancias en línea recta, lo que puede derivar en rutas inviables o ineficientes cuando se introducen obstáculos. Además, pocos estudios optimizan simultáneamente la asignación de tareas, el orden de visita y la realización de la ruta bajo estas restricciones específicas de 2.5 dimensiones.

Metodología
Los autores proponen un marco de dos etapas que combina una capa determinista de realización de rutas con un optimizador de programación metaheurístico.

1. Modelo de Programación:

   • Objetivo: Una función multiobjetivo que minimiza la distancia de viaje agregada, la distancia acumulada máxima por cada UAV (makespan) y la desviación estándar de las longitudes de las rutas entre los UAV (equilibrio de carga de trabajo).
   • Costos de Arista: En lugar de la distancia euclidiana, los costos de las aristas ($c_{ij}$) se derivan de una búsqueda A* en un grafo de ocupación estático. Esto asegura que el algoritmo de programación tenga en cuenta los desvíos horizontales alrededor de obstáculos y zonas de no vuelo.
   • Restricciones: El modelo impone límites de carga útil, longitud máxima de salida y restricciones de retorno al depósito único. Un decodificador construye las salidas empaquetando tareas hasta alcanzar los límites de capacidad o de alcance.

2. Realización de Ruta (2.5 Dimensional):

   • Horizontal: A* reconstruye trayectorias libres de colisiones entre las tareas basándose en la programación.
   • Vertical: Un modelo de altitud 2.5D asigna perfiles de elevación. El UAV mantiene una altura de crucero ($H_c$) sobre el terreno, desciende suavemente a una altitud de trabajo ($H_{min}$) sobre la copa de los árboles en los sitios de las tareas, y se adhiere a un ángulo de ascenso máximo ($20^\circ$).
   • Verificación de Viabilidad: La distancia espacial 3D realizada se calcula post-programación y se verifica contra el límite de autonomía del UAV.

3. Optimizador de Morsa Mejorado (CRWO):
   Para resolver el problema de programación combinatoria NP-duro, los autores mejoran el Optimizador de Morsa (WO) estándar con tres estrategias específicas:

   • Mutación Diferencial Aleatoria: Utiliza la diferencia entre la mejor solución histórica y los individuos aleatorios para dirigir la perturbación, equilibrando la exploración y la explotación.
   • Aprendizaje Basado en la Oposición de Imagen de Lente: Genera soluciones candidatas simétricas a través del espacio de búsqueda para escapar de los óptimos locales.
   • Búsqueda de Vecindad Discreta: Aplicada a las soluciones de élite para refinar las reasignaciones de tareas y las prioridades de visita.
   • Codificación: Una representación de doble clave aleatoria codifica tanto la asignación de tareas al UAV como la prioridad de visita, permitiendo que los operadores de optimización continua resuelvan problemas discretos.

Contribuciones Clave

• Formulación con Conciencia de Obstáculos: El artículo formula un modelo de programación donde los costos de las aristas se precalculan mediante A* en lugar de la distancia euclidiana, asegurando que el objetivo de optimización se alinee con los costos de las rutas ejecutables.
• Algoritmo CRWO: El desarrollo de una metaheurística mejorada (CRWO) diseñada específicamente para la programación de múltiples UAV de alta dimensión y con restricciones, demostrando un rendimiento superior sobre el WO estándar, PSO, GWO y otros.
• Marco de Realización 2.5D: Un enfoque secuencial que desacopla la búsqueda de programación 2D de la realización de la ruta 3D, asegurando que las programaciones generadas cumplan con las restricciones de despeje del terreno y ángulo de ascenso sin complicar el espacio de búsqueda con una dinámica 3D completa.
• Evaluación Exhaustiva: Un riguroso benchmarking contra ocho algoritmos en densidades de obstáculos bajas, medias y altas, incluyendo estudios de ablación para aislar la contribución de los componentes específicos de CRWO.

Resultos Experimentales
Los experimentos se realizaron en un mapa de huerto de 800m × 800m con 50 tareas y 6 UAV.

• Desempeño vs. Baselines: En el escenario de obstáculos medios, el CRWO superó al baseline más fuerte (PSO) reduciendo el valor objetivo medio en un 3.71%, la distancia espacial máxima acumulada por UAV en un 3.70% y la desviación estándar de la longitud de la ruta entre UAV en un 47.62%.
• Equilibrio de Carga de Trabajo: El CRWO logró consistentemente la menor variación de carga de trabajo (desviación estándar) en todas las densidades de obstáculos, indicando una utilización superior de la flota.
• Viabilidad: Todas las salidas realizadas cumplieron con las restricciones de autonomía, evitación de obstáculos, despeje del terreno (mínimo 5.52m) y ángulo de ascenso ($\le 20^\circ$).
• A* vs. Euclídeo: El uso de costos de arista A* no redujo significativamente la distancia total agregada en comparación con la programación euclidiana, pero mejoró significamente el equilibrio de la carga de trabajo (reduciendo la desviación estándar de la longitud de la ruta de 50.43m a 23.11m en ejecuciones pareadas).
• Ablación: El estudio confirmó que la combinación de mutación diferencial, aprendizaje de oposición y búsqueda de vecindad discreta era necesaria para lograr el rendimiento final; eliminar cualquier componente degradó los resultados.

Significancia y Reclamaciones
El artículo afirma que el CRWO ofrece un método de programación práctico para operaciones de protección de cultivos estáticas de un solo depósito donde la evitación de obstáculos y el equilibrio de la flota son críticos. Los autores enfatizan que el método es un "programador equilibrado" más que un algoritmo de ruta mínima pura; su valor principal radica en distribuir la carga de trabajo de manera uniforme y asegurar que se cumplan las restricciones de seguridad sin requerir un acoplamiento 3D complejo durante la fase de optimización.

Los autores mantienen un alcance modesto, reconociendo que el marco actual está limitado a mapas estáticos, demandas deterministas y flotas homogéneas. Declaran explícitamente que el método no garantiza un óptimo global y que se requiere trabajo futuro para abordar la reasignación dinámica, flotas heterogéneas y la incertidumbre en las condiciones de vuelo. El estudio concluye que, si bien las ganancias en distancia agregada son marginales, las mejoras significativas en el equilibrio de la carga de trabajo y el cumplimiento de la seguridad hacen que el CRWO sea una solución viable para la protección dirigida de cultivos.