La méthode utilisée dans OTTO

OTTO

Principes de OTTO

Mémoire

Nous avons vu que les structures de mémoire utilisées dans OTTO sont de la forme Sj = (γj , Dj , {(D¯ 1 j , T1). . .(D¯ N j , TN )}) où γj est le seul groupe auquel il est possible que Aj appartienne (en tout cas d’après les informations disponibles) auquel cas on a Aj ∈ γ Dj j et où (D¯ k j , Tk) indique que l’agent Aj n’était pas membre du groupe [Ak, Tk] à la date D¯ k j . Le groupe [Ak, Tk] est (s’il existe) le groupe le plus récent que Ak ait créé et D¯ k j la date la plus récente à laquelle on sait que Aj n’était pas membre de ce groupe (toujours d’après les informations disponibles). Ces structures Sj possèdent autant d’éléments de la forme (D¯ k j , Tk) que d’agents dans l’équipe. Dans OTTO, chaque agent conserve et met à jour une de ces structures pour chacun des autres membres de l’équipe. On voit donc que l’espace mémoire nécessaire croît avec le carré de l’effectif de l’équipe. L’idée clef derrière la gestion de la mémoire dans LOTTO est de restreindre cet espace mémoire en ne gardant qu’une partie de ces structures Sj , ce qui réduit non seulement leur nombre, mais aussi leur taille car on ne garde dans Sj un élément (D¯ k j , Tk) que si la structure Si correspondant à ce leader est en mémoire (voir figure 8.1). En effet si on décide de ne pas s’intéresser à l’agent Al il est inutile de garder (D¯l j , Tl) dans les structures Sj . C’est même impossible car on ne connaît alors même plus son existence. Dans LOTTO chaque agent ne garde donc en mémoire qu’un nombre limité Nmax de structures de la forme1 Sj = (γj , Dj , {(D¯ Ai j , TAi ). . .}) pour suivre l’équipe. Au début de l’activité de l’équipe les agents ne connaissent pas sa composition, ils découvrent les autres agents présents par écoute flottante. À chaque message reçu, un agent est susceptible de découvrir l’existence d’un nouvel agent et donc de créer une structure Sj correspondante. Lorsque Nmax structures ont été créées et qu’un nouvel agent est découvert, il faut choisir entre ne pas garder trace de ce nouvel agent ou en « oublier » un autre pour lui faire de la place. Pour déterminer quelles structures Sj garder dans l’espace mémoire limité de l’agent Ai , nous séparons ces structures par ordre d’importance en quatre classes, indiquées dans le tableau 8.1. Tout d’abord la structure la plus prioritaire pour l’agent Ai est Si , celle qui le concerne lui-même. Ensuite viennent les structures qui concernent les agents qui appartiennent au même groupe que Ai . Cela est crucial pour préserver la cohérence intragroupe, ne serait-ce que pour le leader. En effet, un leader doit connaître les membres de son groupe, la taille de la mémoire borne donc la taille des groupes possibles dans LOTTO. Ensuite viennent les leaders des autres groupes, ce sont les agents auxquels devra s’adresser Ai s’il veut rejoindre un autre groupe. Puis enfin vient le reste de l’équipe s’il reste de la place en mémoire. Au sein d’une même classe, on donne la priorité à l’information la plus récente : Sj1 est préféré à Sj2 si Dj1 > Dj2 . Toutes choses étant égales par ailleurs, il semble en effet préférable de privilégier un agent dont on vient d’avoir des nouvelles par rapport à un autre dont on n’a plus entendu parler depuis quelques temps et avec lequel on a donc moins de chances de pouvoir interagir.  

Conditions de communication

La méthode utilisée dans OTTO pour simuler les conditions de communication n’est pas applicable si l’on augmente sensiblement le nombre d’agents dans les simulations. En effet si l’on considère par exemple un système comprenant 100 agents et une fiabilité de 50% (valeur par défaut du paramètre α dans OTTO qui correspond à la densité moyenne du graphe de communication), chaque agent a en moyenne une cinquantaine d’agents avec qui communiquer à tout instant. On voit bien qu’alors les agents risquent d’être saturés de messages, et si l’on porte le nombre d’agents à 1000, c’est cette fois à 500 interlocuteurs potentiels que chacun doit faire face si la fiabilité reste la même ! La notion de fiabilité des communications ne semble donc pas être pertinente dans les SMA aux effectifs importants. Pour LOTTO, nous avons donc choisi de placer les agents dans l’espace et de leur donner une portée de communication limitée afin de donner aux communications la propriété de localité (voir section 5.3.2). Ainsi, en faisant se déplacer les agents dans un espace donné, les possibilités de communication évoluent de manière continue en une bonne approximation de ce que pourraient rencontrer, par exemple, un ensemble de micro-robots qui exploreraient une zone donnée de manière collaborative. Pour information, le tableau 8.2 donne une correspondance entre portée des communications et densité du graphe de communication (équivalente à la fiabilité dans OTTO). Bien qu’une portée de 500m semble être une valeur plutôt élevée de la portée des communications des agents si on les place dans une zone de 1km2 , cela correspond à la fiabilité de référence dans OTTO.