Introduction au contrôle d'essaims (multi-robots) — Création de groupes, de formations et de consensus

Lorsqu'une démonstration aérienne de drones voit des centaines de drones modifier simultanément leur formation, ou lorsqu'une flotte de robots d'entrepôt se déplace sans collision, il n'existe pas de centre de commande unique calculant chaque mouvement en temps réel. Dans la plupart des cas, chaque robot se contente d'analyser des informations limitées sur son environnement et de suivre des règles simples ; de là émerge un comportement ordonné et cohérent pour l'ensemble du groupe. Cet article explore le concept de contrôle d'essaims (contrôle multi-robots) – la construction d'un ensemble complexe à partir d'éléments simples – sous trois angles : le mouvement en essaim, la formation par consensus et le contrôle de formation.

Un robot en essaim sur le terrain (Kilobot)

Image : Kilobot robot swarm (asuscreative, CC BY-SA 4.0), Wikimedia Commons. Un exemple représentatif de recherche en robotique en essaim fonctionnant uniquement selon des règles locales, et non avec les drones ou les robots d'entrepôt abordés dans le texte.

0. Contenu de cet article

• Le problème que le contrôle en essaim cherche à résoudre et pourquoi un seul robot ne suffit pas

• La relation entre les informations que chaque robot peut obtenir (entrée) et la sortie (commande de vitesse) qui en découle

• La différence architecturale entre les conceptions centralisées et décentralisées

Le fonctionnement du comportement grégaire basé sur des règles locales, illustré par les Boids

Les mathématiques de la formation de consensus via les algorithmes de consensus

Les différences entre trois approches de contrôle de formation : leader-suiveur, structure virtuelle et comportemental

L'influence des contraintes de communication (latence, déconnexion, bande passante) sur la conception du contrôle en essaim

Quelle approche choisir pour quelle application : spectacles de drones, robots d'entrepôt, recherche en cas de catastrophe, etc.

1. En bref : Qu'est-ce que le contrôle en essaim ?

En une phrase : Le contrôle en essaim est un cadre de contrôle qui produit un comportement collectif significatif pour l'ensemble du système. L'ensemble du groupe – alignement, maintien de la formation, consensus, division du travail – repose sur les informations limitées et les règles comportementales simples détenues par chacun des nombreux robots.

L'idée clé est que « personne ne détient nécessairement le plan global ». De même qu'un vol d'oiseaux n'a pas de chef, de nombreux algorithmes de contrôle d'essaims sont conçus pour que chaque robot utilise uniquement les informations concernant les autres robots à proximité (ses voisins). Ainsi, même sans connaître l'état complet du groupe, l'essaim, dans son ensemble, finit par se déplacer comme une seule unité cohérente. Cette idée – « construire un ordre global à partir d'informations locales » – est ce qui distingue fondamentalement le contrôle d'essaims du contrôle d'un robot unique.

2. Pourquoi le contrôle d'essaims est-il nécessaire ?

Si un problème peut être résolu par un seul robot performant, le contrôle d'essaims n'est pas nécessaire. Le contrôle en essaim est privilégié en pratique dans les situations où une unité unique est, en théorie ou en pratique, désavantagée. Par exemple :

• Couverture spatiale : un seul robot mettrait trop de temps à explorer un vaste site sinistré ou un champ d'un bout à l'autre. Répartir le travail entre plusieurs robots réduit le temps de recherche de manière approximativement proportionnelle au nombre de robots.

• Redondance et tolérance aux pannes : avec une configuration à unité unique, une seule panne interrompt toute la mission ; un essaim composé de nombreux robots peut poursuivre la mission avec les robots restants, même si certains abandonnent.

• Travail simultané en plusieurs points : certaines missions nécessitent intrinsèquement d'être présent à plusieurs endroits simultanément, comme former des figures lors d'un spectacle de drones ou transporter simultanément des marchandises vers différents emplacements dans un entrepôt.

• Coût par unité : plutôt que de construire un seul robot haute performance, l'utilisation de nombreux robots simples et peu coûteux peut s'avérer avantageuse en termes de coût total et de flexibilité de déploiement.

Pour concrétiser ces avantages, il ne suffit pas d'augmenter le nombre de robots ; il faut des lois de contrôle qui empêchent les collisions tout en maintenant un comportement collectif aligné sur l'objectif. C'est le rôle du contrôle d'essaim.

3. Quelles sont les entrées ?

Les informations que chaque robot peut utiliser pour le contrôle d'essaim peuvent être classées comme suit, selon sa configuration de communication et de détection :

• État propre : position, vitesse et orientation du robot. Généralement obtenues par GPS, odométrie ou une méthode d'autolocalisation comme VIO/LIO.

