Un protocole de coordination d’agents introspectifs pour la ... · Un protocole de coordination d’agents introspectifs pour la chorégraphie dynamique de services Yasmine Charif

Un protocole de coordination d’agentsintrospectifs pour la chorégraphiedynamique de services

Yasmine Charif — Nicolas Sabouret

Université Pierre et Marie Curie-Paris6, UMR 7606, LIP6,4 Place Jussieu, Paris, F-75005 France

[email protected] [email protected]

RÉSUMÉ. L’objectif de notre travail est de proposer une approche dynamique pour la composi-tion de services. L’approche étudiée -la chorégraphie de services- s’appuie sur la collaborationdécentralisée entre une collection de services dont le but est d’atteindre un objectif donné. Dansnotre approche, ce but consiste à satisfaire des besoins d’utilisateurs humains non préalable-ment définis au travers d’un plan de composition. Pour ce faire, notre approche appuie sur unprotocole de coordination multiagent dans lequel les capacités de collaboration des servicessont modélisées à l’aide d’agents introspectifs. Ces agents sont capables de raisonner sur leurspropres actions (ou sur les services qu’ils offrent), de décomposer une tâche en fonction deleurs compétences, et de se coordonner dynamiquement avec d’autres agents pour pallier leurslimites et couvrir les besoins à satisfaire.

ABSTRACT. We propose in our work to model a dynamic approach for service composition. Thestudied approach -service choreography- relies on the decentralized collaboration of a set ofservices which aim is to achieve a specific goal. In our work, this goal consists to satisfy needsin software services freely expressed by human users (non predefined through a compositionplan). The collaborations of services in our approach are made possible by a dynamic agentcoordination protocol. In this coordination model, the services’ collaboration capabilities aremodeled through introspective agents capable to reason on their own actions (or on the servicesthey offer), in order to dynamically take part to a task achievement, and to coordinate with otheragents so as to overcome their limitations and cover the user needs to be satisfied.

MOTS-CLÉS : Service web, composition dynamique de services, chorégraphie de services, sys-tèmes multiagent, modèle de coordination, protocole d’interaction.

KEYWORDS: Web Services, Dynamic Service Composition, Service Choreography, Multi-AgentSystems, Coordination Model, Interaction Protocol.

L’objet. Volume 8 – n˚2/2005, pages 1 à 15

2 1 INTRODUCTION

1. Introduction

Si une application ou un client requiert des fonctionnalités, et qu’aucun serviceexistant n’est apte seul à les fournir, il devrait être possible de combiner plusieurs ser-vices afin de répondre aux besoins énoncés. C’est ce que l’on appelle la compositionde services. Celle-ci vise à faire interopérer, interagir et coordonner plusieurs servicespour la réalisation d’un but. Les travaux du domaine (Barros et al., 2005; Dijkmanet al., 2004; Peltz, 2003) identifient trois angles sous lesquels cette coordination peutêtre décrite : la chorégraphie, l’interface de comportement et l’orchestration. La cho-régraphie décrit les interactions entre une collection de services et ce d’un point de vueglobal. L’interface de comportement décrit l’ordre légal d’exécution des opérationsspécifiques à un service. Enfin, l’orchestration décrit du point de vue d’un service lesinteractions de celui-ci ainsi que les étapes internes (ex. transformations de données,invocations à des modules internes) entre ses interactions.

Nous nous intéressons aux processus qui consistent à satisfaire les besoins d’uti-lisateurs humains exprimés dans des environnements ouverts et distribués tels que leweb ou l’intelligence ambiante (AmI) pour rechercher des services spécifiques (ser-vice au sens fourniture de quelque chose de valeur). Ces processus sont complexes etrequièrent la collaboration de plusieurs services (logiciels). Ils nécessitent de spécifierles rôles des services impliqués, les échanges de messages entre les services jouantces rôles ainsi que les contraintes sur l’ordre d’exécution des messages. En d’autrestermes, ils requièrent la spécification d’une chorégraphie de services. Les travaux exis-tants, par exemple (Kavantzas et al., 2004), se concentrent sur le développement delangages de chorégraphie pour décrire le rôle que chaque service doit jouer dans uneinteraction lors du processus de composition. La chorégraphie, qui est collaborativeet dynamique par définition, est cependant implémentée par les travaux existants demanière statique. Dans ces travaux, les services doivent respecter les spécificationsfournies dans un document de chorégraphie décrivant les interactions et leur flot decontrôle. De plus, il n’existe pas de langage pour formuler le but de composition à sa-tisfaire puisque celui-ci est décrit par l’expert à travers les spécifications du documentde chorégraphie. Ces limites font qu’il n’y a actuellement pas de solution dynamiquepour le problème de la composition de services répondant à des besoins non préala-blement définis au travers d’un plan de composition. Nous parlerons alors en contrastede “besoins librement exprimés par l’utilisateur”.

Dans cet article, nous proposons une approche de chorégraphie dynamique danslaquelle les services collaborent de manière autonome afin d’atteindre un objectifdonné (satisfaire les besoins d’utilisateurs humains sur le web ou l’AmI). Concevoirune approche dynamique de chorégraphie de services requiert de modéliser des ca-pacités de collaboration au sein des services, et ainsi des propriétés d’adaptativité,de proactivité et d’interactivité. Ces propriétés ont en outre été largement étudiéesdans les communautés agent et multiagent. En effet, par analogie à la chorégraphiede services, la coordination entre agents autonomes est définie comme un processusd’agencement et de répartition des actions d’un système distribué en vue d’atteindre unobjectif déterminé ou d’obtenir une meilleure rentabilité des composants du système.

3

Selon (Malone et al., 1994), la coordination peut également être définie comme lagestion des interdépendances entre les activités. Ainsi, plusieurs mécanismes de coor-dination multiagent (ex. (Shehory et al., 1999), (Caillou et al., 2002), (Durfee, 1988))ont été spécifiés afin d’aider les agents à construire des solutions seuls ou en coopéra-tion avec d’autres agents. Ceci fait que les systèmes multiagent (SMA) sont particuliè-rement bien adaptés pour la modélisation des problèmes de distribution, de flexibilité,et de collaboration caractérisant la conception d’une chorégraphie dynamique de ser-vices. Dans ce contexte, l’une des récentes réflexions pour les architectures orientéesservices (SOA) consiste à substituer le noyau orienté objet des services par un noyauorienté agent (Huhns, 2002; Booth et al., 2003). Les services tiendraient alors comptedu contexte d’ouverture et de distribution de l’environnement, bénéficieraient des ca-ractéristiques de proactivité, de flexibilité et d’adaptativité des agents, et deviendraientde plus réellement interactifs. En outre, puisque les agents peuvent potentiellementparticiper à des interactions complexes tout en maintenant la coordination avec leursaccointants, les services pourraient être dotés des prérequis pour la modélisation d’unecollaboration dynamique entre services.

Pour toutes ces raisons, l’objectif de nos travaux est d’étudier concrètement l’uti-lisation du paradigme multiagent, et particulièrement les mécanismes de coordinationmultiagent, pour modéliser une chorégraphie dynamique de services. Plus précisé-ment, notre travail a pour but de définir un protocole de coordination multiagent, oùles agents peuvent raisonner sur les tâches à accomplir et les décomposer en fonc-tion de leurs compétences. Nous parlons alors d’agents introspectifs pour désigner cesagents qui ont la capacité d’observer leurs propres actions et d’en déduire s’ils sont ca-pables de prendre en charge intégralement ou partiellement une tâche. En utilisant leprotocole défini, les agents peuvent alors se coordonner entre eux afin de pallier leurslimites et couvrir les besoins librement exprimés par l’utilisateur, dans le contexted’environnements ouverts et décentralisés tels que le web et l’AmI.

La suite de cet article est organisée comme suit. Dans la section 2, nous synthéti-sons les limites des modèles de coordination existants et relevons les propriétés dontun modèle de coordination multiagent doit être doté pour supporter une chorégraphiedynamique de services. Dans la section 3, nous donnons une vue globale de notreapproche de chorégraphie et décrivons notre SOA combinant technologies agent etservices web. Nous y présentons notamment notre modèle d’agent introspectif, la for-malisation des besoins de l’utilisateur, et le langage de communication entre agents(ACL). Nous présentons dans la section 4 le protocole de coordination proposé poursupporter la chorégraphie entre services et spécifions plus particulièrement les règlesdialectiques utilisées par les agents pour traiter leurs conversations. Nous abordonsdans la section 5 les évaluations analytique et expérimentale de notre protocole en vé-rifiant d’abord les principales propriétés du protocole (terminaison, complexités cal-culatoire et de communication), et en illustrant son comportement à travers le dérou-lement d’un scénario implémenté. Enfin, nous concluons cet article en section 6 parles contributions de notre approche de chorégraphie et les travaux en perspective.

4 2 ÉTAT DE L’ART

2. Coordination d’agents & composition de services dans la littérature

Nos travaux s’intéressent à la conception d’une approche dynamique de choré-graphie de services à l’aide d’un modèle de coordination multiagent. Cette sectionprésente l’analyse des mécanismes de coordination multiagent existants appliqués auproblème de la chorégraphie de services, et souligne les propriétés souhaitées pournotre modèle.

2.1. Analyse des modèles de coordination d’agents pour la composition de services

La coordination multiagent utilise comme support des mécanismes tels que la for-mation de coalitions, la planification ou les protocoles d’interaction. Nous ne les dé-crivons pas en détail dans cette section. En revanche, nous analysons en fonction dechaque mécanisme les travaux en composition de services s’étant appuyés sur cesmodèles de coordination multiagent.

2.1.1. La formation de coalition

Plusieurs travaux exploitant les technologies SMA pour la composition de services(ex. (Ermolayev et al., 2003), (Müller et al., 2006)) proposent d’utiliser des méca-nismes de formation de coalitions (ex. (Shehory et al., 1999), (Aknine, 2000)). Parexemple, les travaux de (Müller et al., 2006) emploient un agent utilisateur qui publiedans un blackboard le but de composition à satisfaire. Ce but contient la descriptiond’un workflow générique référençant des “types” de services (ex. service de locationde voiture, d’hôtellerie, etc). Les agents-services existants, au delà d’une deadlined’inscription, récupèrent du blackboard les sous-buts à satisfaire, et procèdent à unappariement entre les types de services recherchés et les services qu’eux-mêmes pro-posent afin d’évaluer s’ils peuvent ou non contribuer à une coalition. Chaque agent-service peut ensuite proposer ou accepter la demande d’un autre agent-service pourformer une coalition. Pour qu’un nouvel agent-service rejoigne une coalition, il doitêtre sujet au vote de tous les agents-services la formant. L’approche de (Ermolayev etal., 2003) exprime les besoins à satisfaire en terme de contraintes (ex. budget=1500AC)et de préférences (ex. petit déjeuner continental). Les services sont alors composés àtravers la coalition d’agents médiateurs qui ont pour rôle de réaliser les tâches requisespar les services.

