Contribution à l'optimisation d'un comportement collectif pour un groupe de robots autonomes

ÉíÈÚÔáÇ ÉíØÇÑÞíãáÏÇ ÉíÑÆÇÒáÌÇ ÉíÑæåáÌãÇ íãáÚáÇ ËÍÈáÇ æ áíÇÚáÇ íãáÚÊáÇ ÉÑÇÒæ ÇíÖæÈ ÏãÍã ÇíÌæáæäßÊáÇ æ ãæáÚáá äÇÑåæ ÉÚãÇÌ

Présentée par : Amine BENDAHMANE

Intitulé

Contribution à l'Optimisation d'un Comportement Collectif pour un Groupe de Robots Autonomes

Faculté : Faculté des Mathématiques et Informatique

Département : Informatique

Domaine :Informatique

Filière : Informatique

Intitulé de la Formation : Reconnaissance Des Formes Et Intelligence Artificielle

Devant le Jury Composé de :
Membres de Jury	Grade	Qualité	Domiciliation
CHOURAQUI Samira	Pr	Présidente	USTO-MB
TLEMSANI Redouane	MCA	Encadreur	USTO-MB
ADJOUDJ Réda	Pr	Examinateur	U-SBA
BOUKLI HACENE Sofiane	Pr	Examinateur	U-SBA
YEDJOUR Dounia	MCA	Examinatrice	USTO-MB

Année Universitaire : 2022/2023

2023

République Algérienne Démocratique et Populaire
Ministère de l'Enseignement Supérieur et de la Recherche Scientifique
Université des Sciences et de la Technologie d'Oran Mohamed Boudiaf
Faculté des Mathématiques et Informatique
Laboratoire Signal-Image-Parole (SIMPA)

Contribution à l'Optimisation d'un Comportement
Collectif pour un Groupe de Robots Autonomes

Thèse en vue de l'obtention de diplôme de
doctorat en INFoRMATIQUE

Présentée par AMINE BENDAHMANE

Devant le jury composé de

CHOURAQUI SAMIRA	PR.	Présidente	USTOMB
TLEMSANI REDoUANE	MCA	Directeur de thèse	USTOMB
ADJOUDJ RÉDA	PR.	Examinateur	U-SBA
BOUKLI HACENE SoFIANE	PR.	Examinateur	U-SBA
YEDJOUR DoUNIA	MCA	Examinateur	USTOMB

2

A ma famille, ma femme

et mes amis.

3

REMERCIEMENTS

Je tiens à remercier mes deux directeurs de thèse, le Pr. BENYETTOU Abdelkader et le Dr. TLEMSANI Redouane, pour leurs conseils inestimables et pour avoir accepté d'encadrer ce travail dont j'espère qu'il sera à la hauteur de leurs espérances.

Je remercie également Mme la présidente du jury, Pr. CHOURAQUI Samira, pour sa disponibilité, ainsi que l'ensemble des membres du jury, à savoir : le Pr. ADJOUDJ Réda, Pr. BOUKLI HACENE Sofiane et Dr. YEDJOUR Dounia, pour avoir accepté de donner de leurs temps pour examiner ce travail.

Je remercie le Pr. BERACHED Nasreddine pour m'avoir toujours ouvert son laboratoire et m'avoir permis de faire des expériences sur des robots réels sans poser de conditions.

Je remercie aussi l'ensemble de mes enseignants qui m'ont appris la méthodologie scientifique et les connaissances techniques requises pour aboutir à ce travail, dont j'espère qu'il sera à la hauteur de leurs espérances. Sans oublier le personnel administratif de la faculté ainsi que le service de poste-graduation.

Pour finir, je remercie tous ceux qui ont contribué de près ou de loin pour la réalisation de ce travail. Notamment ma famille qui m'a accompagné tout au long de la réalisation de travail, ainsi que mes amis et mes collègues.

4

RéSUMé

