## 4.1 Introduction

Ce chapitre présente la série d'expériences effectuées afin de valider notre modélisation du problème d'exploration et évaluer les performances de l'algorithme xBOA.

Nous utiliserons notre plateforme de benchmarking afin de comparer les performances de cet algorithme avec les différentes métaheuristiques incluses dans le simulateur (GA, ACO, PSO, CMAES, GWO, ABC) pour la résolution du problème d'exploration de zones inconnues. Nous comparerons également les performances du xBOA avec l'algorithme BOA original et ses autres variantes (MBOA, SABOA, ABOA).

Nous analyserons ensuite les résultats d'une série d'expériences visant à accélérer la vitesse d'exécution de l'algorithme tout en analysant la robustesse des méthodes citées face à la réduction de la taille de la population.

Nous présenterons aussi une expérience pour évaluer l'adaptabilité de notre approche dans un contexte multirobots. Le but étant de valider les capacités du modèle à pouvoir générer un comportement collectif pour les robots sans besoin d'intégrer des mécanismes de synchronisation explicite. Pour finir, nous testerons l'approche sur un robot réel.

## 4.2 Configuration matérielle

Dans le but d'effectuer les expériences souhaitées, nous avons utilisé trois machines.

La première consiste en un ordinateur portable de moyenne gamme avec une mémoire vive de 8Go et un processeur Intel i7 de 4ème génération. Ce processeur possède 4 cores ayant chacun une fréquence d'horloge de 2.8Ghz. Bien que cet ordinateur inclut aussi une carte graphique, celle-ci n'a pas été utilisée pour les raisons citées dans la section 3.2.2, ainsi que le fait que les deux autres machines utilisées pour effectuer les expériences ne possédaient pas de capacités de calcul graphique.

La deuxième machine utilisée consiste en un service cloud de Google appelé Collaboratory (ou Google Colab) offrant une machine virtuelle utilisant un processeur Intel Xeon de 2 cores cadencés à 2.3Ghz avec une mémoire vive de 12Go. L'utilisation de ce service est gratuite pour des sessions de calcul dont la durée est inférieure à 12h.

La troisième machine utilisée consiste en un cluster disponible au Plateau Technique de Calcul Intensif IBN-BAJA à l'Université des Sciences et de la Technologie d'Oran Mohamed Boudiaf - USTOMB. Ce cluster destiné à effectuer des calculs à hautes performances (High Performance Computing) possède une mémoire vive de 32Go et 24 processeurs Intel Xeon de 6 cores chacun cadencés à 2Ghz. Ce cluster nous a permis d'effectuer des sessions de simulation de longue durée en répétant la même expérience plusieurs fois.

Chaque machine utilise un système d'exploitation différent. Le code a été déployé sur ces machine sans nécessiter de changement ou de compilation, ce qui a démontré la portabilité de notre simulateur sur des systèmes de type Linux et Windows. Le code n'a pas encore été testé sur un système de type iOS mais ne devrait présenter aucun problème de compatibilité.
## 4.3 Expérience 1 : Évaluation de l’algorithme xBOA dans un contexte multirobots

La série d'expériences présentée dans cette section vise à valider l'adaptabilité de l'ap-
proche dans un scénario multirobots. Selon ce que l'on peut observer sur la figure 4.1, les
robots déployés à partir de la même position de départ ont pu se disperser dans l'environne-
ment pour explorer la surface entière sans aucun changement nécessaire dans l'algorithme
pour coordonner leurs déplacements. Ceci montre la flexibilité de la modélisation proposée
pour s'adapter aux scénarios mono et multirobots.

En effet, chaque robot possède sa propre population de solutions candidates et essaie
de maximiser sa propre valeur de fitness indépendamment des autres robots. Ces robots
n'échangent pas de messages entre eux, mais collaborent passivement en modifiant une
carte globale qui est stockée dans une mémoire centrale. Lorsqu'un robot se déplace, il
met à jour cette carte partagée afin d'y insérer les obstacles détectés et marquer la zone
observée comme étant visitée. Les autres robots vont donc automatiquement éviter cette

<figure><img src="image_56.png" /><figcaption>FIGURE 4.1 – Progression visuelle du scenario multirobots en utilisant la méthode xBOA avec 3 robots</figcaption></figure>
zone lorsqu'ils planifient les prochaines trajectoires puisque la fonction fitness pénalisera ces régions déjà visitées.

Étant donné que les robots ne sont pas conscients de la présence des autres robots, ils n'échangent pas de messages entre eux par rapport à leurs chemins planifiés ou des régions prévues à être visitées dans le futur. Tout ce qu'ils échangent c'est la position des obstacles détectés et les zones déjà visitées auparavant. De ce fait, il arrive que plusieurs robots décident de se diriger vers la même direction puisque cela maximise leur valeur de fitness. Ce comportement est observé au départ de l'expérience lorsqu'ils choisissent tous le chemin diagonal maximisant la zone à observer, ou parfois au milieu de l'expérience tel qu'on peut le voir sur la figure 4.1. Cependant, nous observons que dans l'ensemble, le système arrive quand même à faire disperser les robots dans des régions séparées, ce qui a pour effet d'accélérer le temps d'exploration de la zone comparé aux scénarios où on n'utilise qu'un seul robot.

Afin de montrer l'adaptabilité de l'approche à des environnements beaucoup plus larges, nous avons effectué une autre expérience en utilisant une carte inspirée d'une usine ayant une superficie égale à 30x50 mètres. La figure 4.2 montre un résultat intermédiaire enregistré pendant l'exécution. Cette expérience a été répétée plusieurs fois en changeant le nombre de robots, elle a montré la capacité de l'approche à les pousser à explorer la zone entière même en cas de forte densité d'obstacles ou de l'augmentation de la superficie de l'environnement.

Par ailleurs, cette série d'expériences a permis aussi d'apprécier la facilité d'utilisation de notre simulateur, puisqu'il s'adapte automatiquement à l'ajout de nouveaux scénarios et au changement du nombre de robots. L'utilisateur n'aura qu'à effectuer un paramétrage de

<figure><img src="image_57.png" /><figcaption>FIGURE 4.2 – Progression visuelle d'un scénario à grande échelle en utilisant la méthode xBOA avec 2 robots</figcaption></figure>
l'expérience sans se soucier des mécanismes internes de détection des obstacles, de mise à jour de la carte globale, ou de l'évitement des collisions entre les robots. Ce genre de tâches sont souvent un frein à beaucoup de chercheurs venant de domaines différents puisqu'elles nécessitent d'avoir une bonne compréhension des problématiques de navigation robotique et du fonctionnement des grilles d'occupation.

## 4.4 Expérience 2 : Comparaison entre les stratégies d'exploration à court terme et à long terme

Cette expérience vise à comparer deux stratégies d'exploration. La première consiste à planifier la mission à long terme en sélectionnant plusieurs points de destination au départ de l'exécution ; calculer un chemin pour visiter ces points selon leur ordre de sélection ; puis répéter l'opération après avoir visité tous ces points. Quant à la deuxième stratégie, elle consiste à faire une planification à court terme en ne sélectionnant qu'un seul point à la fois ; le robot devra donc attendre jusqu'à avoir visité sa destination actuelle avant de choisir la prochaine.

La figure 4.3 montre un exemple d'exécution des deux stratégies en utilisant la méthode xBOA. Cette visualisation étape par étape montre que la stratégie à long terme est moins efficace que la stratégie à court terme lorsque l'environnement est inconnu à l'avance. En effet, la planification à long terme de plusieurs points de destination au début de la mission se base sur des informations très limitées puisque le robot n'a aucune connaissance à priori de l'emplacement des murs et des obstacles avant de les avoir détectés grâce à son LIDAR. Le processus d'optimisation choisit donc ces destinations en ne tenant compte que de l'information de distance à vue d'oiseau par rapport au robot. Cependant, lorsque celui-ci commence à se déplacer pour visiter ces points, il met à jour sa carte en collectant les informations des positions des obstacles et des différents chemins possibles. Toutefois, il n'utilisera ces informations que lors de la prochaine phase de sélection après avoir visité tous les points planifiés. En d'autres termes : le robot continuera donc à visiter les destinations prévues initialement sans profiter de l'apport des nouvelles informations récoltées en chemin, et tombera souvent dans une redondance poussant le robot à revisiter une zone déjà explorée auparavant.

Pour illustrer ce problème de redondance, la figure 4.3 montre un exemple où la visite du 3ème point en utilisant la stratégie à long terme n'a apporté aucun gain, et ceci à cause du manque de visibilité lors de la phase de sélection. Alors que la stratégie à court terme a permis d'éviter cette redondance en utilisant les informations récoltées lors de la visite du 1er et 2ème point pour pousser le robot à visiter une nouvelle zone.

