💻 computer science

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

Este artigo apresenta um algoritmo distribuído para formação de enxames de robôs sob copas de árvores que, utilizando apenas sensores e computação a bordo sem comunicação explícita ou conhecimento prévio do ambiente, garante a manutenção da proximidade e a evasão de colisões em cenários densos, conforme validado por simulações e experimentos reais com drones em florestas.

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

Publicado 2026-03-02

📖 4 min de leitura☕ Leitura rápida

CC BY 4.0

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

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você tem um grupo de pequenos pássaros robóticos (drones) que precisam voar juntos em uma floresta densa, cheia de galhos, folhas e árvores. O objetivo deles é chegar a um ponto específico, mas sem bater uns nos outros, sem bater nas árvores e, o mais importante, mantendo-se sempre próximos uns dos outros, como um bando de pássaros reais.

O problema é que, nessa floresta, eles não podem usar Wi-Fi para conversar (não há comunicação explícita) e não têm GPS (o sinal não chega lá dentro). Cada drone precisa tomar suas próprias decisões olhando apenas para o que está ao seu redor, usando seus próprios "olhos" (sensores) e "cérebro" (computador de bordo).

Este artigo apresenta uma solução inteligente para esse desafio, chamada de Algoritmo Distribuído Baseado em Lloyd. Aqui está a explicação simplificada:

1. O Conceito Principal: O "Mapa de Territórios"

Pense no algoritmo como uma forma de dividir a floresta em territórios invisíveis para cada drone.

A Metáfora do Voronoi: Imagine que cada drone joga uma pedra no chão e desenha um círculo ao redor dela. Se outro drone joga uma pedra perto, o espaço entre eles é dividido ao meio. Cada drone fica responsável por cuidar da sua própria "fatia" de território.
O Algoritmo Lloyd: É uma regra matemática que diz: "Para ser o melhor dono do seu território, você deve voar para o centro exato da sua fatia." Se todos fizerem isso, eles se espalham de forma organizada e cobrem a área sem se chocar.

2. O Desafio da Floresta (Obstáculos e Erros)

Na teoria, isso é fácil. Mas na floresta real, existem dois problemas grandes:

Obstáculos: As árvores ocupam espaço. Se o drone voar para o centro do seu território e houver uma árvore ali, ele vai bater.
Erros de Medição: Os sensores dos drones não são perfeitos. Eles podem achar que uma árvore está a 5 metros, quando na verdade está a 4,5. Eles podem achar que o amigo está a 10 metros, quando está a 11.

3. A Solução Criativa: "Bolhas de Segurança" e "Cobertores"

Os autores criaram uma estratégia de três camadas para resolver isso:

Ajustando o Território (Geometria): Em vez de desenhar linhas retas, o algoritmo "esmaga" o território do drone se houver uma árvore perto. Ele cria uma barreira invisível ao redor das árvores e dos outros drones. O drone só pode voar dentro da parte segura do seu território.
A "Bolha de Incerteza" (O Cobertor): Como os sensores erram um pouco, o drone não vai direto para o centro exato do território. Ele deixa uma margem de segurança, como se estivesse usando um cobertor grosso.
- Analogia: Imagine que você está dirigindo à noite com neblina. Você não dirige exatamente no meio da faixa; você fica um pouco mais para o lado, deixando espaço caso o carro ao lado se mova ou se você tenha errado a distância. O algoritmo faz isso calculando um "espaço extra" (chamado de du) para garantir que, mesmo com erros de medição, ninguém bata em ninguém.
A Regra do "Não se Afaste": Para garantir que o bando não se separe, o algoritmo adiciona uma regra extra: "Você pode ir para o centro do seu território, mas não pode ir tão longe que saia da distância máxima permitida do seu amigo mais próximo." É como se eles estivessem todos ligados por elásticos invisíveis.

4. Como eles testaram?

Eles não ficaram apenas no computador.

Simulação: Eles criaram florestas virtuais com 16 drones e viram que o sistema funcionava perfeitamente, evitando colisões mesmo com erros simulados.
Realidade: Eles levaram até 4 drones reais para uma floresta densa na República Tcheca. Os drones voaram sozinhos, sem GPS e sem conversar entre si, usando apenas câmeras e sensores a laser para ver as árvores e os outros drones. Eles conseguiram atravessar a floresta mantendo o grupo unido e sem bater em nada.

Resumo em uma frase

É como ensinar um bando de drones a voar em uma floresta escura e cheia de árvores, onde eles não podem falar entre si, mas conseguem se manter juntos e seguros porque cada um calcula seu próprio caminho, deixando sempre uma margem de segurança extra caso seus sensores "vejam" as coisas um pouco erradas.

Por que isso é importante?
Isso permite que robôs trabalhem em lugares onde o sinal de internet ou GPS não funciona (como florestas, cavernas ou em caso de desastres), realizando missões de busca, resgate ou monitoramento ambiental de forma autônoma e segura.

1. Problema Abordado

O artigo aborda o desafio de coordenar um enxame de robôs aéreos (UAVs) para realizar tarefas de "flocking" (voo em formação/agrupamento) em ambientes complexos e densamente obstruídos, especificamente sob copas de árvores (florestas).

Os principais desafios identificados são:

Ausência de comunicação explícita: Os robôs não podem trocar dados como trajetórias futuras, posições ou velocidades em tempo real.
Falta de infraestrutura externa: Não há acesso a sistemas de localização global (GNSS/GPS) ou sistemas de captura de movimento externos.
Incertezas e Erros: O sistema deve lidar com erros de rastreamento (tracking errors) devido à dinâmica do robô e incertezas de medição provenientes dos sensores a bordo.
Restrições de Segurança e Proximidade: É necessário garantir a ausência de colisões com obstáculos e outros robôs, ao mesmo tempo em que se mantém uma distância máxima pré-definida entre os vizinhos (manutenção da proximidade/flocking).

