💻 computer science

Polar Coordinate-based Differential Evolution for Moving Target Search Using Vision Sensor on Unmanned Aerial Vehicles

Este artículo propone un algoritmo de Evolución Diferencial basado en Coordenadas Polares (PDE) que integra el modelado de la dinámica del objetivo, funciones de aptitud bayesianas y restricciones cinemáticas de UAV para optimizar las trayectorias de búsqueda de objetivos móviles, demostrando una probabilidad de detección y un tiempo de ejecución superiores tanto en simulaciones como en experimentos reales con UAV.

Autores originales: Thu Hang Khuat, Duy-Nam Bui, Thuy Ngan Duong, Manh Duong Phung

Publicado 2026-07-21

📖 8 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Thu Hang Khuat, Duy-Nam Bui, Thuy Ngan Duong, Manh Duong Phung

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que estás jugando una partida de escondite de alto riesgo, pero la persona que buscas está huyendo, el mapa es enorme y solo tienes un par de binoculares que se vuelven borrosos si el sol es demasiado brillante o el viento es demasiado fuerte. Esta es la realidad diaria de los equipos de búsqueda y rescate que intentan encontrar excursionistas perdidos o supervivientes en zonas de desastre. En el mundo de la ciencia, esto se conoce como "búsqueda óptima", un rompecabezas donde las computadoras intentan determinar la mejor ruta para tomar para no desperdiciar tiempo precioso. La idea clave aquí es que el tiempo es el enemigo; cuanto más tiempo busques, más difícil será encontrar a alguien porque su ubicación se convierte en una suposición en lugar de un hecho. Para resolver esto, los científicos utilizan "drones" (robots voladores) equipados con cámaras, pero programar estos drones para que vuelen la ruta perfecta es increíblemente difícil porque los drones tienen límites físicos: no pueden girar instantáneamente, tienen una velocidad máxima y no pueden volar para siempre.

Este artículo presenta una nueva y astuta forma de enseñar a los drones a cazar objetivos en movimiento, como una persona perdida o un superviviente flotante. Los autores, un equipo de investigadores de Vietnam y Corea, crearon un nuevo algoritmo llamado "Evolución Diferencial basada en coordenadas polares" (o PDE por sus siglas en inglés). Piensa en esto como un entrenador superinteligente que no solo le dice al dron hacia dónde ir, sino cómo mover su cuerpo para llegar allí. En lugar de usar coordenadas de mapa estándar (como "ve 10 metros a la derecha, luego 5 metros arriba"), el algoritmo PDE habla el lenguaje nativo del dron: "gira este ángulo y vuela esta distancia". Al hacer esto, el dron evita quedarse atrapado en callejones sin salida o intentar realizar giros imposibles. Los investigadores probaron este método en simulaciones por computadora y con un dron real en un campo, y descubrieron que el PDE era mejor para encontrar el objetivo más rápido que otros métodos populares, especialmente cuando el objetivo se movía y el área de búsqueda era grande.

El Problema: La carrera por el "Tiempo de Oro"

En la búsqueda y el rescate, existe un concepto llamado "tiempo de oro". Esta es la corta ventana justo después de que alguien desaparece cuando las posibilidades de encontrarlo con vida son más altas. A medida que el tiempo transcurre, las probabilidades caen. ¿Por qué? Porque la persona puede moverse, el viento puede empujarla o el terreno puede ocultarla. Los métodos de búsqueda tradicionales suelen depender de equipos en tierra o aviones pilotados, que pueden ser lentos o peligrosos. Aquí entra el dron (UAV). Los drones pueden cruzar rápidamente terrenos peligrosos y ver cosas que los humanos no pueden. Pero aquí está el truco: si solo le dices a un dron que vuele aleatoriamente, podría perder el objetivo. Si le dices que vuele en una cuadrícula perfecta, podría perder tiempo sobrevolando puntos vacíos. El objetivo es encontrar la ruta de vuelo perfecta que maximice la probabilidad de detectar al objetivo lo más rápido posible.

El Cerebro: Cómo "piensa" el dron

Para encontrar el mejor camino, el dron necesita un cerebro que pueda predecir dónde podría estar el objetivo. Los autores modelaron el movimiento del objetivo como un "proceso de Markov". En términos simples, esto significa que el siguiente movimiento del objetivo depende principalmente de dónde está ahora mismo y cómo se está moviendo, no de dónde estaba hace una hora. Es como predecir una hoja flotando río abajo; conoces la dirección de la corriente, así que puedes adivinar dónde estará en unos segundos.