Dans la stratégie à court terme, le robot ne sélectionne qu'un seul point de destination. Il se déplacera pour le visiter tout en mettant à jour la carte de l'environnement puis sélectionnera un nouveau point en utilisant les nouvelles informations récoltées en chemin. La qualité du choix est donc meilleure puisqu'il élimine les destinations n'apportant aucun gain supplémentaire ou qui sont trop coûteuses par rapport aux gains qu'ils pourront apporter. Cette stratégie est aussi avantageuse dans le cas des environnements dynamiques où les positions des obstacles changent à cause de portes ouvertes et fermées par exemple,
<figure><img src="image_58.png" /><figcaption>(a) État d'avancement de la mission d'exploration en utilisant la stratégie à long terme (surface explorée 64%)</figcaption></figure>

<figure><img src="image_59.png" /><figcaption>(b) État d'avancement de la mission d'exploration en utilisant la stratégie à court terme (surface explorée 91%)</figcaption></figure>

**FIGURE 4.3** – Comparaison entre les deux stratégies d'exploration en utilisant la méthode xBOA

ou à cause d'objets déplacés. Le robot pourra prendre en compte les derniers changements de la carte à chaque fois qu'une destination est atteinte.

L'inconvénient de cette stratégie cependant est la nécessité de répéter le processus de sélection des points de destination plus fréquemment. Il est donc nécessaire que le temps d'exécution de ce processus soit court puisque le robot restera en état d'attente le temps de finir ses calculs.

Aussi nous remarquons que cette stratégie à réussi à explorer presque la totalité de la zone dans l'exemple montré par la figure 4.3 en visitant 3 points seulement. Elle a pu atteindre un taux d'exploration de 91% contrairement à la stratégie à long terme qui n'a réussi à explorer que 64% de la surface de la zone, soit un résultat inférieur de 27% comparé à la stratégie à court terme.

## 4.5 Expérience 3 : Recherche des meilleurs hyperparamètres

Les métaheuristiques sont sensibles aux choix des paramètres initiaux. Une pratique courante dans la littérature consiste à comparer les performances des méthodes en utilisant les paramètres originaux utilisés par les auteurs dans leurs premières publications [11]. Ceci peut être un bon choix si nous comparons ces méthodes en utilisant les fonctions
de benchmarking standards; toutefois, le problème d'exploration de zones inconnues est
par nature un problème incrémental et partiellement observable, ce qui peut rendre les
paramètres par défaut moins optimaux.

De ce fait, nous avons effectué une expérience préliminaire afin de rechercher les meilleurs
paramètres de chaque méthode pour ce problème en particulier. Ceci nous permutera de
comparer les résultats de ces métaheuristiques dans leurs performances optimales et éviter
qu'elles soient piégées dans des optimums locaux à cause de mauvaises initialisations.

Il n'existe pas de formule mathématique précise pour trouver les meilleurs hyperpara-
mètres d'une méthode, ceci doit se faire expérimentalement en essayant plusieurs valeurs et
comparer leurs résultats. Bien que beaucoup de chercheurs utilisent la méthode manuelle,
nous avons préféré utiliser la bibliothèque *Hyperopt* [18]. Cette bibliothèque permet d'op-
timiser les paramètres d'entrée d'un algorithme en effectuant une recherche sélective sur
une plage de valeurs. Elle offre plusieurs stratégies de recherche dont principalement la
méthode de recherche aléatoire (*Random Search* [17]) et recherche par l'algorithme TPE
(*Tree-structured Parzen Estimator* [18]) qui montrent des résultats meilleurs comparés aux
méthodes classiques telles que la stratégie de recherche par grille (*Grid Search*) [17].

Le fonctionnement de base de la bibliothèque *Hyperopt* consiste à exécuter plusieurs
fois l'algorithme qu'on veut optimiser en utilisant des valeurs aléatoires pour l'initialisation
des hyperparamètres, puis d'adapter ces valeurs selon les résultats obtenus après plusieurs
essais. En répétant cette opération un nombre suffisant de fois, la bibliothèque arrive à
réduire la plage de paramétrage afin de choisir une combinaison qui donne de bons résultats.

En profitant de la puissance de calcul du cluster de calcul intensif de l'USTOMB, nous avons lancé l'optimisation des hyperparamètres de toutes les métaheuristiques incluses dans notre simulateur à raison de 30 essais par méthode en répétant chaque essai 3 fois, ce qui donne un total de 90 exécutions chacune. Le Tableau 4.1 liste les meilleurs paramètres trouvés durant cette expérience, nous nous baserons sur ces valeurs pour effectuer les prochaines expériences.

Certaines méthodes telles que ABC, GWO et CMAES ne requièrent pas de paramétrage
manuel. Pour les autres méthodes, les paramètres suivants ont été sélectionnés :

- GA : nous avons utilisé une stratégie de sélection par tournoi de taille 2 et une mutation polynomiale avec un index de distribution de 76.

- PSO : nous avons utilisé une taille de voisinage de 4 avec un facteur d'accélération cognitif supérieur au facteur d'accélération social, ce qui attire chaque particule vers la meilleure position dans son voisinage au lieu de retourner à sa meilleure position trouvée précédemment.

- Variantes de BOA : ces paramètres sont expliqués en détail dans la section 2.8. Les valeurs des meilleurs paramètres sont présentées dans le tableau 4.1.
<table><caption>TABLE 4.1 – Valeurs des meilleurs hyperparamètres trouvés après 30 essais</caption><thead><tr><th>Methods</th><th>Hyperparameters</th><th>Values</th><th>Methods</th><th>Hyperparameters</th><th>Values</th></tr></thead><tbody><tr><td rowspan="3">BOA<br>(pop size 20)</td><td>Power exponent</td><td>0.547</td><td rowspan="3">BOA<br>(pop size 5)</td><td>Power exponent</td><td>0.73</td></tr><tr><td>Sensor modality</td><td>0.602</td><td>Sensor modality</td><td>0.577</td></tr><tr><td>Switch probability</td><td>0.395</td><td>Switch probability</td><td>0.331</td></tr><tr><td rowspan="3">xBOA<br>(pop size 20)</td><td>Power exponent</td><td>0.905</td><td rowspan="3">xBOA<br>(pop size 5)</td><td>Power exponent</td><td>0.994</td></tr><tr><td>Sensor modality</td><td>0.257</td><td>Sensor modality</td><td>0.518</td></tr><tr><td>Crossover probability</td><td>0.593</td><td>Crossover probability</td><td>0.583</td></tr><tr><td rowspan="3">GA</td><td>Crossover probability</td><td>0.11</td><td rowspan="3">mBOA<br>(pop size 5)</td><td>Power exponent</td><td>0.61</td></tr><tr><td>Mutation probability</td><td>0.215</td><td>Sensor modality</td><td>0.356</td></tr><tr><td>Mutation distribution index</td><td>76.026</td><td>Switch probability</td><td>0.762</td></tr><tr><td rowspan="4">PSO</td><td>Social component coef.</td><td>1.506</td><td rowspan="4">ABOA<br>(pop size 5)</td><td>Power exponent</td><td>0.992</td></tr><tr><td>Cognitive component coef.</td><td>3.379</td><td>Sensor modality</td><td>0.98</td></tr><tr><td>Max velocity</td><td>0.329</td><td>Switch probability</td><td>0.983</td></tr><tr><td>Inertia weight</td><td>0.449</td><td>μ</td><td>1.356</td></tr><tr><td>ABC, GWO,<br>CMAES</td><td>No parameters to optimize<br>(auto-tuning)</td><td></td><td>SABOA<br>(pop size 5)</td><td>Switch probability</td><td>0.237</td></tr></tbody></table>

## 4.6 Expérience 4 : Comparaison de l'algorithm e xBOA avec les métaheuristiques populaires

Dans cette série d'expériences, nous allons comparer les performances des différentes métaheuristiques incluses dans notre simulateur pour la résolution du problème d'exploration de zones inconnues.

Selon ce qu'on peut voir sur les Figures 4.4 et 4.5 ainsi que le Tableau 4.2, les méthodes xBOA, PSO, GA et CMAES ont présenté des résultats presque similaires sur la plupart des scénarios, surtout dans le cas de l'exploration à court terme. Ceci signifie que le processus d'optimisation a convergé avec succès vers la solution optimale. Toutefois, nous observons une dégradation de la convergence de BOA et GWO à certaines périodes provoquées par leur blocage dans un optimum local poussant le robot à revisiter une zone déjà explorée pendant un certain intervalle de temps. Cependant, ces méthodes finissent par échapper à ce minimum local après un certain nombre de pas et rattraper leur retard.