• Informations relatives aux robots voisins : position et vitesse relatives des robots proches, observées directement par des capteurs tels que des caméras, des LiDAR ou des systèmes de télémétrie UWB (ultra-large bande).

• Messages via la communication : informations de position, de vitesse et d'intention (sa prochaine direction) explicitement envoyées par d'autres robots via une liaison sans fil.

• (Dans les architectures centralisées) commandes provenant d'un nœud central : positions cibles ou affectations de rôles distribuées aux robots par un ordinateur central (une station au sol, par exemple) qui suit l'état de l'ensemble de l'essaim.

Il est important de noter que de nombreux algorithmes de contrôle d'essaim pratiques ne nécessitent pas « l'état complet de l'essaim » en entrée. Les algorithmes fonctionnant uniquement à partir d'informations relatives provenant de quelques robots proches constituent l'approche dominante, ce qui permet précisément d'éviter que le volume d'informations que chaque robot doit traiter n'explose à mesure que le nombre de robots augmente.

4. Quel est l'objectif ? Quels sont les résultats ?

Le contrôle d'essaim fournit en définitive, pour chaque robot, la manière dont il doit se déplacer à l'instant suivant (une consigne de vitesse ou une position cible). L'« état souhaitable pour l'ensemble » que cette sortie vise à atteindre se divise en plusieurs catégories, selon l'objectif.

• Consensus : convergence d'une grandeur d'état (position, vitesse ou estimation) de tous les robots vers une valeur commune.

• Formation : chaque robot maintient en permanence une relation positionnelle relative spécifiée avec les autres (triangle, ligne, cercle, etc.).

• Floodage : sans forme cible explicite, l'essaim se déplace comme une masse cohérente, évitant les collisions et synchronisant sa vitesse avec celle de ses voisins.

• Allocation des tâches : attribution à chaque robot de la tâche discrète (recherche, transport, etc.) qu'il doit effectuer.

Ces étapes partagent la structure suivante : « l'accumulation des sorties locales de chaque robot satisfait une propriété collective attendue pour l'ensemble ». L'architecture de base de la section suivante illustre cette boucle d'accumulation.

5. Architecture de base

La boucle de traitement interne à chaque robot suit globalement les mêmes quatre étapes, quel que soit l'algorithme de contrôle de l'essaim.

Figure 1 — Chaque robot exécute une boucle à haute fréquence : collecte d’informations sur ses voisins, application des règles locales, émission d’une commande de vitesse et réintégration du mouvement résultant dans la détection du cycle suivant.

Cette boucle, exécutée simultanément par de nombreux robots, permet à l’essaim d’adopter un comportement ordonné, même si aucun robot ne connaît l’ensemble du système. Le choix de déterminer qui détient l’information globale est à l’origine de la différence architecturale abordée ci-après.

Figure 2 — Une architecture centralisée est une structure en étoile où un nœud central connaît l'état de chaque robot et envoie des commandes. Une architecture décentralisée est une structure maillée où les robots échangent des informations uniquement avec leurs voisins ; ainsi, une panne du nœud central n'arrête pas l'ensemble du système.

6. Algorithmes représentatifs

Boids — Construction du mouvement grégaire à partir de règles locales

Boids est un modèle proposé par Craig W. Reynolds dans son article de 1987 intitulé « Flocks, Herds, and Schools: A Distributed Behavioral Model » (Vols, troupeaux et bancs : un modèle comportemental distribué), afin de reproduire le mouvement grégaire des oiseaux et des poissons en infographie. Chaque individu (boid) observe uniquement ses voisins et se déplace dans une direction obtenue par pondération et sommation de trois règles simples.

• Séparation : s’éloigner des voisins trop proches.

• Alignement : adapter sa vitesse à la direction moyenne des voisins.

• Cohésion : se rapprocher de la position moyenne des voisins.

Dans chacune de ces règles, un individu ne connaît que la position et la vitesse relatives d’une poignée de voisins ; personne ne suit explicitement la forme ou le centre de l’ensemble du groupe. Pourtant, de la simple superposition de ces trois règles émerge un mouvement grégaire naturel : le groupe évite les collisions tout en se déplaçant comme une seule masse. Ce phénomène – « des schémas globaux complexes émergeant de la superposition de règles locales simples » – est l’idée fondamentale qui sous-tend tout le domaine du contrôle des essaims.

Champs de potentiel — Générer du mouvement à partir d'attraction et de répulsion

La méthode des champs de potentiel artificiels d'Oussama Khatib, proposée dans son article de 1986 intitulé « Évitement d'obstacles en temps réel pour les manipulateurs et les robots mobiles », a été initialement conçue pour l'évitement d'obstacles par un robot isolé. Cependant, en combinant un potentiel attractif vers l'objectif avec un potentiel répulsif provenant des robots voisins, elle s'applique naturellement au contrôle d'essaims.