2. Metodologia Proposta

Os autores propõem um algoritmo de controle distribuído baseado no Algoritmo de Lloyd, adaptado para lidar com incertezas e ambientes não estruturados.

A. Fundamentação Teórica (Diagramas de Voronoi Ponderados)

O núcleo do método utiliza Diagramas de Voronoi Ponderados Convexos (CWVD). Cada robô calcula sua célula de Voronoi ( $V_i$ ) baseada apenas nas posições relativas dos vizinhos e obstáculos detectados localmente.

A função de custo é minimizada através do gradiente, levando cada robô ao centróide de sua célula.
Para garantir segurança, a geometria da célula é remodelada ( $A_i$ ) para garantir que o caminho do robô até o centróide seja livre de colisões, considerando o raio físico dos robôs e obstáculos.

B. Manutenção da Proximidade (Flocking)

Para garantir que os robôs não se dispersem, a célula de Voronoi é further restringida por um conjunto $M_i$ , que define um limite máximo de distância ( $\Gamma_{ij}$ ) para os vizinhos. A célula final ( $F_i$ ) é a interseção da área segura e da área de proximidade.

Teorema 1 e 2: Os autores provam que, ao controlar o robô para o centróide da célula $F_i$ , garantem-se simultaneamente a segurança (sem colisões) e a manutenção da proximidade.

C. Estratégia Adaptativa para Incertezas

Uma contribuição central é a gestão de erros de rastreamento e incertezas de medição sem redefinir a geometria da célula (o que poderia tornar a célula vazia).

Função de Ponderação ( $\phi_i$ ): Utiliza-se uma função em forma de Laplaciano centrada em um ponto alvo ( $\bar{p}_i$ ).
Fator de Espalhamento ( $\beta_i$ ): O parâmetro $\beta_i$ $β_{i}$ é adaptado online. Ele controla a "ganância" do robô em relação ao objetivo.
- Um $\beta_i$ menor torna o robô mais agressivo (centróide mais próximo do objetivo/borda).
- Um $\beta_i$ maior torna o robô mais conservador (centróide mais afastado das bordas).
Mecanismo de Segurança: O valor mínimo de $\beta_i$ ( $\beta_{min}$ ) é calculado dinamicamente para garantir que o centróide permaneça a uma distância segura ( $d_u$ ) das bordas da célula. Essa distância $d_u$ é a soma dos erros máximos de rastreamento e das incertezas de medição (baseadas na covariância das estimativas). Isso cria uma margem de segurança que absorve os erros.

D. Implementação Prática

Controle: O comando de velocidade desejado é gerado via Model Predictive Control (MPC) para lidar com a dinâmica não linear dos UAVs.
Sensores: O sistema opera apenas com sensores a bordo: IMU, Lidar 2D, sensor de altitude e o sistema UVDAR (UltraViolet Direction And Ranging) para detecção relativa de outros robôs.

3. Principais Contribuições

Algoritmo Distribuído e Sem Comunicação: Um método que permite flocking em ambientes densos sem troca de dados explícita entre robôs e sem infraestrutura externa (GNSS).
Condições Suficientes de Segurança: Prova matemática de que o algoritmo garante ausência de colisões e manutenção da proximidade, mesmo na presença de erros de medição e rastreamento.
Estratégia de Adaptação de Incertezas: Um método inovador que ajusta a agressividade do robô (via $\beta_i$ ) para compensar erros, evitando que o robô saia de sua célula de segurança devido a imprecisões.
Validação Experimental Real: Demonstração bem-sucedida em um cenário real de floresta densa com até 4 UAVs, operando sem GPS e apenas com sensores a bordo.

4. Resultados

Simulações:
- Testes com até 16 robôs em ambientes com obstáculos aleatórios.
- Comparação com o algoritmo PACNav (estado da arte sem comunicação). O método proposto superou o PACNav em taxas de sucesso (100% vs 0% em cenários densos) e tempo de convergência, especialmente à medida que o número de robôs aumentava.
- Ajuste do parâmetro de incerteza ( $d_u$ ) mostrou que, embora um valor zero seja mais rápido, ele falha em evitar colisões; o valor calculado teoricamente garante segurança.
Experimentos Reais (Floresta):
- Realizado com 4 UAVs em uma floresta densa (sem GPS).
- Os robôs navegaram 40 metros em direção ao objetivo, mantendo as restrições de flocking e evitando colisões com árvores e entre si.
- O sistema lidou com oclusões temporárias e erros de medição do UVDAR através das estratégias práticas de rejeição de dados e re-projeção de posições.
- Todos os 4 robôs completaram a missão com sucesso, mantendo a segurança e a proximidade conforme a matriz de adjacência definida.

5. Significado e Relevância

Este trabalho é significativo porque preenche uma lacuna crítica na robótica de enxames: a capacidade de operar de forma autônoma, segura e coordenada em ambientes não estruturados e densos (como florestas ou escombros de desastres) sem depender de comunicações de rede ou infraestrutura externa.

A abordagem demonstra que é possível garantir segurança teórica (collision avoidance) e desempenho prático (flocking) mesmo com sensores imperfeitos e dinâmica de robôs complexa. A capacidade de operar sob copas de árvores, onde o GPS falha e a comunicação é bloqueada, torna esta tecnologia altamente relevante para aplicações de busca e resgate, monitoramento ambiental e inspeção de infraestrutura em áreas remotas. O código fonte é aberto, facilitando a reprodução e o avanço da pesquisa na área.