Il est important de noter que la métrique du « nombre de pas » (step number) correspond au nombre de mouvements et de rotations effectués par le robot. Il est fortement corrélé avec la durée de la mission, mais de manière non linéaire puisque le temps nécessaire pour effectuer une rotation à 45° est différent de celui requis pour se déplacer un mètre en avant.
Nous avons choisi d'analyser le nombre de pas au lieu du temps d'exploration à cause de l'importance du facteur énergie dans le domaine de la robotique; le nombre de mouvements qu'un robot peut effectuer est limité par la capacité de sa batterie. Si dans notre cas le robot avait une capacité de batterie pour effectuer seulement 100 pas par exemple, il ne pourra explorer que 80% de la première scène (Empty map) en utilisant l'algorithme BOA, au lieu de 85% s'il utilisait xBOA, PSO ou CMAES. L'algorithme BOA apparaît donc moins efficace que les autres méthodes en considérant ce critère d'évaluation.

<table><caption>TABLE 4.2 – Taux d'exploration obtenus à la fin de la mission d'exploration</caption><thead><tr><th colspan="7">Short-term exploration</th></tr><tr><th rowspan="2">Method</th><th colspan="3">Empty map</th><th colspan="3">House map</th></tr><tr><th>Average</th><th>Min</th><th>Max</th><th>Average</th><th>Min</th><th>Max</th></tr></thead><tbody><tr><td>ABC</td><td>98.12</td><td>97.22</td><td>≥ 99</td><td>90.1</td><td>88.36</td><td>92.7</td></tr><tr><td>BOA</td><td>96</td><td>94.79</td><td>≥ 99</td><td>93.4</td><td>91.84</td><td>95.13</td></tr><tr><td>CMAES</td><td>98.49</td><td>95.66</td><td>≥ 99</td><td>93.29</td><td>89.4</td><td>96.18</td></tr><tr><td>GA</td><td>97.38</td><td>82.81</td><td>≥ 99</td><td>93</td><td>92.01</td><td>94.96</td></tr><tr><td>GWO</td><td>93.03</td><td>92.88</td><td>93.05</td><td>67.7</td><td>67.7</td><td>67.7</td></tr><tr><td>PSO</td><td>98.16</td><td>97.39</td><td>≥ 99</td><td>93.19</td><td>88.71</td><td>94.79</td></tr><tr><td>xBOA</td><td>98.23</td><td>93.92</td><td>≥ 99</td><td>91.63</td><td>82.63</td><td>94.44</td></tr></tbody><thead><tr><th colspan="7">Long-term exploration</th></tr><tr><th>Method</th><th>Average</th><th>Min</th><th>Max</th><th>Average</th><th>Min</th><th>Max</th></tr></thead><tbody><tr><td>ABC</td><td>98.02</td><td>96.52</td><td>≥ 99</td><td>86.38</td><td>80.38</td><td>92.18</td></tr><tr><td>BOA</td><td>93.87</td><td>91.49</td><td>97.74</td><td>84.61</td><td>73.26</td><td>92.36</td></tr><tr><td>CMAES</td><td>94.16</td><td>83.85</td><td>≥ 99</td><td>82.23</td><td>77.43</td><td>86.45</td></tr><tr><td>GA</td><td>97.63</td><td>96.52</td><td>≥ 99</td><td>87.67</td><td>79.86</td><td>95.48</td></tr><tr><td>GWO</td><td>93.4</td><td>93.4</td><td>93.4</td><td>83.68</td><td>83.68</td><td>83.68</td></tr><tr><td>PSO</td><td>96.44</td><td>92.88</td><td>≥ 99</td><td>87.06</td><td>84.2</td><td>90.97</td></tr><tr><td>xBOA</td><td>96.37</td><td>93.57</td><td>98.61</td><td>89.9</td><td>79.16</td><td>94.1</td></tr></tbody></table>

Les Figures 4.6 et 4.7 nous permettent d'analyser le temps de calcul total pour chaque méthode durant la mission d'exploration. Étant donné que les processeurs sont une ressource coûteuse en termes de prix de fabrication et d'énergie consommée, la tendance dans le domaine des systèmes multirobots est de réduire au maximum le temps de calcul requis pour accomplir la mission afin de permettre l'utilisation de processeurs plus petits et moins gourmands. La méthode idéale devrait donner une qualité d'exploration maximale tout en nécessitant un minimum de temps de calcul. Toutefois, il est rarement le cas d'obtenir un tel résultat, ce qui nous contraint souvent à trouver un compris entre ces deux critères de comparaisons.
<figure><img src="image_60.png" /></figure>

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

<caption>FIGURE 4.4 – Résultats de la simulation de la mission d'exploration en utilisant la stratégie à court terme</caption>

<footnote>*Les résultats présentent les valeurs moyennes de 10 exécutions</footnote>
<figure><img src="image_62.png" /></figure>

*Les résultats présentent les valeurs moyennes de 10 exécutions

<caption>FIGURE 4.5 – Résultats de la simulation de la mission d'exploration en utilisant la stratégie à long terme</caption>
Nous remarquons dans les résultats présentés par ces figures la présence de plusieurs pics sur l'axe du temps de calcul. Ces pics correspondent au temps requis par le robot pour calculer les prochains points à visiter en utilisant l'une des métaheuristiques, sachant que le robot est figé pendant ce temps puisqu'il n'a pas encore de point de destination pour pouvoir planifier un chemin de déplacement. Nous remarquons aussi que le temps de calcul pendant le déplacement du robot est relativement négligeable, ceci s'explique par le fait que le robot ne nécessite pas d'effectuer des opérations de calculs compliquées pendant le déplacement puisque cette phase se limite à mesurer la distance avec l'obstacle le plus proche pour éviter les collisions ainsi que la mise à jour des probabilités d'occupation dans la carte.

Bien que les méthodes xBOA, GA et ABC donnent de meilleurs résultats en termes de taux d'exploration comparés à BOA, elles nécessitent un temps de calcul plus long. Ceci s'explique par la simplicité des opérations de l'algorithme BOA et sa complexité réduite comparée aux autres méthodes. Les résultats présentés dans la Figure 4.8 renforcent cette explication; nous observons clairement que le temps de calcul de la méthode BOA est inférieur à celui de xBOA, GA et ABC, et que le nombre d'appels à la fonction de fitness (*fitness evaluations*) est inférieur.

Nous observons aussi que la méthode ABC requiert un temps de calcul considérable dans toutes les expériences, qui est supérieur au double du temps requis par les autres méthodes. Ceci est causé par la nature de l'algorithme ABC qui est divisé en 3 phases dont chacune nécessite la réévaluation des individus, ce qui conduit à un grand nombre d'exécutions de la fonction objectif. Cette lenteur le rend inadapté aux scénarios en situation réelle, car les robots ne doivent pas rester immobilisés pendant une longue période.

Par ailleurs, nous remarquons que la méthode CMAES domine les autres méthodes sur le critère du temps de calcul, mais elle est parfois dominée par la méthode BOA en termes de taux d'exploration, alors que cette dernière est elle-même dominée par xBOA dans tous les scénarios sur ce même critère. La méthode GWO est elle aussi dominée par xBOA sur ce critère, mais elle enregistre un temps de calcul plus rapide.

Il est important de noter à partir de la figure 4.8 que le temps de calcul moyen pour sélectionner le prochain point de destination est relativement long; moyennant 150 à 450 secondes durant lesquelles le robot est à l'arrêt en attendant le résultat du processus d'optimisation. Ceci n'est pas recommandé pour des scénarios où le temps est un facteur critique tel que les missions de sauvetage par exemple. Deux potentielles solutions sont possibles dans ce cas. La première consiste à profiter des fonctionnalités de parallélisme offertes par les processeurs modernes pour évaluer plusieurs individus de la population en même temps. Des résultats préliminaires nous ont permis de réduire de moitié le temps d'exécution en utilisant cette technique.

La deuxième stratégie consiste à réduire la taille de la population, ce qui revient donc à réduire le nombre de solutions candidates évaluées par la fonction objectif. Dans la série d'expériences suivante, nous allons analyser l'impact de cette deuxième stratégie sur la qualité des solutions générées.
Execution time — Empty Map

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

Execution time — House Map

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

*Les résultats présentent les valeurs moyennes de 3 exécutions

<caption>FIGURE 4.6 – Comparaison de la durée totale de la mission d'exploration pour la stratégie à court terme</caption>
<figure><img src="image_65.png" /></figure>

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

*Les résultats présentent les valeurs moyennes de 3 exécutions

<caption>FIGURE 4.7 – Comparaison de la durée totale de la mission d'exploration pour la stratégie à long terme</caption>
<figure><img src="image_67.png" /><figcaption>(a) Nombre d'évaluations de la fonction de fitness</figcaption></figure>

<figure><img src="image_68.png" /><figcaption>(b) Temps moyen de calcul pour chaque métaheuristique</figcaption></figure>

<caption>FIGURE 4.8 – Nombre d'évaluations de la fonction de fitness et temps moyen de calcul pour chaque métaheuristique</caption>

<footnote>*Les résultats présentent les valeurs moyennes de 3 exécutions</footnote>
## 4.7 Expérience 5 : Evaluation de la robustesse de l'algorithm e xBOA face à la réduction de taille de la population

