💻 computer science

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

Questa lettera presenta un algoritmo distribuito per il flocking di robot multipli sotto chioma che, operando a quota costante senza comunicazione esplicita o informazioni pregresse, garantisce l'evitamento delle collisioni e il mantenimento della formazione in ambienti complessi e affollati, come dimostrato da simulazioni ed esperimenti reali in una fitta foresta.

Autori originali: Manuel Boldrer, Vit Kratky, Viktor Walter, Martin Saska

Pubblicato 2026-03-02

📖 4 min di lettura☕ Lettura da pausa caffè

CC BY 4.0

Autori originali: Manuel Boldrer, Vit Kratky, Viktor Walter, Martin Saska

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

🌲 Il "Branco di Uccelli" che non parla, ma si guarda intorno

Immagina di dover guidare un gruppo di piccoli droni attraverso una foresta fitta e buia. Non c'è GPS, non c'è internet e non possono parlarsi tra loro (nessun WhatsApp o radio). Devono solo guardarsi intorno, evitare gli alberi e tenersi vicini, come un branco di uccelli che vola insieme.

Questo è esattamente il problema che gli autori di questo articolo hanno risolto. Hanno creato un "cervello" digitale per i droni che permette loro di muoversi in gruppo in modo sicuro, anche se non sanno esattamente dove si trovano gli altri o se i loro sensori fanno un po' di confusione.

Ecco come funziona, spiegato con delle metafore:

