💻 computer science

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

Cet article présente un algorithme distribué permettant à des essaims de robots aériens de voler à altitude constante sous une canopée dense en évitant les collisions et en maintenant la cohésion du groupe, sans communication explicite ni connaissance préalable de l'environnement, tout en tenant compte des incertitudes de capteurs et de suivi.

Auteurs originaux : Manuel Boldrer, Vit Kratky, Viktor Walter, Martin Saska

Publié 2026-03-02

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Manuel Boldrer, Vit Kratky, Viktor Walter, Martin Saska

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

🌲 Le Défi : Se déplacer en groupe dans une forêt sans se perdre ni se cogner

Imaginez que vous devez envoyer une petite troupe de drones (des robots volants) pour explorer une forêt très dense, remplie d'arbres, de branches et de buissons. Le but est qu'ils arrivent ensemble à un endroit précis, en restant proches les uns des autres (comme un banc de poissons), mais sans jamais se percuter ni heurter un arbre.

Le problème, c'est que dans une forêt :

Pas de Wi-Fi : Les drones ne peuvent pas se parler par radio (le signal est bloqué par les arbres).
Pas de GPS : Le ciel est caché par le feuillage, ils ne savent pas où ils sont sur une carte globale.
Des capteurs imparfaits : Leurs "yeux" (caméras, lasers) voient parfois mal à cause de la poussière ou des ombres.

Comment faire pour qu'ils agissent comme une seule entité coordonnée sans jamais se donner de nouvelles ?

🕊️ La Solution : L'Algorithme "Lloyd" et la "Danse des Oiseaux"

Les chercheurs de l'Université technique de Prague ont créé un algorithme (un programme de cerveau) inspiré de la nature. Ils l'appellent un algorithme basé sur Lloyd.

Voici comment ça marche, avec une analogie simple :

1. Le concept du "Territoire Personnel" (Le Diagramme de Voronoï)

Imaginez que chaque drone dessine une bulle invisible autour de lui. Cette bulle représente tout l'espace qui lui appartient maintenant.

Si un drone voit un arbre, il recule sa bulle pour ne pas le toucher.
S'il voit un autre drone, il ajuste sa bulle pour ne pas empiéter sur le territoire du voisin.
La magie : Chaque drone ne regarde que ce qui est immédiatement autour de lui. Il ne sait pas où sont les autres drones loin de lui. Il ajuste simplement sa position pour aller vers le "centre" de sa propre bulle. C'est comme si chaque oiseau cherchait le milieu de son propre nid sans jamais parler aux autres.

2. La "Bulle de Sécurité" (Gérer les erreurs)

C'est ici que l'innovation est cruciale. Les robots ne sont pas parfaits. Parfois, ils croient être à 2 mètres d'un arbre alors qu'ils sont à 2,5 mètres (erreur de mesure). Parfois, ils dérapent un peu (erreur de pilotage).

L'algorithme ajoute une marge de sécurité (comme une zone tampon).

Au lieu de viser le centre exact de sa bulle, le drone vise un point un peu plus "sûr", loin des bords.
L'analogie : Imaginez que vous marchez dans le brouillard avec un ami. Au lieu de vous tenir exactement à 1 mètre de lui (ce qui est risqué si vous trébuchez), vous décidez de rester à 1,5 mètre. Si vous trébuchez, vous ne le heurtez pas.
Si les capteurs disent "c'est flou", le drone devient plus prudent et reste plus loin des bords de sa bulle. S'ils disent "c'est clair", il peut être un peu plus agressif pour avancer vite.

3. La règle du "Groupe" (Le Flocking)

Pour que le groupe reste ensemble, l'algorithme impose une règle simple : "Tu ne dois jamais t'éloigner de plus de X mètres de tes voisins immédiats."
Même si le drone veut aller vite vers sa destination, s'il voit qu'il s'éloigne trop de son voisin, il ralentit ou change de direction pour rester dans le "groupe". C'est comme une bande d'amis qui marchent dans un parc : si l'un s'éloigne trop, il s'arrête pour attendre les autres, sans qu'il y ait besoin de crier "Attends-moi !".

🧪 Les Résultats : Des tests réels dans la vraie forêt