De façon générale, les agents dans les algorithmes de formation de coalitiondoivent atteindre un consensus afin que soit alloué à chacun un ensemble de tâches desorte que les préférences de chaque agent soient satisfaites. Cependant, on considèredans ces algorithmes que les tâches ont été décomposées en amont et que chaque sous-tâche obtenue est monolithique. Ainsi, ces solutions se basent sur l’hypothèse qu’ilexiste des agents capables de satisfaire intégralement une ou plusieurs des sous-tâchesà accomplir. De plus, les approches proposées utilisent des métriques d’évaluationquantitatives telles que le nombre de coalitions formées et abandonnées et négligentl’évaluation qualitative du résultat fourni par la composition de services en fonction

2.1 Analyse des modèles de coordination agent pour la composition de services 5

de besoins à satisfaire (ex. les besoins à satisfaire ont-il été intégralement satisfaits ?,quelles dépendances apparaissant dans les besoins à satisfaire ont été traitées ?, etc).

2.1.2. La planification distribuée

Les travaux en composition de services automatisent souvent le processus de com-position en le traitant comme un problème de planification (ex. (Wu et al., 2003; Tra-verso et al., 2004; Ponnekanti et al., 2002)). Par exemple, les auteurs dans (Traverso etal., 2004) effectuent la planification en commençant par traduire les descriptions desservices disponibles en systèmes d’états-transitions décrivant leurs interactions dyna-miques avec des services externes. En effet, les services disponibles étant au départdéfinis en OWL-S (Martin et al., 2004) (modèle pour la description déclarative de pro-cessus de services web), leur transformation en systèmes d’états-transitions permet deles soumettre à un moteur de planification (et ensuite pour les auteurs de comparerles performances entre une approche de composition sémantique vs. exécutable). Latâche de composition consiste alors à trouver un plan satisfaisant un but de compo-sition dans le domaine des services disponibles. Les plans générés par l’algorithmede planification sont des automates pouvant être traduits en code exécutable. L’ou-til SWORD (Ponnekanti et al., 2002) automatise la tâche de composition en utilisantdes descriptions de services basées sur les règles. L’utilisateur spécifie les faits desétats initial et final. Le planificateur tente alors de construire une chaîne de servicespouvant satisfaire ces besoins. Quant aux travaux de (Bourdon et al., 2007) et (Wu etal., 2003), ils des planificateurs de la famille HTN (Hierchical Task Network), pourla construction d’un plan global à partir des descriptions (préconditions, effets) desservices.

De façon générale, dans les méthodes de planification distribuée (Georgeff, 1990;Durfee, 2001), et en particulier dans la planification multiagent orientée tâche, onconsidère une tâche globale qu’un agent manager décompose en sous-tâches qui sontallouées à un ensemble d’agents coopératifs capables de les réaliser. Dans ce modèle,la coordination des sous-tâches (et des agents) est effectuée à travers le plan de l’agentmanager. Cependant, la disponibilité des agents capables d’exécuter une sous-tâchen’est jamais garantie. En conséquence, plusieurs itérations pour décomposer et distri-buer la tâche globale peuvent ainsi être nécessaires avant que les sous-tâches obtenuesne correspondent aux capacités d’agents existants, et que les agents n’exécutent réel-lement le plan. Finalement, dans ce modèle de coordination, aucune hypothèse n’estfaite sur la manière dont les agents coopératifs vont réaliser leur(s) sous-tâche(s).D’autres approches de planification, dites de partage de résultats, suggèrent de de-mander au programmeur de fournir la description du workflow (Osman et al., 2005).Cependant, même si elles ont un coût réduit, ces stratégies demeurent statiques etconduisent à des solutions ad-hoc qui dépendent fortement de l’application. Enfin,les approches se basant sur la planification HTN (Hierchical Task Network) utilisentune planification qui en fait est très puissante pour les domaines où la connaissanceest complète et détaillée, ce qui n’est pas le cas avec les services web, comme l’ontdémontré Klush et al. dans (Klush et al., 2005).

6 2 ÉTAT DE L’ART

2.1.3. Les protocoles d’interaction

À notre connaissance, il n’existe pas de protocole d’interaction spécifiquementconçu pour le problème de la composition de services. Les travaux qui s’en rap-prochent sont par exemple ceux de (Paurobally et al., 2005) qui transcrivent, pourla négociation entre services, le protocole Rubinstein (Rubinstein, 1982) (alternantproposition et contre-proposition) dans la description XML des services, ou encorele protocole WS-Agreement (Andrieux et al., 2004) qui spécifie des conversations àdeux étapes, une offre suivie d’un accord, pour l’établissement de contrats et d’accordsentre un service fournisseur et un consommateur.

De manière générale, les protocoles d’interaction existants (Rubinstein, 1982;FIPA, 2001) supposent également que les sous-tâches à réaliser sont monolithique (ouatomiques), c’est-à-dire que chaque agent peut soit intégralement exécuter la tâchedemandée ou ne pas l’exécuter. Cela limite leur application dans la composition deservice dans le mesure où la décomposition et la répartition du but global de com-position doit s’effectuer sur la base des fonctionnalités disponibles et non en amont(Ermolayev et al., 2003). En effet, le CNP (Contract Net Protocol) par exemple estun protocole simple où un agent manager envoie un cfp (call for proposal) aux agentsparticipants qui peuvent soit accepter soit refuser de réaliser l’intégralité de la tâche.De plus, il néglige les stratégies possibles de raisonnement sur les capacités des agentsparticipants. C’est la raison qui fait que ce protocole n’est appliqué que dans des pro-blèmes où les tâches à accomplir sont bien définies et décomposées.

2.2. Discussion

Les travaux du domaine ont relevé plusieurs problématiques à prendre enconsidération pour le développement d’une approche de composition de services(Chakraborty et al., 2001), (Austin et al., 2004). Il s’agit notamment de la décou-verte de services, la gestion et la coordination des services, l’infrastructure d’échanged’information, la tolérance aux fautes et le passage à l’échelle, et l’adaptativité. Enparticulier, la découverte de services efficace devrait permettre de trouver tous lesservices se conformant à une fonctionnalité donnée, indistinctement de la façon del’invoquer. C’est la raison pour laquelle des modèles tels que OWL-S et WSMO ontété proposés pour la description uniforme de services web sémantiques, moyennantun langage sémantique. Une bonne architecture de découverte de services devrait êtrecapable d’effectuer un raisonnement sur la description des services afin de trouverles services appropriés. Or, certaines propriétés recherchées peuvent être absentes ouencore non nécessairement exprimées, dans l’interface publique ou sémantique d’unservice, de la même manière que la formulation des besoins à satisfaire. Ceci ne de-vrait pas exclure la sélection du service puisque c’est là que l’adaptativité des serviceset la coordination entre services interviennent. Chaque service pourrait en effet dé-composer les tâches demandées sur la base de ses fonctionnalités et se coordonneravec ses pairs pour l’obtention des informations ou fonctionnalités requises pour laréalisation de l’intégralité de sa tâche.

7

Lorsque l’on confronte ces besoins pour le développement d’une approche de com-position de services à l’analyse des modèles de coordination multiagent existants, ilapparaît finalement que la principale limite de leur application au problème de la cho-régraphie dynamique de services s’inscrit dans l’hypothèse faite sur les tâches à satis-faire. On suppose que celles-ci sont décomposées en amont de la coordination alorsque, au contraire, la tâche à accomplir devrait pouvoir être décomposée sur la basedes fonctionnalités disponibles (en sous-tâches interdépendantes en terme d’exécu-tion), et non en amont de la découverte et la coordination des services (Ermolayev etal., 2003). Cela nécessite que les agents puissent, avant tout, accéder à leurs donnéeset leurs actions afin de raisonner dessus et déterminer si une tâche est complexe etnécessite ainsi le concours d’autres agents pour son accomplissement. Or, les plate-formes de développement d’agents actuelles, telles que JADE (JADE, 2004) ou JACK(JACK, 1999), ne permettent aux agents d’accéder à leurs actions (préconditions eteffets) et leur état courant (actions valides, données). De plus, les ACLs actuels (Fininet al., 1992; FIPA, 2001) ne permettent pas d’exprimer des questions ou des assertionsà propos des capacités des agents (McBurney et al., 2002; Berger et al., 2005). Enfin,les protocoles d’interaction existants (FIPA, 2001; Rubinstein, 1982) ne prennent pasen compte des dépendances entre différentes sous-tâches issues de la décompositiond’une tâche globale.

En conséquence, même s’ils constituent un paradigme adapté pour traiter les pro-blèmes de distribution, d’ouverture et de flexibilité de l’environnement des servicesweb, les modèles de coordination existants ne suffisent pas en l’état à couvrir le pro-blème de la chorégraphie de services. C’est là que nos travaux interviennent. Nousavons pour objectif de proposer un modèle de coordination orienté tâche, i.e. danslequel le but est défini de manière globale (typiquement, les besoins de l’utilisateur).Dans cette optique, nous voulons concevoir un protocole d’interaction, fondé sur desagents capables d’observer leurs actions, de raisonner dessus, et d’interagir à pro-pos de besoins librement exprimés par l’utilisateur et de leurs capacités propres. Cesagents peuvent ainsi prendre dynamiquement part à la décomposition d’une tâche àrésoudre et de se coordonner avec d’autres agents afin de pallier leurs limites et ainsiadéquatement couvrir l’intégralité de la tâche demandée. Nous présentons dans ce quisuit l’architecture, combinant technologies agent et services web, ainsi que les agentsintrospectifs sur lesquels s’appuie notre approche, et nous spécifions le protocole decoordination supportant l’approche de chorégraphie dynamique de services.

3. Architecture orientée services basée sur un SMA

Nous décrivons dans cette section notre architecture combinant services web etSMA. Pour ce faire, nous donnons d’abord un aperçu général de notre approche dechorégraphie et de la structure en couches des agents offrant des services de notrearchitecture. Nous explicitons alors plus amplement celle-ci par la formalisation desbesoins de l’utilisateur et la description des couches de connaissance et de communi-cation des agents introspectifs qui composent notre architecture.