1. La "Torta" che si divide da sola (L'Algoritmo di Lloyd)

Pensa alla foresta come a una grande torta. I droni sono le persone che vogliono mangiarla.

Il vecchio modo: Ognuno cerca di prendere la fetta più grande possibile, rischiando di litigare o di finire contro un albero.
Il nuovo metodo (Lloyd): Immagina che ogni drone disegni una linea invisibile a metà strada tra sé e il drone più vicino. Questo divide la foresta in "territori" (come le celle di un alveare). Ogni drone sa che il suo compito è stare al centro del suo territorio.
Il trucco: Se un drone si sposta, le linee si ridisegnano automaticamente. È come se la torta si riformasse istantaneamente per dare a tutti uno spazio sicuro.

2. La "Bolla di Sicurezza" (Evitare gli ostacoli)

Nella foresta ci sono alberi, rami e rocce. I droni non sanno dove sono esattamente, ma hanno dei sensori (come occhi laser).

Gli autori hanno creato una bolla di sicurezza attorno a ogni drone. Se questa bolla tocca un albero o un altro drone, il sistema dice: "Stop! Non andare lì".
È come se ogni drone avesse un'aura magica che lo protegge. Se l'aura tocca qualcosa, il drone cambia rotta immediatamente per non scontrarsi.

3. Il "Freno di Emergenza" per gli errori (Gestione dell'incertezza)

Qui sta la vera genialità. I sensori dei droni non sono perfetti. A volte pensano che un albero sia più vicino di quanto non sia, o che un altro drone sia più lontano.

L'analogia del conducente: Se guidi di notte e vedi una nebbia fitta, non vai a tutta velocità. Rallenti e tieni una distanza maggiore dal bordo della strada.
Nel paper: Il drone calcola quanto "nebbia" (errore) c'è. Se i sensori sono incerti, il drone diventa più "pavido" (conservativo). Allarga il suo territorio e si sposta più lontano dai bordi pericolosi. Se i sensori sono sicuri, può essere più veloce e audace.
Questo permette ai droni di non andare in crash anche quando i loro "occhi" vedono cose un po' sfocate.

4. Il "Branco" (Mantenere la vicinanza)

Non basta evitare gli alberi; i droni devono anche stare vicini tra loro (flocking), come un branco di pesci.

Il sistema ha una regola: "Non allontanarti troppo dal tuo migliore amico".
Anche se un drone vuole andare veloce, se il suo amico è indietro, il sistema lo rallenta o lo spinge indietro per mantenere la formazione. È come se fossero legati da un elastico invisibile che non si spezza mai.

🌳 La prova sul campo: La Foresta Reale

Gli autori non si sono fermati ai computer. Hanno preso dei droni veri e li hanno mandati in una foresta vera, senza GPS e senza comunicazione radio tra di loro.

Cosa è successo? Hanno volato fino a 4 droni insieme, navigando tra gli alberi, evitando collisioni e mantenendosi vicini.
Il risultato: Funziona! Anche con errori di misurazione e senza sapere esattamente dove sono gli altri, il sistema li ha tenuti al sicuro.

In sintesi

Questo articolo ci dice che non serve un "capo" che comanda tutti, né una rete internet perfetta per far volare un gruppo di robot insieme. Basta dare a ogni robot delle regole semplici (stai al centro del tuo spazio, non toccare gli altri, tieni conto dei tuoi errori) e il gruppo si muoverà come un'unica entità intelligente e sicura, proprio come un branco di uccelli che attraversa una tempesta.

È un passo avanti enorme per far volare sciami di droni in luoghi difficili come foreste, città caotiche o zone di disastro, dove le comunicazioni sono impossibili.

Titolo: Algoritmo distribuito basato su Lloyd per lo sciame di robot multipli sotto chioma (under-canopy) consapevole dell'incertezza

1. Problema e Contesto

Il lavoro affronta la sfida del controllo di sciami di robot (in particolare UAV) in ambienti complessi, densi e non strutturati, come le foreste. L'obiettivo è realizzare un comportamento di "flocking" (mantenimento della vicinanza tra i robot) mentre si naviga verso una destinazione, soddisfacendo vincoli rigorosi:

Ambiente: Operazione in spazi affollati (ostacoli come alberi) senza mappatura a priori.
Comunicazione: Assenza di comunicazione esplicita tra i robot (nessuno scambio di traiettorie future, posizioni o velocità).
Localizzazione: Utilizzo esclusivo di sensori di bordo (IMU, Lidar 2D, altimetro, sistema UVDAR) senza GNSS o sistemi di cattura del movimento esterni.
Vincoli: Garantire l'evitamento delle collisioni (con ostacoli e altri robot) e il mantenimento della vicinanza (proximity maintenance) entro una distanza massima definita, nonostante errori di tracciamento (tracking errors) e incertezze di misurazione.

2. Metodologia Proposta

L'approccio si basa su una modifica distribuita dell'algoritmo di Lloyd, tipicamente usato per la partizione di Voronoi, adattato per la navigazione multi-robot.

Diagrammi di Voronoi Ponderati Convessi (CWVD):
- Viene utilizzato un CWVD per definire la cella di responsabilità di ogni robot ( $V_i$ ), considerando solo le posizioni relative dei robot vicini e degli ostacoli.
- La cella è definita come l'intersezione di tre sotto-insiemi:
  1. $\tilde{V}^p_i$ : Cella basata sui robot vicini (per il flocking).
  2. $\tilde{V}^o_i$ : Cella basata sugli ostacoli (per la sicurezza).
  3. $S_i$ : Cella limitata dal raggio di sensing del robot.
- Un parametro $\epsilon$ regola il comportamento (da aggressivo a conservativo).
Ridefinizione della Geometria della Cella per la Sicurezza:
- Per garantire la sicurezza fisica, la cella viene ulteriormente ridotta tenendo conto del raggio fisico dei robot ( $\delta$ ) e degli ostacoli.
- Viene introdotta una cella finale $F_i = A_i \cap M_i$ , dove $M_i$ è l'insieme che impone il vincolo di vicinanza massima ( $\Gamma_{ij}$ ) con i vicini.
- Teoremi di Sicurezza: Gli autori dimostrano che, muovendosi verso il baricentro ( $c_{F_i}$ ) della cella $F_i$ , il robot garantisce l'evitamento delle collisioni e il mantenimento della vicinanza, poiché il percorso rettilineo verso il baricentro rimane all'interno della cella convessa sicura.
Gestione delle Incertezze e degli Errori:
- Il cuore dell'innovazione è una strategia adattiva per gestire gli errori di tracciamento (dovuti alla dinamica del robot) e le incertezze di misurazione (rumore dei sensori).
- Invece di ridisegnare la cella (che potrebbe diventare vuota), si adatta il fattore di diffusione $\beta_i$ della funzione di peso $\phi_i(q)$ (una funzione a campana Laplaciana centrata sul punto obiettivo).
- Un valore di $\beta_i$ più alto spinge il baricentro più lontano dai bordi della cella, creando un margine di sicurezza.
- Viene calcolato un limite inferiore $\beta_{min}$ basato sulla somma degli errori massimi attesi (errore di tracciamento $d_u^t$ + incertezza di misura $d_u^m$ ). Questo garantisce che il baricentro rimanga a una distanza di sicurezza dai bordi della cella, anche in presenza di errori.
Controllo Dinamico:
- Il controllo di riferimento viene implementato tramite un MPC (Model Predictive Control) per rispettare la dinamica reale del drone (velocità, accelerazione), risolvendo un problema di ottimizzazione a ogni passo.

3. Contributi Chiave

Algoritmo Distribuito Senza Comunicazione: Un metodo che permette a uno sciame di operare in foreste dense senza rete di comunicazione e senza un sistema di riferimento globale comune.
Condizioni di Sicurezza Sufficienti: Dimostrazione teorica che garantisce l'evitamento delle collisioni e il mantenimento della vicinanza anche in presenza di errori di stima e tracciamento.
Strategia Adattiva per l'Incertezza: Un approccio innovativo che regola l'aggressività del robot (tramite $\beta$ ) in base alle incertezze misurate, evitando che il robot esca dalla sua cella di sicurezza a causa del rumore.
Validazione Reale: Implementazione e test su piattaforme reali (fino a 4 UAV) in un ambiente forestale reale, utilizzando solo sensori di bordo (UVDAR per la localizzazione relativa, Lidar per gli ostacoli).

4. Risultati

Simulazioni:
- Testati sciami di 9 e 16 robot in ambienti con ostacoli casuali.
- Confronto con l'algoritmo PACNav: il metodo proposto ha mostrato una scalabilità superiore e un tasso di successo del 100% nel mantenere sicurezza e vincoli di vicinanza, mentre PACNav falliva in scenari complessi o con molti robot.
- L'uso del parametro $d_u$ (margine di sicurezza) ha dimostrato di sacrificare leggermente la velocità di arrivo per garantire la sicurezza assoluta.
Esperimenti Reali (Foresta):
- Eseguiti con 3 e 4 UAV in una foresta senza segnale GNSS.
- I robot hanno navigato con successo verso un obiettivo a 40 metri di distanza, mantenendo la formazione e evitando collisioni con alberi e tra loro.
- Sono stati dimostrati la robustezza del sistema e la capacità di gestire errori temporanei di stima (es. occlusione degli alberi) tramite strategie pratiche di proiezione delle posizioni.
- I dati sperimentali confermano che i vincoli di sicurezza e di vicinanza sono stati rispettati per tutta la durata della missione.

5. Significato e Impatto

Questo lavoro rappresenta un passo significativo verso l'autonomia reale degli sciami di robot in ambienti non strutturati.

Indipendenza dall'Infrastruttura: La capacità di operare senza GNSS e senza comunicazione inter-robot rende la soluzione ideale per missioni di ricerca e soccorso, monitoraggio ambientale o operazioni militari in aree remote.
Robustezza Teorica e Pratica: A differenza di molti approcci esistenti che richiedono un tuning empirico fine dei parametri per garantire la sicurezza, questo metodo fornisce condizioni sufficienti basate su grandezze misurabili (errori di covarianza, errori di tracciamento).
Scalabilità: L'approccio dimostra di funzionare bene sia in simulazione con molti robot che in scenari reali con limitazioni hardware, aprendo la strada a future estensioni 3D e a sciami più grandi.

In sintesi, il paper presenta una soluzione completa che unisce teoria geometrica (Voronoi), controllo adattivo e validazione sperimentale rigorosa per risolvere il problema del flocking sicuro in ambienti ostili e incerti.