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 +1 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 h5, alors que l'erreur totale
accumulée est de l'ordre de h4.
|