Stratégie de rendez-vous dans les systèmes multi-agents

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.