Table des matières
Introduction générale
1 Le problème de la stratégie de Rendez-vous
|
1
3
|
|
1.1
|
Introduction
|
3
|
|
1.2
|
Agents et Systèmes multi-agents
|
3
|
|
|
1.2.1 Définitions
|
3
|
|
|
1.2.2 Architectures des SMA
|
5
|
|
|
1.2.3 Classification des agents
|
7
|
|
|
1.2.4 Domaines d'application des SMA
|
9
|
|
|
1.2.5 Quelques exemples de SMA
|
9
|
|
1.3
|
SMA et robots mobiles
|
11
|
|
|
1.3.1 Définitions
|
11
|
|
|
1.3.2 Application des SMA aux robots mobiles
|
12
|
|
|
1.3.3 Exemples de SMA réalisés en robotique
|
12
|
|
1.4
|
Stratégie de Rendez-vous des SMA
|
13
|
|
|
1.4.1 Situation du problème
|
13
|
|
|
1.4.2 Définition de la stratégie
|
13
|
|
|
1.4.3 Exemples d'application de la stratégie
|
14
|
|
|
1.4.4 Les différentes approches adoptées
|
14
|
|
1.5
|
Conclusion
|
14
|
2
|
Différentes approches de la stratégie de
rendez-vous
|
15
|
|
2.1
|
Introduction
|
15
|
|
2.2
|
La poursuite cyclique
|
15
|
|
|
2.2.1 Préalables mathématiques
|
16
|
|
|
2.2.2 Poursuite cyclique traditionnelle
|
19
|
2.2.3 Poursuite cyclique hiérarchique 20
2.2.4 Poursuite cyclique à L liens 24
2.2.5 Comparaison et taux de convergence 25
2.3 Le rapetissement de polygone 29
2.3.1 Préalables mathématiques 30
2.3.2 Rapetissement par la courbure de Menger-Melnikov 33
2.3.3 Le schéma linéaire 35
2.3.4 Remarques 35
2.4 Conclusion 35
3 Mise en oeuvre de la simulation 37
3.1 Introduction 37
3.2 Vérification et implémentation des algorithmes
sous Matlab 38
3.2.1 Résolution de la dynamique du système 38
3.2.2 Implémentation des algorithmes et tracé des
trajectoires sous Matlab 39
3.3 Mise en oeuvre de la simulation 45
3.3.1 Cahier de charge du simulateur 47
3.3.2 Conception du simulateur 47
3.3.3 Réalisation de l'interface graphique 53
3.4 Conclusion 56
4 Résultats et discussions 57
4.1 Résultats obtenus sous Matlab 57
4.1.1 Comparaison entre les méthodes 57
4.1.2 Mise à l'échelle du nombre de couches dans un
schéma hiérarchique 59
4.1.3 Mise à l'échelle du nombre de liens dans un
schéma à L liens 59
4.2 Résultats de la simulation 59
4.2.1 Poursuite cyclique 61
4.2.2 Rapetissement de polygone 62
4.2.3 Remarques 63
4.3 Conclusion 63
Table des figures
1-1
|
Interaction d'un agent avec son environnement
|
4
|
1-2
|
Architecture d'un SMA à contrôle centralisé
|
6
|
1-3
|
Architecture d'un SMA à contrôle distribué
|
6
|
1-4
|
Structure d'un agent réactif dans un environnement
multi-agents
|
7
|
1-5
|
Structure d'un agent cognitif dans un environnement
multi-agents
|
8
|
2-1
|
la structure d'une poursuite cyclique traditionnelle à 4
agents
|
19
|
2-2
|
Structure d'un schéma hiérarchique à 2
couches (9 agents, 3 groupes)
|
22
|
2-3
|
Trois couches d'hiérarchie dans une poursuite cyclique
|
23
|
2-4
|
Structure d'une poursuite cyclique de 5 agents à 2 liens
|
25
|
2-5
|
La dynamique du rapetissement de courbe
|
32
|
2-6
|
Rapetissement de polygone
|
33
|
2-7
|
Le cercle circonscrit de 3 points de la courbe
|
34
|
3-1
|
4 agents dans une poursuite cyclique traditionnelle
|
41
|
3-2
|
16 agents dans une poursuite cyclique hiérarchique
à 4 couches
|
43
|
3-3
|
8 agents dans une poursuite cyclique à 4 liens
|
44
|
3-4
|
Rapetissement par Menger-Melnikov d'un polygone formé
par 16 agents
|
46
|
3-5
|
Rapetissement par le Schéma linéaire d'un groupe
de 16 agents
|
46
|
3-6
|
Diagramme de classes
|
49
|
3-7
|
Diagramme de séquences
|
54
|
3-8
|
Interface principale de la simulation
|
55
|
3-9
|
Rapport des résultats
|
56
|
4-1
|
Les 3 méthodes de la poursuite cyclique d'un groupe de
16 agents
|
58
|
4-2
|
Trajectoires des deux méthodes du rapetissement de
polygone
|
59
|
4-3
|
La poursuite cyclique hiérarchique de 16 agents en
fonction du nombre de couches. . .
|
60
|
4-4 La poursuite cyclique à 4, 8 ou 12 liens 60
4-5 Le comportement observé des agents avec la
méthode de Menger-Melnikov 62
Introduction générale
Parmi les domaines d'application de la robotique, nous
trouvons les missions de sauvetage où la présence de l'homme est
menacée et telles que des robots sauveteurs doivent se réunir
à un lieu donné pour effectuer cette mission au même
moment. Plusieurs stratégies sont nécessaires pour effectuer une
navigation fiable de robots mobiles dans un environnement contraint, l'une
d'elles est la convergence à un point de rendez-vous.
Dans une telle situation, on cherche à concevoir une
stratégie de rendez-vous d'un groupe de robots mobiles autonomes et
homogènes, formant un système multi-agents. Dans ce
mémoire, ce problème a été étudié et
les solutions proposées dans la littérature notamment par Stephen
L. Smith[1], ont été testées. Les travaux de Smith
s'intéressent au développement d'algorithmes pour l'allocation de
tâches dans des groupes de robots mobiles.
Inspirés par ses travaux et par sa thèse de
master sur les stratégies de rendez-vous et de stabilisation de
formations, nous allons implémenter deux approches de la
stratégie de rendez-vous dont la poursuite cyclique et le rapetissement
de courbe.
Notre travail se compose de quatre chapitres. Le premier
représente une synthèse bibliographique sur les systèmes
multi-agents appliqués dans le domaine de la robotique et à la
stratégie de rendez- vous.
Au second chapitre, une description analytique approfondie de
notre système et des différentes solutions proposées sera
établie. Le système est composé de n agents se situant
dans un plan complexe, chaque agent peut détecter les positions de
certains des autres agents, selon la méthode employée. Un agent
considéré comme leader doit initialiser tous les agents avec les
informations nécessaires à l'accomplissement de la
stratégie. Un rapport entre les taux de convergence des
différentes méthodes est calculé pour comparer entre
elles.
Au troisième chapitre, une mise en oeuvre des solutions
proposées au chapitre 2 sera réalisée. Dans un premier
temps, nous allons vérifier la validité et la convergence des
algorithmes sous matlab, et tracer les trajectoires effectuées par les
agents. Ensuite, une interface graphique sera réalisée,
permettant de simuler les différentes approches de cette
stratégie, visualiser le comportement des
agents et calculer certaines valeurs d'évaluation.
Finalement, nous discuterons les résultats obtenus par
la simulation et présenterons les avantages et les inconvénients
de chaque méthode, ainsi que les éventuelles difficultés
rencontrées dans l'implémentation des algorithmes.
|