Se déplacer simplement dans la direction descendante du gradient du potentiel attractif U_{\text{att}}, qui diminue à mesure que l'on s'approche de l'objectif, et du potentiel répulsif U_{\text{rep}}, qui augmente brusquement lorsqu'on se rapproche trop d'un voisin, produit un mouvement dirigé vers l'objectif tout en évitant les collisions avec les autres robots. La règle de séparation des Boids repose, en substance, sur le même principe que ce potentiel répulsif.

Le modèle de Vicsek et les algorithmes de consensus — les mathématiques de la formation du consensus

Alors que Boids est né d'une motivation à la fois technique et visuelle — « reproduire le mouvement des animaux » —, la physique a emprunté une voie différente, étudiant le mouvement des essaims à travers un modèle mathématique plus simplifié. Le modèle de Vicsek, publié par Tamás Vicsek et ses collègues dans Physical Review Letters en 1995, est un modèle simple — qui revient presque à extraire uniquement la règle d'alignement de Boids — dans lequel chaque particule se déplace à vitesse constante tout en suivant la direction moyenne de ses voisines, à laquelle s'ajoute du bruit. Ce modèle a montré que, selon l'intensité de ce bruit, l'essaim subit une transition de phase entre une phase ordonnée, où le groupe se déplace de manière cohérente, et une phase désordonnée, où le mouvement est dispersé.