El dron también necesita saber qué tan buenos son sus "ojos". El artículo utiliza un modelo llamado NVESD para calcular la probabilidad de detectar al objetivo. Esto no se trata solo de qué tan lejos está el objetivo; se trata de la calidad de la imagen. Si el sol deslumbra, o si el objetivo es pequeño y borroso, la probabilidad de verlo disminuye. El algoritmo combina estas dos cosas —dónde podría estar el objetivo y qué tan probable es que la cámara lo vea— para crear un "mapa de creencias". Este mapa es como un mapa de calor donde los puntos más brillantes muestran la mayor probabilidad de que el objetivo esté allí.

La Solución: El truco de las Coordenadas Polares

La innovación central de este artículo es cómo el dron planifica su ruta de vuelo. La mayoría de los algoritmos de computadora usan "coordenadas cartesianas", que son como una cuadrícula en un papel de dibujo milimetrado (valores x e y). Aunque esto funciona para las matemáticas, es terrible para los drones. Si un dron está volando y necesita girar, un algoritmo cartesiano podría calcular una ruta que requiera que el dron gire en un círculo instantáneamente o vuele más rápido de lo que su motor permite. Es como decirle a un coche "muévete 5 metros al norte y 5 metros al este" sin importarle que el coche tenga un radio de giro mínimo.

Los autores propusieron usar "coordenadas polares" en su lugar. En lugar de decir "ve al punto (x, y)", el algoritmo le dice al dron: "Vuela esta distancia ( $\rho$ ) a este ángulo ( $\psi$ )." Esto coincide con cómo se mueve realmente el dron. Al usar este método, el algoritmo respeta naturalmente los límites físicos del dron. No puede sugerir un giro demasiado cerrado o una velocidad demasiado alta porque las matemáticas están construidas alrededor de esos límites desde el principio.

Envolvieron esta idea dentro de un algoritmo de "Evolución Diferencial" (DE). La DE es un tipo de "inteligencia de enjambre" que funciona como un equipo de exploradores. Imagina a un grupo de excursionistas tratando de encontrar la cima más alta en una cadena montañosa con niebla. No conocen todo el mapa, pero comparten notas. Si un excursionista encuentra un punto alto, los demás se mueven hacia esa área pero también intentan direcciones ligeramente diferentes para ver si pueden encontrar algo aún más alto. La parte "Diferencial" significa que observan la diferencia entre dónde están dos excursionistas para decidir hacia dónde saltar a continuación.

Los autores combinaron esta inteligencia de enjambre con su sistema de coordenadas polares. Los llaman PDE. En sus simulaciones, este equipo de drones virtuales exploró el área de búsqueda de manera mucho más eficiente que los equipos que usaban métodos estándar.

Los Resultados: Simulaciones y Vuelos Reales

Los investigadores probaron su algoritmo PDE en seis escenarios diferentes, que van desde áreas pequeñas de 600m x 600m hasta zonas masivas de 2000m x 2000m. Compararon el PDE contra otros algoritmos famosos como la Optimización por Enjambre de Partículas (PSO), Algoritmos Genéticos (GA) y la Evolución Diferencial (DE) estándar.

En las simulaciones por computadora, el PDE encontró consistentemente el objetivo con una mayor probabilidad y lo hizo más rápido. Por ejemplo, en un escenario, el PDE logró una probabilidad de detección de aproximadamente 0.529, mientras que el algoritmo DE estándar solo logró 0.410. El artículo señala que el DE estándar a menudo se quedaba "atrapado" en óptimos locales, lo que significa que encontraba un buen lugar pero no podía ver el mejor lugar porque estaba atrapado en un bucle. El PDE, gracias a sus coordenadas polares, fue mejor para escapar de estos bucles y encontrar la mejor ruta global.

No se detuvieron solo en juegos de computadora. Llevaron un dron real 3DR Solo a un campo para probar la teoría. El dron fue programado con la ruta PDE y volado sobre un área de 80m x 80m. Una persona (el objetivo) caminaba a una velocidad de 1.5 m/s. El dron siguió la ruta generada por el algoritmo, y la ruta que realmente voló coincidió muy de cerca con el plan. El dron logró volar sobre el área donde se esperaba que estuviera el objetivo, y la cámara capturó a la persona. Los autores señalan que, aunque la prueba en el mundo real fue exitosa, dependió de que el objetivo se moviera exactamente como se predijo. En un desastre real, las cosas son más desordenadas, pero la prueba demostó que el algoritmo genera rutas que los drones reales realmente pueden volar.

Por qué es importante

