Modélisation d'un système multi-agents : application à la réunion d'attribution des charges horaires au département d'informatique de gestion

CHAP. 3. LES PROTOCOLES D'INTERACTION FIPA-ACL

3.2. ANALYSES

Le tableau 3 donne les principaux protocoles d'interactions spécifiés dans FIPA-ACL, ainsi que les performatifs initiant des conversations équivalentes en KQML (qui ne définit pas à proprement parler de protocoles d'interaction, mais associe à certains performatifs un protocole implicite dont ils sont les premiers messages).

Tableau 3. Protocoles d'interaction standards de FIPA- ACL

Source : Jouvin, Délégation de Rôle et Architectures Dynamiques de systèmes Mullti-agents conversationnels, Université Lyon I-Claude Bernard, Paris, Thèse de Doctorat 2003.

Dans les sous-sections suivantes nous analyserons en détail les principaux protocoles de cette liste.

a. Request et dérivés (Query et Propose)

La figure 6 représente les protocoles FIPA-Request et FIPA-propose en Agent UML. Ces différents protocoles suivent tous un schéma d'exécution proche : ils sont composés d'une requête initiale, suivie d'une réponse qui peut-être soit un refus, soit une acceptation. L'acceptation est implicite dans le cas de query, où le résultat est alors directement renvoyé. Pour request, l'acceptation est suivie de la notification du succès ou de l'échec dans la tâche demandée. Pour propose, la tâche est seulement négociée mais n'est pas effectuée dans le cadre de la conversation.

Figure 5. FIPA-Request et FIPA-Propose en Agent UML (tiré des spécifications de FIPA)

Redondance. Le diagramme de FIPA-Request illustre la remarque de la section 3.1 a sur la redondance des rôles dans la spécification globale du protocole. L'auteur semble avoir choisi de représenter ici les alternatives du côté du participant. Ce rôle stipule par exemple qu'un inform ne peut être envoyé qu'après avoir envoyé un agree. La définition du rôle d'initiateur, quant à elle, semble accepter les messages dans n'importe quel ordre, sans aucune contrainte, ce qui est inexact en réalité.

Le fait est que la notation condensée combinant plusieurs réceptions de message sur une même ligne de vie ne permet pas de relier les segments d'activation à d'autres segments d'activation passés. En notation non condensée, il aurait été possible de prolonger le segment suivant la réception de agree, jusqu'à une alternative se séparation en trois branches pour réceptionner les trois autres messages, ce qui aurait permis d'exprimer que l'initiateur ne peut recevoir ces derniers qu'après réception de agree.

En outre, du côté participant, l'auteur utilise une condition de garde (agreed) pour exprimer cette même contrainte. Il aurait été plus intuitif de la représenter graphiquement, en utilisant des lignes de vie séparées, dont une contiendrait le segment de l'envoi du agree qui se prolongerait alors jusqu'à l'envoi de message complexe.

Exceptions. La spécification de ces protocoles inclut explicitement l'envoi de notunderstood, qui correspond à une exception du protocole. À l'inverse, d'autres protocoles plus complexes ne les incluent pas. Il serait plus clair de choisir une ligne de conduite : soit d'exclure systématiquement le traitement des exceptions de la définition du protocole ; soit de l'inclure, mais d'utiliser une notation plus synthétique, comme le propose Koning^82(*).

b. Contract-Net et Iterated-Contract-Net

Figure 6. FIPA-Contract-Net et FIPA-Iterated-Contract-Net en Agent UML

Le protocole Contract-Net, introduit par Smith^83(*), a suscité beaucoup d'enthousiasme dans plusieurs domaines, dont les systèmes multi-agents, car il reflétait une nouvelle vision décentralisée de certains problèmes d'optimisation. En soi, ce protocole est particulièrement simple, ce qui est aussi une raison de son succès.

Dans FIPA-Contract-Net, L'initiateur divulgue à un ensemble de participants un appel à proposition, CFP ; puis collecte les propositions émises par les participants. Il choisi un gagnant, selon un critère donné, et rejette les propositions des autres.

La figure 7 présente les diagrammes Agent UML de Contract-Net, et de sa version itérative, Iterated-Contract-Net. Le premier diagramme comporte une erreur sur les réceptions de failure, inform et inform-ref, qui ne sont bien-sur pas successives : la ligne d'activation devrait ici être divisée en 3 segments.

Boucle. Comme le montre la figure 7, Iterated-Contract-Net boucle sur une sous-conversation de type Contract-Net, tant que l'initiateur envoi des CFP. Dès lors qu'une des propositions est acceptée, ou que toutes sont refusées, il se termine.

Parallélisme. Dans Iterated-Contract-Net, les messages envoyés en parallèle après le branchement conditionnel possèdent une clause d'ordonnancement dans le temps. Il me semble que cela appelle la question suivante : pourquoi spécifier l'envoi parallèle de messages, s'ils doivent être ordonnés dans le temps ? Peut-être l'auteur du schéma a-t-il eu recours à ce stratagème parce que la notation n'autorise pas la création d'une nouvelle ligne d'activation après un envoi de message complexe.

c. English-Auction et Dutch-Auction

Figure 7. FIPA-English-Auction et FIPA-Dutch-Auction en Agent UML

(tirés des spécifications FIPA)

Ces deux protocoles d'enchère de FIPA-ACL sont intéressants car ils sont simples à appréhender intuitivement, mais comportent plusieurs difficultés de représentation et d'implémentation. La figure 8 en donne les diagrammes Agent UML.