Cette thèse étudie le domaine de la robotique collective, et plus particulièrement les problèmes d'optimisation des systèmes multirobots dans le cadre de l'exploration, de la planification de trajectoires et de la coordination. Elle inclut deux contributions. La première est l'utilisation de l'algorithme d'optimisation des papillon (BOA : Butterfly Optimization Algorithm) pour résoudre le problème d'exploration de zone inconnue avec des contraintes d'énergie dans des environnements dynamiques. A notre connaissance, cet algorithme n'a jamais été utilisé pour résoudre des problèmes de robotique auparavant. Nous avons également proposé une nouvelle version de cet algorithme appelée xBOA basée sur l'opérateur de croisement pour améliorer la diversité des solutions candidates et accélérer la convergence de l'algorithme. La deuxième contribution présenté dans cette thèse est le développement d'une nouvelle plateforme de simulation pour l'analyse comparative de problèmes incrémentaux en robotique tels que les tâches d'exploration. La plateforme est conçue de manière à être générique pour comparer rapidement différentes métaheuristiques avec un minimum de modifications, et pour s'adapter facilement aux scénarios mono et multirobots. De plus, elle offre aux chercheurs des outils pour automatiser leurs expériences et générer des visuels, ce qui leur permettra de se concentrer sur des tâches plus importantes telles que la modélisation de nouveaux algorithmes. Nous avons mené une série d'expériences qui ont montré des résultats prometteurs et nous ont permis de valider notre approche et notre modélisation.

Mots clés :

Systèmes multirobots, comportements intelligents, métaheuristiques, exploration robotique, benchmarking, Butterfly Optimization Algorithm, xBOA

5

ABSTRACT

This thesis studies the domain of collective robotics, and more particularly the optimization problems of multirobot systems in the context of exploration, path planning and coordination. It includes two contributions. The first one is the use of the Butterfly Optimization Algorithm (BOA) to solve the Unknown Area Exploration problem with energy constraints in dynamic environments. This algorithm was never used for solving robotics problems before, as far as we know. We proposed a new version of this algorithm called xBOA based on the crossover operator to improve the diversity of the candidate solutions and speed up the convergence of the algorithm. The second contribution is the development of a new simulation framework for benchmarking dynamic incremental problems in robotics such as exploration tasks. The framework is made in such a manner to be generic to quickly compare different metaheuristics with minimum modifications, and to adapt easily to single and multi-robot scenarios. Also, it provides researchers with tools to automate their experiments and generate visuals, which will allow them to focus on more important tasks such as modeling new algorithms. We conducted a series of experiments that showed promising results and allowed us to validate our approach and model.

Keywords:

Multirobot systems, intelligent behaviors, metaheuristics, robotics exploration, bench-marking, Butterfly Optimization Algorithm, xBOA

6

