Simulation du modèle en étoile sous le nom d’OTTO

OTTO

Nous avons réalisé une série d’expériences sur une mise en œuvre en simulation du modèle en étoile sous le nom d’OTTO (Organizing Teams Through Overhearing) [Legras, 2002]. Les processus de décision de plusieurs agents artificiels y sont simulés grâce à des machines à états finis qui leur permettent de créer, quitter ou vérifier des groupes. Les possibilités de communication sont elles aussi simulées avec des machines à états finis pour chaque paire d’agents. Ceci nous permet d’observer les performances relatives de l’architecture face aux variations des divers paramètres. 7.2 Protocole expérimental 7.2.1 Simulations stochastiques Afin de simuler un temps continu au sein d’une simulation à temps discret, nous utilisons un intervalle de temps (ou tick d’horloge) court par rapport aux autres grandeurs temporelles des simulations (un tick de 0,05s comparé à des grandeurs de plusieurs secondes). Les différentes machines à états finis suivent toutes le même principe : en l’absence d’autre interférence, leur évolution est soumise à des lois de Poisson P(t/τ ) : à chaque état est associée une constante de temps τ qui correspond au temps moyen pendant lequel la machine reste dans cet état avant de subir une transition. Du point de vue de la mise en œuvre, les lois de Poisson présentent une propriété très intéressante : si la valeur δ du tick d’horloge est petite par rapport à la constante de temps τ de la loi (δ  τ ), on peut considérer qu’un événement a une probabilité δ/τ de se produire entre chaque tick. Ainsi à chaque pas de la simulation, une machine change d’état naturellement avec une probabilité constante de δ/τ .

Communications

 À tout moment, on peut représenter les possibilités de communication entre agents par un graphe non-orienté dont les nœuds sont les agents et les arêtes la possibilité entre les deux agents concernés de communiquer. On appelle la densité d’un graphe le rapport entre son nombre d’arêtes et le nombre d’arêtes du graphe complet correspondant (N(N − 1)/2, voir firgure 7.2). Nous définissons deux paramètres pour caractériser les conditions de communication entre les agents dans une simulation : 1. la fiabilité α qui représente la densité moyenne du graphe de communication au cours du temps, et donc la probabilité moyenne qu’a un message d’atteindre un agent dans le système ; 2. la stabilité Tcomm qui représente le temps moyen d’un cycle « communication possible – impossibilité de communiquer » entre deux agents.Nous associons donc une machine cyclique à deux états (ON,OFF) à chaque arête du graphe de communication complet (voir figure 7.1). Au début de la simulation, chacune de ces machines a une probabilité α d’être dans l’état ON (communication possible entre ces deux agents) et une probabilité (1 − α) d’être dans l’état OFF (communication impossible entre ces deux agents). Par la suite, ces machines suivent une évolution entièrement déterminée par des lois de Poisson de constantes TON = αTcomm et TOFF = (1 − α)Tcomm. Il vient donc que deux agents ont à un moment donné une probabilité α de pouvoir communiquer et qu’un cycle de ces machines dure en moyenne Tcomm = TON + TOFF.

Agents

Une simulation concerne un ensemble de N agents homogènes dont l’état et les décisions sont représentés par des machines à états finis. Les figures 7.3, 7.4 et 7.5 représentent ces différentes machines. Leur évolution peut se faire selon trois types de transitions : 1. les flèches noires pleines correspondent aux évolutions suivant une loi de Poisson avec la constante de temps associée au nœud (TCHK , TQUIT , etc.) Lorsque ces transitions sont déclenchées, l’agent émet un message du type associé à la transition ; 2. les flèches noires en pointillés correspondent aux évolutions liées à la réception d’un message par l’agent ; 3. les flèches en gris clair correspondent aux transitions déclenchées par l’évolution d’une autre machine à états du même agent. 

Trois types de machines sont utilisées :

 self : 

Chaque agent est doté d’une telle machine afin de représenter le fait qu’il croit faire partie d’un groupe (IN) ou non (OUT). S’il est membre d’un groupe, un agent décide de le quitter (ou de le dissoudre s’il en est le leader) au bout d’un temps moyen TQUIT . Si l’agent ne croit pas être membre d’un groupe il crée son propre groupe (AFF) ou tente d’en rejoindre un préexistant (avec un JOIN vers un groupe présent dans sa carte de l’organisation de l’équipe) tous les TJOIN (voir figure 7.3a). Ce temps est généralement assez court, en effet l’idée est d’éviter les agents solitaires. On peut noter au passage que le fait d’émettre un AFF ne fait pas que l’agent se considère membre d’un groupe, ce n’est le cas que lorsqu’il reçoit son propre message. D’ailleurs, la seule transition qui permet de passer de OUT à IN ne peut se faire que par la réception d’un message (figure 7.3b). La figure 7.3c illustre enfin l’évolution liée à la réception d’un message indiquant que l’agent n’appartient plus à son groupe.

doubt 

 Chaque agent est doté d’une telle machine afin de lui donner un comportement de vérification de l’état de son groupe. La machine suit une évolution parallèle à celle de self entre OK et OUT (figure 7.4a), mais dans l’état OK l’agent est susceptible d’émettre un CHK vers son groupe et de passer alors dans l’état DOUBT. Le comportement de la machine dépend alors du statut de leader (ou non) de l’agent. Si l’agent est simple membre (figure 7.4b) il attendra un temps moyen TWAIT avant de QUITter son groupe, à moins qu’il ne reçoive un AFF de son leader l’incluant dans le groupe, le faisant repasser du même coup sur OK (flèche pointillée). Si, au contraire, l’agent est leader de son groupe, il attendra pendant un temps moyen TWAIT que les membres de son groupe se manifestent avant d’exprimer la nouvelle composition du groupe (flèche pleine, figure 7.4c).

member 

 Ces machines sont utilisées par les leaders, ils en utilisent une par agent dans l’équipe (IN pour les membres, OUT pour les autres). Lorsque la machine doubt d’un leader passe sur DOUBT, les machines associées aux membres passent de IN à DOUBT (flèche grise, figure 7.5a). Le fait de recevoir un BEL d’un membre fait repasser la machine correspondante sur IN (voir figure 7.5b). Ainsi, lorsque le leader émet le AFF après avoir patienté pendant TWAIT , il n’inclut dans le groupe que les membres dont la machine est sur IN, ce qui fait passer les autres sur OUT..