El artículo sugiere que, al hablar el lenguaje del dron (coordenadas polares) y utilizar una estrategia de búsqueda inteligente basada en equipos, podemos hacer que las operaciones de búsqueda y rescate sean más efectivas. El algoritmo PDE no solo encuentra una ruta; encuentra una ruta factible que respeta los límites del dron mientras maximiza la probabilidad de un rescate. Aunque los autores admiten que un solo dron solo puede cubrir un área limitada debido a la duración de la batería, sugieren que este método podría ser la base para una flota de drones trabajando juntos en el futuro. Por ahora, es un paso significativo hacia la creación de robots voladores más inteligentes, más rápidos y más útiles cuando cada segundo cuenta.

Resumen Técnico: Evolución Diferencial basada en Coordenadas Polares para la Búsqueda de Objetos en Movimiento mediante Sensores de Visión en Vehículos Aéreos No Tripulados

Planteamiento del Problema

El artículo aborda el desafío de localizar un objetivo en movimiento en operaciones de búsqueda y rescate, donde la probabilidad de encontrar a un superviviente con vida disminuye rápidamente con el tiempo ("tiempo de oro"). El objetivo central es generar una trayectoria de vuelo óptima para un Vehículo Aéreo No Tripulado (UAV) equipado con un sensor de visión que maximice la probabilidad acumulada de detectar un objetivo dinámico dentro de un tiempo de búsqueda finito.

El problema se caracteriza por diversas complejidades:

Dinámica del Objetivo: El objetivo se modela como una entidad dinámica, que a menudo se desplaza debido a factores ambientales (p. ej., viento, corrientes) o su propio movimiento, lo que hace que el espacio de búsqueda dependa del tiempo.
Limitaciones del Sensor: La detección depende de un sensor de visión (cámara RGB), donde la probabilidad de detección no es binaria, sino una función de la calidad de la imagen, el contraste del objetivo y las capacidades de visión del observador.
Restricciones Cinemáticas: El UAV tiene limitaciones físicas con respecto a la velocidad, los ángulos de giro y la altitud, las cuales deben respetarse para asegurar que la trayectoria generada sea factible.
Complejidad Computacional: El problema de búsqueda se formula como un problema de optimización NP-duro donde el número de soluciones factibles crece exponencialmente con el tiempo y el espacio de búsqueda, lo que hace que los métodos de optimización exacta clásicos (p. ej., cálculo diferencial) sean impracticables.

Metodología

Los autores proponen un marco integral que combina el modelado probabilístico, la estimación bayesiana y un nuevo algoritmo metaheurístico.

1. Modelado Matemático:

Dinámica del Objetivo: El movimiento del objetivo se modela como un proceso de Markov determinista. La probabilidad de transición se representa mediante una función delta de Dirac, asumiendo que el siguiente estado del objetivo depende únicamente de su estado actual y de los parámetros cinemáticos conocidos (velocidad y rumbo). La incertidumbre en la ubicación inicial se captura mediante un mapa de creencias gaussiano.
Modelo de Detección: La verosimilitud de detección se deriva del modelo NVESD (Desarrollo de Simulación e Ingeniería de Visión Nocturna). Este modelo calcula el Rendimiento de Seguimiento del Objetivo (TTP) basándose en la uniformidad de la imagen, los umbrales de visión del observador y el contraste del objetivo. La probabilidad de detección $p(D_k|\xi^t_k)$ es una función del tamaño del objetivo, la huella de la cámara y la geometría de visualización.
Actualización de la Creencia: Se emplea un marco bayesiano recursivo. El proceso implica una fase de predicción (utilizando la ecuación de Chapman-Kolmogorov para propagar el mapa de creencias basado en la dinámica del objetivo) y una fase de actualización (ajustando el mapa de creencias basándose en la verosimilitud de los eventos de "no detección" observados por el UAV).
Función Objetivo: La estrategia de búsqueda pretende maximizar la probabilidad de detección acumulada $P_N$ sobre $N$ pasos. La función de aptitud (fitness) $J$ se define como la suma de las probabilidades de detectar al objetivo por primera vez en cada paso.

2. Evolución Diferencial basada en Coordenadas Polares (PDE):
Para resolver el problema de optimización NP-duro, los autores introducen un algoritmo de Evolución Diferencial (DE) modificado y adaptado para la planificación de trayectorias de UAV.