8 3 ARCHITECTURE ORIENTÉE SERVICES BASÉE SUR UN SMA

Figure 1. Vue d’ensemble de l’approche de chorégraphie.

3.1. Vue d’ensemble de l’architecture développée

Notre travail a pour objectif de proposer une approche décentralisée, dynamique etautomatique de chorégraphie de services. Comme l’illustre la figure 1, notre approchese déroule en quatre principales étapes (dans cet article, seulement la première et latroisème sont détaillées) :

1) D’abord, un utilisateur humain formule ses besoins à une entité médiatrice (sousforme d’interface graphique). Ces besoins incluent des questions sur des données (ex.quelle est la résolution de l’appareil photo ?) et/ou des commandes d’action (ex. enre-gistre ce programme, achète l’appareil photo) ainsi que des contraintes globales (ex.sur un prix global).

2) Un module de découverte de services extrait ensuite des mots-clés de la requêtede l’utilisateur pour découvrir des services candidats à la composition. Ceux-ci sontrecherchés à partir d’un registre en ligne de services web.

3) Les services candidats tentent alors de satisfaire cette requête en s’envoyant desmessages. C’est la phase de chorégraphie de services. Leurs interactions sont régiespar un protocole de coordination que nous présentons dans la section 4.

4) Enfin, l’ensemble des services ayant collaboré pour satisfaire les besoins del’utilisateur sont proposés à ce dernier, ainsi que leur réponse. Ceci sous conditionsque les services et leur réponse satisfassent les contraintes globales énoncées par l’uti-lisateur. Une entité médiatrice, que nous appellerons plus tard l’agent de l’utilisateur,se charge de cette sélection.

Afin d’implanter cette approche de chorégraphie, notre architecture envisage unservice, tel que dans la recommandation du W3C (Booth et al., 2004), comme une en-tité abstraite devant être implémentée par un agent concret. Nos agents sont composésde trois couches principales :

La couche de connaissance qui inclut une base de données et un ensemble d’actions.Celles-ci peuvent être encapsulées dans un service déployable et publiable surle web. C’est pourquoi nous parlons d’agent offrant un service.

3.2 Couche de connaissance : Modèle et connaissances des agents introspectifs 9

La couche de communication permet le transport des messages. C’est un ACL quigère cette couche de l’agent et qui structure les messages construits par celui-ci.Par ailleurs, notre architecture génère à partir du code des agents une interfaceWSDL leur permettant de communiquer sur le web via le protocole de trans-port standard SOAP (ceci en transcrivant en XML les messages exprimés dansl’ACL et en les encapsulant dans des enveloppes SOAP).

La couche de traitement des requêtes et gestion du protocole permet à l’agent detraiter les messages reçus en fonction de ses compétences et des précédentsmessages échangés.

À travers cette structure, les agents peuvent offrir un ensemble de fonctionnalitésou services, via leur couche de connaissance. Dans ce qui suit, nous décrivons lescapacités d’introspection et de raisonnement des agents sur lesquels s’appuie notreapproche de chorégraphie ainsi que leur apport dans celle-ci.

3.2. Couche de connaissance : Modèle et connaissances des agents introspectifs

Le langage dans lequel les agents de notre architecture sont écrits est appelé VDL-XML (Sabouret et al., 2003). Il permet d’associer à chaque agent un arbre (définissantles données et les actions de l’agent) réécrit à chaque cycle d’exécution et mettant ainsià jour l’état de l’agent (ses données et actions). Ce dernier peut donc à tout instant ac-céder aux actions possibles et impossibles et procéder par la suite à un raisonnement.C’est la raison pour laquelle ces agents sont dits introspectifs. Formellement, les don-nées et les actions d’un agent sont définies comme suit :

3.2.1. Données

Soit F l’ensemble de symboles d’attributs, tels que prix, réference, durée, etc. Labase de données d’un agent introspectif est un ensemble D = {d1, d2, . . . , d|D|} oùchaque donnée d ∈ D est un ensemble de valeurs associées aux attributs.

NOTATION. Nous notons equal(f, d, value) le fait qu’un attribut f ∈ F de la donnéed ∈ D ait la valeur value. La donnée d est ainsi caractérisée par :

∧ni=1equal(fi, d, valuei) [1]

Par exemple, si un agent fournit un service de vente d’appareils photonumériques, il pourrait avoir dans sa base de données l’appareil photoc caractérisé par : equal(type, c, camera) ∧ equal(trademark, c, canon) ∧equal(reference, c, EOS40D).

3.2.2. Actions

En plus d’une base de données, les agents sont munis d’actions définissant lesservices qu’ils offrent. Chaque action d’un agent est définie par un tuple A =〈name, P,E〉 où :


– name est le nom de l’action (ex. enregistrer programme télé) ;– P est un ensemble de préconditions ;– E est un ensemble d’effets. Ceux-ci représentent des modifications à effectuer

sur les données de l’agent et/ou des interactions avec d’autres agents.

Dans notre modèle, les capacités d’introspection ainsi que la coordination dyna-mique des agents sont centrées sur les préconditions P seulement dont nous distin-guons deux types exclusifs : (1) Les patrons d’évènements décrivent les évènementsqui déclenchent une action et ont pour rôle de spécifier le format autorisé des évè-nements déclenchant l’action en question ; (2) Les conditions de garde sont des ex-pressions booléennes qui doivent être vérifiées pour que l’action soit exécutée (ex.température < 25˚C).

3.2.3. Fondements de l’introspection

Les capacités introspectives des agents s’appuient sur les préconditions de typepatron d’évènement. Chaque patron d’évènement a la forme E(f1, . . . , fn) où E estle nom de l’évènement et chaque fi ∈ F est un symbole d’attribut, tel que :∀i 6= j, fi 6= fj (c’est-à-dire que les symboles d’attributs dans l’évènement E sonttous différents). Nous parlerons des fi comme d’attributs attendus par l’agent pourdéclencher l’action dont le patron d’évènement E(f1, . . . , fn) est la précondition.

NOTATION. Les évènements qu’un agent introspectif reçoit ont la formeE(p1, ..., pm). Chaque paramètre pk est une variable renseignant les valeurs d’un ouplusieurs attributs fj déclarés dans un patron d’évènement. Ainsi, un paramètre p estdéfini par :

p = ∧lj=1equal(fj , x, valuej) [2]

Par exemple, une action acheter produit dont le patron d’évènement estBuy(ref, iban, adr) peut être déclenchée si l’agent reçoit l’évènement suivant :Buy(equal(ref, x, E31X ), equal(iban, y, 678) ∧ equal(adr, y, Paris)) fournissantainsi la référence du produit (x) et le numéro du compte en banque ainsi que l’adressede l’acheteur (y).

Détection d’attributs manquants

Dans le cas où les noms des évènements dans un patron d’évènement et un évène-ment reçu sont identiques, et que l’ensemble des attributs renseignés Fr ne couvre pasl’ensemble des attributs attendus Fa, l’agent peut calculer l’ensemble des attributsmanquants {Fa − Fr}, i.e. ce sont les attributs attendus pour exécuter une action etqui n’ont pas été renseignés à travers les paramètres reçus.

La construction de cet ensemble permet à un agent de décomposer et de s’allouerdynamiquement les tâches à réaliser en fonction de ses compétences. Ainsi, si l’onconsidère que l’exécution d’une sous-tâche débouche sur la provision de la valeur

3.3 Couche de communication : Besoins de l’utilisateur et modèle de requêtes 11

d’un ou plusieurs attributs, la capacité d’introspection décrite permet alors à l’agentd’informer ses pairs de ce qu’il est capable d’accomplir au niveau d’une tâche glo-bale, ainsi que des sous-tâches qui doivent être nécessairement réalisées par les autresagents (ou attributs manquants) pour qu’il puisse exécuter sa propre sous-tâche. Nousprésentons ce mécanisme en section 4.

3.3. Couche de communication : Besoins de l’utilisateur et modèle de requêtes

Les besoins de l’utilisateur ainsi que le contenu des messages échangés entre lesagents de notre SOA sont formalisés moyennant le modèle de requêtes présenté ci-après. Nous spécifions la syntaxe et la sémantique de ce modèle et définissons la for-malisation des besoins de l’utilisateur.

3.3.1. Modèle de requêtes

Une requête r est une paire : rdef= 〈α, γ〉 où α est un performatif et γ est le contenu

(ou l’objet) de la requête1. Le performatif α de la requête peut ainsi prendre les valeurssuivantes :

– What-is : pour les requêtes qui représentent les questions à propos des donnéesde l’agent. ex. « Quelle est la durée du vol LH710 ? ».

– Assert-is : pour les assertions à propos des valeurs des données de l’agent (enréponse aux requêtes What-is). ex. « La durée du vol LH710 est de 12 heures ».

– Order : pour commander l’exécution d’une action étant donné un ensemble deparamètres (envoyé à travers un évènement). ex. « Livre le piano à Monzen-Nakacho ».

– Ack : pour les confirmations d’exécution d’actions (en réponse aux requêtesOrder). ex. « Livraison à Monzen-Nakacho effectuée ».

– Assert-cannot : pour exprimer qu’un agent est incapable d’exécuter une action.ex. « Je ne fais pas de livraison ».

– Assert-can : pour exprimer qu’un agent peut exécuter une commande, moyen-nant certains paramètres. ex. « Je peux effectuer la livraison, mais il me faut l’adresseexacte de livraison ».

– Unknown : pour exprimer que l’agent n’a pas la ressource demandée. ex. « Jen’ai pas de programme télé ».

– Missing : pour communiquer les attributs que l’agent n’a pas pu interpréter. Parexemple, un agent peut recevoir la commande « Réserve une chambre d’hôtel auxdates de la conférence MFI’08 » qui dépend du résultat de la sous-requête « Quellessont les dates de la conférence MFI’08 ». L’agent peut alors répondre « Je ne connaispas les dates de la conférence MFI’08 » en utilisant le performatif Missing.

1. Par analogie à la théorie des actes de langage (Searle, 1969), le performatif α peut être assi-milé à l’acte illocutoire, et le contenu de la requête γ au contenu propositionnel.


α γ

What-is selections | C′

Assert-is D′

Missing selectionsUnknown F ′

Order E(p1, ..., pm)Ack

Assert-cannot EAssert-can E,F ′

Tableau 1. Syntaxe du modèle de requêtes.

Le tableau 1 reporte pour chaque perfomatif α le contenu de la requête γ corres-pondant, sachant que :