Afin d'étudier la possibilité d'accélérer les algorithmes BOA et xBOA en réduisant la taille de la population, nous avons effectué une série d'expériences afin de mesurer l'influence de la taille de la population sur ces algorithmes et la robustesse de ces derniers.

Dans un premier temps, nous avons effectué une expérience sur l'algorithm e BOA original en variant la taille de la population de 20 à 5 papillons tout en gardant les autres paramètres fixes.

Les résultats présentés sur la figure 4.9 montrent que la réduction du nombre de solutions candidates (papillons) réduit considérablement le temps d'exécution de la métaheuristique. En effet, ce temps a diminué de 320 secondes à 110 secondes en divisant la taille de la population en quatre. Toutefois, ceci affecte aussi la qualité de l'exploration puisque

<table><caption>TABLE 4.3 – Evolution du taux d'exploration selon la taille de la population en utilisant l'algorithm e BOA</caption><caption>Short-term exploration - House map</caption><thead><tr><th>Pop size</th><th>Average</th><th>Min</th><th>Max</th></tr></thead><tbody><tr><td>05 butterflies</td><td>86.11</td><td>81.77</td><td><strong>95.13</strong></td></tr><tr><td>10 butterflies</td><td>88.66</td><td>79.68</td><td><strong>95.13</strong></td></tr><tr><td>20 butterflies</td><td><strong>92.84</strong></td><td><strong>89.75</strong></td><td>94.27</td></tr></tbody></table>

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

*Les résultats présentent les valeurs moyennes de 3 exécutions

<caption>FIGURE 4.9 – Comparaison des résultats en utilisant l'algorithm e BOA avec différentes tailles de population sur l'environnement *House Map*</caption>
le taux total de la surface explorée a baissé de 6.73%, tel que nous pouvons le voir sur le tableau 4.3.

Bien que cette baisse du taux d'exploration est importante, le gain apporté de pouvoir calculer le prochain point de destination en moins de 110 secondes apporte son lot d'avantages puisque ce temps d'attente est acceptable pour beaucoup de scénarios de robotique dans le monde réel par rapport au temps initial qui était trois fois plus long.

En prenant ces résultats comme ligne de base, nous avons effectué d'autres expériences pour mesurer les performances de notre méthode ainsi que celles des autres métheuristiques lorsque la taille de la population est réduite à 5 solutions. Les résultats sont présentés sur le tableau 4.3 et les figures 4.10 et 4.11.

La première remarque notable que nous pouvons constater en observant les graphes se trouve au niveau du taux d'exploration des méthodes PSO et GWO dont l'amélioration s'est arrêtée après avoir atteint les valeurs de 75% et 62% respectivement, malgré qu'elles démontraient des résultats proches de ceux des autres méthodes lorsque la taille de la population était plus grande.

La deuxième observation notable c'est que la surface de la zone visitée à la fin de la mission n'a pas pu dépasser le taux de 97% pour l'environnement *Empty Map* et 93.35% pour l'environnement *House Map*, et ceci, même si le niveau d'énergie du robot n'a pas encore atteint 0. Après la visualisation des trajectoires des robots dans le simulateur, nous avons remarqué que ceci est dû au blocage des robots dans un minima local où ils revisitent des régions déjà explorées. Ceci s'explique par le manque de diversification dans les solutions puisque le nombre très réduit de la population a engendré une convergence prématurée vers une solution unique. C'est-à-dire que tous les cinq individus de la population avaient (presque) la même valeur.

Une potentielle solution pour éviter ce problème serait d'augmenter l'espace de recherche graduellement en augmentant la taille de la population lorsque le taux de la surface explorée dépasse un certain seuil (par exemple 80%). En d'autres termes : commencer la recherche en utilisant une taille de population réduite afin d'accélérer le temps de calcul, puis augmenter le nombre d'individus à la fin de la mission pour diversifier la population et échapper aux minimas locaux. Ceci devrait être une meilleure stratégie pour profiter des avantages des deux paramétrages, sans sacrifier la qualité du résultat obtenu à la fin de la mission.

Nous observons également que la méthode xBOA domine toutes les autres méthodes sur les critères du taux d'exploration et de la convergence de la valeur de fitness, mais elle souffre d'un temps d'exécution élevé. De l'autre côté, la méthode CMAES est dominante sur le critère du temps moyen de calcul qui avoisine les 25 secondes, mais elle souffre d'un taux d'exploration inférieur à xBOA de 10%. La méthode ABC est la plus lente de toutes les méthodes, elle nécessite 175 secondes de temps de calcul pour arriver à un résultat presque similaire à celui de xBOA. Tandis que GA offre un bon compromis entre qualité et vitesse d'exécution. La figure 4.12 montre la différence de ces résultats avec ceux obtenus lors de la série d'expériences précédente qui utilisait une taille de population de 20 individus.

Étant donné que la méthode xBOA a pu garder un taux d'exploration supérieur aux
<figure><img src="image_70.png" /></figure>

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

*Les résultats présentent les valeurs moyennes de 3 exécutions*

<caption>FIGURE 4.10 – Comparaison du taux d'exploration et durée de la mission en utilisant la stratégie à court-terme et une population de taille 5</caption>
<figure><img src="image_72.png" /></figure>

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

*Les résultats présentent les valeurs moyennes de 3 exécutions

<caption>FIGURE 4.11 – Comparaison du temps moyen de calcul et convergence de la valeur de fitness en utilisant la stratégie à court-terme et une population de taille 5</caption>
autres méthodes pendant toute la durée de la mission (voir la figure 4.10), et étant donné que les autres méthodes n'ont pu approcher le taux de xBOA que vers la fin de la mission, nous pouvons conclure que cette méthode est la plus robuste d'entre eux face à la réduction de la taille de la population et qu'elle serait plus avantageuse à utiliser dans beaucoup des situations. Par exemple, Si la batterie était limitée, xBOA permettrait d'explorer 10% à 20% plus de surface que les autres métaheuristiques en général.

Une solution alternative serait d'utiliser la méthode GA qui offre un résultat proches de xBOA vers la fin de la mission avec un temps d'exécution similaire à l'algorithme BOA classique.

Toutefois, dans le cas où le temps d'exécution est critique, nous pouvons envisager d'utiliser la méthode CMAES qui donne des résultats très rapides en sacrifiant la qualité des

<table><caption>TABLE 4.4 – Taux d'exploration obtenus à la fin de la mission en utilisant l'algorithme BOA avec une population de taille 5</caption><thead><tr><th colspan="7">Short-term exploration</th></tr><tr><th rowspan="2">Method</th><th colspan="3">Empty map</th><th colspan="3">House map</th></tr><tr><th>Average</th><th>Min</th><th>Max</th><th>Average</th><th>Min</th><th>Max</th></tr></thead><tbody><tr><td>ABC</td><td>97.32</td><td>95.83</td><td>98.61</td><td>90.59</td><td>84.72</td><td>96</td></tr><tr><td>BOA</td><td>96.09</td><td>92.01</td><td>≥99</td><td>87.13</td><td>83.68</td><td>95.13</td></tr><tr><td>CMAES</td><td>94.46</td><td>89.4</td><td>98.61</td><td>82.8</td><td>76.73</td><td>93.22</td></tr><tr><td>GA</td><td>96.09</td><td>87.5</td><td>≥99</td><td>92.36</td><td>89.23</td><td>96</td></tr><tr><td>GWO</td><td>89.61</td><td>84.37</td><td>92.53</td><td>62.03</td><td>60.76</td><td>62.32</td></tr><tr><td>PSO</td><td>93.03</td><td>84.37</td><td>98.26</td><td>74.9</td><td>70.83</td><td>77.6</td></tr><tr><td>xBOA</td><td>96.14</td><td>92.88</td><td>98.26</td><td>93.35</td><td>92.18</td><td>93.92</td></tr></tbody></table>

<figure><img src="image_74.png" /><figcaption>(a) Temps de calcul moyen (en minutes)</figcaption></figure>

<caption>(b) Temps total de la mission (en minutes)</caption>

<caption>FIGURE 4.12 – Impact de la réduction de la taille de population sur le temps de calcul et temps de la mission en utilisant les différentes métaheuristiques</caption>
solutions.

Ces trois méthodes appartiennent au front des solutions non dominées (Pareto-front) et sont donc simultanément optimales. Toutes les autres méthodes sont dominées et appartiennent à la liste des solutions non optimales. La figure 4.13 illustre cette classification.

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

*Toutes les solutions sous la ligne rouge sont dominées*

FIGURE 4.13 – Visualisation du front des solutions dominantes (Pareto-front) pour les différentes métaheuristiques en utilisant une population de taille 5

## 4.8 Expérience 6 : Comparaison de xBOA avec les autres variantes de l’algorithme BOA