Transformación de Coordenadas: A diferencia de la DE estándar que opera en coordenadas cartesianas ( $x, y$ ), la PDE propuesta codifica la trayectoria de vuelo en coordenadas polares. Cada segmento de la trayectoria está representado por una longitud de paso ( $\rho$ ) y un ángulo de guiñada ( $\psi$ ).
Integración de Restricciones: Al utilizar coordenadas polares, las restricciones cinemáticas (velocidad máxima, radio de giro mínimo) se integran directamente en el espacio de búsqueda limitando los rangos de $\rho$ y $\psi$ . Esto asegura que todas las soluciones candidatas generadas sean físicamente factibles para el UAV.
Flujo del Algoritmo: El algoritmo sigue las operaciones estándar de la DE (mutación, cruce, selección), pero opera sobre la población codificada en polares.
- Mutación: Genera nuevas trayectorias añadiendo la diferencia entre dos individuos a un individuo base en el espacio polar.
- Cruce: Combina las trayectorias mutantes y las existentes.
- Selección: Convierte las trayectorias polares a puntos de paso (waypoints) cartesianos para evaluar la función de aptitud (probabilidad de detección acumulada) y selecciona los mejores individuos para la siguiente generación.

Contribuciones Clave

El artículo describe tres contribuciones primarias:

Formulación del Problema: El problema de búsqueda se formula rigurosamente como una tarea de optimización que integra restricciones prácticas, incluyendo la dinámica del objetivo (proceso de Markov), modelos de sensores (visión basada en NVESD) e incertidumbre de la información inicial.
Desarrollo del Algoritmo PDE: Se desarrolla un nuevo algoritmo de Evolución Diferencial basada en Coordenadas Polares (PDE). Al mapear el espacio de soluciones a coordenadas polares, el algoritmo incorpora naturalmente las restricciones cinemáticas del UAV, estrecha el espacio de búsqueda y mitiga el riesgo de converger a óptimos locales en comparación con los enfoques basados en cartesianas.
Validación Experimental: La practicidad del método se valida mediante extensas simulaciones en diversos escenarios (variando tamaños de mapa y movimientos del objetivo) y experimentos en el mundo real utilizando una plataforma de UAV física (dron 3DR Solo).

Resultados

El rendimiento de la PDE se evaluó frente a algoritos metaheurísticos de vanguardia, incluyendo DE estándar, Algoritmo Genético (GA), Optimización por Enjambre de Partículas (PSO), Optimización del Lobo Gris (GWO) y Gaining-Sharing Knowledge (GSK).

Probabilidad de Detección: En simulaciones a través de seis escenarios con distintos tamaños de mapa (600 m a 2000 m) y conteos de puntos de paso, la PDE logró la mayor probabilidad de detección acumulada en 5 de los 6 escenarios. En el escenario restante, se situó a menos del 0.2% del algoritmo con mejor desempeño (GSK). La DE estándar tuvo un desempeño deficiente en varios escenarios, quedando atrapada frecuentemente en óptimos locales.
Tiempo de Ejecución: La PDE demostró una eficiencia computacional superior, siendo el algoritmo más rápido en 5 de los 6 escenarios. Los autores atribuyen esto a la eliminación de las costosas conversiones trigonométricas requeridas en la DE basada en cartesianas para derivar ángulos de rumbo y longitudes de paso.
Escalabilidad y Robustez: El algoritmo mantuvo su rendimiento a medida que aumentaban los tamaños del mapa, aunque la probabilidad de detección disminuyó naturalmente con áreas de búsqueda más grandes debido a la dispersión del mapa de creencias. El método también mostró tendencias consistentes bajo distintos niveles de incertidumbre inicial ( $\sigma_0$ ).
Validación en el Mundo Real: Los experimentos con un UAV real generaron y ejecutaron con éxito una trayectoria de vuelo factible. El UAV siguió la trayectoria planificada y el objetivo fue detectado dentro del campo de visión de la cámara, confirmando la viabilidad de las trayectorias generadas y la validez del enfoque teórico.

Significación y Reivindicaciones

El artículo afirma que el algoritmo PDE propuesto ofrece un equilibrio superior entre la probabilidad de detección y el tiempo de ejecución en comparación con los métodos existentes. Su significación radica en:

Factibilidad: Al codificar las trayectorias en coordenadas polares, el algoritmo respeta intrínsecamente las restricciones cinemáticas del UAV, asegurando que las trayectorias de búsqueda generadas sean ejecutables por hardware real.
Eficiencia: El uso directo de variables polares reduce la carga computacional, haciendo que el algoritmo sea adecuado para operaciones de búsqueda y rescate en tiempos críticos.
Practicidad: La integración de modelos de sensores realistas (NVESD) y la dinámica del objetivo hace que el enfoque sea aplicable a escenarios del mundo real que involucran objetivos en movimiento y condiciones de detección imperfectas.

Los autores concluyen que, si bien un solo UAV tiene limitaciones para cubrir áreas grandes debido a la batería y las restricciones de trayectoria, el marco propuesto proporciona una base sólida para futuras extensiones hacia sistemas coordinados de múltiples UAV para entornos dinámicos a gran escala.