<figure><img src="image_1.png" /></figure>

NICOLAS GAUVILLE, FRANÇOIS CHARPILLET

Approche locale pour l'exploration autonome d'environnements inconnus par une
flottille de robots

Volume 3, n° 5-6 (2022), p. 625-643.

DOI not yet assigned

© Les auteurs, 2022.

<figure><img src="image_2.png" /></figure>

Cet article est diffusé sous la licence

CREATIVE COMMONS ATTRIBUTION 4.0 INTERNATIONAL LICENSE.

http://creativecommons.org/licenses/by/4.0/

<figure><img src="image_3.png" /></figure>

La Revue Ouverte d'Intelligence Artificielle est membre du
Centre Mersenne pour l'édition scientifique ouverte

www.centre-mersenne.org

e-ISSN : pending
# Approche locale pour l'exploration autonome d'environnements inconnus par une flottille de robots

Nicolas Gauville<sup>a</sup>, François Charpillet<sup>b</sup>

RÉSUMÉ. — L'exploration autonome d'un environnement inconnu peut être envisagée de différentes manières. On peut notamment citer les approches par frontières, où des robots sont affectés à des zones inexplorées de la carte. Ces dernières sont efficaces, mais nécessitent de partager une carte et globaliser les décisions d'affectation. Les approches *Brick and Mortar*, quant à elles, utilisent un marquage au sol avec une prise de décision locale, mais donnent des performances beaucoup moins intéressantes. L'algorithme présenté ici est un compromis entre ces deux approches, permettant une prise de décision locale et, de façon surprenante, des performances proches des approches par frontières globales. Nous proposons également une étude comparative de la performance des trois différentes approches : *Brick & Mortar, frontières globales et frontières locales*. Notre algorithme local est également complet pour le problème d'exploration et peut être facilement distribué sur des robots avec une perte de performance mineure.

MOTS-CLÉS. — multirobot, stigmergie, exploration.

## 1. INTRODUCTION

L'exploration autonome d'un environnement inconnu est un défi important en robotique mobile. L'exploration peut être une fin en soi : des robots de nettoyage (aspirateur, tondeuse à gazon, etc.) explorent systématiquement chaque zone à couvrir. Dans les applications plus sophistiquées, il s'agit principalement d'acquérir des informations : cartographier l'environnement [4], rechercher un intrus, localiser une source sonore ou olfactive [15, 21], ou encore rechercher d'éventuelles personnes à secourir dans un bâtiment en feu, ...

Une flotte composée de nombreux petits robots peut s'avérer particulièrement adaptée à l'exploration rapide d'un grand bâtiment, permettant une grande répartition des robots dans l'espace et ainsi une exploration simultanée de différentes zones. Ce cas particulier pose cependant différents problèmes : (1) la quantité d'informations partagée entre les robots doit être peu importante, (2) des robots petits et nombreux

<footnote><sup>a</sup> Safran Electronics & Defense Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy</footnote>

<footnote>E-mail: nicolas.gauville@loria.fr</footnote>

<footnote><sup>b</sup> Université de Lorraine, CNRS, Inria, LORIA, F-54000 Nancy</footnote>

<footnote>E-mail: francois.charpillet@inria.fr.</footnote>
<figure><img src="image_4.png" /><figcaption>FIGURE 1.1. Robot Minirex (utilisé pour le projet Cart-O-Matic) explorant une zone test.</figcaption></figure>

auront souvent des capacités de calcul faibles et (3) les communications entre les différents robots peuvent être coupées.

L'objectif de cet article est de proposer une approche par frontières locales pour aborder le problème de l'exploration multirobot. L'objectif principal de ce travail est de proposer une approche efficace, même dans un environnement où la communication est restreinte, pour résoudre le problème de l'exploration avec un grand nombre de robots. Nous avons également essayé de fournir un algorithme aussi simple que possible, exécutable avec des ressources limitées.

Notre approche, bien qu'inspirée des approches par frontières globales, aborde différemment le problème de l'exploration : dans le cas de l'approche globale, c'est avant tout un problème de planification, où l'algorithme doit décider de l'affectation des robots aux frontières connues. Dans notre version locale, les robots ne connaissent pas le nombre ou la position des autres robots et ne s'en soucient pas. Ils réagissent uniquement aux informations locales. La collaboration entre robots se fait par stigmergie, dans notre cas simulé à l'aide d'une carte qui est partagée entre robots à intervalles réguliers, mais d'autres méthodes pourraient être envisagées pour limiter au mieux la quantité et la fréquence des informations partagées [11].

## 2. ÉTAT DE L'ART

L'exploration multirobot vise à explorer un environnement inconnu le plus rapidement possible pour une équipe homogène de robots mobiles. C'est une question proche du problème de couverture [10], mais avec une carte inconnue. Établir une classification des différentes approches de l'exploration peut s'avérer difficile de par la diversité de ces dernières et la multitude de critères pouvant les discriminer. Nous
pouvons cependant considérer d'une part les approches réactives, où les robots utilisent des informations perceptibles depuis leur position, et d'autre part les approches de planification, où l'ensemble des informations sont considérées.

## 2.1. APPROCHES RÉACTIVES

