WOW !! MUCH LOVE ! SO WORLD PEACE !
Fond bitcoin pour l'amélioration du site: 1memzGeKS7CB3ECNkzSn2qHwxU6NZoJ8o
  Dogecoin (tips/pourboires): DCLoo9Dd4qECqpMLurdgGnaoqbftj16Nvp


Home | Publier un mémoire | Une page au hasard

 > 

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


par Amine BENDAHMANE
Université des Sciences et de la Technologie d'Oran Mohamed Boudiaf - Doctorat en informatique - Intelligence Artificielle 2023
  

sommaire suivant

Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy

ÉíÈÚÔáÇ ÉíØÇÑÞíãáÏÇ ÉíÑÆÇÒáÌÇ ÉíÑæåáÌãÇ

íãáÚáÇ ËÍÈáÇ æ áíÇÚáÇ íãáÚÊáÇ ÉÑÇÒæ

ÇíÖæÈ ÏãÍã ÇíÌæáæäßÊáÇ æ ãæáÚáá äÇÑåæ ÉÚãÇÌ

 

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~ÓJP@ñ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~ÓjP@ñ:4. @ .Ê::4 Z@X~@ Õæ~J~~®~K é9Yë l.×A;QK. QKcents~~ ú~~ É~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Ì @ ~é~KPA~®ÖÏ ÈAÒ~JÉB@ ÉîD ð A~ÓA« éÊm.~~ ~é~®K~Qcents~. l.×A~KQ~.Ë@ ÕæÒ' Õç

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»ÓJP@ñ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~ÓJP@ñk~ , ~HA~É@QaË@ ~m~ ~éJ~ÓJP@ñk~ , ûAJ~ÓJP@ñ. @ 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

sommaire suivant






Bitcoin is a swarm of cyber hornets serving the goddess of wisdom, feeding on the fire of truth, exponentially growing ever smarter, faster, and stronger behind a wall of encrypted energy








"Tu supportes des injustices; Consoles-toi, le vrai malheur est d'en faire"   Démocrite