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

2.2.4 Poursuite cyclique à L liens

En comparant, dans la partie qui va suivre, les deux techniques étudiées précédemment, la pour-
suite cyclique hiérarchique donne un taux de convergence plus élevé que le schéma traditionnel.
Cependant, elle demande plus de liens de communication entre les agents, chaque agent perçoit plus
d'un agent contrairement au traditionnel où chaque agent ne capte que l'agent qui le suit dans l'ordre.
Pour cette raison, un schéma intermédiaire a été introduit où le nombre de connexions entre
agents est inférieur au schéma traditionnel, ou plus ou moins contrôlé, et où chaque agent chasse le

FIG. 2-4 - Structure d'une poursuite cyclique de 5 agents à 2 liens.

centre d'un groupe d'agents.

Dans une poursuite cyclique à L liens, chaque agent possède un lien de communication avec "L" agents. S'il y a NL agents, alors il y aura un total de LNL connexions dans le système. La stratégie que nous adopterons est la suivante :

Dans un système de NL agents, l'agent "i" poursuit le centre des agents de "i+1" jusqu'à "i+L" (modulo NL). Formellement ceci s'écrit :

1
L

_zi=

_XL
m=1

zi+m(modNL) ~ zi i=1, . . . ,NL.

ou sous une forme vectorielle : _zi = Az avec _ANLXNL une matrice circulante de la forme :

,0,...0) (2.17)

| _{z }

L uns