` jÊÓ

~

~

ûA~K_ñK_.ðQË@ ~éÒ ~cents~~^~@~_á~_~m~~ É~KAÓ YK_~Yj~JËAK_.ð , .1J_~«AÒm_.Ì @ ûA~K_ñK_.ðQË@ ÈAm_.× 6-_ðQ£B@ è 11. _€PY~K B@ ~_‡J_~~~~JË@_ð ~_H@_PAÖÏ@ J_~cents~m~~ ð ~

._ú3/4J_~~KAÓ_ñ~K_ð^~#172;A ~°~JÉB@ LAJ_~É _ú~~ ôXY.:ÖÏ@ ~

~~

_Ð@Y j.:É@ _ú É _úÍ_ð B@ LëAÖÏ@
·
· _ù~ÒÊË@ ÈAj_. ÖÏ@ _ú~~~_á~_~.:ÒëAÓ _úΫ .1k_ðQ£B@ è .i,ë ÉÒ ~~~
Q~~ «~ ji.1.A1ÖÏ@ #172;A :°.:É@ .1Ê3/4:Ó ÉmÌ (Butterfly Optimization Algorithm) 3YK_~Yg_. âJ_~ÓJ_P@_ñk~

_ÕæK

~~ _ÕËA~JÒÊ« Yg _úΫ. ûñK.ðQË@ 4P+ _ú~~ û@_QgaË@_ð 3X_ðYjÖÏ@ alcentsË@  _ðQåt ûA«@_QÓ _(c)Ó ~é~_ðQÖÏ@

_P@Y«@_{~ Ð}YLÉ , _L3AJ_~Ë@
_· ®i _ú~~. ~A~K_ñK_.ðQË@ É~KAÓ ÉmÌ ÉJ_.~ ~_áÓ~éJ_~Ó~_PP@_ñ~mÌ @è jë _Ð@Y ~j;É@

i

·_ñ:,~K @1»_ð ~é1YË@ _{I.Ag. c./}Ó AëZ@X@~_á~_~s #172;Y_îE_. xBOA _ùÒ ~éJ_~Ó~_PP@_ñ~mÌ

~ @ è lë _áÓ YK_~Yg_.
Aë~_ðA :3@_{~ Õ}^-æK_{~ ú~}~æË@ È_ñÊmÌ @ i Ég _ú~~ ~_HAJ_~Ój_P@_ñ:4. @ .Ê::4 Z@X^~@ _Õæ_~J_~~®~K é9Yë _l.×A;_QK_{. Q}K_~ñcents~~ _ú~~ É~JÒ~J~K _ú~æ_ê~ , .1J_~.;A:Ë@ .1ÒëAÖÏ@ AÓ@ _ð , ~ _áÓ é«_ñÒm_.× ÈAÒ~JÉAK_. ~éJ_.~@_QÖÏ@_ð ,_(c)KA ~'J_.Ë@ É~®~K_ð , ~_H@_PAÖÏ@ J_~cents~m~~ #172;A ~°~JÉB@ ÉA -t..o éJ~~. ~_HA~K_ñK_.ðQË@ _~®«_ñË@ _`~~A'~mÌ @ ~é~K_PA~®ÖÏ ÈAÒ~JÉB@ É_îD _ð A~ÓA« éÊm_.~~ ~é~®K_~Qcents~_{. l.}×A~K_Q~_.Ë@ _ÕæÒ' _Õç

QñK~ é~K^~ ~@ AÒ» . 3XY:ÖÏ@ð 4K~XQ~®Ë@ ûA~KñK.ðQË@ ûAëñK~PA~J~~É (c)Ó AJ~°J~~KAÓñ~Kð

i@ J~°~JË@ð , 4Qå4

~

@ Qar~@ ÐAêÓ úΫ J~~»Q"JAK. ÑêË iÒa~É AÜØ ÑîE.PAm.~~ .1~JÖ~ß~B û@ðX@ c4tkAJ.ÊË

ék~~~ É~JÓ ~éJ_~Òë

. YÖ ß

z

i

éÖß~Y

®Ë@ ~_HAJ_~Ó ~_PP@_ñ~mÌ

~@_(c)ÓA_î

_PA

_ð6YK_~Yg_. ûA_»ÓJ_P@_ñk

· ;~NJa @ _H*AÒÊ3/4Ë@ N

i

_€AJ_~9 , _ù~;@_ñ.:Ë@ ûj.;Ë@ ,_úÍB@ #172;A~:°~JÉB@ , .1J» ~YË@ ûAJ_~»_ñÊË@ , âJ_~«AÒm_.Ì @ ,:_,
·A
·.;_ñK_.ðQË@ 416@

~

xBOA ôJ_~ÓJ_P@_ñk~ , ~_HA~É@_QaË@ _~m~ ~éJ_~ÓJ_P@_ñk~ , ûAJ_~ÓJ_P@_ñ. @ Z@X @

7

TABLE DES MATIÈRES