Le fonctionnement d'une enchère est proche de celui de Iterated-Contract-Net, avec quelques nuances. Il s'agit de boucle d'itérations comportant un appel à propositions (cfp), suivi de propositions de la part des participants. Dans le cas de l'enchère à l'anglaise, le prix va croissant, et la boucle continue tant que des participants répondent en émettant au moins une proposition au cfp. Pour l'enchère à la hollandaise, le prix est fixé plus haut que le prix du marché, puis ce dernier va décroissant à chaque itération. Au début aucun participant ne répond, et l'enchère se termine dès qu'un ou plusieurs participants proposent à une itération. L'enchère hollandaise est à première vue plus avantageuse pour le vendeur, car il a toutes les chances d'obtenir le meilleur prix des acheteurs.

Égalité : L'initiateur départage les participants ayant proposés simultanément à la dernière itération par l'envoi d'un accept au vainqueur, et de reject pour les autres Time-out. Ces deux protocoles sont basés sur un time-out à chaque itération. Les participants ne sont pas obligés de signifier qu'ils refusent un cfp, leur silence est un refus implicite. Ce time-out introduit un état mixte, qui rend le protocole difficile à implémenter.

Il est curieux de constater que ce time-out n'est pas représenté sur les diagrammes dans les spécifications de FIPA, alors qu'il est essentiel au protocole.

Nous pouvons noter que, tout comme contract-net, les deux messages du dernier branchement parallèle sont agrémentés d'une clause d'ordonnancement.

Cardinalités : Le message request présente une cardinalité de 1, alors que celle de inform est de n. L'interprétation intuitive est qu'un inform est envoyé à tous les participants, le vainqueur compris, indiquant la fin de l'enchère, puis un request est envoyé uniquement au vainqueur.

- Soit nous considérons que toute cardinalité de n (ou supérieures à 1) implique une réception synchronisée de n messages ;

- Soit nous considérons séparément le comportement induit par chaque participant, auquel cas une réception multiple est par défaut non synchronisée, et les divergences de comportement des participants sont représentées par des alternatives. Il sera alors possible d'exprimer, dans l'enchère, que le request ne sera envoyé qu'au vainqueur, à qui l'initiateur a déjà envoyé accept.

d. Brokering et Recruiting

Les protocoles FIPA-Brokering et FIPA-Recruiting sont tous deux directement inspirés de leurs équivalents dans KQML. Ils constituent tous deux des actes de courtage, dont le principe général est qu'un agent courtier, comparable à un facilitateur, joue le rôle d'intermédiaire entre un agent initiateur et les participants avec lesquels ce dernier souhaite interagir, le courtier ayant pour tâche de trouver des participants adéquats. L'utilité de ces protocoles dans les systèmes multi-agents a été soulignée notamment par Finin et al. ^84(*)

La figure 9 donne le diagramme de FIPA-Recruiting en Agent UML. FIPABrokering est similaire, à ceci près que la réponse du sous-protocole est d'abord reçu par le courtier (broker) qui la retransmet à l'initiateur.

En FIPA-ACL l'initiateur va d'abord envoyer un message de type proxy, dans lequel est imbriqué le premier message de la conversation cible, et le profile des participants qu'il recherche. Puis le courtier va rechercher des participants adéquats, mettre à jour les destinataires du message imbriqué, et le transmettre aux participants. Ensuite, la sous-conversation imbriquée va se dérouler (nous n'en savons pas plus), puis les participants vont renvoyer soit au courtier, dans le cas de Brokering, soit directement à l'initiateur, dans le cas de Recruiting, une « réponse finale ».

Figure 8. FIPA-Recruiting en Agent UML (Tiré des spécifications de FIPA)

Réponse et délégation. La sémantique naïve de réponse ne s'applique à toute sous conversation, en particulier si elle est multi-partie. Il se peut que le protocole de cette conversation implique une participation beaucoup plus active que l'attente d'une réponse de la part de l'initiateur. Dans le cas de Recruiting, nous pouvons imaginer que la conversation va se poursuivre entre l'initiateur (ou le destinator) et les participants, sans que le courtier n'intervienne, ce qui règle le problème. Mais dans le cas de Brokering, devons-nous considérer que le courtier va jouer le rôle de l'initiateur dans la conversation imbriquée ? Ou bien devons-nous considérer qu'il va rediriger chaque message à l'initiateur, puis que l'initiateur lui renverra les réponses intermédiaires, elles-mêmes imbriquées dans des messages de type proxy, à renvoyer aux participants? La spécification ne répond malheureusement pas à ces questions. Celle du performatif proxy ne nous aide pas davantage.

* ⁸² Jean-Luc Koning, Marc-Philippe Huget, Jun Wei, Xu Wang: Extended Modeling Languages for Interaction Protocol Design. Dans les actes de International Workshop on Agent Oriented Software Engineering (AOSE), Montréal, Canada, Mai 2001. Michael Wooldridge, Gerhard Weiß, Paolo Ciancarini (éd.), LNCS vol. 2222.

* ⁸³ Reid Smith: The Contract Net: A Formalism for the Control of Distributed Problem Solving. Dans les actes de International Joint Conference on Artificial Intelligence (IJCAI), Cambridge, MD, USA, Août 1977. R. Reddy (éd.), W. Kaufmann

* ⁸⁴ Tim Finin, Rich Fritzson, Don McKay, Robin McEntire: KQML as an Agent Communication Language. Dans Conference on Information and Knowledge Management (CIKM), (), Décembre 1994.