Ayant constaté les avantages et les inconvénients de l’algorithme xBOA par rapport aux autres métaheuristiques, nous avons effectué une dernière série d’expériences dont le but est de comparer les performances de cet algorithme face aux autres variantes du BOA citées auparavant dans l’état de l’art (voir section 2.8). Nous avons gardé la même taille de population que la série d’expériences précédente, à savoir 5 papillons.

Selon ce que l'on peut voir sur la figure 4.14 et 4.15 ainsi que le tableau 4.5, la méthode xBOA domine les autres variantes dans le critère du taux d'exploration durant toute la durée de la mission. Elle atteint un résultat supérieur à celui de l'algorithme BOA original de 4.24%. Elle les domine également dans le critère de la convergence de la valeur de fitness.

Cette amélioration est due à l'utilisation de l'opérateur de croisement qui augmente la diversité de la population. En effet, en remplaçant les solutions existantes par de nouvelles solutions, nous encourageons l'algorithme à explorer diverses zones dans l'espace
<table><caption>TABLE 4.5 – Comparatif du taux d'exploration en utilisation les variantes de l'algorithme BOA avec une population de taille 5</caption><thead><tr><th colspan="4">Short-term exploration - House map</th></tr><tr><th>Method</th><th>Average</th><th>Min</th><th>Max</th></tr></thead><tbody><tr><td>BOA</td><td>89.11</td><td>81.77</td><td><strong>95.13</strong></td></tr><tr><td>ABOA</td><td>90.38</td><td>81.77</td><td><strong>95.13</strong></td></tr><tr><td>mBOA</td><td>89.14</td><td>81.07</td><td><strong>95.13</strong></td></tr><tr><td>SABOA</td><td>85.13</td><td>82.98</td><td>85.93</td></tr><tr><td>xBOA</td><td><strong>93.35</strong></td><td><strong>92.18</strong></td><td>93.92</td></tr></tbody></table>

de recherche au lieu d'intensifier la recherche au niveau local. Ceci permet à l'algorithme d'échapper au piège de converger prématurément vers un minima local, ce qui augmente les chances de trouver l'optimum global.

Toutefois, chaque nouvel individu créé doit être évalué, ce qui engendre l'augmentation du nombre d'évaluations de la fonction fitness. Par conséquent, le temps de calcul de l'algorithme augmente aussi. Étant donné que le paramètre de probabilité de croisement était fixé à 0.583, il y a donc 58% plus d'individus à évaluer dans l'algorithme xBOA comparé au BOA classique.

L'algorithme mBOA souffre aussi d'un temps de calcul élevé, ceci est causé par les calculs supplémentaires ajoutés à cette variante dans la phase d'exploitation intensive. Bien que cette nouvelle phase permet d'accélérer la convergence de l'algorithme par rapport à la méthode BOA classique, elle reste tout de même dominée par l'algorithme xBOA que ce soit dans les critères du temps, de la convergence ou du taux d'exploration de la zone.

ABOA domine les autres variantes dans le critère du temps d'exécution, mais n'est pas parvenue à dépasser à un taux d'exploration de 90.38%, alors que xBOA a pu atteindre un résultat supérieur. Quant à l'algorithme SABOA, il a donné le résultat le moins performant avec un taux d'exploration de 85.13%, mais possède néanmoins l'avantage de n'avoir qu'un seul hyperparamètre en entrée, ce qui réduit la complexité du paramétrage.

Les deux solutions dominantes sont donc :

- ABOA : qui possède le meilleur temps de calcul ; et

- xBOA : qui obtient le meilleur taux d'exploration.

Il faut donc considérer le choix d'un bon compris entre la maximisation de la surface explorée et le temps de calcul nécessaire. Ce choix dépendra de la nature de la mission : dans un contexte d'une mission de sauvetage par exemple, le facteur « temps » est très important, ce qui rend envisageable la décision de privilégier la réduction de la durée d'exécution au profit de la qualité d'exploration. En revanche, dans un contexte de déminage, de nettoyage ou de surveillance, il serait judicieux de privilégier la maximisation de la zone explorée au dépourvu du temps de calcul, jusqu'à une certaine mesure.
<figure><img src="image_76.png" /></figure>

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

*Les résultats présentent les valeurs moyennes de 10 exécutions

<caption>FIGURE 4.14 – Comparaison des variantes de l’algorithme BOA en utilisant la stratégie à court terme et une population de taille 5</caption>
<figure><img src="image_78.png" /></figure>

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

<caption>FIGURE 4.15 – Suite de la comparaison des variantes de l’algorithme BOA en utilisant la stratégie à court terme et une population de taille 5</caption>

<footnote>*Les résultats présentent les valeurs moyennes de 10 exécutions</footnote>
Un autre facteur a prendre en considération aussi est la stabilité des résultats. En effet, après avoir répété l'expérience 10 fois, le xBOA a enregistré un taux de stabilité élevé avec un résultat presque similaire à chaque exécution (~1 à 2% d'écart). Alors que l'algorithme ABOA vacillait dans une marge de 15% de différence entre les résultats.

<figure><img src="image_80.png" /><figcaption>FIGURE 4.16 – Visualisation du front des solutions dominante (Pareto-front) pour les variantes de BOA en utilisant une population de taille 5</figcaption></figure>

## 4.9 Expérience 7 : Test en utilisant un robot réel

Afin de valider l'adaptabilité de notre approche aux expériences du monde réel, nous avons effectué des tests sur le robot P3DX du laboratoire LARESI situé dans le département d'électronique de USTOMB. Pour cela, nous avons séparé le système en deux parties. D'un côté, un ordinateur portable connecté au réseau local du laboratoire via une connexion wifi joue le rôle de serveur. Il exécute le processus d'optimisation pour générer le prochain point de destination à visiter ainsi que l'algorithme de planification de chemin pour calculer les positions intermédiaires, qui sont ensuite transformées en un ensemble de commandes de mouvements puis envoyées au robot via une socket TCP.

Une fois que le robot reçoit une commande de mouvement (move, turn, stop), il la transforme en une commande de vitesse pour le contrôle des moteurs en utilisant les routines du système ROS (Robot Operating System), celui-ci communiquera directement avec le microcontrôleur du robot via l'interface ROSARIA pour exécuter les commandes. En parallèle à cela, un autre programme basé sur ROS s'occupe de collecter les informations mesurées par le Lidar à une fréquence de 10Hz puis les envoyer au serveur pour mettre à jour la carte de l'environnement.
Un problème rencontré durant les expériences était l'accumulation de l'erreur de localisation causée par le glissement du robot sur le sol. En effet, notre simulateur supposait que la localisation du robot était connue à chaque instant *t*, toutefois, dans le monde réel ceci ne pouvait se faire sans l'intégration d'un dispositif électronique de positionnement. La méthode que nous avons utilisée sur le robot P3DX se base sur l'odométrie, qui est une technique peu chère se basant sur le calcul du nombre de rotations des roues pour estimer la distance parcourue par le robot et son angle. Cependant, nous avons remarqué des mini-glissements du robot à la fin de chaque mouvement qui le fait dévier de 1 ou 2 centimètres de sa trajectoire. Bien que cette déviation n'est pas importante, son accumulation après plusieurs mouvements s'accroît et engendre une localisation erronée.

Afin de résoudre ce problème sans avoir besoin d'utiliser des dispositifs de localisation plus complexes, nous avons intégré un mécanisme de contrôle en boucle fermée (contrôleur PID) pour réduire la vitesse de rotation des roues lorsque le robot se rapproche de l'emplacement prévu, avec une possibilité de revenir légèrement en arrière pour corriger sa position si nécessaire.

Les codes sources de ce contrôleur PID basé sur le système ROS ainsi que le programme pour le contrôle du robot en utilisant les commandes distantes par TCP sont disponible en open source sur le lien cité en bas de page <fnref n="1" />. La figure 4.17 montre des photos prises durant les expériences dans le laboratoire.

Dans les travaux futurs, nous allons optimiser le système en intégrant directement les calculs des points de destination et de la planification de trajectoires dans l'ordinateur de bord du robot, et ceci afin qu'il puisse être autonome et continuer sa mission même si la connexion avec le serveur est interrompue. Étant donné les faibles capacités de calcul de cet ordinateur de bord, il serait judicieux de profiter des résultats obtenus durant l'expérience

<figure><img src="image_81.png" /><figcaption>FIGURE 4.17 – Expérience sur le robot réel</figcaption></figure>

<footnote n="1">1. https://github.com/amineHorseman/pioneer_bci</footnote>
précédente par rapport à la réduction de la taille de population afin d'alléger les calculs.
L'utilisation du xBOA dans ce contexte serait donc appropriée étant donné ses capacités
de diversification des solutions dans les populations à petite taille, ainsi que sa stabilité à
atteindre un taux d'exploration élevé lors de chaque exécution.

## 4.10 Conclusion

Nous avons présenté dans ce chapitre une série d'expériences effectuées dans le but d'évaluer les performances de l'algorithmme xBOA. Nous l'avons comparé à plusieurs autres métaheuristiques, ainsi que les autres variantes de BOA récemment introduites dans la littérature.