Remerciements 3

Résumé 4

Table des matières 9

Liste des figures 12

Liste des tableaux 13

Introduction Générale 14

I 1	Etude théorique Les systèmes multirobots		16 17
	1.1	Introduction	18
	1.2	Les systèmes multirobots	18
		1.2.1 Présentation des systèmes multirobots	18
		1.2.2 Les domaines d'applications	19
	1.3	Les types de systèmes multirobots	22
		1.3.1 Classification par type de comportements	22
		1.3.2 Classification par type de synchronisation	24
		1.3.3 Classification par type d'architecture du système	24
		1.3.4 Classification par autonomie	26
		1.3.5 Classification par type de robots	28
	1.4	Catégorisation des problématiques liées aux systèmes multirobots	29
		1.4.1 La navigation	30
		1.4.2 La cartographie	31
		1.4.3 La localisation	36
		1.4.4 La planification	38
		1.4.5 L'exploration	39
		1.4.6 La communication	42
		1.4.7 Autres problématiques	43
	1.5	Etat de l'art et travaux connexes	44
		1.5.1 Les méthodes déterministes	44
		1.5.2 Les méthodes à base d'apprentissage machine	46
		1.5.3 Les méthodes stochastiques	46
	1.6	Conclusion	48
2	Les métaheuristiques		49
	2.1	Introduction	50
	2.2	Les métaheuristiques	50
	2.3	Les types de métaheuristiques	51
		2.3.1 Les méthodes à base de trajectoires	51
		2.3.2 Les méthodes à base de population	53

8

2.4 Les mécanisme des métaheuristiques 57

2.4.1 La fonction objectif 57

2.4.2 L'exploration et l'exploitation 57

2.4.3 La convergence 58

2.4.4 Les hyperparamètres 59

2.4.5 Les contraintes 60

2.4.6 Les générations 60

2.4.7 Les critères d'arrêt 60

2.4.8 L'optimalité et la dominance 61

2.5 Structure de base d'une métaheuristique 62

2.5.1 La phase d'initialisation 62

2.5.2 Le corps de l'algorithme 62

2.5.3 La phase finale 62

2.6 Fondements théoriques de métaheuristiques populaires 64

2.6.1 Les algorithmes génétiques (GA) 64

2.6.2 L'optimisation par Essaim de Particules (PSO) 66

2.6.3 L'otimisation par Colonie de Fourmies (ACO) 67

2.7 Les Fondements théoriques de l'Algorithme d'Optimisation des Papillons

(BOA) 69

2.8 Les variantes de l'algorithme BOA 73

2.9 Amélioration de l'Algorithme d'Optimisation des Papillons en utilisation

l'opérateur de croisement (xBOA) 75

2.10 Conclusion 78

II Etude expérimentale 79

3 Méthodologie, modélisation et paramétrage 80

3.1 Introduction 81

3.2 PyRoboticsLab : un nouvel outil de simulation et de benchmarking . . . 81

3.2.1 Motivations pour la création d'une nouvelle plateforme de simulation 82

3.2.2 Les objectifs de conception 83

3.2.3 L'architecture du système 85

3.2.4 Les outils et technologies 87

3.2.5 Les scénarios de bechmarking 89

3.3 Modélisation géométrique des robots 89

3.4 Modélisation du processus de navigation, planification et évitement d'obs-

tacles 91

3.5 Modélisation des grilles d'occupation 93

3.6 Modélisation du problème d'exploration 97

3.6.1 Modélisation mono et multirobots 97

3.6.2 Les critères d'évaluation 100

3.6.3 La complexité du modèle 101

3.7 Paramétrage et configuration 101

3.7.1 Paramétrage des expériences 101

3.7.2 Paramétrage de l'environnement de simulation 102

9

3.8 Conclusion 104

4 Expériences et analyse 105

4.1 Introduction 106

4.2 Configuration matérielle 106