Le cadre qui formalise rigoureusement cette idée du modèle de Vicsek en termes de théorie du contrôle est l'algorithme de consensus. Dans le cadre défini par Reza Olfati-Saber et Richard M. Murray dans leur article de 2004 paru dans IEEE Transactions on Automatic Control, entre autres, l'état de chaque robot x_i (qui peut être n'importe quoi : position, orientation, estimation) est continuellement mis à jour dans la direction qui réduit l'écart avec ses voisins.

La somme de ces états pour tous les robots donne \dot{\mathbf{x}} = -L\mathbf{x}. L est une matrice appelée laplacien du graphe, qui représente la structure même du réseau de communication : qui peut communiquer avec qui. Tant que le graphe de communication est connexe (il existe un chemin, direct ou indirect, entre chaque paire de robots), cette simple règle de mise à jour permet de faire converger l'état de chaque robot vers une valeur commune. Il s'agit du fondement mathématique des algorithmes de consensus, applicables à un large éventail de problèmes au-delà de l'alignement d'essaims : synchronisation temporelle, moyennage distribué d'estimations, etc.

Contrôle de formation — Modèle leader-suiveur, structure virtuelle et contrôle comportemental

Pour maintenir une formation géométrique précise (triangle, file indienne, etc.), on utilise le contrôle de formation, un cadre plus ciblé. Il existe trois approches de conception représentatives.

• Modèle leader-suiveur : un robot (ou un sous-ensemble) fait office de leader, et les autres le suivent en maintenant une position relative par rapport à lui. Le cadre présenté par Jaydev P. Desai, James P. Ostrowski et Vijay Kumar à ICRA 1998, puis dans IEEE Transactions on Robotics and Automation en 2001, en est un exemple représentatif. Il utilise la théorie des graphes pour définir explicitement quel robot suit qui. Ce modèle est intuitif et facile à mettre en œuvre, mais il présente l’inconvénient que toute la formation a tendance à s’effondrer si le leader tombe en panne. - Structure virtuelle : une approche proposée par M. Anthony Lewis et Kar-Han Tan dans leur article de 1997 intitulé « High Precision Formation Control of Mobile Robots Using Virtual Structures ». Cette approche considère la formation entière comme une structure rigide virtuelle unique, chaque robot suivant une position fixe sur cette structure. Elle garantit une grande précision pour la formation dans son ensemble, mais nécessite le calcul de la trajectoire cible pour l’ensemble de la structure, ce qui rend difficile la conception entièrement décentralisée.

• Approche comportementale : une approche présentée par Tucker Balch et Ronald C. Arkin dans IEEE Transactions on Robotics and Automation en 1998. Plusieurs comportements réactifs — « maintenir la formation », « se diriger vers l’objectif », « éviter les obstacles » — sont calculés en parallèle et pondérés pour générer le mouvement réel. Proche de l’approche Boids, elle confère à chaque robot une grande autonomie et une grande robustesse, mais la précision géométrique de la formation est généralement inférieure à celle des deux autres approches.

7. Différences entre les algorithmes

De manière générale, plus la précision géométrique de la formation est privilégiée (structure virtuelle), plus le partage d'informations et le coût de calcul sont importants ; plus la décentralisation et la robustesse sont privilégiées (Boids, basée sur le comportement), plus la précision de la formation est sacrifiée. Les algorithmes de consensus constituent un juste milieu théoriquement viable entre ces deux extrêmes, garantissant à la fois une convergence mathématique rigoureuse et une décentralisation ne nécessitant que la communication entre voisins.

8. Points faibles / Environnements complexes

Nombre des difficultés rencontrées par le contrôle d'essaims lors de sa mise en œuvre et de son fonctionnement sont des problèmes spécifiques aux collectifs, inexistants dans le contrôle de robots individuels.

• Latence et déconnexion des communications : la plupart des garanties de convergence des algorithmes de consensus supposent que le graphe de communication est connexe. Dans les environnements réels, la communication peut être interrompue ou retardée par la portée radio ou des obstacles. Dès lors que cette hypothèse n'est plus vérifiée, des problèmes surviennent : le consensus ne converge pas ou converge vers une valeur erronée.

• Scalabilité : dans une architecture centralisée, la charge de calcul et les besoins en bande passante du nœud central augmentent fortement avec le nombre de robots, et au-delà d'un certain seuil, les performances en temps réel ne peuvent plus être maintenues. Même dans les architectures décentralisées, la charge de détection et de communication augmente dans les environnements denses comportant de nombreux voisins. - Minima locaux et blocages : les méthodes de champ de potentiel peuvent bloquer un robot à un « minimum local », où plusieurs forces répulsives et attractives s’équilibrent, l’empêchant d’atteindre l’objectif (un exemple typique est un embouteillage où plusieurs robots tentent d’entrer simultanément dans un passage étroit).

• Conception à tolérance aux pannes insuffisante : les conceptions décentralisées sont théoriquement considérées comme robustes aux pannes partielles, mais en pratique, les conceptions présentant une certaine asymétrie inhérente — comme le modèle leader-suiveur — peuvent conserver des modes de défaillance plus fragiles que prévu.

• Robots et capteurs hétérogènes : dans les déploiements réels où les modèles de robots et les capteurs embarqués ne sont pas uniformes, la précision et la fréquence des informations obtenues par chaque robot diffèrent, et les algorithmes basés sur un modèle idéal unique ont tendance à mal fonctionner tels quels.

9. Choix pratiques

Le choix d’un algorithme de contrôle d’essaim dépend largement de la priorité accordée par l’application à la « précision de la formation » ou à la « robustesse/décentralisation ».

• Spectacles de drones : les trajectoires et formations prédéterminées doivent être exprimées avec une extrême précision. De nombreux systèmes de production adoptent une conception proche d'une structure centralisée/virtuelle, distribuant des trajectoires précalculées à chaque drone (la précision et la reproductibilité sont privilégiées par rapport à la prise de décision autonome en vol).

• Flottes de robots d'entrepôt/logistique : de nombreux robots de transport doivent se répartir des tâches évolutives (quelle étagère pour quelle destination). Une conception hybride centralisée/décentralisée est courante : un système de gestion centralisé assure l'attribution des tâches, tandis que la génération de trajectoires et l'évitement des collisions sont traités de manière décentralisée pour chaque robot. Consultez le Guide de planification de trajectoires pour les principes fondamentaux de la planification de trajectoires. - Recherche en cas de catastrophe, surveillance agricole et autres applications à grande échelle : la communication étant souvent instable dans ces environnements, les approches décentralisées, peu dépendantes d'un centre (combinaisons de type Boids ou couverture par consensus), sont privilégiées. Les décisions comportementales des robots individuels sont souvent combinées à un cadre de planification comportementale.

• Essaims de robots à petite échelle pour la recherche et l'éducation : ces dispositifs expérimentaux, composés de peu de robots et bénéficiant d'une communication stable, privilégient généralement les structures virtuelles ou les architectures leader-suiveur, axées sur la précision de la formation.

Quelle que soit l'application, le choix d'une architecture de contrôle d'essaim repose sur trois questions essentielles : « Combien de robots seront utilisés ? », « Quelle est la stabilité de l'environnement de communication ? » et « Quelle est l'exigence prioritaire en matière de tolérance aux pannes : précision de la formation ou robustesse ? ».

10. Résumé (Récapitulatif en trois lignes)

• Le contrôle d'essaim est un cadre qui génère un comportement ordonné pour le groupe dans son ensemble à partir de règles locales utilisant uniquement les informations limitées dont dispose chaque robot concernant ses voisins.

• Les méthodes Boids et de champ potentiel permettent un mouvement de groupe décentralisé, tandis que les algorithmes de consensus permettent la formation d'un consensus avec une garantie de convergence mathématiquement établie via le laplacien du graphe.

• Le contrôle de formation basé sur le leader-suiveur, la structure virtuelle et le comportement occupe différentes positions dans le compromis entre la précision de la formation et la robustesse/décentralisation, et doit être choisi en fonction de l'application.