Les chercheurs n'ont pas juste joué sur un ordinateur. Ils ont envoyé jusqu'à 4 drones réels dans une vraie forêt dense (sans GPS, sans Wi-Fi).

Le résultat : Les drones ont réussi à traverser la forêt, à éviter les arbres, à éviter de se percuter entre eux et à rester groupés.
La robustesse : Même quand un drone a eu un moment de doute (parce qu'un arbre cachait un autre drone), l'algorithme a permis au groupe de s'adapter et de continuer sans paniquer.

💡 En résumé

Ce papier décrit une méthode pour faire voler des robots en groupe dans des environnements chaotiques et sans communication.

Pas de chef : Pas de drone leader qui donne des ordres.
Pas de communication : Ils ne se parlent pas, ils se "voient" juste.
Prudence intelligente : Ils savent qu'ils peuvent se tromper et s'adaptent en temps réel pour rester en sécurité.

C'est comme si vous appreniez à un groupe de touristes à traverser une forêt obscure en leur disant simplement : "Regardez juste autour de vous, restez à distance de sécurité des arbres, et assurez-vous de ne pas perdre de vue vos voisins immédiats." Le résultat est un mouvement fluide, sûr et coordonné, même dans le chaos.

1. Problématique

L'article aborde le défi du contrôle de vol en essaim (flocking) de robots aériens (UAV) dans des environnements complexes et encombrés, spécifiquement sous une canopée forestière dense. Les contraintes principales sont les suivantes :

Environnement : Opération dans des zones non structurées (forêts) sans signal GNSS et sans infrastructure de communication externe.
Contraintes de communication : Absence de communication explicite entre les robots (pas d'échange de trajectoires futures, de positions ou de vitesses). Chaque robot doit prendre des décisions basées uniquement sur des informations locales.
Sécurité et Cohésion : Garantir l'évitement des collisions avec les obstacles et les autres robots tout en maintenant une contrainte de proximité (flocking) avec un sous-ensemble de voisins défini.
Incertitudes : Le système doit être robuste face aux erreurs de suivi (tracking errors) dues à la dynamique du robot et aux incertitudes de mesure (bruit des capteurs embarqués).

L'objectif est de synthétiser une loi de commande distribuée permettant à l'essaim d'atteindre une région cible tout en respectant ces contraintes de sécurité et de cohésion, sans connaissance a priori de l'environnement.

2. Méthodologie

L'approche proposée est basée sur une adaptation de l'algorithme de Lloyd, un algorithme d'optimisation de couverture de Voronoï, modifié pour gérer les incertitudes et les contraintes de proximité.

A. Géométrie de la cellule et Diagrammes de Voronoï Pondérés Convexes (CWVD)

L'espace de mission est partitionné en cellules $V_i$ pour chaque robot $i$ .
La cellule est définie comme l'intersection de trois ensembles :
1. CWVD pour les robots ( $V^p_i$ ) : Basé sur la position relative des voisins, utilisant un paramètre de prudence $\epsilon_p$ pour ajuster l'agressivité du mouvement.
2. CWVD pour les obstacles ( $V^o_i$ ) : Basé sur la position des obstacles détectés.
3. Zone de détection ( $S_i$ ) : Limitée au rayon de détection du capteur.
Reformulation de la géométrie pour la sécurité : Pour garantir l'évitement des collisions, la géométrie de la cellule est remodelée en tenant compte du rayon physique des robots ( $\delta_i$ ) et des obstacles. Une cellule finale $A_i$ est construite pour garantir que le chemin vers le centroïde reste sans collision.
Contrainte de proximité (Flocking) : Une sous-ensemble $M_i$ est ajouté pour limiter la distance aux voisins spécifiques, définissant la cellule finale $F_i = A_i \cap M_i$ .

B. Loi de commande et Fonction de pondération

La loi de commande est un contrôle proportionnel dirigé vers le centroïde $c_{F_i}$ de la cellule $F_i$ pondérée par une fonction $\phi_i(q)$ .
Fonction de pondération adaptative : La fonction $\phi_i(q)$ $ϕ_{i} (q)$ est de forme laplacienne, centrée sur un point cible $\bar{p}_i$ $\overset{p}{ˉ}_{i}$ . Un facteur d'étalement $\beta_i$ $β_{i}$ est ajusté dynamiquement :
- Il régule l'« avidité » du robot vers sa cible.
- Il est utilisé comme mécanisme principal pour compenser les erreurs.

C. Gestion des incertitudes et des erreurs

C'est l'apport majeur de la méthodologie. Au lieu de remodeler la cellule (ce qui pourrait rendre la cellule vide en cas d'erreur), l'algorithme ajuste le paramètre $\beta_i$ pour maintenir le centroïde à une distance de sécurité $d_u$ des bords de la cellule.

Incertitudes de mesure ( $d_u^m$ ) : Déduites de la covariance des mesures de distance (ex: UVDAR).
Erreurs de suivi ( $d_u^t$ ) : Déduites des erreurs maximales de suivi de trajectoire.
Condition suffisante : En imposant une borne inférieure à $\beta_i$ , le centroïde est contraint de rester dans une zone où, même avec les pires erreurs d'estimation et de suivi, la sécurité et la proximité sont préservées.

D. Implémentation

Les commandes sont générées via un MPC (Model Predictive Control) pour respecter la dynamique réelle des UAVs.
La localisation relative est assurée par le système UVDAR (UltraViolet Direction And Ranging) et la cartographie d'obstacles par Hector SLAM avec un Lidar 2D.

3. Contributions Clés

Algorithme Distribué sans Communication : Une méthode permettant le flocking dans des environnements denses uniquement via des capteurs embarqués, sans réseau de communication ni référence globale commune.
Garanties Théoriques de Sécurité et de Proximité : Démonstration de conditions suffisantes garantissant l'absence de collisions et le maintien de la proximité, même en présence d'erreurs de suivi et d'incertitudes de mesure bornées.
Stratégie Adaptative d'Incertitude : Une approche innovante utilisant le paramètre de dispersion $\beta_i$ pour compenser dynamiquement les erreurs, évitant ainsi la perte de définition de la cellule de contrôle.
Validation Expérimentale Réelle : Réussite de la mission avec jusqu'à 4 UAVs dans une forêt dense, sans GNSS, démontrant la robustesse du système face aux occlusions et au bruit des capteurs.

4. Résultats

Simulations :
- Comparaison avec l'algorithme PACNav [6] (qui ne nécessite pas de communication).
- L'algorithme proposé montre une meilleure scalabilité (fonctionne avec 9 et 16 robots) et un taux de réussite de 100 % en termes d'évitement de collisions et de maintien de la proximité, contrairement à PACNav qui échoue dans des scénarios plus denses.
- L'ajustement du paramètre $d_u$ (marge d'incertitude) permet de trouver un équilibre entre temps de mission et sécurité.
Expériences Réelles (Forêt) :
- Déploiement réussi avec 3 et 4 UAVs.
- Les robots ont navigué sur 40 mètres en maintenant les contraintes de flocking et de sécurité.
- Les données montrent que malgré des incertitudes de mesure élevées (occlusions par les arbres), les stratégies de rejet de données aberrantes et de réprojection des positions ont permis de maintenir la mission.
- Les vitesses moyennes observées se situaient entre 0,33 et 0,37 m/s, avec des temps de mission allant de 150 à 175 secondes.

5. Signification et Impact

Ce travail représente une avancée significative pour le déploiement de systèmes multi-robots autonomes dans des environnements réels et hostiles (forêts, zones de catastrophe) où les infrastructures de communication et de localisation (GNSS) sont absentes ou peu fiables.

Robustesse : La capacité à intégrer explicitement les erreurs de capteurs et de suivi dans la conception de la loi de commande rend l'algorithme beaucoup plus fiable que les approches théoriques idéalisées.
Autonomie : La démonstration que le flocking peut être réalisé sans communication explicite ouvre la voie à des essaims de robots capables de fonctionner dans des environnements où le spectre radio est encombré ou bloqué.
Réutilisabilité : Le code étant open-source et l'algorithme basé sur des principes géométriques généraux, cette méthode peut être adaptée à d'autres types de robots ou d'environnements 2D.

En résumé, l'article propose une solution complète, théoriquement fondée et expérimentalement validée, pour le contrôle d'essaims de robots dans des conditions réalistes et incertaines.