💻 computer science

Distributed Lloyd-Based algorithm for uncertainty-aware multi-robot under-canopy flocking

Este artículo presenta un algoritmo distribuido para el vuelo en formación de múltiples robots bajo la cubierta forestal que garantiza la evitación de colisiones y el mantenimiento de la proximidad utilizando únicamente sensores a bordo y sin comunicación explícita, validado mediante simulaciones y experimentos reales en bosques densos.

Autores originales: Manuel Boldrer, Vit Kratky, Viktor Walter, Martin Saska

Publicado 2026-03-02

📖 4 min de lectura☕ Lectura para el café

CC BY 4.0

Autores originales: Manuel Boldrer, Vit Kratky, Viktor Walter, Martin Saska

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

¡Claro que sí! Imagina que tienes un grupo de amigos (drones) que quieren caminar juntos por un bosque muy denso, lleno de árboles, ramas y terreno difícil. Ellos no tienen teléfonos para hablar entre sí, ni un mapa del bosque, ni siquiera saben dónde está el norte (no usan GPS). Sin embargo, quieren llegar a un punto específico manteniéndose cerca unos de otros, como un rebaño de ovejas o un banco de peces, sin chocar entre ellos ni contra los árboles.

Este artículo presenta una "receta" o algoritmo inteligente que permite que esto suceda. Aquí te lo explico con una analogía sencilla:

1. El Problema: El Bosque de los "Sordos y Ciegos"

Imagina que los drones son como personas vendadas en un bosque. No pueden gritar para avisar a los demás "¡Oye, voy a la izquierda!" (no hay comunicación). No tienen un mapa (no saben dónde están los árboles). Solo tienen sus propios ojos (sensores) para ver lo que tienen justo enfrente.

El reto es doble:

No chocar: Si caminan rápido, podrían chocar contra un árbol o contra su amigo.
No separarse: Si uno se va muy lejos, el grupo se rompe y pierden la ventaja de trabajar en equipo.

2. La Solución: El "Pastor Invisible" (El Algoritmo de Lloyd)

Los autores usan una idea matemática llamada Algoritmo de Lloyd, que es como un "pastor invisible".

Imagina que el bosque está dividido en "territorios" invisibles para cada dron (como un mapa de Voronoi). Cada dron tiene su propio territorio y su objetivo es ir al centro exacto de su territorio.

Si el territorio se hace pequeño porque hay un árbol cerca, el dron se mueve para no chocar.
Si el territorio se hace grande porque hay espacio, el dron avanza hacia su meta.

Pero, ¿cómo se mantienen juntos si no hablan? Aquí entra la parte mágica: El algoritmo redefine los bordes de sus territorios. En lugar de tener un territorio fijo, el dron ajusta su "zona de seguridad" para asegurarse de que sus amigos siempre estén dentro de su rango de visión, como si cada dron tuviera una cuerda elástica imaginaria que lo mantiene cerca de sus vecinos.

3. El Truco de la "Caja de Seguridad" (Manejo de Errores)

Este es el punto más importante y genial del artículo. Los sensores de los drones no son perfectos. A veces, el dron cree que un árbol está a 5 metros, pero en realidad está a 4.8 metros. O cree que su amigo está a 10 metros, pero en realidad está a 10.5.

Si el dron se mueve con confianza total, podría chocar.
La solución: El algoritmo actúa como un paranoico muy inteligente.

Imagina que el dron dibuja un "círculo de duda" alrededor de todo lo que ve.
En lugar de ir al centro de su territorio, el dron elige un punto que esté lejos de los bordes de ese territorio.
¿Por qué? Porque si hay un error de medición (el dron se equivocó un poco), el dron seguirá estando a salvo dentro de su zona segura. Es como si caminaras por un acantilado y decidieras caminar siempre a 2 metros del borde, por si acaso te resbalas o ves mal la distancia.

El artículo demuestra que, incluso si los sensores fallan un poco o el dron se mueve de forma un poco torpe, este "margen de seguridad" garantiza que nadie chocará y nadie se perderá.

4. La Prueba de Fuego: El Bosque Real

No solo lo probaron en una computadora (simulación), sino que lo llevaron a un bosque real en la República Checa.