Les approches réactives les plus courantes regroupent les algorithmes *fourmis* et les approches de type *Brick & Mortar*. Dans les deux cas, les robots ne communiquent pas directement entre eux, mais indirectement à l'aide de traces déposées dans l'environnement. La différence entre ces deux classes d'algorithmes est la nature des traces déposées : dans le cas des algorithmes fourmis, l'environnement joue un rôle actif permettant de faire évoluer les traces déposées au fil du temps, par exemple avec un phénomène d'évaporation (diminution de leur quantité au fil du temps) ou de diffusion. Dans ces deux approches, les décisions sont prises localement, mais le partage d'une carte globale entre robots est nécessaire pour partager les traces virtuelles laissées sur la carte.

Les approches « purement fourmis », utilisant des phénomones dispersées par l'environnement pour répartir les robots [1, 22], sont souvent plus difficiles à mettre en place que les approches *Brick & Mortar*, car il faut également faire évoluer les phénomones déposées (évaporation, dispersion, ...). Garnier et al. ont par exemple proposé un système de projection de points avec des robots équipés de capteurs de lumière pour simuler ces phénomones partagées [11, 17], mais cela nécessite d'avoir un appareil pouvant projeter des points sur l'ensemble de la surface à explorer, ce qui n'est pas envisageable dans le cas de l'exploration d'un bâtiment inconnu. Nous préférerons donc ici les approches *Brick & Mortar* où il suffit de partager les traces laissées.

Parmi les approches récentes, certaines utilisent l'apprentissage par renforcement [7, 8] à différents niveaux, allant du module de *SLAM* aux planificateurs ainsi qu'au choix du prochain point à explorer [12, 16, 18, 19].

## 2.2. PLANIFICATION ET ORDONNANCEMENT

L'exploration peut également être considérée comme un problème d'ordonnancement ; l'approche par frontières [6, 9, 23] consiste à attribuer à chaque robot une frontière, c'est-à-dire une limite entre les parties explorées et inexplorées de la carte. Dans ce cas, un consensus global doit également être assuré.

Si les approches locales sont efficaces, elles restent beaucoup plus lentes que les approches par frontières en termes de temps d'exploration : les robots doivent effectuer de nombreux marquages pour ne pas se bloquer mutuellement ou « oublier » une zone à explorer. Les approches par frontières sont plus efficaces et basées sur des algorithmes plus simples, mais nécessitent une coordination des décisions entre robots qui peut poser différents problèmes dans des situations réelles où une communication constante ne peut être assurée [13]. De plus, l'algorithme d'assignation des frontières utilisé nécessite souvent un temps de calcul non linéaire en fonction du nombre de robots et de la taille de la grille, ce qui peut la rendre inapplicable dans une situation réelle si la carte est trop grande ou s'il y a trop de robots. Cependant, il existe différentes méthodes
pour optimiser l'affectation et les données échangées, par exemple en partageant uniquement les frontières et non la carte entière [14]. Enfin, notre approche locale peut facilement être distribuée, et fonctionne également avec des communications limitées (voir section 5).

## 2.3. FRONTIÈRES GLOBALES

Dans le cas de l'approche par frontières globales, chaque robot possède une grille d'occupation pouvant prendre trois états : *inexploré*, *exploré* et *obstacle*, initialisée à *inexploré*. À chaque itération, chaque robot marque l'ensemble des cellules dans son rayon de perception comme *exploré* ou *obstacle*. Les frontières entre les zones explorées et inexplorées de la carte peuvent alors être calculées en détectant toutes les cellules contiguës qui ont à la fois des voisines immédiates explorées et inexplorées.

Une fois toutes les frontières de la carte détectées, l'algorithme d'assignation (*MinPos* [5]) est utilisé toutes les 4 itérations pour assigner une frontière à chaque robot, et ceux-ci peuvent alors se diriger vers la frontière qui leur a été assignée. La stratégie d'assignation *MinPos* est décrite en 4.1.

## 2.4. ALGORITHMME BMILRV

L'algorithme BMILRV[2] utilise de nombreux marquages sur la grille d'occupation : un état parmi un ensemble d'états {*inexploré*, *exploré*, *fermé*, *obstacle*, *rendez-vous*}, une valeur indiquant si un robot contrôle une cellule donnée, la direction prise lors du dernier passage sur une cellule, et une variable booléenne indiquant si un robot donné est déjà passé sur une cellule. Les robots peuvent également être dans différents modes parmi {détection de boucle, contrôle de boucle, fermeture de boucle, nettoyage, pause, arrêt}.

De manière informelle, l'algorithme BMILRV consiste à maintenir une liste de cellules ouvertes permettant d'accéder à toutes les zones inexplorées de la carte, tout en fermant progressivement toutes les cellules qui peuvent l'être (qui ne bloqueront pas le passage vers une zone inexplorée), évitant ainsi de repasser dans les zones déjà visitées.

Lorsque des boucles sont présentes dans le chemin constitué par les cellules explorées, les robots peuvent les fermer en plusieurs étapes permettant d'éviter de bloquer un robot. Le robot détectant la boucle (entrant dans une cellule explorée sur laquelle il est déjà passé en venant de la même direction), va alors passer en mode « contrôle de boucle » et parcourir cette boucle pour la marquer comme contrôlée avec son identifiant, vérifiant ainsi qu'il est le seul à chercher à la fermer à ce moment. S'il parvient à marquer la totalité de la boucle, il effectue alors un second passage en mode « fermeture » ou il va fermer les cellules de la boucle jusqu'à la première intersection, et enfin parcourir la boucle une troisième fois en sens inverse en mode « nettoyage » pour enlever les traces indiquant qu'il contrôle la boucle. S'il ne parvient pas à contrôler la boucle, alors il passe directement en mode « nettoyage » si le robot qui la contrôle a une priorité supérieure, ou en mode « pause » s'il est prioritaire, en attendant que l'autre robot ait nettoyé ses traces sur la boucle.
<figure><img src="image_5.png" /><figcaption>FIGURE 2.1. Représentation de la grille lors d'une exploration par l'algorithme BMILRV. Les cellules fermées sont en gris, ouvertes en vert, point de rendez-vous en jaune et inexplorées en blanc. Les chiffres dans les cellules correspondent aux numéros des robots contrôlant ces cellules, l'état des robots est indiqué en rouge.</figcaption></figure>