4.3 Expérience 1 : Évaluation de l'algorithme xBOA dans un contexte multirobots107 4.4 Expérience 2 : Comparaison entre les stratégies d'exploration à court terme

et à long terme 109

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

4.6 Expérience 4 : Comparaison de l'algorithme xBOA avec les métaheuris-

tiques populaires 112
4.7 Expérience 5 : Evaluation de la robustesse de l'algorithme xBOA face à la

réduction de taille de la population 120
4.8 Expérience 6 : Comparaison de xBOA avec les autres variantes de l'algo-

rithme BOA 125

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

4.10 Conclusion 131

Conclusion générale et perspectives 132

Bibliographie 140

10

LISTE DES FIGURES

1.1	Images de systèmes multirobots dans le monde réel	18
1.2	Différents aspects étudiés selon la nature du domaine appliqué aux systèmes
	multirobots	19
1.3	Utilisation de robots pour la gestion portuaire (système Kalmar AutoStrad
	[33])	20
1.4	Exemple d'un scénario où un groupe de robots s'entraident pour déplacer
	un objet lourd (Université Georgia Tech)	21
1.5	Exemple d'un scénario de modélisation 3D d'un parc urbain en utilisant
	plusieurs plusieurs robots (Australian Centre for Field Robotics)	22
1.6	Types d'architectures de systèmes multirobots	25
1.7	Exemple d'un système hétérogène constitué d'un robot volant et d'un robot mobile terrestre pour la supervision d'une zone agricole (Australian Centre
	for Field Robotics)	29
1.8	Détection d'obstacles en utilisant la technique du Vector Field Histogram [20]	31
1.9	Diagramme de relations entre l'environnement du robot et sa représenta-
	tion interne	32
1.10	Exemple d'une carte métrique 2D construite en utilisant la technique des
	grilles d'occupations [1]	34
1.11	Exemples de cartes métriques 3D	34
1.12	Exemple d'une carte topologique	35
1.13	Résultat d'un processus de fusion de cartes [74]	36
1.14	Schématisation des différents repères utilisés pour la localisation relative et
	globale [29]	37
1.15	Localisation par balises RFID [22]	38
1.16	Simulation d'un scénario industriel basé sur les algorithmes de planification
	de trajectoires [42]	40
1.17	Exemple de décomposition d'une carte et balayage en utilisant une trajec-
	toire en zigzag [48]	41
1.18	Exemple de sélection de régions à visiter dans un scénario de surveillance
	[49]	41
2.1	Classification des métaheuristiques [28]	51
2.2	Exemple d'une recherche à solution unique	52
2.3	Exemple d'une recherche à base de population de solutions	53
2.4	Processus de base d'un algorithme génétique	54
2.5	Optimisation de chemins par un ensemble de fourmis [56]	55
2.6	Optimisation à base d'interactions physiques entre les atomes [67]	56
2.7	Difference entre les stratégies d'exploration et d'exploitation d'une méta-
	heuristique [70]	58
2.8	Exemple de convergence d'une population de solutions [21]	59
2.9	Visualisation d'un front optimal (Pareto Front) séparant les solutions domi-
	nées des solutions non dominées [65]	61
2.10	Structure de base d'une métaheuristique	63
2.11	Diagramme de l'algorithme génétique	65
2.12	Pseudo-code de l'algorithme ACO	68

11

2.13 Diagramme de l'algorithme BOA 70

2.14 Pseudo-code de l'algorithme BOA 72

2.15 Résumé de l'état de l'art de l'algorithme BOA et ses différentes variantes 74

2.16 Exemple et pseudo-code de l'opérateur de croisement 75

2.17 Pseudo-code de l'algorithme xBOA 76

2.18 Diagramme de l'algorithme xBOA 77

3.1 Exemple d'un simulateur moderne basé sur un moteur de jeux vidéos pour

l'entraînement des voitures autonomes [31] 82