Pusieron hasta 4 drones volando entre árboles.
No usaron GPS (que no funciona bien bajo las hojas de los árboles).
No usaron radio para hablar entre ellos.
Usaron una cámara especial que ve luces ultravioletas (como si los drones llevaran gafas de sol especiales para verse entre sí).

El resultado: ¡Funcionó! Los drones lograron cruzar el bosque, esquivar árboles, mantenerse juntos y llegar a la meta sin chocar ni perderse, todo tomando decisiones por sí mismos, como un enjambre de abejas.

En Resumen

Este artículo nos dice que podemos tener un grupo de robots que actúen como un solo organismo inteligente, incluso si están "sordos" (sin comunicación), "ciegos" (sin mapa global) y en un entorno caótico (un bosque). La clave es ser conservador y prudente: asumir que tus sentidos pueden fallar y dejar siempre un margen de seguridad, ajustando tu camino en tiempo real para mantener el equilibrio entre "ir rápido" y "no chocar".

Es como enseñar a un grupo de amigos a caminar de la mano en la oscuridad sin chocar contra las paredes, solo sintiendo el espacio que tienen a su alrededor.

Resumen Técnico: Algoritmo Distribuido Basado en Lloyd para Agrupamiento (Flocking) Multi-robot bajo Cobertura con Conciencia de Incertidumbre

1. Planteamiento del Problema

El trabajo aborda el desafío de coordinar un enjambre de robots (específicamente UAVs) en entornos complejos y densamente cluttered (como un bosque), operando a una altitud constante. El problema central se define bajo las siguientes restricciones críticas:

Sin comunicación explícita: Los robots no pueden intercambiar información dependiente del tiempo (trayectorias futuras, posiciones, velocidades) ni depender de un marco de referencia común.
Sin información a priori: No se conoce el mapa del entorno ni la ubicación de los obstáculos antes de la misión.
Solo sensores a bordo: La toma de decisiones se basa exclusivamente en la percepción local (IMU, Lidar 2D, altímetro y sistema UVDAR).
Restricciones de seguridad y proximidad: Los robots deben evitar colisiones con obstáculos y entre sí, manteniendo simultáneamente una distancia máxima predefinida con un conjunto de vecinos (requisito de flocking o mantenimiento de proximidad).
Incertidumbre: El sistema debe ser robusto frente a errores de seguimiento (tracking errors) y errores de medición de los sensores.

El objetivo es sintetizar una ley de control distribuida que garantice que el enjambre alcance una región objetivo manteniendo la cohesión del grupo y evitando colisiones, a pesar de las incertidumbres y la falta de comunicación.

2. Metodología Propuesta

La propuesta se basa en una adaptación del Algoritmo de Lloyd, tradicionalmente utilizado para la partición de Voronoi, modificándolo para entornos dinámicos y con incertidumbre.

Diagramas de Voronoi Ponderados Convexos (CWVD):
- Se utiliza un diagrama de Voronoi que considera tanto a los robots vecinos como a los obstáculos.
- Se introduce un parámetro de cautela $\epsilon$ (donde $\epsilon=1$ es más agresivo y $\epsilon=2$ corresponde al diagrama de Voronoi clásico) para regular la conservadurismo del movimiento.
- La celda de cada robot ( $V_i$ ) se redefine para incluir restricciones de proximidad y seguridad.
Reconfiguración de la Geometría de la Celda ( $F_i$ ):
- La celda final $F_i$ $F_{i}$ es la intersección de tres conjuntos:
  1. $\tilde{V}^p_i$ : Celda Voronoi ajustada para robots vecinos (considerando el radio físico de los robots).
  2. $\tilde{V}^o_i$ : Celda Voronoi ajustada para obstáculos.
  3. $S_i$ : Celda limitada por el radio de detección del sensor.
  4. $M_i$ : Conjunto de puntos que satisfacen la restricción de proximidad con los vecinos designados ( $\|q - p_j\| \le \Gamma_{ij}$ ).