Les différentes étapes de l’algorithme BMILRV ne sont pas triviales ; elles nécessitent de nombreuses vérifications pour fermer correctement les cellules, et un décalage ou asynchronisme dans la procédure de marquage des cellules pourra bloquer les robots. Pour des raisons de place, nous n’entrerons pas dans les détails du fonctionnement de l’algorithme ici.

## 2.5. POSITIONNEMENT DE NOTRE APPROCHE

L’algorithme proposé ici est un compromis entre l’approche *Brick & Mortar* et l’assignation de frontières : c’est une approche de frontières locales, où les robots partagent une carte, mais avec une prise de décision locale pour chaque robot. Notre approche est donc moins sensible à l’asynchronisme et réduit significativement les calculs effectués par chaque robot, car le nombre de cellules prises en compte à un moment donné est beaucoup moins important.

Toutes les approches considérées ici utilisent des grilles d'occupation pour représenter le monde, et considèrent que chaque robot est équipé d'un Lidar principalement utilisé pour la localisation et la cartographie simultanées (SLAM). Cependant, notre approche, comme celle par frontières globales, peut être adaptée à d'autres représentations du monde [20]. De nombreuses représentations sont possibles, telles que les quadtrees ou l'addition-soustraction de géométrie [3].
# 3. SUIVI DE FRONTIÈRES LOCALES

## 3.1. EXPLORATION EXHAUSTIVE

De façon informelle, l’algorithme local consiste à marquer tout chemin parcouru comme visité, à se déplacer le plus loin possible vers des zones inconnues, et revenir sur ses pas lorsqu’il n’y a plus de zone inconnue visible, jusqu’à ce que l’on en retrouve une.

Lorsque le robot est revenu à son point de départ sans avoir vu aucune zone inexplorée, toute la carte a été explorée.

Dans le cas de plusieurs robots, selon les conditions initiales et la topologie de la carte, un ou plusieurs robots peuvent être revenus à leur point de départ avant la fin de l’exploration, ce qui entraîne une mauvaise distribution de l’exploration et réduit la performance de l’algorithme. Pour réduire cette perte de performance, on peut envisager d’utiliser dans ce cas les traces des autres robots pour reprendre l’exploration une fois qu’ils sont revenus au point de départ, si tous les autres robots ne se sont pas arrêtés. Cette piste d’amélioration est implémentée dans la partie 6.

<figure><img src="image_6.png" /><figcaption>FIGURE 3.1. Représentation de la grille lors d'une exploration par l'algorithme par frontières locales (cellules explorées en blanc, traces en vert ; les cellules vert foncé et jaune correspondent aux frontières locales des robots vert foncé et jaune).</figcaption></figure>

## 3.2. FORMALISATION (FRONTIÈRES LOCALES)