• selections est un ensemble d’expressions f(x) où f est un symbole d’attribut(comme prix, durée) et x une variable. Tout comme dans SQL, on peut utiliser pourles requêtes What-is le mot clé ∗ au lieu de l’attribut f pour obtenir tous les attributsà propos d’une donnée dans la base de données.• C′ ⊂ C est un ensemble de contraintes composé d’une conjonction de

op(f, x, value) où op est un symbole de prédicat canonique tel que op ∈{equal, greater, less} et :

- equal(f, d, value) est vraie ssi f(d) = value ;- greater(f, d, value) est vraie ssi f(d) > value ;- less(f, d, value) est vraie ssi f(d) < value.

Ainsi, le prédicat op est utilisé dans l’expression des contraintes dans les requêtesWhat-is. Lorsque sa valeur est à equal, on le retrouve dans l’expression des attributsdéfinissant une donnée (c.f. équation 1) et les paramètres d’un évènement (c.f. équa-tion 2).• D′ ⊂ D est un ensemble de données et F ′ ⊂ F un ensemble d’attributs.

Pour des raisons de lisibilité, nous adoptons la notation α(γ) pour écrire les requêtes.

Exemple. La requête « Je peux réserver, mais il me manque la date de départ »s’écrira : Assert-can(Book, checkOut-date).Ou encore la requête « Quelles sont les informations relatives au vol LH710 » s’écrira :What-is(∗(x)|equal(flight-num, x, LH710)).

3.4 Couche de communication : Langage de communication entre agents (ACL) 13

Dépendances entre requêtes

Dans le cas des requêtes What-is et Order, le traitement peut dépendre de la résolu-tion d’autres requêtes. Pour formaliser ces dépendances entre requêtes, nous adoptonsla notation suivante :

g(request-get)

tel que g est un symbole d’attribut, et request-get représente une valeur pour g qui estobtenue suite à la résolution d’une autre requête. On parle alors de sélection indéfinie.

En effet, si une contrainte d’une requête What-is ou le paramètre d’une requêteOrder comporte l’expression g(request-get), alors la requête en question est dépen-dante de celle qui fournira la valeur de l’attribut g.

Exemple. Soit la requête r=What-is(memoCard-ref(x)|equal(type, x, memo-card)∧ greater(storage-capacity, x, 1Go)∧ equal(compliant-with, x, camera-ref(request-get))).

Cette requête demande la référence d’une carte mémoire dont la capacité de stockagedoit être supérieure à 1Go et dont le modèle doit être compatible avec la référenced’un appareil photo devant être obtenue par la résolution d’une des requêtes de l’utili-sateur. En conséquence, cette requête est dépendante de celle qui fournira la valeur del’attribut camera-ref .

3.3.2. Besoins de l’utilisateur

La coordination des agents a pour but de satisfaire un ensemble de besoins énoncéspar l’utilisateur que nous formalisons par la paire Υ def= 〈R, C〉 où :

– R est un ensemble de requêtes telles que définies précédemment. Dans notre mo-dèle, les requêtes de l’utilisateur seront uniquement composées de requêtes What-iset de commandes Order.

– C un ensemble de contraintes globales sur les services demandés. Chaquecontrainte c ∈ C est une expression booléenne sur les résultats fournis par deux ouplusieurs services (ex. le prix d’achat et de livraison ne doit pas dépasser 70AC).

3.4. Couche de communication : Langage de communication entre agents (ACL)

Le langage utilisé par les agents dans notre architecture pour communiquer estcompatible avec l’ACL de FIPA. Néanmoins, pour des fins de facilités syntaxiqueset pour atteindre plus facilement nos objectifs, nous avons introduit dans notre ACLdes performatifs de plus haut niveau (ex. Assert-can, Missing) supportant la chorégra-

14 4 PROTOCOLE DE COORDINATION DYNAMIQUE MULTIAGENT

Figure 2. Vue globale du comportement du SMA.

phie dynamique. Cet ACL est appelé VDL-ACL (Charif et al., 2004) et structure lesmessages comme suit :

m = [ sender,receiver,conv-id,reply-with,in-reply-to,req-id,content ]

[3]

Cette structure, similairement aux messages KQML (Finin et al., 1992) et FIPA-ACL, comprend des niveaux contenu et de communication2. Les messages VDL-ACLont ceci de particulier que le performatif est dans le contenu du message, ce contenuétant un ensemble ordonné C = {r1, r2, . . .} de requêtes. Un message VDL-ACLprécise par ailleurs l’identifiant conv-id de la conversation dans laquelle un agent estimpliqué, l’identifiant reply-with du message auquel le message construit répond,et inscrit dans un tableau req-id l’identifiant des requêtes de l’utilisateur auxquellescelles construites dans C répondent.

4. Protocole de coordination pour la chorégraphie dynamique de services

Nous avons précédemment décrit l’architecture orientée services basée sur unSMA sur laquelle notre approche de chorégraphie s’appuie. Dans cette section, nousspécifions le protocole de coordination supportant notre approche dynamique de cho-régraphie de services. Ce protocole, qui tient compte de la décomposition dynamique

2. Puisque nous nous focalisons sur la spécification du protocole, nous n’avons pas traité desproblèmes d’intercompréhension que l’on peut usuellement résoudre via des ontologies. C’estla raison pour laquelle le champ sur l’ontologie utilisée n’apparaît pas dans notre ACL.

4.1 Aperçu général 15

des tâches et des dépendances apparaissant entre elles, permet aux agents de se coor-donner de manière décentralisée et distribuée afin de satisfaire les besoins complexesexprimés par l’utilisateur.

4.1. Aperçu général

4.1.1. Rôles des agents

Comme illustré par la figure 2 le protocole de coordination utilisé par les agentsspécifie deux rôles possibles : (1) Agent participant qui est le rôle d’un agent impli-qué dans la coordination, et qui a pour objectif d’interagir avec d’autres agents pourrépondre aux besoins à satisfaire ; (2) Agent de l’utilisateur qui est principalement encharge d’intergir avec l’utilisateur et de diffuser ses requêtes aux agents participants.

Definition 1 On dit qu’un agent a résolu une requête dès qu’il a réussi à construire,pour une requête reçue What-is ou Order, une requête réponse de performatifAssert-is, Ack, Unknown ou Assert-cannot. On dit qu’il l’a satisfaite si la réponseconstruite est de performatif Assert-is ou Ack. Son rôle se termine dès lors qu’il arésolu toutes ses requêtes.

4.1.2. Trace des interactions

Les agents dans notre SMA interagissent et se coordonnent en fonction desmessages reçus et de ceux qu’ils se sont précédemment échangés. Pour ce faire,chaque agent est muni d’une table d’historique. Une table d’historique associéeà un agent a, notée ~a, est un ensemble d’enregistrements, chacun étant dédié àune conversation. Pour un agent, un enregistrement d’une conversation est défini par∇ def= (id,m0,M,U) tel que :

– id est l’identifiant de l’enregistrement (ou de la conversation dans laquellel’agent est impliqué). Il correspond à la valeur du champ conv-id des messages im-pliqués dans l’interaction3.

– m0 est le message envoyé à tous les participants pour initier la conversation. Ilcontient les besoins de l’utilisateur à satisfaire et est appelé message initiateur.

–M est l’ensemble de messages que l’agent a envoyés et reçus durant la conver-sation.

– U est l’ensemble de réponses finales, construites par l’agent, devant êtreenvoyées à l’agent de l’utilisateur. Chaque réponse finale est un ensemble{ρ1j

, . . . , ρ|R|j} contenant pour chaque requête ri de l’utilisateur une résolution ρij

(ex. il peut proposer dans ρij un appareil photo Canon, et dans ρij′ un Sony).

3. Un message construit en réponse à un autre a la même valeur du champ conv-id. En consé-quence, les messages échangés pour la résolution d’un même ensemble de besoins ont le mêmeidentifiant conv-id.


Chaque fois qu’un agent reçoit ou envoie un message, il stocke, met à jour ouconsulte, dans sa table d’historique, l’élément approprié de l’enregistrement corres-pondant. Par ailleurs, il envoie un message réponse à l’agent de l’utilisateur lorsqu’ila collecté au moins une réponse finale dans U (i.e. une résolution pour chacune desrequêtes de l’utilisateur).

4.2. Spécification du protocole de coordination

Dans un protocole d’interaction, les agents doivent s’accorder sur les séquencesde messages possibles et sur leur contenu (Greaves et al., 2000). Ainsi, un protocoled’interaction est un ensemble de règles dialectiques4 plus ou moins génériques para-tagées par les agents et régissant le traitement de leurs conversations.

Dans cette section, nous présentons graphiquement les règles par des microproto-coles en utilisant AUML (extension des diagrammes de séquence UML 2.0) (Bauer etal., 2005).

4.2.1. Calcul de l’ensemble des agents destinataires ℵ

Lorsqu’un agent construit un message, il calcule systématiquement l’ensemble ℵdes agents auxquels le message doit être envoyé. Il procède comme suit.

Soit un agent a recevant un message m et ~a sa table d’historique. Soit ∇ l’en-registrement dédié à la conversation relative à m, dont m0 est le message initiateur,tel que : ∇ = (id,m0,M,U). Pour chaque requête ρi construite en réponse à unerequête ri de m, l’agent doit calculer l’ensemble ℵ des agents auxquels ρi doit êtreenvoyée :

– Si ρi est une requête Missing, Assert-can ou What-is alors elle doit être envoyéeà tous les agents participants5 pour que ceux-ci tentent de trouver les informationsdemandées.

Par exemple, si la requête reçue ri est une requête What-is demandant des infor-mations à propos d’une carte mémoire devant être compatible avec un appareil photorecherché à travers une autre requête, l’agent construit une réponse ρi de performatifMissing signifiant que la requête reçue ri présente des dépendances et que l’agent,pour la résoudre, a d’abord besoin des informations concernant l’appareil photo. Lesdestinataires de la réponse construite ρi (de type Missing) sont alors tous les agentsparticipants afin que ceux-ci tentent de fournir les informations manquantes ;

4. Une règle dialectique spécifie quels messages sont admis pour un état donné de l’interaction(Koning, 2007).5. Les identités de ces agents sont mémorisées dans un registre local après leur découverte dansun registre public.

4.2 Spécification du protocole de coordination 17