L'évaluation des méthodes s'est basée sur 5 critères de comparaison. Les résultats montrèrent que l'algorithmme xBOA surpasse BOA et ses autres variantes, mais requiert un temps de calcul élevé. L'algorithmme proposé surpasse aussi les autres métaheuristiques telles que PSO, GA, GWO et ABC dans certains scénarios.

Nous avons aussi effectué une expérience pour évaluer l'adaptabilité de notre approche dans un contexte multirobots. Les résultats nous ont permis de valider notre modélisation du mécanisme de synchronisation implicite et observer l'émergence d'un comportement collectif au sein des robots leur permettant de se disperser dans l'environnement et minimiser la redondance même pour des zones à large échelle. Nous avons également effectué une expérience sur un robot réel de type P3DX au sein du laboratoire LARESI basé sur le middleware ROS et une communication avec le serveur via une connexion wifi en utilisant des sockets TCP.

Les résultats obtenus durant ces expériences ont été satisfaisants sur certains critères, mais ont démontré aussi les limites de l'algorithmme xBOA. Nous présenterons dans la conclusion générale quelques perspectives d'amélioration de cette méthode.
CONCLUSION GÉNÉRALE ET PERSPECTIVES

Nous avons présenté dans cette thèse nos travaux sur l'optimisation du comportement collectif d'un groupe de robots autonomes en utilisant les métaheuristiques.

Ce travail était divisé en deux parties principales. La première était consacrée à l'étude des fondements théoriques des systèmes multirobots et des métaheuristiques pour l'optimisation globale. Tandis que la deuxième présentait notre modélisation du problème d'exploitation de zones inconnues avec des contraintes d'énergie, ainsi que la série d'expériences réalisées pour la valider.

Cette thèse a introduit deux contributions principales. D'un côté le développement d'une nouvelle plateforme de simulation appelée PyRoboticsLab pour l'évaluation et le benchmarking d'algorithmes dédiés à la résolution des problèmes de navigation robotique, planification de trajectoires, exploration et surveillance. Et de l'autre côté l'introduction d'un nouvel algorithme xBOA que nous avons proposé comme nouvelle variante de la métaheuristique BOA.

Nous avons utilisé notre plateforme de benchmarking afin de comparer les performances de notre nouvel algorithme à plusieurs autres métaheuristiques utilisées dans la littérature. L'évaluation des méthodes s'est basée sur cinq critères de comparaison. Les résultats ont montré que l'algorithme xBOA surpasse BOA et ses autres variantes, mais requiert un temps de calcul plus long. L'algorithme proposé surpasse aussi les autres métaheuristiques telles que PSO, GA, GWO et ABC dans certains scénarios.

Nous avons procédé aussi à une série d'expériences pour évaluer l'adaptabilité de notre approche dans un contexte multirobots, et optimiser la coordination entre les robots en introduisant des mécanismes d'échange d'informations pour permettre aux robots de se disperser efficacement et minimiser la redondance.

D'autres améliorations d'ordre programmatique ont aussi été introduites telles que l'utilisation du parallélisme dans le processus d'évolution pour permettre d'évaluer plusieurs individus en même temps et accélérer le temps global de calcul des points de destinations.

Nous avons également effectué une expérience réelle sur un robot de type P3DX dont le
but était de vérifier le bon fonctionnement des outils proposés. Cette expérience nous a per-
mis de détecter et résoudre les problèmes de localisation basée sur l'odométrie et d'adapter
notre approche au middleware ROS.

Dans les travaux futurs, nous nous consacrerons à améliorer la plateforme de simula-
tion afin d'y intégrer plus d'algorithmes, et ce afin d'offrir aux chercheurs de ce domaine
une suite complète de benchmarking et un outil uniformisé pour positionner leurs travaux.
L'outil pourra aussi intégrer plus de scénarios et des environnements variés avec l'intégra-
tion d'obstacles dynamiques.

Le simulateur pourra aussi être utilisé à des fins pédagogiques afin de faire découvrir
aux étudiants en informatique le domaine de l'intelligence artificielle appliquée aux pro-
blématiques de la robotique collective, sans qu'ils aient à se soucier des détails théoriques
relatifs à la modélisation des capteurs laser, ou du calcul des probabilités d'occupation.

Du côté de l'algorithme xBOA, nous projetons de le tester sur d'autres types de problé-
matiques d'optimisation combinatoire. Nous pourrons considérer la piste d'améliorer cet
algorithme en introduisant un mécanisme plus adaptatif pour équilibrer les phases d'ex-
ploration et d'exploitation, ou de tester différents opérateurs de croisement pour analyser
leur effet sur la convergence de l'algorithme.
BIBLIOGRAPHIE

[1] Nur Aira ABD RAHMAN et al. « A coverage path planning approach for autonomous radiation mapping with a mobile robot ». In : *International Journal of Advanced Robotic Systems* 19.4 (2022), p. 17298806221116483.

[2] Laith ABUALIGAH et al. « Reptile Search Algorithm (RSA): A nature-inspired metaheuristic optimizer ». In : *Expert Systems with Applications* 191 (2022), p. 116158.

[3] Laith ABUALIGAH et al. « The arithmetic optimization algorithm ». In : *Computer methods in applied mechanics and engineering* 376 (2021), p. 113609.

[4] Afsoon AFZAL et al. « A study on the challenges of using robotics simulators for testing ». In : *arXiv preprint arXiv:2004.07368* (2020).

[5] Jeffrey O AGUSHAKA, Absalom E EZUGWU et Laith ABUALIGAH. « Dwarf mongoose optimization algorithm ». In : *Computer methods in applied mechanics and engineering* 391 (2022), p. 114570.

[6] Somaye AHMADI, H. KEBRIAEI et Hadi MORADI. « Constrained coverage path planning: evolutionary and classical approaches ». In : *Robotica* 36 (fév. 2018), p. 1-21.
DOI: 10.1017/S0263574718000139.

[7] Mohammad AL KHAWALDAH et Andreas NUCHTER. « Enhanced frontier-based exploration for indoor environment with multiple robots ». In : *Advanced Robotics* 29 (avr. 2015). DOI: 10.1080/01691864.2015.1015443.

[8] Sankalap ARORA et Priyanka ANAND. « Binary butterfly optimization approaches for feature selection ». In : *Expert Systems with Applications* 116 (2019), p. 147-160.

[9] Sankalap ARORA et Satvir SINGH. « An improved butterfly optimization algorithm for global optimization ». In : *Advanced Science, Engineering and Medicine* 8.9 (2016), p. 711-717.

[10] Sankalap ARORA et Satvir SINGH. « Butterfly algorithm with levy flights for global optimization ». In : 2015 *International conference on signal processing, computing and control (ISPCC)*. IEEE. 2015, p. 220-224.

[11] Sankalap ARORA et Satvir SINGH. « Butterfly optimization algorithm: a novel approach for global optimization ». In : *Soft Computing* 23.3 (2019), p. 715-734.

[12] Sankalap ARORA, Satvir SINGH et Kaan YETILMEZSOY. « A modified butterfly optimization algorithm for mechanical design optimization problems ». In : *Journal of the Brazilian Society of Mechanical Sciences and Engineering* 40.1 (2018), p. 1-17.

[13] Adel Saad ASSIRI. « On the performance improvement of Butterfly Optimization approaches for global optimization and Feature Selection ». In : *Plos one* 16.1 (2021), e0242612.

[14] Mahdi AZIZI. « Atomic orbital search: A novel metaheuristic algorithm ». In : *Applied Mathematical Modelling* 93 (2021), p. 657-683.

[15] Antoine BAUTIN, Olivier SIMONIN et François CHARPILLET. « MinPos : A Novel Frontier Allocation Algorithm for Multi-robot Exploration ». In : oct. 2012, p. 496-508.
ISBN : 978-3-642-33514-3. DOI : 10.1007/978-3-642-33515-0_49.
[16] Amine BENDAHMANE et Redouane TLEMSANI. « Unknown area exploration for robots with energy constraints using a modified Butterfly Optimization Algorithm ». In : *Soft Computing* 27 (2023), p. 3785-3804. doi : 10.1007/s00500-022-07530-w.

[17] James BERGSTRA et Yoshua BENGIO. « Random search for hyper-parameter optimization. » In : *Journal of machine learning research* 13.2 (2012).

[18] James BERGSTRA, Dan YAMINS, David D COX et al. « Hyperopt: A python library for optimizing the hyperparameters of machine learning algorithms ». In : *Proceedings of the 12th Python in science conference*. T. 13. Citeseer. 2013, p. 20.

[19] Francesco BISCANI et Dario IZZO. « A parallel global multiobjective framework for optimization: pagmo ». In : *Journal of Open Source Software* 5.53 (2020), p. 2338. doi : 10.21105/joss.02338.

