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

Chapitre 3

Mise en oeuvre de la simulation

3.1 Introduction

La simulation consiste à effectuer des expériences sur un modèle d'un système réel, dans notre cas, il s'agit d'une stratégie de collectivité de robots autonomes dans un environnement spécifique. Pour ce faire, nous décomposons cette activité en quatre étapes :

Analyse du système réel, et des informations que l'on désire obtenir sur son comportement.

- Représentation d'un modèle, dans lequel nous ne retenons que les caractéristiques qui semblent pertinentes par rapport aux résultats recherchés, sous forme d'un programme de simulation. L'expérimentation, dans laquelle nous faisons évoluer le modèle, c'est à dire interpréter le

programme de simulation à l'aide d'un schéma d'exécution adapté qui est le simulateur.

- Analyse des résultats produits, et en déduire des informations sur le comportement du système réel.

La première étape a été traitée dans le chapitre précédent. Dans celui-ci, il s'agit de prendre en charge les deux étapes qui suivent en développant une interface graphique sous forme d'une applet Java, pour simuler les différentes approches de la stratégie de rendez-vous et en déceler quelques caractéristiques. Dans le dernier chapitre, nous réaliserons la dernière étape.

Avant de procéder à la conception de l'interface de simulation, et compte tenu de la complexité des méthodes présentées au chapitre précédent, nous avons jugé nécessaire de passer par une étape intermédiaire, qui consiste à vérifier et à étudier la faisabilité des algorithmes. Ceci a été fait en utilisant Matlab, qui est un langage de calcul mathématique, car notre système implémente des algorithmes employant plusieurs d'outils mathématiques.

3.2 Vérification et implémentation des algorithmes sous Matlab

Avant de réaliser notre simulation sous Java, nous avons pensé à mettre en oeuvre des algorithmes implémentant les différentes stratégies et méthodes présentées au chapitre précédent. Cette implémentation permettra de vérifier la réalisabilité des algorithmes, de tracer les trajectoires des robots mobiles réalisant la stratégie de Rendez-vous, et de comparer entre les différentes approches. Cette étape fut très simple et très rapide, car Matlab offre une boite à outils mathématiques très riche contenant toutes les fonctions nécessaires à notre étude.

3.2.1 Résolution de la dynamique du système

Dans les deux approches adoptées pour réaliser la stratégie de Rendez-vous (Poursuite cyclique, Rapetissement de polygone), il s'agit de résoudre des systèmes dynamiques décrivant l'évolution d'agents mobiles autonomes dans un environnement spécifique. Ces systèmes sont régis par des équations différentielles d'ordre 1 qui sont sous la forme suivante :

x_ = f(t,x)

Pour résoudre ce type d'équation, nous utilisons la méthode de Runge Kutta d'ordre 4 [10] afin de calculer les positions des agents aux instants "t".

Définition 3.1 Les méthodes de Runge-Kutta sont des méthodes d'analyse numérique d'approximation de solutions d'équations différentielles. Elles portent le nom des mathématiciens Carl Runge et Martin Wilhelm Kutta. Ces méthodes reposent sur le principe de l'itération, c'est-à-dire qu'une première estimation de la solution est utilisée pour calculer une seconde estimation, plus précise, et ainsi de suite.

Algorithme 3.1 Algorithme de Runge Kutta d'ordre 4 Considérons le problème suivant :

x_ = f(t,x) x(t0) = x0 connu

La méthode de RK4 est donnée par l'équation:

xi+1 = xi +

h 6 (w1 +2w2 +2w3+w4)

w1 = f(t ,x )

w2 = f(t +h 2 ;x +h 2 k1)

w3 = f(t +h 2 ;x +h 2 k2)

w4 = f(t +h,x +hk3)

L'idée est que la valeur suivante x ₊₁ est approchée par la somme de la valeur actuelle x et du produit de la taille de l'intervalle h par la pente estimée. La pente est obtenue par une moyenne pondérée de pentes :

w1 est la pente au début de l'intervalle.

w2 est la pente au milieu de l'intervalle, en utilisant la pente w1 pour calculer la valeur de x au point t + h 2 par le biais de la méthode d'Euler.

w3 est de nouveau la pente au milieu de l'intervalle, mais obtenue cette fois en utilisant la pente w2 pour calculer x.

w4 est la pente à la fin de l'intervalle, avec la valeur de x calculée en utilisant w3.

Dans la moyenne des quatre pentes, un poids plus grand est donné aux pentes au point milieu.

pente =	w1 + 2w2 + 2w3 + w4
	6

L'ordre 4 signifie que l'erreur commise à chaque étape est de l'ordre de h⁵, alors que l'erreur totale accumulée est de l'ordre de h⁴.