– Si la réponse construite ρi est une requête Assert-is, Assert-cannot, Ack ouUnknown, et qu’elle répond à une requête du message initiateur6, alors elle est consi-dérée comme une résolution à une des requêtes de l’utilisateur. En conséquence, elleest stockée dans la table d’historique dans l’élément U de l’enregistrement corres-pondant à la conversation. Lorsque l’agent aura collecté une réponse finale dans U(contenant des résolutions ρi), il l’envoie à l’agent de l’utilisateur à travers un mes-sage réponse (contenant les résolutions ρi) ;

– Sinon, la requête doit être envoyée seulement à l’agent émetteur de m.

4.2.2. Les règles dialectiques

Lorsqu’un agent reçoit un message, il traite en fait un ensemble de requêtes dontles performatifs sont dans {What-is, Order, Unknown, Missing, Assert-is, Assert-can,Assert-cannot, Ack}. Les situations rencontrées par l’agent, ainsi que leur gestionsuivant les règles dialectiques de notre protocole, sont ainsi résumées :

– Si la requête reçue est What-is ou Order, l’agent répond suivant ses connais-sances et ses compétences par des requêtes de performatifs Assert-is, Unknown, Ack,Assert-cannot, Assert-can ou Missing.

– Si la requête reçue est Missing(selections) ou Assert-can(E,F ′), l’agent re-cherche dans sa table d’historique si une assertion à propos des selections indéfiniesou des attributs manquants F ′ a été reçue.

– Si l’agent reçoit une assertion Assert-is, il vérifie dans sa table d’historique si elleétait attendue ou pas, i.e. s’il a précédemment envoyé une requête What-is, Missing ouAssert-can, et s’il peut alors l’exploiter pour (re)tenter de satisfaire une requête nonrésolue.

– S’il reçoit une requête Unknown, c’est qu’il a sollicité des informations auprèsd’autres agents pour une certaine requête. Dans ce cas, il doit vérifier s’il doit endéduire qu’il est finalement incapable de la satisfaire ou s’il lui manque des donnéesà solliciter auprès de l’utilisateur.

Nous montrons dans ce qui suit la contribution de notre approche par la spécifi-cation détaillée d’une règle dialectique (celle pour le traitement des requêtes Order).Nous donnons le principe général pour toutes les autres7.

Requêtes Order

Lorsqu’un agent reçoit une commande Order(E(p1, p2, . . .)), où E est un nomd’évènement et pk des paramètres, il procède suivant le microprotocole de la fi-gure 3.(a), dont le fonctionnement est détaillé dans l’algorithme 1. Ainsi :

1) il construit la confirmation d’exécution Ack(E(p1, p2, . . .)) si :

6. Ceci peut être vérifié à travers les valeurs des champs reply-with et in-reply-to desmessages impliqués.7. Le lecteur trouvera les spécifications intégrales dans (Charif, 2007).


Algorithm 1 Traitement des commandes Order.ENTRÉES: m le message reçu ; r = 〈Order, E(p1, . . . , pm)〉 la requête à traiter ; ~

la table d’historique de l’agent et∇ l’enregistrement de la conversation ;SORTIES: ρ la requête réponse construite.

1: store(m, ~) ;2: si known(E) alors3: si {Fa −Fr} = ∅ alors4: si getActionEffects(E) = S alors5: ρ← 〈Ack, E(S)〉 ;6: sinon ρ← 〈Ack, E(p1, ..., pm)〉 ;7: sinon si {Fa −Fr} = F ′ alors8: si |{pk}k| = 1 alors9: ρ← 〈What-is, {fi(var)}i6|F ′| | p1〉 ;

10: sinon ρ← 〈Assert-can, E,F ′〉 ;11: sinon si ∃pk et g(request-get)∝ pk alors12: ρ← 〈Missing, g(request-get)〉 ;13: finsi14: sinon15: ρ← 〈Assert-cannot, E〉 ;16: finsi17: Rechercher des connaissances dans ∇ si performative(ρ) ∈{Missing,Assert-can,What-is} ;

- il reconnaît l’évènement E, i.e. l’évènement E apparaît dans la préconditionE(f1, f2, ...) d’une des actions de l’agent (fonction known dans l’algorithme 1) ;

- et que tous les attributs attendus ont été renseignés à travers pk, i.e. les para-mètres pk sont des conjonctions d’attributs-valeurs incluant les attributs attendus parla précondition de l’action déclenchée ({Fa −Fr} = ∅ dans l’algorithme 1) ;

2) il construit la réponse Missing(g(request-get)), où g est un symbole d’attribut,si un des paramètres pk de l’évènement est exprimé en fonction de g(request-get).Dans l’algorithme 1, ceci est représenté par l’expression g(request-get)∝ pk ;

3) il répond par Assert-cannot(E), s’il ne reconnaît pas l’évènement E ;4) s’il reconnaît l’évènement E, et s’il détecte des attributs manquants, il procède

à la décomposition de la commande Order comme le décrit la section suivante.

Exemple. Soit un agent convertisseur Euro-Yen recevant l’ordre de convertir100AC à travers la requête Order(ConvertEuroY en(equal(amount, x, 100AC))).Si l’agent traite la commande et qu’aucun message n’est envoyéà l’issue de l’exécution de l’action, l’agent construit la réponse :Ack(ConvertEuroY en(equal(amount, x, 100AC))). L’agent peut égalementenvoyer le résultat de la conversion si son action a pour effet d’émettre un messagecontenant le résultat (représenté par S dans l’algorithme 1). La réponse construiteserait alors : Ack(ConvertEuroY en(equal(converted, x, 16500U))). Si l’agent


n’avait pas reconnu l’évènement ConvertEuroY en, sa réponse aurait été :Assert-cannot(ConvertEuroY en).

Currification des requêtes Order

Lorsque l’agent reçoit une commande Order(E(p1, p2, . . .)), qu’il reconnaîtl’évènement E mais ne s’est pas vu fournir les valeurs des attributs manquantsF ′ = {f1, f2, . . .} (cas 4 précédemment énuméré), alors il construit la réponseAssert-can(E,F ′).

Si l’évènement ne comporte qu’un seul paramètre p, l’agent peut tenter de re-trouver les valeurs des attributs manquants en exploitant ceux qu’il a reçus, tel quel’illustre le microprotocole de la figure 3.(b). Dans nos travaux, ce traitement n’esteffectué que sur les requêtes à un seul paramètre, ceci pour éviter des problèmesd’explosion combinatoire. Pour retrouver les valeurs d’attributs manquants, l’agentconstruit la requête : What-is(f1(v), f2(v), ...| p) où {f1, f2, . . .} = F ′ sont les at-tributs manquants, p est le paramètre de la commande reçue, et v la variable utiliséedans l’expression du paramètre p.

En conséquence, lorsqu’un agent ne peut exécuter intégralement une commande, ilpeut la décomposer en construisant des requêtes What-is afin de retrouver les attributsmanquants. Une fois les valeurs de ces attributs retrouvées ou calculées, elles sontutilisées pour traiter la commande originale Order. Nous appelons currification cetteprocédure par analogie à celle du lambda calcul.

Exemple. Soit Order(Record(equal(title, x, Desperate Housewives)) la com-mande envoyée à un agent pour lui demander d’enregistrer le programme télé dont letitre est Desperate Housewives. Supposons que cet agent soit muni d’une actiondont la précondition est le patron d’évènement : Record(channel, duration, time).L’agent nécessite ainsi les valeurs des attributs channel, duration et time pour dé-clencher son action. Afin de retrouver les valeurs des attributs attendus, en exploitantcelles des attributs reçus (title), l’agent construit la requête :What-is(channel(x), duration(x), time(x)| equal(title, x, Desperate Housewives).À cette requête, l’agent tente d’abord lui-même d’y répondre. S’il échoue, il la diffusealors à ses accointants.

Requêtes What-is

Lorsqu’un agent reçoit une requête What-is(selections|constraints), il la traitecomme suit :

– Si les contraintes de la requête sont vérifiées dans la base de données de l’agent,i.e. il existe des données D′ qui satisfont les contraintes de la requête, alors l’agentconstruit l’assertion Assert-is(D′) ;

– Si selecs est un ensemble de sélections indéfinies dans les contraintes de la re-quête, alors l’agent construit la réponse Missing(selecs) ;


Figure 3. Protocoles pour (a) le traitement des requêtes Order ; (b) la décomposition(currification) des requêtes Order.

– Autrement, si les contraintes ne sont pas vérifiées dans la base de données del’agent, il construit la réponse Unknown(*).

Le traitement des requêtes What-is est représenté par le microprotocole de la fi-gure 4.(a).

Exemple. Notre précédent agent construit la requêteWhat-is(channel(x), duration(x), time(x)| equal(title, x, DesperateHousewives))pour rechercher les attributs channel, duration et time lui faisant défaut.Il l’envoie à ses accointants parmi lesquels se trouve un agent télévisionpossédant un télétexte. Si cet agent possède un programme répondant à lacontrainte equal(title, x, DesperateHousewives), alors il enverra une réponseAssert-is(equal(channel, d, 6),equal(duration, d, 45min),equal(time, d, 20h50)).Sinon, il envoie la réponse Unknown(*).

Requêtes Missing

Si un agent reçoit un message contenant une réponse Missing(g(request-get)), ilrecherche un message mémorisé dans sa table d’historique contenant une requête ρk

où : (1) ρk est une assertion telle que ρk =Assert-is(D′) ; (2) ∃d ∈ D′ telle que g ∝ d.

Cela veut dire que l’agent aura à trouver dans sa table d’historique une assertiondans laquelle la valeur de l’attribut g est définie. S’il trouve une telle assertion, alors


il construit une réponse Assert-is(D′′) où D′′ = {equal(g, dk, valuek)}k∈N représenteles expressions définissant les valeurs de l’attributs requis g. Sinon, l’agent construitla réponse Unknown(*).

Le traitement des requêtes Missing est représenté par le microprotocole illustré surla figure 4.(b).

Exemple. Considérons un utilisateur qui envoie une requête pour recher-cher un appareil photo r1=What-is(camera-ref |equal(type, x, camera) ∧...) et une autre pour rechercher une carte mémoire compa-tible r2=What-is(memoCard-ref(x)|equal(type, x, memo-card) ∧equal(compliant-with, x, camera-ref(request-get))). Un agent acces-soire recevant la requête r2 renverrait à ses accointants la requêteMissing(camera-ref(request-get)) signifiant qu’il nécessite la valeur de l’attributdépendant camera-ref . Supposons qu’un agent PhotoSon&Vidéo ait reçu et résolur1. Selon la précédente règle dialectique, en recevant la requête Missing envoyée parl’agent accessoire, il enverrait la réponse Assert-is(equal(camer-ref, c, EX321))(gràce à laquelle l’agent accessoire pourrait construire une réponse à r2).

Figure 4. Protocoles pour le traitement des requêtes (a) What-is ; (b) Missing.

Requêtes Unknown

Lorsqu’un agent reçoit une requête Unknown, il récupère dans sa table d’historiquela requête originale r à laquelle la requête Unknown reçue répond. Si r est une requêteWhat-is ou une commande Order, l’agent vérifie :

1) si, entre temps, il a envoyé une résolution en réponse à r. Dans ce cas, il ignorela requête Unknown reçue. Cela correspond au fait que l’agent a précédemment en-voyé la même requête à plusieurs de ses accointants. S’il a reçu une assertion de la


part de l’un d’eux lui permettant de résoudre sa requête originale, alors il ignore lesréponses Unknown que certains autres ont pu lui envoyer ;

2) sinon, il vérifie si les agents auxquels il a émis la requête d’origine r ont tousrépondu. Si c’est le cas, et qu’il n’y a aucune assertion parmi les réponses collectées,cela veut dire que l’agent n’a aucune nouvelle connaissance pour la résolution de sarequête d’origine :