circ(--L,1,... 1

1

A= L

Exemple 2.3 Prenons le cas de NL = 5 agents, avec L = 2 (voirFigure e-4). la matrice de transformation A est la suivante :

A = 1 ₂circ(-2, 1,1,0,0) = circ(-1,¹ 2, ¹ 2,0,0).

2.2.5 Comparaison et taux de convergence

Dans cette partie, nous comparerons entre les trois différentes méthodes de la poursuite cyclique. Cette comparaison servira à faire une sélection entre les méthodes selon différents facteurs, elle sera ensuite appuyée par les résultats de notre simulation au dernier chapitre.

En plus du temps de convergence et de la vitesse moyenne des agents calculés à la fin de la simulation, un rapport est calculé pour exprimer l'augmentattion dans le taux de convergence entre

chaque couple de méthodes : Schéma traditionnel / l'hiérarchique, hiérarchique / Poursuite cyclique à L liens et ce dernier / schéma traditionnel.

Définition 2.4 Le taux de convergence des agents à leur centre est déterminée à partir de la valeur propre non nulle de A2 avec la partie réelle absolue la plus petite, nous appellerons cette dernière "valeur 'y".

Définition 2.5 L'augmentation dans le taux de convergence (R) calculé représente la rapidité de convergence du groupe d'agents au centre, avec une méthode comparé à l'autre méthode, c'est un rapport entre les parties réelles des valeurs 'y des deux différentes méthodes :

Ï(valeur 'y(m^~ethode 1))

R = Ï(valeur 'y(m^~ethode 2)) Ï: La partie réelle du nombre complexe.

Poursuite cyclique traditionnelle / hiérarchique

Soit : NL le nombre d'agents total.

Le taux de convergence correspondant à cette comparaison est:

Ï(valeur 'yhier)(2.18) Ï(valeur 'ytrad)

RL = traditionnel

hierarchique

Pour trouver la valeur 'y, nous devons d'abord calculer les valeurs propres de la matrice de transformation correspondant à la méthode utilisé AL (A1).

D'après 2.15, la matrice A_m est une matrice circulante à blocs, ses valeurs propres sont donc :

VP(A_m) = nm_[ VP(Am_1 + ^{(e2~j(r_1)Inm} - 1)I)

r=1

donc, les VP(A_m) sont les n_m ensembles de _{VP(Am_1)} décalées à gauche par a_m(r) = e2~i(r_1)Inm1. Nous remarquons que :

-2< Ï(a_m(r))<0 Vr=1,...,n_m.

car : Ï(o_m(r)) = cos(2r(r - 1)/n_m) - 1. et -1 < cos(2r(r - 1)/n_m) < +1.

Pour trouver la valeur 'y, nous devons d'abord déterminer toutes les valeurs 'y possibles de VP(A_m). Ces valeurs 'y appartiennent aux ensembles des VP avec le décalage à gauche le plus petit.

- Le premier ensemble des VP(A_m), elles sont simplement les _{VP(Am_1)} décalées par a_m(1) = 0, donc les valeurs 'y possibles de cet ensemble sont les valeurs 'y des VP(Am_1).

- L'ensemble des VP avec le décalage suivant le plus petit est donné par Am_1 + a_m(2)I (ou également a_m(n_m))[1]. Pour cet ensemble, la VP nulle de _{Am_1(la} VP la plus à droite) est décalée à gauche de a_m(2). Elle est donc la valeur 'y de cet ensemble, et est donnée par:

'y_m := e2~jInm - 1

De cette façon, on constitue l'ensemble des valeurs 'y possibles. Ensuite, la 'y-value des VP(A_m) doit être, ou la valeur 'y des _{VP(Am_1),} ou bien 'y_m. Ceci est un schéma récursif, pour chaque couche ajoutée, une autre VP est ajoutée à l'ensemble des 'y - values possibles. Plus concrètement :

Pour la première couche, la valeur 'y des VP(A1) est : 'y1 := e2~u/n1 - 1.

La deuxième couche, la valeur 'ye des VP(A2) est la valeur 'y des VP(A1) qui n'est autre que 'y1 ou bien : 'y2 := e2~3/n2 - 1.

De même pour la troisième couche, la valeur 'y des VP(A3) est 'y1, 'y2 ou : 'y3 := e2~3In3 - 1.

...

Pour les VP(A_m) la valeur 'y du schéma hiérarchique à L couches est donnée par:

'y := e2~j' - 1 w = max m

{nm}, m=1,...,L.

Pour la poursuite cyclique traditionnelle, il n'existe qu'une seule couche donc, la valeur 'y est donnée par : 'y := e2~j'NL - 1.

Ainsi, à partir de 2.18 l'augmentation du taux de convergence utilisant le schéma hiérarchique en comparaison avec la poursuite cyclique traditionnelle est :

Hi^~erarchique R = Traditionnel

<(e^2~iI - 1) <(e^2~iI^NL - 1)

cos(2r/w) - 1 cos(2r/NL) - 1

Pour simplifier cette expression, nous remplaçons le cos par son développement limité de l'ordre

1 avec :

cos(x) = _Pn

i=0 (_1)ⁱ

_(2i)! x2n + o(x²ⁿ) à l'ordre 2n avec o(x²ⁿ) -! 0 cos(x) à l'ordre 1 : cos(x) = 1 - ¹ ₂x². d'où :

1_1 2 (2ir/$)2_1 R 1_ 2 1 (21r/NL)2_1

~ 2=$ ) 2 ~NL 2 ~ NL 2 = = = 21r/NL $ maxm{nm}

Remarque 2.4 Dans le schéma hiérarchique à deux couches, le taux de convergence est directement:

max{n1, n2}

NL = min{n1,n2}²

(R2 =

2

Cas particulier: Lorsque n1 = n2 = /N2 les N2 agents convergent approximativement N2 fois

plus rapidement utilisant le schéma hiérarchique qu'utilisant la P.C traditionnelle.

.

Remarque 2.5 Pour la distribution optimale des n_m, trouvée précédemment concernant le schéma hiérarchique général. Et d'après 2.16 Le taux de convergence est :

~ (

( _NL J 2 ~ 2 ~ J 2 ~ 2

L1

NL L

R L = NL ~ N_1IL = N2(L_1)=L

L pNL = = = N

_N1/L L L L

L

Dans tous les cas, RL ~ 1 et donc, la convergence au centre utilisant une hiérarchie se fait plus rapidement que le schéma traditionnel.

Cependant, le schéma hiérarchique nécessite plus de liens de communications que le traditionnel, d'où plus de senseurs => il est donc plus coûteux.

Poursuite cyclique hiérarchique / à liens

De la même manière, nous retrouvons la valeur 'y de la poursuite cyclique à L liens, pour la comparer à celle du schéma hiérarchique, et calculer le taux de convergence.

D'après la formule 2.17 et utilisant la forme polynomiale de la matrice A qui est : A = q_c(P) avec : q_c(s) = 1 _Ls^L + ¹ _Ls^L_1 + ... + ¹ _Ls - s⁰,

VP(A) = ~q_c(1), q_c(w), q_c(w²), ..., q_c(w^NL_1)~

avec : w = e2~j=NL

La matrice A est circulante, elle possède donc une seule VP nulle q_c(1) et toutes les autres se situent dans la partie gauche du plan. S.L. Smith [1] a montré qu'il faut que NL » L pour que la valeur 'y des VP(A) soit donnée par q_c(w) = 'y.

XL 1 'y = qc(w) = L(w + w^2 + ~ ~ ~ + w^L) - 1 = 1 L m=1

e2~jm=NL - 1

et la partie réelle de est :

XL 1 <('y) = L m=1

(cos(2mr/NL)) - 1

CHAPITRE 2. DIFFÉRENTES APPROCHES DE LA STRATÉGIE DE RENDEZ-VOUS 29

Ainsi, le taux de convergence est :

Hi^~erarchique R = L-lien

cos(2r/w) - 1

(cos(2mr/NL)) - 1

=

avec w = max{n1, n2, ..., nL}

1
L

_PL
m=1

Toujours en utilisant le développement limité du cosinus, simplifions cette expression :

1_1 ₂ (2ir/$)2_1

R = PL

m=1

(27r $ )2

=

( _27r )2 1 PL

_m2

NL L m=1

(NL )2

L ~ :

$

(1_1 ₂ ( 27rm

NL )2)_1

_PL
m=1

1
L

_m2

1
L

_PL
m=1

De même, nous avons: R ~ 1 et donc, le schéma hiérarchique à L couches converge plus rapidement que celui à L liens, même s'ils demandent tous les deux le même nombre de capteurs.

Poursuite cyclique à L liens / Traditionnelle

Dans les comparaisons précédentes, nous avons calculé les valeurs 'y correspondant aux deux méthodes respectives (traditionnelle, L-liens). D'où l'augmentation dans le taux de convergence de la P.C à liens comparée à la traditionnelle est la suivante :

L - liens

R = Traditionnelle

(cos(2mr/NL)) - 1

=

cos(2r/NL) - 1

Après simplification du cos par son développement limité de l'ordre 1 :

(1_1 ₂ ( 27rm

NL )2)_1

1_ 1 2 (21r/NL)2_1

_PL

_Pm=1 2 ( 27r

1 NL )2 =m=

m2 ~ 1 = Les agents avec le schéma à L liens

R=

1

1_1 ₂ ( NL 27r )2

m²_1 L

1
L

_PL
m=1

convergent plus rapidement qu'avec le traditionnel, mais demandent plus de liens de communications et donc plus de senseurs.