- Teoremas de Seguridad: Se demuestra que si el robot se mueve hacia el centroide de su celda $F_i$ (que es un conjunto convexo), se garantiza la ausencia de colisiones en todo momento.
Función de Ponderación Adaptativa ( $\phi_i(q)$ ):
- Se utiliza una función de distribución tipo Laplaciana centrada en una posición objetivo $\bar{p}_i$ .
- Se introduce un factor de dispersión $\beta_i$ que varía en el tiempo. Este factor controla la "codicia" del robot: un $\beta_i$ pequeño acerca el centroide al objetivo (más agresivo), mientras que un $\beta_i$ grande lo aleja de los bordes de la celda (más conservador).
Gestión de Incertidumbres y Errores:
- Estrategia Adaptativa: En lugar de reconfigurar la celda geométrica (lo cual podría dejar al robot sin celda definida debido a errores), se ajusta dinámicamente $\beta_i$ .
- Se define una distancia de margen $d_u$ que suma el error máximo de seguimiento ( $d^t_u$ ) y la incertidumbre de medición ( $d^m_u$ ).
- Se impone un límite inferior a $\beta_i$ ( $\beta^{min}_i$ ) para asegurar que el centroide de la celda permanezca a una distancia segura ( $d_u$ ) de los bordes de la celda, compensando así los errores de estimación de posición de los vecinos y obstáculos.
Control de Dinámica:
- La ley de control se implementa mediante un Control Predictivo Basado en Modelos (MPC) para manejar las dinámicas no ideales de los UAVs, las restricciones de entrada y los errores de seguimiento.

3. Contribuciones Clave

Algoritmo Distribuido sin Comunicación: Se logra un comportamiento de flocking cohesivo en entornos densos sin necesidad de redes de comunicación explícitas ni sistemas de localización global (GNSS).
Garantías Teóricas de Seguridad y Proximidad: Se establecen condiciones suficientes para garantizar la evitación de colisiones y el mantenimiento de la proximidad, incluso en presencia de errores de seguimiento y medición acotados.
Estrategia de Adaptación de Parámetros: Se propone un método sistemático para seleccionar los parámetros del algoritmo (específicamente $\beta$ y las distancias de margen) basándose en cantidades medibles (covarianza de estimación, errores de seguimiento), eliminando la necesidad de ajustes empíricos finos típicos en el estado del arte.
Validación en Escenarios No Estructurados: Es uno de los pocos trabajos que valida experimentalmente un algoritmo de flocking en un bosque real con múltiples UAVs, utilizando solo sensores a bordo.

4. Resultados

Simulaciones:
- Se probaron enjambres de hasta 16 robots en entornos con obstáculos aleatorios.
- Comparado con el algoritmo PACNav (otro método sin comunicación), la propuesta demostró una mayor escalabilidad y tasa de éxito (100% en escenarios complejos donde PACNav falló).
- La inclusión de la gestión de incertidumbres ( $d_u > 0$ ) aumentó el tiempo de misión ligeramente pero garantizó la seguridad, mientras que $d_u=0$ resultaba en colisiones.
Experimentos Reales:
- Se realizaron pruebas en un bosque denso con hasta 4 UAVs.
- Sensores: Se utilizó RPLiDAR A3 para obstáculos, Hector SLAM para mapeo local y el sistema UVDAR (LEDs UV y cámaras) para la detección relativa de otros robots sin GNSS.
- Rendimiento: Todos los UAVs alcanzaron el objetivo manteniendo las restricciones de seguridad y proximidad durante toda la misión, a pesar de las oclusiones de árboles y errores de medición.
- Se demostró la robustez del algoritmo ante variaciones de parámetros y la naturaleza caótica del entorno.

5. Significado e Impacto

Este trabajo representa un avance significativo en la robótica de enjambres para aplicaciones en entornos no estructurados (búsqueda y rescate, monitoreo forestal, agricultura).

Independencia de Infraestructura: Al eliminar la dependencia de comunicaciones y GNSS, el sistema es viable en zonas donde la infraestructura es inexistente o está dañada.
Robustez Operativa: La capacidad de manejar incertidumbres de forma explícita y adaptativa permite operar de manera segura en condiciones reales, donde los sensores nunca son perfectos.
Escalabilidad: La naturaleza distribuida y asincrónica del algoritmo permite que el sistema escale a un mayor número de robots sin degradar el rendimiento de la seguridad.
Reproducibilidad: El código es de código abierto y los experimentos se realizaron en un entorno real, proporcionando una base sólida para futuras investigaciones en coordinación multi-robot bajo restricciones severas.

En conclusión, el artículo presenta una solución teóricamente fundamentada y experimentalmente validada para el control de enjambres en entornos complejos, superando las limitaciones de métodos anteriores que requerían comunicación o ignoraban las incertidumbres de los sensores.