- Ainsi, si la requête d’origine est What-is, l’agent construit la réponseUnknown(∗) ;

- Si c’est une commande Order dans laquelle les valeurs de certains attributsF ′ lui faisaient défaut, il construit la réponse Unknown(F ′).

Le microprotocole correspondant à cette règle est représenté sur la figure 5.(a).

Exemple. Dans notre précédent exemple, si l’agent PhotoSon&Vidéo n’avait pu pro-poser d’appareil photo pour la requête r1, il aurait envoyé une réponse Unknown(*) enréponse à la requête Missing (construite suite au traitement de r2) envoyée par l’agentaccessoire. En recevant une réponse Unknown, l’agent accessoire vérifie s’il a reçuune assertion de la part d’un des autres participants qu’il a sollicités pour sa requêteMissing. S’il n’a d’autres réponses reçues que Unknown, il en déduit qu’il ne peut ré-soudre la requête initiale r2 et finit par construire lui-même une réponse Unknown(*).

Requêtes Assert-can

Si un agent reçoit un message contenant une requête réponse Assert-can(E,F ′),tout comme pour des requêtes Missing, il recherche dans sa table d’historique uneassertion où les attributs f ∈ F ′ sont renseignés.

Si une ou plusieurs assertions sont trouvées pour chaque f ∈ F ′, l’agent enconstruit une où il fournira les valeurs possibles de ces attributs manquants, sinonil envoie une requête Unknown. Ceci est représenté par le microprotocole de la fi-gure 5.(b).

Requêtes Assert-is

D’après les règles dialectiques précédemment spécifiées, si un agent reçoit uneassertion Assert-is, c’est qu’il a envoyé au travers d’un précédent message soit une re-quête What-is, Missing ou alors Assert-can (c.f. les microprotocoles des figures 5.(a),3.(b) et 5.(b)). L’agent doit alors vérifier si cette assertion était bien attendue et à queltype de requête elle répond afin de savoir ce qu’il doit en faire. Il recherche alors danssa table d’historique le message auquel celui reçu répond. Une fois ce message trouvé,l’agent explore son contenu. Selon la requête à l’origine de l’assertion reçue (récupé-rée moyennant le tableau d’identifiant req-id), l’agent doit gérer l’un des trois cassuivants :

1) L’assertion reçue répond à une requête Assert-can. Cela veut dire que l’agenta précédemment échoué à résoudre une requête Order (c.f. le microprotocole de lafigure 3.(a)). L’agent utilise alors l’assertion reçue pour résoudre la commande origi-


Figure 5. Protocoles pour le traitement des requêtes (a) Unknown ; (b) Assert-can.

nale Order.2) L’assertion répond à une requête What-is. Dans ce cas, la requête What-is a été

construite par l’agent pour décomposer une commande Order (c.f. le mirco-protocolede la figure 3.(b)). L’agent utilise alors l’assertion reçue pour tenter de résoudre ànouveau cette commande initiale Order.

3) L’assertion répond à une requête Missing. Dans ce cas : (1) si la requêteMissing répond elle-même à une requête What-is (c.f. le microprotocole de la fi-gure 4.(a)), l’agent utilise l’assertion pour résoudre la requête What-is d’origine ; (2)sinon, si la requête Missing répond à une requête Order (c.f. le microprotocole de lafigure 3.(a)), l’agent utilise l’assertion pour répondre à la commande Order d’origine.

La figure 6 représente le microprotocole pour le traitement des requêtes Assert-is.

Exemple. Reprenons l’exemple de l’enregistrement de programme,et en particulier l’agent ayant reçu la commande d’enregistrementOrder(Record(equal(title, x, Desperate Housewives)) et ayant construitla requête What-is pour tenter de trouver les attributs attendus channel,duration et time pour déclencher son action. Précédemment, nous avons vuque l’agent télévision, ayant reçu la requête What-is, a envoyé une assertionAssert-is(equal(channel, d, 6),equal(duration, d, 45min),equal(time, d, 20h50))renseignant les attributs attendus par le premier agent. En recevant cette assertion,l’agent récupère la commande initiale, et remplace le paramètre du titre avec celuicomportant les valeurs des attributs channel, duration et time attendus par sonaction. Il peut à présent résoudre la commande reçue avec les paramètres qui luiconviennent.


Figure 6. Protocole pour le traitement des assertions Assert-is.

4.3. Détection d’attributs manquants à retourner à l’utilisateur

Lorsque l’agent de l’utilisateur a reçu toutes les réponses des agents participants, ilcalcule les listes des réponses candidates. Ainsi, pour chaque requête, il calcule l’en-semble de résolutions proposées. Si l’une des requêtes de l’utilisateur n’a pas d’autresrésolutions que Unknown(F ′), alors l’ensemble des attributs manquants F ′ est re-tourné à l’utilisateur. Dans notre modèle cela implique que l’utilisateur n’a pas fourniles valeurs de ces attributs qui sont nécessaires à la résolution de ses requêtes.

Exemple. Supposons un utilisateur qui a exprimé la requêter=Order(Deliver(equal(ref, x, EX321))) demandant de se faire livrer un pro-duit dont la référence est EX321. Supposons également que l’agent Livraison soitmuni du patron d’évènement Deliver(ref, deliveryAdr) pour son action livrerproduit. Pour répondre à la requête r, suivant la règle dialectique de la currification(c.f. figure 3.(b)), l’agent construit d’abord la requête What-is demandant aux agentsparticipants la valeur de l’attribut manquant deliveryAdr. Si aucun agent n’a pula calculer, l’agent Livraison reçoit des réponses Unknown de ses accointants. Ilconstruit alors lui-même une réponse Unknown(deliveryAdr) suivant la règle dia-

25

lectique pour le traitement des requêtes Unknown (c.f. figure 5.(a)). Si c’est la seulerésolution collectée par l’agent de l’utilisateur pour la requête r, alors l’utilisateur sevoit retourner l’attribut manquant deliveryAdr (signifiant que la valeur de ce derniern’a pas été fournie).

5. Évaluations analytique et expérimentale

Cette section décrit l’évaluation analytique de notre approche en y étudiant la ter-minaison et les complexités calculatoire et de communication de notre protocole decoordination. Elle présente ensuite son évaluation expérimentale en analysant le dé-roulement d’un scénario implémenté.

5.1. Évaluation analytique du protocole de coordination

5.1.1. Terminaison

Proposition 1 Chaque rôle de notre protocole de coordination, soit le rôle d’agentparticipant et l’agent de l’utilisateur, se termine en un nombre fini d’étapes.

Preuve. Pour prouver la proposition 1, et ainsi qu’un agent participant ne peut s’impli-quer dans des cycles de requête-réponse, nous regroupons toutes les règles dialectiquesrégissant les conversations des agents en une seule grammaire qui décrit le comporte-ment global du protocole.

Nous formalisons cette grammaire par l’algèbre de processus du langage ISOLOTOS (Bolognesi et al., 1987) en considérant chaque performatif de notre ACLcomme un microcomportement possible dans le comportement global du protocole(ex. Missing est un microcomportement qui consiste à construire et envoyer, dans leSMA, une requête de performatif Missing). La figure 7 illustre l’arbre de notre gram-maire et démontre que chaque microcomportement, et quelque soit les microcom-portements qu’il engendre, finit, directement ou indirectement (par exit). Par consé-quent, le traitement des requêtes dans notre protocole de coordination se termine en unnombre fini d’étapes. La terminaison du traitement de l’ensemble des requêtes pourchaque agent implique ainsi la terminaison de notre protocole.

5.1.2. Complexité de communication

Soit k le nombre de requêtes de l’utilisateur et n le nombre d’agents, comprenantles agents participants et l’agent de l’utilisateur, dans notre protocole de coordination.La complexité de communication de notre protocole, i.e. le nombre total de messagesémis au pire cas, est de l’ordre de O(kn2). Comparée à celle du CNP, dont la com-plexité de communication est de l’ordre de O(kn), notre protocole implique plus demessages échangés. Néanmoins, contraitement au CNP et à d’autres protocoles d’in-teraction, les messages supplémentaires générés dans notre protocole permettent detraiter les dépendances entre les tâches et la décomposition des tâches.

26 5 ÉVALUATIONS ANALYTIQUE ET EXPÉRIMENTALE

Figure 7. Arbre défini par notre protocole.

5.1.3. Complexité calculatoire

Pour chaque message qu’un agent reçoit, il doit traiter chacune des k requêtes quele message contient en utilisant les règles dialectiques précédemment définies. Durantcette étape, l’agent doit rechercher des informations dans sa table d’historique parmiles messages reçus de la part de n agents. Par conséquent, la complexité calculatoirede notre protocole de coordination est polynomiale et, est au pire cas, de l’ordre deO(kn).

5.2. Évaluation expérimentale : Un scénario implémenté

Pour évaluer les performances de notre protocole de coordination, nous avons im-plémenté (en Java 1.5) un SMA composé d’agents introspectifs. Nous présentons danscette section un des scénarii implémentés nécessitant la coordination d’agents afin d’yillustrer le comportement des règles dialectiques de notre protocole.

5.2.1. Description du scénario

Considérons un utilisateur voulant louer un film, dont le titre est The Prestige,au format MPEG. Dans ce scénario, la demande de l’utilisateur sera émise dans uncontexte où il n’y pas de service disponible fournissant des vidéos MPEG. Au lieude quoi, il y a un service fournisseur de vidéos UIF et un service convertisseurUIF-MPEG. Par ailleurs, cet utilisateur veut aussi obtenir l’affiche de ce même film etconnaître le prix de vente du film trouvé. Ces deux dernières requêtes vont dépendredu résultat trouvé à la première. Les requêtes de l’utilisateur sont formalisées dansnotre modèle par :

r1=Order(GetMpegV ideo(equal(type, x, video)∧equal(title, x, The Prestige))) ;

5.2 Évaluation expérimentale : Un scénario implémenté 27

r2=Order(DisplayJacket(equal(refMovie, y, refMovie(request-get)))) ;

r3=What-is(price(z)|equal(refMovie, z, refMovie(request-get))).

Ces requêtes sont envoyées aux cinq agents participants suivants :

1) L’agent UIFVideoProvider qui est muni d’une base de données contenant lesinformations à propos de films au format UIF ;