Nous considérons une flotte homogène de *m* robots mobiles $R = \{r_1, \dots, r_m\}$ équipés de capteurs leur permettant de détecter des obstacles dans un rayon de perception $\rho$. Les robots utilisent une grille d'occupation *O* représentant la carte, où chaque cellule peut être dans trois états : *inexploré*, *obstacle* ou *exploré*, ainsi qu'une grille *P* pour assigner un booléen à chaque cellule, indiquant si une cellule est visitée ou non (c'est-à-dire si un robot a été sur cette cellule), initialisée à *faux*. Ces cartes sont échangées à
intervalles réguliers entre les robots (voir section 5). Enfin, chaque robot peut définir une cellule objectif (représentant un point à atteindre sur la carte), et possède une trace $G_{r_i}$ correspondant à la distance maximale parcourue depuis le point de départ.

Pour chaque déplacement (d'une cellule), chaque robot connaît l'état des cellules dans son rayon de perception et sa position sur la grille (x, y). On notera $V_{r_i}^t$ l'ensemble des cellules visibles perçues par le robot à un moment donné $t$ qui ne sont pas des obstacles.

Les cartes locales ($G$ et $\mathcal{P}$) sont partagées entre les robots toutes les $d_{\text{sync}}$itérations avec la procédure décrite dans la partie 5.

Le paramètre $d_{\text{max}}$ est utilisé pour forcer les robots à réassigner la cellule objectif à intervalles réguliers, évitant ainsi de choisir une cible maintenue trop longtemps si le rayon de perception est grand.

Chaque robot $r_i$ applique l'algorithme suivant :

(1) Marquer toutes les cellules visibles comme explorées :
$$ \forall (x, y) \in V_{r_i}^t, O_{r_i}(x, y) = \text{exploré} $$

(2) Si aucune cellule objectif n'est définie, déterminez les frontières locales $\mathcal{F}$, c'est-à-dire toutes les cellule de $V_{r_i}^t$ ayant des voisins inexplorés.

(a) Si $|\mathcal{F}| > 0$, choisir la cellule frontière la plus éloignée de toute cellule visitée (dans la grille $\mathcal{P}_{r_i}$) à une distance maximale $d_{\text{max}}$ de la cellule comme nouvel objectif.

(b) Si $|\mathcal{F}| = 0$ et si on est de retour à la cellule de départ, s'arrêter.

(c) Sinon, retournez un pas en arrière sur la trace $G_{r_i}$ : choisir la cellule, parmi les 4 cellules adjacentes, ayant la valeur $G_{r_i}(x, y)$ la plus basse.

(3) Sinon, si une cellule objectif est définie

(a) Si $G_{r_i}(x, y) = 0$, mettre à jour la trace : $G_{r_i}(x, y) = 1 + \max(G_{r_i}(x - 1, y), G_{r_i}(x + 1, y), G_{r_i}(x, y - 1), G_{r_i}(x, y + 1))$.

(b) Mettre à jour la grille : $\mathcal{P}_{r_i}(x, y) = 1$

(c) Se rapprocher de l'objectif (à l'aide d'un algorithme de pathfinding parmi les cellules visibles), puis revenir à l'étape 1.

(4) Si plus de $d_{\text{sync}}$itérations ont été effectuées depuis le dernier partage de carte, partagez la carte $(O_{r_i}, \mathcal{P}_{r_i})$ avec les autres robots (voir section 5).

Dans nos expériences, nous avons utilisé l'algorithme A* pour rechercher le chemin optimal entre les robots et leurs cellules objectifs (avec la distance euclidienne comme heuristique).

# 4. COMPARAISON DES DIFFÉRENTES APPROCHES

## 4.1. ALGORITHMES CHOISIS

Puisque l'algorithme présenté ici est un compromis entre les approches *Brick & Mortar* et par *frontière*, nous avons choisi de le comparer à un algorithme par frontières globales et à un algorithme *Brick & Mortar*.
Les approches par frontières peuvent être mises en œuvre avec différentes stratégies d'affectation et différentes conditions de réaffectation. Nous avons choisi la stratégie d'affectation *MinPos* présentée dans [5], et réassignons les frontières toutes les $d_{max}$ itérations ($d_{max}$ est le paramètre utilisé dans l'algorithme local, et correspond au nombre maximum de déplacements entre chaque changement de cellule objectif, donnant ainsi une condition de réaffectation proche). La stratégie d'affectation *MinPos* consiste à calculer, pour chaque robot *i* et chaque frontière *j*, un rang $r_{i,j}$, correspondant au nombre de robots plus proches de la frontière *j* que le robot *i*, puis à attribuer à chaque robot la frontière la plus proche pour laquelle son rang est minimal.

Il existe également différentes approches *Brick & Mortar*. Celle que nous avons implémentée ici, *BMILRV* (Brick & Mortar Improved Long Range Vision) [2], permet de considérer un ensemble de cellules dans le rayon de perception du robot, et pas seulement la cellule sur laquelle le robot se trouve, ce qui permet une comparaison plus directe avec notre approche locale, considérant à un instant donné pour un robot le même nombre de cellules voisines.

<figure><img src="image_7.png" /><figcaption>FIGURE 4.1. Cartes testées (les points rouges correspondent aux points de départ des robots).</figcaption></figure>

## 4.2. CONDITIONS EXPÉRIMENTALES

Nous allons comparer les trois approches afin d'explorer une carte inconnue. L'approche par frontières globales reproduit l'expérience décrite dans [9] avec réaffectation de l'objectif tous les $d_{max}$ changements de cellule, et la stratégie d'assignation *MinPos*. Comme cette approche ne fournit pas de point de rendez-vous, nous considérerons le nombre total d'itérations jusqu'à ce que la carte soit entièrement visitée. Nous
observerons ainsi le pourcentage de cellules explorées par rapport au nombre d'itérations passées. L'approche BMILRV est une reproduction de l'algorithme décrit dans [2]. Enfin, l'approche par frontières locales correspond à l'algorithme décrit dans la partie 3.2.

Cette partie présente les résultats expérimentaux réalisés sur simulateur pour 4 cartes différentes présentées figure 4.1. Les points de départ des robots sont représentés par les points rouges. Dans ces expériences, la carte est partagée à chaque itération ($d_{sync}= 1$, voir section 5 pour la version distribuée), le rayon de perception $\rho$ est de 5 cellules, et $d_{max} = 2$.

Le *labyrinthe 2* est celui utilisé dans [2], le *labyrinthe 1* est une variante avec des couloirs plus étroits. La carte *Cercle* permet de tester un environnement avec peu d'obstacles (par rapport au rayon de perception des robots), et la carte *Blocs* correspond à un environnement avec de nombreux obstacles isolés, formant ainsi des boucles pour les robots.

### 4.3. SIMULATEUR UTILISÉ

Pour obtenir une première comparaison expérimentale des performances des différents algorithmes, nous avons implémenté un simulateur en Python permettant d'exécuter les algorithmes dans des conditions identiques sur les 4 cartes présentées figure 4.1.

<figure><img src="image_8.png" /><figcaption>FIGURE 4.2. Simulateur utilisé pour les expériences, ici avec l'algorithme par frontières globales. La partie gauche montre la carte des robots (cellules explorées en blanc, inexplorées en gris et frontières en couleurs), et la partie droite le monde « réel » avec les trajectoires des robots. Le menu de gauche permet de sélectionner les différents algorithmes (frontières globales, frontières locales, BMILRV) et les conditions de l'expérience (points de départ, robot, cartes, synchronisation).</figcaption></figure>

Notre simulateur (capture d'écran 4.2) permet une exécution décentralisée des algorithmes des robots. Dans nos expériences, nous supposons que la localisation est parfaite, que les robots ont une taille plus petite que la taille d'une cellule dans la grille d'occupation et que la détection des obstacles est toujours correcte. Une taille de cellule trop grande posera des problèmes de granularité. Par exemple, si la taille d'une
cellule correspond à la taille d'une porte laissant juste le robot passer, et que cette porte n'est pas tout à fait alignée avec la grille, alors elle risque d'être perçue comme un obstacle et donc bloquer l'exploration d'une partie de la carte. Pour éviter ce type de problème, il est possible de choisir des cellules relativement petites, de représenter la carte avec un quadtree, ou encore une représentation linéaire de l'environnement sans grille d'occupation (ce qui a été fait avec le simulateur 3D que nous avons développé, et présenté figure 7.1).

## 4.4. DURÉE DE L'EXPLORATION

La figure 4.3 représente le nombre d'itérations nécessaires pour explorer la carte entière avec $m = 3$ robots pour les différentes approches.

<figure><img src="image_9.png" /><figcaption>FIGURE 4.3. Durée totale de l'exploration pour chaque approche sur les cartes testées avec $m = 3$ robots.</figcaption></figure>

L'approche *BMILRV* est beaucoup plus lente que les approches par frontières locales et globales, surtout lorsqu'il y a des obstacles isolés (forçant l'algorithme *BMILRV* à contrôler les cycles), ce qui est le cas des cartes *Labyrinthne 1* et *Blocs*. Les deux approches frontières donnent des résultats comparables, l'approche globale restant légèrement meilleure.

L'approche par frontières locales donne parfois une moins bonne dispersion des robots, et donc de moins bonnes performances, en particulier sur la carte *Labyrinthne 2*. Plusieurs améliorations peuvent être envisagées pour se rapprocher des performances de l'approche globale (voir 8.2).
4.5. PROGRESSION DE L'EXPLORATION

La figure 4.4 présente l'évolution du pourcentage de cellules vues au cours du temps (en nombre d'itérations) pour les approches par frontières locales et globales, sur les deux premières cartes.

<figure><img src="image_10.png" /><figcaption>FIGURE 4.4. Évolution du pourcentage de cellules vues au cours du temps (m = 3 robots) sur les deux premières cartes.</figcaption></figure>

L'algorithme local perd facilement du temps lorsque les robots reviennent en arrière parce qu'ils prennent le même chemin que lors de leur premier passage, contrairement à l'algorithme global qui calcule le meilleur chemin pour atteindre une frontière. Cependant, les deux algorithmes montrent des résultats similaires, les deux courbes se croisent plusieurs fois pour la carte *Labyrinthe 1*.

4.6. NOMBRE DE ROBOTS

La figure 4.5 montre le nombre d'itérations nécessaires pour explorer les 4 cartes pour différents nombres de robots. Sur ces 4 cartes, les approches par frontières locales et globales donnent des résultats comparables.

Lorsque le nombre de robots augmente, l'algorithme par frontières globales prend
l'avantage en offrant une meilleure répartition des robots sur la carte.

5. VERSION DISTRIBUÉE

Cette partie se concentre sur la version décentralisée de l'algorithme par frontières locales et tente d'évaluer l'impact de la décentralisation sur les performances.
<figure><img src="image_11.png" /><figcaption>FIGURE 4.5. Nombre d'itérations nécessaires pour explorer toutes les cartes pour différents nombres de robots.</figcaption></figure>

## 5.1. PROCÉDURE DE PARTAGE DE CARTE

Le partage de la carte est nécessaire pour deux raisons : la grille d'occupation permet aux robots de définir les frontières locales ; si elle n'est pas partagée, les robots ne peuvent pas savoir si autre un robot a déjà exploré une partie donnée de la carte. De plus, la trace est également partagée pour permettre une meilleure répartition des robots, car elle est utilisée dans le choix de la frontière à définir comme objectif.

Toutes les $d_{\text{sync}}$itérations, chaque robot peut envoyer sa grille d'occupation $\mathcal{O}$ et ses cellules visitées $\mathcal{P}$ à tous les autres robots. Lorsqu'un robot $r_i$ reçoit des données d'un autre robot $r_j$ (grille d'occupation $\mathcal{O}_{r_j}$ et cellules visitées $\mathcal{P}_{r_j}$), il met à jour sa grille d'occupation de la façon suivante :

$$ \mathcal{P}_{r_i}(x, y) = \mathcal{P}_{r_i}(x, y) \lor \mathcal{P}_{r_j}(x, y) $$

Un *ou* logique est appliqué entre la valeur du robot et la valeur reçue : une cellule est visitée si le robot ou tout autre robot l'a déjà marquée comme visitée.

Il n'est pas nécessaire que les robots soient synchronisés pour partager leurs cartes en même temps, ils peuvent les envoyer ou les recevoir à tout moment.

## 5.2. RÉSULTATS EXPÉRIMENTAUX SUR L'EFFET DE LA DÉCENTRALISATION SUR LA DURÉE DE L'EXPLORATION

La figure 5.1 montre le nombre d'itérations nécessaires pour explorer les 4 cartes avec 3 robots pour différentes valeurs $d_{\text{sync}}$.

L'augmentation de la durée de l'exploration lorsque $d_{\text{sync}}$ augmente est due à une moins bonne dispersion, notamment lorsque plusieurs robots sont proches les uns des
<figure><img src="image_12.png" /><figcaption>FIGURE 5.1. Évolution de la durée de l'exploration des 4 cartes pour différentes valeurs de $d_{sync}$</figcaption></figure>

autres : ils explorent alors la même zone simultanément. Concrètement, si l'on suppose que deux robots donnés partagent leur carte d'autant plus souvent qu'ils sont proches, cette diminution sera alors limitée la plupart du temps (la présence de boucles peut cependant faire explorer une même zone à deux robots éloignés).

## 5.3. PERTE DE COMMUNICATION

Bien qu'augmenter $d_{sync}$diminue les performances de l'exploration, une perte de communication, ou une communication éparse ne causera pas de problème dans l'exploration (« oubli » d'une zone, robot bloqué...) et ne peut, dans le pire des cas, que prolonger la durée de l'exploration. Dans des applications concrètes, le partage de cartes entre robots peut être adapté en fonction de leur vitesse et de leur rayon de perception, éventuellement en fonction de la distance entre les robots.

## 6. AMÉLIORATION : « SECONDE CHANCE »

Il peut arriver lors de l'exploration qu'un ou plusieurs robots retournent à leur point de départ et ne trouvent plus de frontières visibles avant que l'exploration soit terminée, laissant les robots encore actifs terminer seuls. Lorsque cela se produit, l'exploration reste complète, mais les robots revenus à leur point de départ ne participent plus, ce qui peut augmenter la durée totale de l'exploration.

Pour éviter cette perte de performances, nous pouvons envisager un système de « seconde chance », autorisant ces robots à repartir explorer les zones restantes en suivant les traces des autres robots. Nous allons donc modifier l'algorithme décrit dans la partie 3.2.
## 6.1. ALGORITHME AVEC SECONDE CHANCE

Pour permettre aux robots de repartir, nous allons ajouter une variable *mode*, assigné à « normal » par défaut, et qui vaudra « secondeChance » lorsqu'un robot repart en suivant les traces des autres robots.

Pour activer le mode seconde chance, nous modifions le point 2. (b) de l'algorithme :

(2) (b) Si $|\mathcal{F}| = 0$ et si on est de retour à la cellule de départ :

i. Si il existe au moins un autre robot qui ne s'est pas arrêté et qui n'est pas en mode seconde chance, passer en mode seconde chance : *mode* ← *secondeChance*. Se déplacer vers une cellule voisine déjà visitée par un autre robot, si possible parmi celles que l'on n'a pas soit même visité. Si on voit à nouveau une frontière, repasser en mode normal.

ii. Sinon, s'arrêter.

## 6.2. ÉVOLUTION DE L'EXPLORATION

Nous allons maintenant comparer trois algorithmes : frontières globales (avec *MinPos*), frontières locales sans seconde chance, et frontières locales avec seconde chance. Cette fois, nous choisissons *m* = 10 robots qui partiront tous du centre du labyrinthe.

La figure 6.1 présente l'évolution de l'exploration pour les trois algorithmes sur le premier labyrinthe. Sur cette carte, où les approches globales et locales donnaient des résultats très proches pour *m* = 3 robots, l'algorithme local prend l'avantage avec la seconde chance, finissant l'exploration avant l'algorithme global.

<figure><img src="image_13.png" /><figcaption>FIGURE 6.1. Évolution du pourcentage de cellules vues au cours du temps (*m* = 10 robots) avec et sans seconde chance.</figcaption></figure>
## 6.3. DURÉE DE L'EXPLORATION

Nous allons maintenant nous intéresser à la durée totale de l'exploration des quatre cartes par les trois algorithmes, pour $m \in \{3, 5, 8\}$.

La figure 6.2 présente le nombre d'itérations nécessaires pour explorer les quatre cartes avec 3, 5 ou 8 robots. L'approche locale s'avère nettement meilleure avec la seconde chance pour 3 ou 8 robots et s'approche des performances de l'approche globale.

<figure><img src="image_14.png" /><figcaption>FIGURE 6.2. Nombre d'itérations nécessaires pour explorer toutes les cartes pour différents nombres de robots. Les robots partent ici groupés au centre des cartes à explorer.</figcaption></figure>

Notons que nous mesurons ici la durée nécessaire pour parcourir tout le labyrinthe. Si nous prenons en compte le temps de retour au point de départ des robots (leur permettant notamment de savoir que l'exploration est terminée), la seconde chance peut dans certains cas allonger l'exploration.

## 7. SIMULATION AVEC LIDAR EN ENVIRONNEMENT 3D PHOTORÉALISTE

Pour réduire la quantité de données échangées entre les robots ainsi que les données mémorisées, il est possible de ne transmettre que les positions occupées par les robots à un intervalle de distances donné. L'algorithme peut alors être exécuté sans grilles, avec uniquement la liste des positions précédentes du robot, la liste des positions reçues et autres robots et les informations perçues par le LIDAR (ensemble de la distance mesurée pour chacun des points). Nous avons également testé notre algorithme avec ce fonctionnement sur un simulateur 3D photoréaliste avec LIDAR présenté figure 7.1.
<figure><img src="image_15.png" /><figcaption>FIGURE 7.1. Exécution de l’algorithme avec le simulateur 3D. Les points du *LIDAR* du robot admissibles sont représentées en bleu, ceux non admissibles en rouge.</figcaption></figure>

# 8. DISCUSSION

## 8.1. FORCES ET FAIBLESSES DES DIFFÉRENTS ALGORITHMES

L'approche *BMILRV* est locale, mais a un fonctionnement complexe (de nombreux états pour les robots, la fermeture des cellules nécessite de nombreux calculs [2]) et donne de mauvais résultats lorsque des obstacles sont isolés ou qu'il y a des boucles sur la carte, forçant les robots à faire plusieurs passages pour marquer les cellules successivement comme contrôlées, fermées et finalement nettoyées (comme le confirment les expériences sur la figure 4.3). À notre connaissance, cette approche n'a pas été adaptée pour une mise en œuvre décentralisée.

L'approche par frontières (globales) est à la fois simple et efficace. Elle peut être distribuée facilement, mais nécessite une synchronisation fréquente de la carte et des positions du robot. Avec la stratégie d'affectation *MinPos* [5], chaque robot prend en compte la position de tous les autres robots pendant chaque affectation, ce qui implique que la carte des frontières globales et la position du robot sont fréquemment partagées. De plus, le temps de calcul de cette stratégie d'affectation dépend du nombre de robots et du nombre de frontières (les distances entre toutes les paires frontière/robot sont calculées à chaque itération), ce qui peut rendre cette méthode inutilisable si le nombre de robots est trop grand, ou si la carte est trop grande.

Enfin, l'approche par frontières locales présente des résultats proches de l'approche globale dans la plupart des cas, tout en ayant une complexité constante, ne dépendant ni du nombre total de robots ni de la taille de la carte. Il est également facilement distribuable sans contrainte sur la fréquence de partage des cartes, et les robots n'ont pas besoin de connaître le nombre ou la position des autres robots. Sans l'ajout de
la « seconde chance », cependant, certains robots peuvent s'arrêter avant la fin de l'exploration, réduisant ainsi la performance de l'exploration.

## 8.2. POSSIBILITÉS D'AMÉLIORATION

La version de l'algorithmme décrite ici ramène au point de départ des robots qui ne trouvent plus de frontières à explorer. Selon la carte et les conditions initiales, un robot peut revenir à son point de départ et s'arrêter avant que la carte entière ne soit explorée (laissant les autres robots terminer l'exploration). La distribution entre les robots est alors moins équilibrée et les performances de l'algorithmme sont réduites. Pour éviter cela, nous pouvons envisager un système de « seconde chance » (voir partie 6), permettant aux robots qui sont revenus à leur point de départ avant la fin de l'exploration de recommencer en suivant la trace de l'un des autres robots jusqu'à ce qu'il trouve une frontière.

La dispersion des robots est également rudimentaire et ne repose que sur le choix d'une cible aussi loin que possible de toute trace laissée. Lorsque plusieurs robots sont proches (dans leurs rayons de perception respectifs), et en particulier si $d_{sync}$ est élevé, l'ajout d'un système de dispersion supplémentaire pourrait également augmenter de manière significative les performances de l'algorithmme sans augmenter considérablement sa complexité.

## 8.3. CONCLUSION

Dans la version proposée ici, l'algorithmme donne de bonnes performances (nombre d'étapes pour compléter la couverture) par rapport aux deux autres approches, et au bénéfice d'une complexité constante (en temps et en mémoire) pour un robot donné, ce qui permet d'utiliser un très grand nombre de robots. En effet, dans le cas de l'approche par frontières globales, les stratégies les plus efficaces, telles que *MinPos*, nécessitent de calculer autant de distances que de paires robot/frontière, ce qui peut poser problème s'il y a un trop grand nombre de robots ou si la carte est trop grande. De plus, notre approche locale est plus facilement distribuable au prix d'une perte de performance possible lorsque les robots sont proches, et ne nécessite pas de synchronisation temporelle entre les robots.

Ces résultats montrent également qu'il existe des approches intermédiaires entre les algorithmes locaux et les algorithmes globaux, pouvant prendre en compte les cellules de la grille dans un rayon de perception déterminé et garantissant une exploration complète.
BIBLIOGRAPHIE

[1] J. P. L. S. DE ALMEIDA, R. T. NAKASHIMA, F. NEVES-JR & L. V. R. DE ARRUDA, « Bio-inspired on-line path planner for cooperative exploration of unknown environment by a Multi-Robot System », Robotics and Autonomous Systems 112 (2019), p. 32 - 48.

[2] M. ANDRIES & F. CHARPILLET, « Multi-robot taboo-list exploration of unknown structured environments », in 2015 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2015, p. 5195-5201.

[3] E. ANGELOPOULOU, T. H. HONG & A. Y. WU, « World model representations for mobile robots », in Proceedings of the Intelligent Vehicles '92 Symposium, 1992, p. 293-297.

[4] M. ARAYA-LOPEZ, V. THOMAS, O. BUFFET & F. CHARPILLET, « A Closer Look at MOMDPs », in 2010 22nd IEEE International Conference on Tools with Artificial Intelligence, vol. 2, 2010, p. 197-204.

[5] A. BAUTIN, O. SIMONIN & F. CHARPILLET, « Minpos: A novel frontier allocation algorithm for multi-robot exploration », in International conference on intelligent robotics and applications, Springer, 2012, p. 496-508.

[6] W. BURGARD, M. MOORS, D. FOX, R. SIMMONS & S. THRUN, « Collaborative multi-robot exploration », in Proceedings 2000 ICRA. Millennium Conference. IEEE International Conference on Robotics and Automation. Symposia Proceedings (Cat. No.00CH37065), vol. 1, 2000, p. 476-481.

[7] D. S. CHAPLOT, D. GANDHI, S. GUPTA, A. GUPTA & R. SALAKHUTDINOV, « Learning to explore using active neural SLAM », https://arxiv.org/abs/2004.05155, 2020.

[8] T. CHEN, S. GUPTA & A. GUPTA, « Learning exploration policies for navigation », https://arxiv.org/abs/1903.01959, 2019.

[9] J. FAIGL, O. SIMONIN & F. CHARPILLET, « Comparison of Task-Allocation Algorithms in Frontier-Based Multi-robot Exploration », in Multi-Agent Systems (Cham) (N. Bulling, éd.), Springer International Publishing, 2015, p. 101-110.

[10] E. GALCERAN & M. CARRERAS, « A survey on coverage path planning for robotics », Robotics and Autonomous Systems 61 (2013), n° 12, p. 1258 - 1276.

[11] S. GARNIER, F. TACHE, M. COMBE, A. GRIMAL & G. THERAULAZ, « Alice in Pheromone Land: An Experimental Setup for the Study of Ant-like Robots », in 2007 IEEE Swarm Intelligence Symposium, 2007, p. 37-44.

[12] J. HU, H. NIU, J. CARRASCO, B. LENNOX & F. ARVIN, « Voronoi-based multi-robot autonomous exploration in unknown environments via deep reinforcement learning », IEEE Transactions on Vehicular Technology 69 (2020), n° 12, p. 14413-14423.

[13] E. A. JENSEN & M. GINI, « Effects of Communication Restriction on Online Multi-robot Exploration in Bounded Environments », in Distributed Autonomous Robotic Systems (Cham) (N. Correll, M. Schwager & M. Otte, éds.), Springer International Publishing, 2019, p. 469-483.

[14] N. MAHDOUI, V. FRÉMONT & E. NATALIZIO, « Cooperative Frontier-Based Exploration Strategy for Multi-Robot System », in 2018 13th Annual Conference on System of Systems Engineering (SoSE), 2018, p. 203-210.

[15] Q. V. NGUYEN, F. COLAS, E. VINCENT & F. CHARPILLET, « Localizing an intermittent and moving sound source using a mobile robot », in 2016 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2016, p. 1986-1991.

[16] M. SAVVA, A. KADIAN, O. MAKSYMETS, Y. ZHAO, E. WIJMANS, B. JAIN, J. STRAUB, J. LIU, V. KOLTUN, J. MALIK, D. PARIKH & D. BATRA, « Habitat: A Platform for Embodied AI Research », in Proceedings of the IEEE/CVF International Conference on Computer Vision (ICCV), 2019.

[17] O. SIMONIN, T. HURAUX & F. CHARPILLET, « Interactive Surface for Bio-inspired Robotics, Re-examining Foraging Models », in 2011 IEEE 23rd International Conference on Tools with Artificial Intelligence, 2011, p. 361-368.

[18] A. SZOT, A. CLEGG, E. UNDERSANDER, E. WIJMANS, Y. ZHAO, J. TURNER, N. MAESTRE, M. MUKADAM, D. CHAPLOT, O. MAKSYMETS, A. GOKASLAN, V. VONDRUS, S. DHARUR, F. MEIER, W. GALUBA, A. CHANG, Z. KIRA, V. KOLTUN, J. MALIK, M. SAVVA & D. BATRA, « Habitat 2.0: Training Home Assistants to Rearrange their Habitat », https://arxiv.org/abs/2106.14405, 2021.

[19] A. H. TAN, F. P. BEJARANO & G. NEJAT, « Deep Reinforcement Learning for Decentralized Multi-Robot Exploration with Macro Actions », https://arxiv.org/abs/2110.02181, 2021.
[20] S. THRUN & A. BÜCKEN, « Integrating grid-based and topological maps for mobile robot navigation », in *Proceedings of the National Conference on Artificial Intelligence*, 1996, p. 944-951.

[21] E. VINCENT, A. SINI & F. CHARPILLET, « Audio source localization by optimal control of a mobile robot », in *2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)*, 2015, p. 5630-5634.

[22] I. A. WAGNER, M. LINDENBAUM & A. M. BRUCKSTEIN, « Distributed covering by ant-robots using evaporating traces », *IEEE Transactions on Robotics and Automation* **15** (1999), n° 5, p. 918-933.

[23] B. YAMAUCHI, « A frontier-based approach for autonomous exploration », in *Proceedings 1997 IEEE International Symposium on Computational Intelligence in Robotics and Automation CIRA'97*. 'Towards New Computational Principles for Robotics and Automation', 1997, p. 146-151.

**ABSTRACT.** — Different approaches exist for multirobot autonomous exploration. These include frontier approaches, where robots are assigned to unexplored areas of the map, which provide good performance but require sharing the map and centralizing decision-making. The Brick and Mortar approaches, on the other hand, use a ground marking with local decision-making, but give much lower performance. The algorithm presented here is a trade-off between these two approaches, allowing local decision-making and, surprisingly, performances are closed to centralized frontier approaches. We also propose a comparative study of the performance of the three different approaches : *Brick & Mortar, Global Frontiers and Local Frontiers*. Our local algorithm is also complete for the exploration problem and can be easily distributed on robots with a minor loss of performance.

**KEYWORDS.** — multirobot, stigmergy, exploration.

Manuscrit reçu le 23 juillet 2021, révisé le 31 janvier 2022, accepté le 14 mars 2022.