3.2 Architecture générale du simulateur PyRoboticsLab 86

3.3 Exemple de quelques types de visualisations générées par le simulateur Py-

RoboticsLab 87
3.4 Modélisation géométrique du robot et des différents repères utilisés pour la

détection d'obstacles 89
3.5 Modèle du bruit ajouté au capteur LIDAR et calcul du degré de confiance de

la mesure 91
3.6 Niveaux d'abstraction du processus de navigation, planification et évite-

ment d'obstacles du simulateur PyRoboticsLab 92
3.7 Schéma général du modèle de navigation, planification et évitement d'obs-

tacles du simulateur PyRoboticsLab 94
3.8 Diagramme de la routine "solve conflict" pour résoudre un problème de blo-

cage entre deux robots 95
3.9 Exemple d'exécution d'un scénario d'exploration et décomposition de la

carte de l'environnement sous forme de grille d'occupation 96
3.10 Un exemple du processus d'évaluation de la fonction fitness pour une po-

pulation de 4 solutions candidates 97

3.11 Diagramme du processus d'exploration d'une zone inconnue 99

3.12 Schéma du modèle utilisé pour assurer la coordination entre les robots . 100

3.13 Cartes de l'environnement de simulation utilisé durant les expériences . 102

3.14 Carte d'environnement utilisé pour simuler les scénarios à large échelle . 103

4.1 Progression visuelle du scenario multirobots en utilisant la méthode xBOA

avec 3 robots 107
4.2 Progression visuelle d'un scénario à grande échelle en utilisant la méthode

xBOA avec 2 robots 108
4.3 Comparaison entre les deux stratégies d'exploration en utilisant la méthode

xBOA 110
4.4 Résultats de la simulation de la mission d'exploration en utilisant la stratégie

à court terme 114
4.5 Résultats de la simulation de la mission d'exploration en utilisant la stratégie

à long terme 115
4.6 Comparaison de la durée totale de la mission d'exploration pour la stratégie

à court terme 117
4.7 Comparaison de la durée totale de la mission d'exploration pour la stratégie

à long terme 118
4.8 Nombre d'évaluations de la fonction de fitness et temps moyen de calcul

pour chaque métaheuristique 119

12

4.9 Comparaison des résultats en utilisant l'algorithme BOA avec différentes

tailles de population sur l'environnement House Map 120
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 122
4.11 Comparaison du temps moyen de calcul et convergence de la valeur de fit-

ness en utilisant la stratégie à court-terme et une population de taille 5 . . 123 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 124
4.13 Visualisation du front des solutions dominantes (Pareto-front) pour les dif-

férentes métaheuristiques en utilisant une population de taille 5 125
4.14 Comparaison des variantes de l'algorithme BOA en utilisant la stratégie à

court terme et une population de taille 5 127
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 128
4.16 Visualisation du front des solutions dominante (Pareto-front) pour les va-

riantes de BOA en utilisant une population de taille 5 129

4.17 Expérience sur le robot réel 130

13

LISTE DES TABLEAUX

1.1	Comparaison entre les architectures des systèmes multirobots	27
1.2	Comparaison entre les capteurs de distance et les capteurs optiques . . . .	33
1.3	Récapitulatif des problématiques de bases dans le domaine des systèmes
	multirobots	43
1.4	Résumé comparatif des travaux cités	47
4.1	Valeurs des meilleurs hyperparamètres trouvés après 30 essais	112
4.2	Taux d'exploration obtenus à la fin de la mission d'exploration	113
4.3	Evolution du taux d'exploration selon la taille de la population en utilisant
	l'algorithme BOA	120
4.4	Taux d'exploration obtenus à la fin de la mission en utilisant l'algorithme
	BOA avec une population de taille 5	124
4.5	Comparatif du taux d'exploration en utilisation les variantes de l'algorithme
	BOA avec une population de taille 5	126

14