2) L’agent UIFtoMPEGConverter qui retourne des films MPEG à partir de filmsUIF donnés en paramètre ;

3) L’agent MovieJacketDisplayer qui retourne des affiches de films à partir deleur référence ;

4) L’agent VideoSeller qui est un service de vente de vidéos. Il est muni d’unebase de données regroupant les informations à propos des vidéos proposées à la vente ;

5) L’agent VideoSeller2 qui est un autre service de vente de vidéos.

5.2.2. Déroulement du scénario

En examinant les requêtes de l’utilisateur, ainsi que les connaissances et capaci-tés des agents participants, on peut conclure qu’aucun agent ne peut seul prendre encharge l’intégralité de chaque requête. Les requêtes de l’utilisateur sont envoyées àl’agent de l’utilisateur UserAgent. La figure 8 illustre un extrait, capturé par le snif-fer de notre application, des conversations des agents pour résoudre ce scénario. Ellemontre qu’au départ tous les agents participants reçoivent la requête de l’utilisateur dela part du UserAgent. Ces requêtes sont regroupées dans un même message initiateurcomme le montre la figure 9. Chaque agent essaye alors de résoudre chaque requêtecontenue dans ce message.

L’agent UIFtoMPEGConverter par exemple, qui peut envoyer des vidéos MPEG(comme demandé par l’utilisateur), nécessite le format UIF du film pour exécuterson action. Suivant la règle dialectique de la currification des commandes, et afin deretrouver les attributs manquants en exploitant ceux reçus, il construit la requête :

What-is(uif -video(x) | equal(type, x, video) ∧ equal(title, x, The Prestige))

L’agent UIFVideoProvider, qui peut répondre à une telle requête, envoie alors uneassertion à l’agent UIFtoMPEGConverter en fournissant les valeurs de l’attribut re-quis uif -video. L’agent UIFtoMPEGConverter retrouve alors la requête originaler1 suivant la règle dialectique pour la gestion des assertions, et la résout moyennantl’assertion reçue. La requête réponse construite est alors proposée à l’utilisateur.

Pour gérer les requêtes dépendantes r2 et r3 (qui dépendent de la valeur de l’at-tribut refMovie), les agents MovieJacketDisplayer, VideoSeller et VideoSeller2envoient des requêtes Missing à leurs accointants dans ℵ. Ils reçoivent la valeur del’attribut refMovie, à travers une assertion, de la part de l’agent UIFtoMPEGCon-verter après que celui-ci a exécuté la commande r1. Suivant la règle dialectique pourla gestion des assertions, les agents récupèrent leurs requêtes d’origine (r2 et r3) et lesrésolvent à l’aide de l’assertion reçue.

28 5 ÉVALUATIONS ANALYTIQUE ET EXPÉRIMENTALE

Figure 8. Extrait de la conversation des agents capturé par le sniffer.

5.2.3. Analyse

Ce scénario a présenté un exemple de besoins d’utilisateur nécessitant la coordi-nation de plusieurs agents. Il a illustré l’utilisation de plusieurs règles dialectiques denotre protocole de coordination pour la résolution de ces besoins. En particulier, àl’aide de ces règles dialectiques, les agents ont pu décomposer les requêtes, s’aiderles uns les autres à fournir les valeurs d’attributs manquants et gérer les dépendancesentre les requêtes (et ainsi se coordonner afin de couvrir les besoins de l’utilisateur).

Concrètement, pour 3 requêtes (dont 2 présentant des dépendances) envoyées à6 agents, 50 messages ont été produits, soit moins que la complexité de communi-cation calculée théoriquement (i.e. 108). Cependant, le nombre de messages pourraitêtre réduit si le calcul des agents destinataires prenait en compte les compétencesdisponibles. En particulier, l’ensemble ℵ des agents destinataires calculés pour les re-quêtes Missing, Assert-can et What-is contient généralement les identifiants de tousles agents participants. Au lieu de cela, ℵ devrait contenir les identifiants des agentsqui ont les compétences les plus appropriées pour résoudre les requêtes à diffuser.Pour ce faire, un registre privé pourrait être créé pour chaque conversation, rempliavec les compétences des agents, et consulté lorsque ℵ est calculé. Par ailleurs, ce scé-

29

Figure 9. Messsage initiateur du scénario.