[20] Johann BORENSTEIN, Yoram KOREN et al. « The vector field histogram-fast obstacle avoidance for mobile robots ». In : *IEEE transactions on robotics and automation* 7.3 (1991), p. 278-288.

[21] Ersin BÜYÜK. « Pareto-based multiobjective particle swarm optimization: examples in geophysical modeling ». In : *Optimisation Algorithms and Swarm Intelligence*. In-techOpen, 2021.

[22] Byoung-Suk CHOI et al. « A hierarchical algorithm for indoor mobile robot localization using RFID sensor fusion ». In : *IEEE Transactions on industrial electronics* 58.6 (2011), p. 2226-2235.

[23] Howie CHOSET et Philippe PIGNON. « Coverage path planning: The boustrophedon cellular decomposition ». In : *Field and service robotics*. Springer. 1998, p. 203-209.

[24] Alberto COLORNI, Marco DORIGO, Vittorio MANIEZZO et al. « Distributed optimization by ant colonies ». In : *Proceedings of the first European conference on artificial life*. T. 142. Paris, France. 1991, p. 134-142.

[25] Michael Lynn CRAMER. « A representation for the Adaptive Generation of Simple Sequential Programs ». In : *Proceedings of an International Conference on Genetic Algorithms and the Applications*. Sous la dir. de John J. GREFENSTETTE. Carnegie-Mellon University, Pittsburgh, USA, juin 1985, p. 183-187.

[26] Marija DAKULOVIĆ, Sanja HORVATIĆ et Ivan PETROVIĆ. « Complete Coverage D\* Algorithm for Path Planning of a Floor-Cleaning Mobile Robot ». In : *IFAC Proceedings Volumes* 44.1 (2011). 18th IFAC World Congress, p. 5950-5955. ISSN : 1474-6670. DOI : https://doi.org/10.3182/20110828-6-IT-1002.03400.

[27] Andrew DAVENPORT et al. « GENET: A connectionist architecture for solving constraint satisfaction problems by iterative improvement ». In : *AAAI*. 1994, p. 325-330.

[28] Susana Estefany DE LEÓN-ALDACO, Hugo CALLEJA et Jesús Aguayo ALQUICIRA. « Metaheuristic optimization methods applied to power converters: A review ». In : *IEEE Transactions on Power Electronics* 30.12 (2015), p. 6791-6803.

[29] Sihao DENG et al. « Application of external axis in robot-assisted thermal spraying ». In : *Journal of thermal spray technology* 21 (2012), p. 1203-1215.
[30] Berat DOĞAN et Tamer ÖLMEZ. « A new metaheuristic for numerical function optimization: Vortex Search algorithm ». In : *Information sciences* 293 (2015), p. 125-145.

[31] Alexey DOSOVITSKIY et al. « CARLA: An open urban driving simulator ». In : *Conference on robot learning*. PMLR. 2017, p. 1-16.

[32] Akif DURDU et al. « Convolutional Neural Networks Based Active SLAM and Exploration ». In : *Avrupa Bilim ve Teknoloji Dergisi* 22 (2021), p. 342-346.

[33] Hugh DURRANT-WHYTE et al. « Field and service applications-an autonomous straddle carrier for movement of shipping containers-from research to operational autonomous systems ». In : *IEEE Robotics & Automation Magazine* 14.3 (2007), p. 14-23.

[34] Alberto ELFES. « Using occupancy grids for mobile robot perception and navigation ». In : *Computer* 22.6 (1989), p. 46-57.

[35] Yuqi FAN et al. « A self-adaption butterfly optimization algorithm for numerical optimization problems ». In : *IEEE Access* 8 (2020), p. 88026-88041.

[36] J.D. FARMER, N. PACKARD et A. PERELSON. « The immune system, adaptation and machine learning ». In : *Physica D* 2 (1986), 187-204.

[37] Diego FERIGO et al. « Gym-ignition: Reproducible robotic simulations for reinforcement learning ». In : *2020 IEEE/SICE International Symposium on System Integration (SII)*. IEEE. 2020, p. 885-890.

[38] Simon FONG, Suash DEB et Ankit CHAUDHARY. « A review of metaheuristics in robotics ». In : *Computers & Electrical Engineering* 43 (2015), p. 278-291.

[39] Miguel GARCÍA et al. « Voronoi-Based Space Partitioning for Coordinated Multi-Robot Exploration ». In : *JoPha: Journal of Physical Agents*, ISSN 1888-0258, Vol. 1, N°. 1, 2007, pags. 37-44 1 (jan. 2007). DOI: 10.14198/JoPha.2007.1.1.05.

[40] Fred GLOVER. « Future paths for integer programming and links to artificial intelligence ». In : *Computers & operations research* 13.5 (1986), p. 533-549.

[41] David E. GOLDBERG. *Genetic Algorithms in Search, Optimization, and Machine Learning*. New York : Addison-Wesley, 1989.

[42] Nir GRESHLER et al. « Cooperative multi-agent path finding: beyond path planning and collision avoidance ». In : *2021 International Symposium on Multi-Robot and Multi-Agent Systems (MRS)*. IEEE. 2021, p. 20-28.

[43] Faiza GUL, Suleman MIR et Imran MIR. « Coordinated multi-robot exploration: Hybrid stochastic optimization approach ». In : *AIAA SCITECH 2022 Forum*. 2022, p. 1414.

[44] Yanju GUO, Xianjie LIU et Lei CHEN. « Improved butterfly optimisation algorithm based on guiding weight and population restart ». In : *Journal of Experimental & Theoretical Artificial Intelligence* 33.1 (2021), p. 127-145.

[45] Nikolaus HANSEN, Sibylle MÜLLER et Petros KOUMOUTSAKOS. « Reducing the Time Complexity of the Derandomized Evolution Strategy with Covariance Matrix Adaptation (CMA-ES) ». In : *Evolutionary computation* 11 (fév. 2003), p. 1-18. DOI: 10.1162/106365603321828970.

[46] Peter E. HART, Nils J. NILSSON et Bertram RAPHAEL. « A Formal Basis for the Heuristic Determination of Minimum Cost Paths ». In : *IEEE Transactions on Systems Science and Cybernetics* 4.2 (1968), p. 100-107. DOI: 10.1109/TSSC.1968.300136.
[47] Dirk HOLZ et al. « Evaluating the Efficiency of Frontier-based Exploration Strategies ». In : t. 1. Juill. 2010, p. 1 -8.

[48] Erno HORVATH, Claudiu POZNA et Radu-Emil PRECUP. « Robot coverage path planning based on iterative structured orientation ». In : *Acta Polytechnica Hungarica* 15.2 (2018), p. 231-249.

[49] Luca IOCCHI, Luca MARCHETTI et Daniele NARDI. « Multi-robot patrolling with coordinated behaviours in realistic environments ». In : *2011 IEEE/RSJ International Conference on Intelligent Robots and Systems*. IEEE. 2011, p. 2796-2801.

[50] Nick JAKOBI, Phil HUSBANDS et Inman HARVEY. « Noise and the reality gap: The use of simulation in evolutionary robotics ». In : *Advances in Artificial Life: Third European Conference on Artificial Life Granada, Spain, June 4-6, 1995 Proceedings* 3. Springer. 1995, p. 704-720.

[51] Seyed Mohammad Jafar JALALI et al. « Evolving artificial neural networks using butterfly optimization algorithm for data classification ». In : *International conference on neural information processing*. Springer. 2019, p. 596-607.

[52] Albina KAMALOVA, Ki Dong KIM et Suk Gyu LEE. « Waypoint Mobile Robot Exploration Based on Biologically Inspired Algorithms ». In : *IEEE Access* 8 (2020), p. 190342-190355.

[53] Albina KAMALOVA et al. « Multi-Robot Exploration Based on Multi-Objective Grey Wolf Optimizer ». In : *Applied Sciences* 9 (juill. 2019), p. 2931. DOI: 10.3390/app9142931.

[54] Pierre KANCIR. « Méthodologie de conception de système multi-robots: De la simulation à la démonstration ». Thèse de doct. Université de Bretagne Sud, 2018.

[55] Dervis KARABOGA. « An Idea Based on Honey Bee Swarm for Numerical Optimization, Technical Report - TR06 ». In : *Technical Report, Erciyes University* (jan. 2005).

[56] Géza KATONA, Balázs LÉNÁRT et János JUHÁSZ. « Parallel ant colony algorithm for shortest path problem ». In : *Periodica Polytechnica Civil Engineering* 63.1 (2019), p. 243-254.

[57] Ali KAVEH et Taha BAKHSHPOORI. « Metaheuristics: outlines, MATLAB codes and examples ». In : (2019).

[58] J. KENNEDY et R. EBERHART. « Particle swarm optimization ». In : *Proceedings of ICNN'95 - International Conference on Neural Networks*. T. 4. 1995, 1942-1948 vol.4. DOI: 10.1109/ICNN.1995.488968.