nario a démontré que les agents réussissaient à gérer des ensembles de requêtes dansun même message (voir par exemple la figure 9 et contrôlaient le flux de messages parle calcul des agents destinataires ℵ en fonction des types de réponses construites. C’estle cas par exemple de l’agent VideoSeller qui a regroupé dans un même message lesrequêtes Missing (pour résoudre r2 et r3) qu’il devait envoyer à ses accointants. Danscet exemple, les requêtes Missing en question visent à récupérer la valeur du mêmeattribut refMovie. Une amélioration possible du protocole consisterait à analyser legroupe de requêtes destinées aux mêmes agents afin d’éviter le redondances.

Enfin, il aurait pu se produire des cas de disparition ou de panne d’agents pendantou à l’issue du processus de coordination, ce qui aurait rendu impossible leur invo-cation par l’utilisateur ou les autres agents. Une amélioration à apporter au protocoleserait d’intégrer une approche de gestion d’exception dans les SMA comme cellesprésentées dans (Platon et al., 2006).

6. Conclusion et perspectives

Des environnements tels que le web et l’informatique diffuse sont des environ-nements ouverts et distribués. Ils se caractérisent par des services très flexibles etdynamiques, où de nouvelles propriétés peuvent apparaître pour un service et de nou-veaux services peuvent être disponibles sur une base quotidienne, et où les besoinsdes utilisateurs en services varient. Dans un tel contexte, le processus de compositionde services pour la satisfaction des besoins de l’utilisateur doit pouvoir s’adapter demanière dynamique avec un minimum d’intervention de la part de l’utilisateur.

30 6 CONCLUSION ET PERSPECTIVES

Dans ce contexte, nous avons proposé une approche dynamique pour la compo-sition de services qui s’appuie sur la collaboration décentralisée d’un ensemble deservices dont le but est de satisfaire des besoins librement exprimés par des utili-sateurs humains. Pour permettre des collaborations dynamiques entre services, sansutilisation de plans prédéfinis, nous avons proposé une architecture orientée servicesbasée sur un système multiagent. Dans cette SOA, les services sont fournis par desagents dotés de capacités introspectives leur permettant d’analyser leurs propres ac-tions afin de déterminer à quelle part d’une tâche ils peuvent contribuer. Nous avonsalors spécifié pour ce SMA un protocole de coordination dynamique afin de supporterla chorégraphie des services. Ce protocole, distribué (au niveau des tâches) et décen-tralisé (au niveau du contrôle), permet aux agents de traiter des besoins complexesde l’utilisateur, les décomposer, gérer les dépendances qui peuvent y apparaître, et secoordonner avec d’autres agents afin de couvrir la satisfaction de ces besoins. De ma-nière générale, les travaux présentés constituent une contribution dans la résolutiondistribuée de problèmes et, au vue de ses domaines d’application, dans la compositionde services sur le web et dans l’intelligence ambiante.

La conception de l’approche de chorégraphie présentée, ainsi que les expérimen-tations effectuées sur le modèle de coordination spécifié, ont donné lieu à plusieursvoies de travaux de recherche futurs, en particulier :

– L’expressivité des contraintes dans notre modèle devrait être étendue car elleest limitée aux opérateurs {equal, greater, less}. De plus, notre modèle ne permet pasd’exprimer des contraintes “continues” du type : “l’appareil photo le moins cher avecla plus haute résolution”. Satisfaire ce type de contraintes requiert d’interpréter despropriétés discrêtes de services et d’inférer la tranche de valeurs intéressant l’utilisa-teur.

– Des contrats devraient être intégrés pour les accords et la compréhension entreles agents. Nous voudrions étudier la mise en place de contrats (accords ou engage-ments) (Knottenbelt et al., 2005) pour vérifier la consistance entre les contrats et lesbesoins de l’utilisateur, ainsi qu’entre des contrats de plusieurs partenaires.

– Les approches existantes pour la composition dans l’informatique diffuse sonttoutes centrées sur un utilisateur se mouvant dans un environnement dynamiquequoique fermé et homogène. La chorégraphie de services devrait alors être étudiéedans un contexte d’environnements dynamiques et hétérogènes, impliquant plusieursproblématiques quant à la disponibilité des services, leurs conditions d’exécution enfonction de chaque environnement, et la gestion de conflits lorsque plusieurs utilisa-teurs cohabitent dans un même environnement.

– Nous avons proposé un modèle d’agent introspectif où les agents raisonnent surles préconditions de leurs actions. Il faut développer plus amplement ce modèle pourexplorer notamment le raisonnement des agents sur les effets de leurs actions. À cetype d’agent, on pourrait demander “qu’est-ce qui se passerait si j’achetais un billetd’avion et que je l’annulais 3 jours plus tard ?”. L’utilisation de tels agents pourraits’avérer très intéressante en MABS (Multi-Agent Based Simulation).

31

7. Bibliographie

Aknine S., Modèles et méthodes de coordination dans les systèmes multi-agents, PhD thesis,Thèse Doctorat. Université Paris IX Dauphine, 2000.

Andrieux A., Czajkowski K., Dan A., Keahey K., Ludwig H., Nakata T., Pruyne J., , RofranoJ., Tuecke S., Xu M., Web Services Agreement Specification (WS-Agreement), Technicalreport, Globus Alliance, 2004.

Austin D., Barbir A., Peters E., Ross-Talbot S., Web Services Choreography RequirementsW3C Working Draft, Technical report, World Wide Web Consortium (W3C), 2004.

Barros A., Dumas M., Oaks P., « A Critical Overview of the Web Services Choreography Des-cription Language (WS-CDL) », Proc. of the Business Process Trends (BPTrends), 2005.

Bauer B., Odell J., « UML 2.0 and Agents : How to Build Agent-based Systems with the NewUML Standard », Engineering Applications of Artificial Intelligence, vol. 18, n˚ 2, p. 141-157, March, 2005.

Berger A., Pesty S., « Towards a Conversational Language for Artificial Agents in MixedCommunity », Proc. of the 3rd International Central and Eastern European Conferenceon Multi-Agent Systems (CEEMAS’05), p. 31-40, 2005.

Bolognesi T., Brinksma E., « Introduction to the ISO Specification Language LOTOS », Com-puter Networks, vol. 14, p. 25-59, 1987.

Booth D., Champion M., Ferris C., McCabe F., Newcomer E., Orchard D., « Web ServicesArchitecture », , http://www.w3.org/TR/2003/WD-ws-arch-20030514/, May, 2003.

Booth D., Haas H., McCabe F., Newcomer E., Champion M., Ferris C., Orchard D., Web Ser-vices Architecture, Technical report, W3C Working Group Note 11, 2004.

Bourdon J., Beaune P., Fiorino H., « Architecture multi-agents pour la composition automatiquede web services », Actes de l’atelier Intelligence Artificielle et Web Intelligence, PlateformeAFIA, 2007.

Caillou P., Aknine S., Pinson S., « A Multi-Agent Method for Forming and Dynamic Restruc-turing of Pareto Optimal Coalitions », Proc. of the 1st International Joint Conference onAutonomous Agents and Multiagent Systems (AAMAS), ACM Press, New York, NY, USA,p. 1074-1081, 2002.

Chakraborty D., Joshi A., Dynamic Service Composition : State-of-the-Art and Research Di-rections, Technical report, University of Maryland, 2001.

Charif Y., Chorégraphie dynamique de services basée sur la coordination d’agents introspectifs,PhD thesis, Thèse Doctorat. Université Paris VI-Pierre et Marie Curie, 2007.

Charif Y., Sabouret N., « A Model of Interactions about Actions for Active and SemanticWeb Services », Proc. Semantic Web Service workshop at 3rd International Semantic WebConference (ISWC’04), p. 31-46, 2004.

Dijkman R., Dumas M., « Service-oriented Design : A Multi-viewpoint Approach », Interna-tional Journal on Cooperative Information Systems, vol. 13, World Scientific PublishingCompagny, p. 338-378, 2004.

Durfee E., Coordination of Distributed Problem Solvers, Kluwer Academic Publishers, Nor-well, MA, USA, 1988.

Durfee E., « Distributed Problem Solving and Planning », Multi-Agent Systems and Applica-tions, Springer-Verlag New York, Inc., p. 118-149, 2001.

32 7 BIBLIOGRAPHIE

Ermolayev V., Keberle N., Plaksin S., « Towards Agent-Based Rational Service Composition –RACING Approach », Proc. of the International Conference on Web Services Europe, vol.LNCS 2853, Springer-Verlag, Erfurt, Germany, p. 167-182, 2003.

Finin T., Fritzson R., McKay D., An overview of KQML : A Knowledge Query and Manipula-tion Language, Technical report, University of Maryland Baltimore Country, 1992.

FIPA, « FIPA Interaction Protocol Library Specification », , http://www.fipa.org/specs/fipa00025/XC00025E.pdf, 2001.

Georgeff M. P., « Planning », in J. Allen, J. Hendler, A. Tate (eds), Readings in Planning,Kaufmann, San Mateo, CA, 1990.

Greaves M., Holmback H., Bradshaw J., « What is Conversation Policy ? », in F. Dignum,M. Greaves (eds), Issues in Agent Communication, Springer-Verlag : Heidelberg, Germany,p. 118-131, 2000.

Huhns M., « Software Agents : The Future of Web Services », Agent Technologies, Infrastruc-tures, Tools, and Applications for E-Services, p. 1-18, 2002.

JACK, « JACK Intelligent Agents Tutorials, Agent Oriented Software Pty », , http://www.disi.unige.it/person/ZiniF/Didattica/Jack/jack_tutorial.pdf, 1999.

JADE, « Java Agent DEvelopement Framework », , http://jade.tilab.com, 2004.

Kavantzas N., Burdett D., Ritzinger G., Fletcher T., Lafon Y., Web Services Description Lan-guage (WS-CDL), Technical report, W3C, 2004.

Klush M., Gerber A., Schmidt M., « Semantic Web Service Composition Planning with OWLS-Xplan », Proc. of the 1st International AAAI Fall Symposium on Agents and the SemanticWeb, AAAI Press, p. 55-62, 2005.

Knottenbelt J., Clark K., « Contract-related Agents », Proc. of the International Workshop ofthe 6th Conference on Computational Logic in Multi-Agent Systems, p. 226-242, 2005.

Koning J.-L., « Operational Semantics Rules as a Computational Coordination Mechanism inMulti-Agent Systems », International Journal on Intelligent Control and Systems, vol. 2,n˚ 12, p. 167-178, 2007.

Malone T., Crowston K., « The interdisciplinary study of coordination », ACM Comput. Surv.,vol. 26, n˚ 1, p. 87-119, 1994.

Martin D., Paolucci M., McIlraith S., Burstein M., McDermott D., McGuinness D., Parsia B.,Payne T., Sabou M., Solanki M., Srinivasan N., Sycara K., « Bringing Semantics to WebServices : The OWL-S Approach », in J. Cardoso, A. Sheth (eds), Proc. of the 1st Interna-tional Workshop on Semantic Web Services and Web Process Composition (SWSWPC’04),vol. 3387, Springer-Verlag, San Diego, CA, USA, p. 26-42, 2004.

McBurney P., Parsons S., Wooldridge M., « Desiderata for Agent Argumentation Protocols »,Proc. of 1st International Joint Conference on Autonomous Agents and Multi-Agent Systems(AAMAS’02), ACM Press, p. 402-409, 2002.

Müller I., Kowalczyk R., Braun P., « Towards Agent-based Coalition Formation for Ser-vice Composition », Proc. of the International Conference on Intelligent Agent Technology(IAT’06), p. 73-80, 2006.

Osman T., Thakker D., Al-Dabass D., « Bridging the Gap between Workflow and Semantic-based Web services Composition », Proc. of the Web Service Composition Workshop (WS-COMPS’05), 2005.

33

Paurobally S., Tamma V., Wooldridge M., « Cooperation and Agreement between SemanticWeb Services », W3C Workshop on Frameworks for Semantics in Web Services. Innsbruck,Austria, June, 2005.

Peltz C., « Web Services Orchestration and Choreography », Computer, vol. 26, n˚ 10, p. 46-52,2003.

Platon E., Mamei M., Sabouret N., Honiden S., Parunak H., « Mechanisms of the Environmentfor Mutli-Agent Systems, Survey and Opportunities », Autonomous Agents and Multi-AgentSystems, vol. 14, p. 1-17, 2006.

Ponnekanti S., Fox A., « SWORD : A Developer Toolkit for Web Services Composition »,Proc. of the 11the WWW Conference, Honolulu, HI, USA, Elsevier, p. 83-107, 2002.

Rubinstein A., « Perfect Equilibrium in a Bargaining Model », Econometrica, vol. 50, n˚ 1,p. 97-109, 1982.

Sabouret N., Sansonnet J., « Un langage de description de composants actifs pour le web sé-mantique », Revue RI3, vol. 3, n˚ 1, p. 9-36, 2003.

Searle J., Speech Acts, Cambridge University Press, 1969.

Shehory O., Kraus S., « Feasible Formation of Coalitions among Autonomous Agents in Non-superadditve Environments », Computational Intelligence, vol. 15, p. 218-251, 1999.

Traverso P., Pistore M., « Automated Composition of Semantic Web Services into ExecutableProcesses », Proc. of the 3rd International Semantic Web Conference, Hiroshima, Japan(ISWC’04), p. 380-394, 2004.

Wu D., Parsia B., Sirin E., Hendler J., Nau D., « Automating DAML’S Web Services Com-position using SHOP2 », Proc. of the International Semantic Web Conference (ISWC’03),p. 195-210, 2003.

SERVICE ÉDITORIAL – HERMES-LAVOISIER14 rue de Provigny, F-94236 Cachan cedex

Tél. : 01-47-40-67-67E-mail : [email protected]

Serveur web : http://www.revuesonline.com

ANNEXE POUR LE SERVICE FABRICATIONA FOURNIR PAR LES AUTEURS AVEC UN EXEMPLAIRE PAPIERDE LEUR ARTICLE ET LE COPYRIGHT SIGNE PAR COURRIER

LE FICHIER PDF CORRESPONDANT SERA ENVOYE PAR E-MAIL

1. ARTICLE POUR LA REVUE :L’objet. Volume 8 – n˚2/2005

2. AUTEURS :Yasmine Charif — Nicolas Sabouret

3. TITRE DE L’ARTICLE :Un protocole de coordination d’agents introspectifs pour la chorégraphiedynamique de services

4. TITRE ABRÉGÉ POUR LE HAUT DE PAGE MOINS DE 40 SIGNES :Chorégraphie dynamique de services

5. DATE DE CETTE VERSION :21 novembre 2008

6. COORDONNÉES DES AUTEURS :

– adresse postale :Université Pierre et Marie Curie-Paris6, UMR 7606, LIP6,4 Place Jussieu, Paris, F-75005 [email protected] [email protected]

– téléphone : 01 44 27 87 94– télécopie : 01 44 27 70 00– e-mail : [email protected]

7. LOGICIEL UTILISÉ POUR LA PRÉPARATION DE CET ARTICLE :LATEX, avec le fichier de style article-hermes.cls,version 1.23 du 17/11/2005.

8. FORMULAIRE DE COPYRIGHT :Retourner le formulaire de copyright signé par les auteurs, téléchargé sur :http://www.revuesonline.com

SERVICE ÉDITORIAL – HERMES-LAVOISIER14 rue de Provigny, F-94236 Cachan cedex

Tél. : 01-47-40-67-67E-mail : [email protected]

Serveur web : http://www.revuesonline.com

Documents

Un protocole de coordination d’agents introspectifs pour la ... · Un protocole de coordination d’agents introspectifs pour la chorégraphie dynamique de services Yasmine Charif