[59] Scott KIRKPATRICK, C Daniel GELATT JR et Mario P VECCHI. « Optimization by simulated annealing ». In : *science* 220.4598 (1983), p. 671-680.

[60] Nathan KOENIG et Andrew HOWARD. « Design and use paradigms for gazebo, an open-source multi-robot simulator ». In : *2004 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS) (IEEE Cat. No. 04CH37566)*. T. 3. IEEE. 2004, p. 2149-2154.

[61] Guocheng LI et al. « An improved butterfly optimization algorithm for engineering design problems using the cross-entropy method ». In : *Symmetry* 11.8 (2019), p. 1049.
[62] Matteo LUPERTO et al. « Robot exploration of indoor environments using incomplete and inaccurate prior knowledge ». In : Robotics and Autonomous Systems 133 (2020), p. 103622.

[63] Ellips MASEHIAN et MR AMIN-NASERI. « A voronoi diagram-visibility graph-potential field compound algorithm for robot path planning ». In : Journal of Robotic Systems 21.6 (2004), p. 275-300.

[64] Ashkan MEMARI, Robiah AHMAD et Abd Rahman Abdul RAHIM. « Metaheuristic algorithms: guidelines for implementation ». In : Journal of Soft Computing and Decision Support Systems 4.6 (2017), p. 1-6.

[65] PE MERGOS et Anastasios SEXTOS. Multi-objective optimum selection of ground motion records with genetic algorithms. IEEE, juin 2018.

[66] Seyedali MIRJALILI, Seyed Mohammad MIRJALILI et Andrew LEWIS. « Grey Wolf Optimizer ». In : Advances in Engineering Software 69 (2014), p. 46-61. ISSN : 0965-9978. DOI : https://doi.org/10.1016/j.advengsoft.2013.12.007.

[67] Himanshu MITTAL et al. « Gravitational search algorithm: A comprehensive analysis of recent variants ». In : Multimedia Tools and Applications 80 (2021), p. 7581-7608.

[68] Sing Yee NG et Nur Syazreen AHMAD. « A Bug-Inspired Algorithm for Obstacle Avoidance of a Nonholonomic Wheeled Mobile Robot with Constraints ». In : Intelligent Computing. Sous la dir. de Kohei ARAI, Rahul BHATIA et Supriya KAPOOR. Cham : Springer International Publishing, 2019, p. 1235-1246.

[69] G PAVAI et TV GEETHA. « A survey on crossover operators ». In : ACM Computing Surveys (CSUR) 49.4 (2016), p. 1-43.

[70] Hindriyanto Dwi PURNOMO et Hui-Ming WEE. « Soccer game optimization with substitute players ». In : Journal of computational and applied mathematics 283 (2015), p. 79-90.

[71] Esmat RASHEDI, Hossein NEZAMABADI-POUR et Saeid SARYAZDI. « GSA: a gravitational search algorithm ». In : Information sciences 179.13 (2009), p. 2232-2248.

[72] Eric ROHMER, Surya PN SINGH et Marc FREESE. « V-REP: A versatile and scalable robot simulation framework ». In : 2013 IEEE/RSJ international conference on intelligent robots and systems. IEEE. 2013, p. 1321-1326.

[73] Ali El ROMEH et Seyedali MIRJALILI. « Multi-Robot Exploration of Unknown Space Using Combined Meta-Heuristic Salp Swarm Algorithm and Deterministic Coordinated Multi-Robot Exploration ». In : Sensors 23.4 (2023), p. 2156.

[74] Sajad SAEEDI et al. « Occupancy grid map merging for multiple robot simultaneous localization and mapping ». In : International Journal of Robotics and Automation 30.2 (2015), p. 149-157.

[75] Jeffrey R SAMPSON. Adaptation in natural and artificial systems (John H. Holland). 1976.

[76] Sushmita SHARMA et al. « MPBOA-A novel hybrid butterfly optimization algorithm with symbiosis organisms search for global optimization and image segmentation ». In : Multimedia Tools and Applications 80.8 (2021), p. 12035-12076.
[77] Zongyuan SHEN, James P. WILSON et Shalabh GUPTA. « $\epsilon^*+$: An Online Coverage Path Planning Algorithm for Energy-constrained Autonomous Vehicles ». In: *Global Oceans 2020: Singapore – U.S. Gulf Coast*. 2020, p. 1-6. DOI: 10.1109/IEEECONF38699.2020.9389353*.

[78] Rakesh SHRESTHA et al. « Learned map prediction for enhanced mobile robot exploration ». In: *2019 International Conference on Robotics and Automation (ICRA)*. IEEE. 2019, p. 1197-1204.

[79] Junnan SONG et Shalabh GUPTA. « $\epsilon^*$: An Online Coverage Path Planning Algorithm ». In: *IEEE Transactions on Robotics* 34 (fév. 2018), p. 526-533. DOI: 10.1109/TRO.2017.2780259*.

[80] Rainer STORN et Kenneth PRICE. « Differential evolution-a simple and efficient heuristic for global optimization over continuous spaces ». In: *Journal of global optimization* 11.4 (1997), p. 341.

[81] Daniel Perea STRÖM, Igor BOGOSLAVSKYI et Cyrill STACHNISS. « Robust exploration and homing for autonomous robots ». In: *Robotics and Autonomous Systems* 90 (2017), p. 125-135.

[82] Lei TAI et Ming LIU. « A robot exploration strategy based on q-learning network ». In: *2016 IEEE international conference on real-time computing and robotics (RCAR)*. IEEE. 2016, p. 57-62.

[83] Mohammad TUBISHAT et al. « Dynamic butterfly optimization algorithm for feature selection ». In: *IEEE Access* 8 (2020), p. 194303-194314.

[84] Zhongmin WANG, Qifang LUO et Yongquan ZHOU. « Hybrid metaheuristic algorithm using butterfly and flower pollination base on mutualism mechanism for global optimization problems ». In: *Engineering with Computers* 37.4 (2021), p. 3665-3698.

[85] David H WOLPERT et William G MACREADY. « No free lunch theorems for optimization ». In: *IEEE transactions on evolutionary computation* 1.1 (1997), p. 67-82.

[86] Benjie XIAO et al. « Ant colony optimisation algorithm-based multi-robot exploration ». In: *International Journal of Modelling, Identification and Control* 18.1 (2013), p. 41-46.

[87] Lei XIE et al. « Tuna swarm optimization: a novel swarm-based metaheuristic algorithm for global optimization ». In: *Computational intelligence and Neuroscience* 2021 (2021).

[88] Anupam YADAV et al. « AEFA: Artificial electric field algorithm for global optimization ». In: *Swarm and Evolutionary Computation* 48 (2019), p. 93-108.

[89] Brian 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. DOI: 10.1109/CIRA.1997.613851*.

[90] Brian YAMAUCHI. « Frontier-based exploration using multiple robots ». In: *Jan. 1998*, p. 47-53. ISBN: 0-89791-983-1. DOI: 10.1145/280765.280773*.

[91] Xin-She YANG. « A new metaheuristic bat-inspired algorithm ». In: *Nature inspired cooperative strategies for optimization (NICSO 2010)* (2010), p. 65-74.
[92] Xin-She YANG. « Flower pollination algorithm for global optimization ». In : *International conference on unconventional computing and natural computation*. Springer. 2012, p. 240-249.

[93] Xin-She YANG. *Nature-inspired metaheuristic algorithms*. Luniver press, 2010.

[94] Zuozhong YIN et al. « A Delivery robot cloud platform based on microservice ». In : *Journal of Robotics* 2021 (2021), p. 1-10.

[95] Chao Yu et al. « Asynchronous Multi-Agent Reinforcement Learning for Efficient Real-Time Multi-Robot Cooperative Exploration ». In : *arXiv preprint arXiv:2301.03398* (2023).

[96] Mengjian ZHANG et al. « A Chaotic Hybrid Butterfly Optimization Algorithm with Particle Swarm Optimization for High-Dimensional Optimization Problems ». In : *Symmetry* 12.11 (2020), p. 1800.

[97] Xiangyang ZHI, Xuming HE et Sören SCHWERTFEGER. « Learning autonomous exploration and mapping with semantic vision ». In : *Proceedings of the 2019 International Conference on Image, Video and Signal Processing*. 2019, p. 8-15.

[98] Yi ZHOU et al. « A PSO-inspired Multi-Robot Map Exploration Algorithm Using Frontier-Based Strategy ». In : *International Journal of System Dynamics Applications*, 2 (avr. 2013), p. 1-13. DOI: 10.4018/ijsda.2013040101.

[99] Mohammad ZOUNEMAT-KERMANI, Amin MAHDAVI-MEYMAND et Reinhard HINKELMANN. « Nature-inspired algorithms in sanitary engineering: modelling sediment transport in sewer pipes ». In : *Soft Computing* 25.8 (2021), p. 6373-6390.