Systèmes Multi-Agents
Professeur: J-P.SANSONNET
Master 2 Recherche Informatique - Université Paris Sud-XI
Février 22, 2005
BISGIN, Ozan Erdem
ozanerdemb@yahoo.com
Le commerce peut être défini simplement comme un échange des produits ou des services. Le commerce électronique (e-commerce) signifie les échanges qui se passent via l’Internet [1]. D’où, les acheteurs et les vendeurs deviennent des entités électroniques [2].
Les applications agents sont des programmes auxquels on peut déléguer (des aspects de) une tâche. Elles diffèrent du logiciel traditionnel car elles négocient entre elles et elles sont personnalisées et semi autonomes. Ces qualités rendent des agents particulièrement utiles pour l'environnement du commerce électronique qui est riche en termes d’information et de processus.
Le commerce électronique devient de plus en plus une réalité. Or, à chaque fois qu’un marchand ou un client souhaite d’échanger des produits via l’Internet, il épuise plusieurs heures pour trouver une bonne solution car l’information est décentralisée et elles varient indépendamment entre eux.
D’autres part, le commerce électronique est quasiment fait par nos interactions: c’est nous qui décide quand nous allons acheter des produits ou combien nous souhaitons de payer pour chaque produit, etc. Donc, la négociation joue un rôle important pendant les échanges des produits ou des services. Par exemple, dans une entreprise, le directeur lui-même doit négocier par téléphone ou par e-mail, même si il s’agit d’un commerce électronique. Dans cet exemple-là, c’est fortement possible de ne pas négocier avec tous les fournisseurs, et le gain de l’entreprise n’est donc pas optimal.
En résumé, il nous faut un système qui cherche les produits auxquelles nous nous intéressons (une classification selon certains critères), et qui négocie avec les différents marchands d’une manière automatique. Aujourd’hui, seules les applications agents correspondent à ce besoin.
De nos jours, les applications agents pour le commerce électronique dont les conceptions varient beaucoup dû à la variété des tâches dans ce domaine, ne possèdent pas un standart commun concernant leur développement. C'est la raison pour laquelle, nous allons les groupes en deuxs qui n'est qu'un choix arbitraire.
Le premier groupe maintient les applications agents qui réduisent le temps de recherche pour un produit en assistant le consommateur. Certaines sont des assistants « intelligentes » qui fournissent des produits alternatifs, vu que des autres fournissent des marchands alternatifs pour un produit. Or, une petite quantité d’elles permettent les utilisateurs (les consommateurs et les vendeurs) la possibilité de négocier pour un produit entre eux. L’inconvénient des applications qui font partie de ce groupe est qu’ils se concentrent sur le prix comme critère, mais ne tient pas compte qu’il existe d’autres critères (comme la durée de la garantie ou l’efficacité d’un service après vente par exemple) pour prendre une décision pertinente. De plus, la négociation est faite entre agents dans une façon naïve qui est insatisfaisante.
Bien qu’il y ait plusieurs classifications des applications agents pour le commerce électronique, le Comportement d’Achat de Consommateur CAC (Consumer Buying Behaviour, CBB) [3], qui est basé sur six étapes fondamentales afin de guider le comportement d’achat du consommateur, peut nous permettre de classer les applications agents pour le commerce électronique existantes le plus formel possible.
Les six étapes sont : l’identification du besoin, le courtage de produit (product brokering), le courtage de marchand (merchant brokering), la négociation, l’achat et la livraison, le service et l’évaluation. Lors d’un classement des applications agents, le courtage de produit, le courtage de marchand et la négociation sont les trois étapes les plus fréquemment utilisées. Le courtage de produit est la seconde étape où les consommateurs déterminent ce qu’ils vont acheter comme produit. On utilise soit un filtrage, soit un système de recommandation des produits se correspondants aux besoins de l’acheteur. Cette étape consiste à comparer les alternatives des produits. Le courtage de marchand est la troisième étape, dans laquelle on ne compare que des alternatives des marchands. La négociation est la quatrième étape où on détermine le prix et/ou les autres critères de la transaction. La négociation est utilisée dans le marché boursier, dans la vente aux enchères, et dans les magasins électroniques où on vent/achète des produits de second main.
Comme les applications agents pour le commerce électronique varient beaucoup selon leurs conceptions, il vaut mieux les classer selon le CAC : si un système fait partie de plus q’une étape, on le classifie selon la dernière étape.
PersonaLogic [4] et Firefly [5] sont deux systèmes commerciaux afin d’assister le choix des consommateurs. Ils se trouvent donc à l’étape courtage du produit, et il s’agit des agents au nom de chaque consommateur.
PersonaLogic utilise un système de filtrage afin de restreindre les choix du consommateur comme produit, et retourne une liste triée des produits établie par le moteur de la satisfaction des contraintes. Quant à Firefly, il utilise un filtrage collaboratif automatique pour trouver les produits appropriés au consommateur (même si il ne les choisit pas encore) grâce aux affinités entre ce consommateur et ses voisins (si les goûts des consommateurs se ressemblent, il s’agit d’un voisinage). Et il lui offre les produits que ses voisins ont déjà jugés et choisis.
Bargain Finder [4] et Jango [4] sont deux systèmes se trouvant à l’étape courtage de marchand, où ces systèmes comparent les alternatifs des marchands, mais pas de produits.
Bargain Finder est le premier système où on compare les prix des produits fournis par neuf sites web. L’inconvénient de ce système est que l’agent n’a que le prix comme le critère de décision : il ne considère pas les services pour ce produits (la garantie, le service après vente, etc.) et un tiers des marchand l’a bloqué à cause de ce défaut. Jango était plus avancé que Bargain Finder, car il n’utilise pas un site web centrale comme celui de dernier, mais des browsers des consommateurs comme moyen d’accès : il évite ainsi le blocage des marchands (qui était le cas avec Bargain Finder).
Kasbah [6], AuctionBot [7] et Tête-à-Tête [8] sont trois systèmes dans lesquels on a la notion multi-agent et celle de négociation; c’est l’étape négociation.
Kasbah fournit des agents d’achat ou des agents de vente pour des utilisateurs. Donc, l’utilisateur crée son agent, le donne une direction stratégique, et l’envoie au marché central des agents. Chaque agent veut accomplir une transaction en utilisant les choix d’utilisateur (prix souhaité, prix minimum (et maximum) acceptable, la date limite, etc.). La négociation entre agents est simple : L’agent d’achat fait une proposition à l’agent de vente, celui de vente dit oui, ou non. Kasbah fournit aux acheteurs (consommateurs) trois stratégies de négociation : inquiet, sang-froid et frugal, qui correspondent respectivement aux fonctions linéaire, quadratique et exponentielle pour augmenter le prix qu’on a proposé dans le temps. L’avantage de cette négociation est qu’il est facile pour l’utilisateur de connaître le comportement de son agent.
AuctionBot est une application agents fournissant une serveur de ventes aux enchères : chaque utilisateur crée une vente aux enchères en sélectionnant le type de la vente aux enchères [14], et en spécifiant ses paramètres (la date limite, la méthode pour résoudre les conflits entre des offres, etc.). Les acheteurs et les vendeurs peuvent ainsi négocier en respectant les protocoles multilatéraux distribués de la négociation de cette vente aux enchères. En fait, un vendeur règle le prix de réservation de sa vente aux enchères et laisse AuctionBot dirige les acheteurs qui font des offres selon les protocoles et les paramètres de la vente aux enchères. De plus, AuctionBot est un marché électronique qui donne aux acheteurs la possibilité de créer ses agents autonomes propres : c’est à l’utilisateur de programmer les stratégies de proposition des offres pour son agent. AuctionBot permet de négocier au cours d’une vente aux enchères, mais elle ne prend en compte que le prix.
Tête-à-Tête est une application agents pour des ventes (comme vente au détail) à l’Internet où la négociation est strictement nécessaire. Elle prend en compte non seulement le prix mais aussi le temps de livraison, la garantie, les options de prêt, le service de cadeaux, et les autres services des marchands qui ajoutent un point fort à un produit. Elle est un système multi-agents comme Kasbah mais elle utilise à la place des trois stratégies (fonctions) simples (ce qui est le cas dans Kasbah), une stratégie argumentative basée sur l’évaluation des contraintes d’un utilisateur. C’est-à-dire, Tête-à-Tête si situent en trois étapes : le courtage de produit, le courtage de marchand et la négociation. Donc, elle évalue des choix d’un utilisateur en deux premières étapes, et elle considère ces choix pendant le rangement des offres des marchands. L’inconvénient de ce système est que le modèle de négociation qu’elle propose n’est pas assez suffisant pour garantir que le gain de deux côtés sera optimal après avoir eu une convention.
Les applications agents du deuxième groupe se concentrent pour éviter les défauts de ceux de premier groupe : elles se basent sur les techniques complexes de la négociation. Leur but est d’automatiser la négociation qui va réduire le temps de négociation et permettre de faire les transactions massivement. Cette automatisation va aussi enlever l’inconvénient majeur d’une négociation se passant entre deux personnes : la réticence à cause de l’embarras ou la personnalité d’une négociateur.
Le problème avec ces applications est qu’il faut un espace commun pour que les agents puissent communiquer. Le fait de définir : un langage commun pour les agents et un technique de la négociation sont deux autres problèmes. La solution est d’utiliser un marché électronique commun : chacun (soit l’acheteur, soit le vendeur) crée son agent propre (agent acheteur, agent vendeur), ils communiquent entre eux (il y a souvent un agent qui assiste à la communication de ces deux agents) dans l’espace fournit par ce marché, et s’il y a accord, ils font une transaction.
Il y a plusieurs systèmes qui proposent des applications agents du deuxième groupe, ils se diffèrent selon leur design du marché, le langage des agents, et le(s) technique(s) pour la négociation. Nous allons voir un de ce système qui propose une application agents dont le langage est XML pour un marché électronique [9]. Voici la figure de son architecture :
Dans ce système, chaque agent a une boîte de messages, il y a donc une queue d’attente. Un agent n’est pas responsable du traitement d’un message, ce qui rend la conception des agents plus facile. Le langage de communication est FIPA-ACL/XML [10] qui a ses avantages (et ses inconvénients par rapport à KQML) : les tags définit le type du message, quelques éléments communs peuvent être introduits en partant par le DTD.
1- Initialement, tous les utilisateurs doivent être inscrits dans le marché électronique afin de créer leurs agents pour acheter ou pour vendre un produit dans le serveur. Les agents vendeur proposent des jobs, les agents acheteurs cherchent des jobs.
2- Un agent créé communique avec l’agent médiateur centrale (manipule des communications des agents) pour entrer son profil, et les détailles du job qu’il cherche (ou il propose) à la BD du marché électronique.
3- Après avoir eu les offres des agents acheteurs et ceux de vendeurs, le médiateur assigne ces agents à la chambre de négociation dans un processus de présélection (en utilisant le fuzzy logic) [11] si leurs profils (leurs préférences personnelles) sont similaires. Dans la chambre, seuls les agents avec les préférences similaires peuvent négocier entre eux.
4- Dans la chambre, il y a un agent vendeur et plusieurs agents acheteurs, il peut négocier avec des autres directement en utilisant plusieurs tactiques.
5- Après avoir négocié assez suffisamment pour prendre une décision finale, la négociation se termine : dans un cas idéal, l’agent acheteur et celui de vendeur ont une convention, et l’agent médiateur va être informé pour qu’il puisse mis à jour la BD. Chaque agent contacte avec son créateur et l’informer avec qui il se met en accord, et l’envoie les termes sur lesquels on est d’accord.
Le modèle de la négociation de cette application agents est développé en suivant ces cinq principes :
1- Confidentialité d’information
: Les fonctions d’utilité d’un agent pour évaluer
la valeur d’un produit est une information privée. Ces fonctions
sont en cohérence avec les préférences d’agent.
2- Confidentialité des tactiques et des stratégies
: Normalement, un agent n’a pas d’information qui décrit
les tactiques et les stratégies qui vont être choisies par un autre
agent. Néanmoins, ensemble de ces tactiques prédéfinies
est connu par tous les agents.
3- Contraintes du temps : Chaque agent doit finir une négociation dans une date limite. La date limite est aussi une information privée. Si on passe cette date, la valeur d’une convention (qui définit le bénéfice de l’utilisateur) devient zéro : les agents sont impatients pour avoir une convention si le délai d’une convention est coûteux (ce qui diminue la valeur d’une convention).
4- L’incertitude dans les deux côtés dans la négociation : Les deux côtés dans une négociation sont toujours incertains même si ils pourront se mettre en accord (La valeur de la convention > 0). Un agent devient de plus en plus incertain si il n’arrive pas à se mettre en accord : les agents sont pessimistes.
5- La stratégie stochastique de la négociation : Contrairement aux applications agents du premier groupe, cette application agents fournis plusieurs tactiques (et plusieurs stratégies pour utiliser ces tactiques) aux agents. Un agent choisit, dans une façon adaptative, une tactique qu’il va utiliser à l’étape suivante de la négociation pour maximiser la valeur de la convention.
Il y a trois types de tactiques prédéfinies :
1- Les tactiques qui dépendent du temps : les agents doivent négocier très rapidement.
2- Les tactiques qui dépendent des ressources : les ressources sont limités, et les agents doivent ont une convention en considérant cette pression.
3- Les tactiques imitatives : Ces tactiques sont utilisées si agent décide de copier les tactiques (plutôt les tactiques) d’un autre agent pendant la négociation.
Selon les tactiques qu’un agent doit choisir à chaque étape de négociation, il évalue une valeur : le coût d’une convention qui sert à décider si la négociation vaut le coup ou pas. Donc, si un agent est une contrainte du temps se comporte différemment que celui ne l’a pas.
La stratégie définit la combinaison des tactiques qu’un agent établie au cours d’une négociation. Cette combinaison et son changement dépend non seulement de l’histoire des négociations anciennes mais aussi de l’état de croyance (La négociation, va-t-elle être finit par une convention? Et le coût de cette convention, est-il encore admissible?) de cet agent.
Cette stratégie construit ainsi une arbre de décision qui commence par trois tactiques prédéfinie (T1, T2, T3) ce que nous avons déjà vu. Au début de la négociation, l’agent choisit aléatoirement à une négociation car la probabilité de choisir ces une de trois sont même au départ. Après, l’agent calcule la valeur de la convention pour chaque nœud selon la probabilité pour atteindre à un nœud particulier, et selon les tactiques que cet agent et celui d’autre vont choisir. Le but du jeu est de maximiser la valeur expectant de la convention, donc chaque agent choisit le nœud par lequel il maximise cette valeur. L’algorithme pour calculer ces probabilités est un processus de décision de Markov [12], où on calcule tous les probabilités des transitions (passer d’une tactique à une autre (ou continuer à utiliser avec la même tactique) dans une intervalle du temps) pour les intervalles du temps discrètes.
Même si l’étape de la négociation que nous avons vue ne couvre pas les autres applications agents du deuxième groupe, elle nous donne une idée concernant leurs architectures et leurs techniques de négociation.
Il existe des autres applications agents du deuxième groupe. Par exemple, eMediator [13] est une autre application agents bien connue où le système se focalise à gérer des ventes aux enchères. Il propose une serveur configurable eAuctionHouse comme une plate-forme des agents, deux langages de communications (plutôt langage pour le passage des offres entre des agents) XOR et XOR-of-OR, un eCommitter pour optimiser surtout le prix des conventions et un eExchangeHouse qui correspond à la chambre des agents ce qu’on vient d’expliquer au-dessus. La théorie de vente aux enchères [14] est ainsi nécessaire pour mieux comprendre ce système.
En résumé, il existe plusieurs organisations de recherche qui se penchent de construire des applications agents pour simplifier la vie des utilisateurs dans ce domaine, et cette approche n’est plus un aspect théorique : il existe plusieurs entreprises qui sont en train de développer des applications agents pour le commerce électronique et les utiliser à l’Internet. Malgré les difficultés de la conception et de la standardisation, les applications agents sont utilisées de plus en plus pour le commerce électronique.
[1] www.rexco.com/glossary.html
[2] Alessio R. Lomuscio, Michael Wooldridge, Nicholas R. Jennings, “A classification scheme for negociation in electronique commerce” Department of computing, Imperial College of Science, Technology and Medecine, 2001
[3] Robert H. Guttman, Alexandros G. Moukas, and Pattie Maes, “Agent-mediated Electronic Commerce: A Survey” Software Agents Group, MIT Media Laboratory, 1998
[4] Il y a beaucoup des articles qui expliquent PersonaLogic, Bargain Finder et Jango (et qui les comparent avec leurs alternatives), il suffit de faire une recherche sur google.
[5] U. Shardanand and P. Maes, “Social Information Filtering: Algorithms for Automating Word of Mouth“ proceedings of the CHI-95 Conference, Denver, CO, ACM Press, May 1995.
[6] Chavez, A, and P. Maes, “Kasbah: An Agent MarketPlace for Buying and Selling Goods”, in proceedings of The First International Conference on The Practical Application of Intelligent Agents and Multi-Agent Technology (PAAM’96), pp. 75-90, 1996.
[7] P. Wurman, M. Wellman, and W. Walsh, “The Michigan Internet AuctionBot: A Configurable Auction Server for Human and Software Agents.” in proceedings of the Second International Conference on Autonomous Agents (Agents’98), May 1998.
[8] R. Guttman and P. Maes, “Agent-mediated Integrative Negotiation for Retail Electronic Commerce.” in the proceedings of the Workshop on Agent Mediated Electronic Trading (AMET’98), Minneapolis, Minnesota, April 1998.
[9] K. Kurbel, F. Teuteberg, D. Szulim, “XML-based Agent Communication for Electronic Marketplaces”, in: Proceedings of ISA 2000 - Intelligent Systems and Applications, Wollongong (Australia), 2000.
[10] FIPA Specification Repository, Part 2 Agent Communication, http://www.fipa.org/repository/index.html, January 2000.
[11] F. Teuteberg, “Fuzzy-Logik und XML zur Repraesentation von Unschaerfe auf einem agentenbasierten Marktplatz zur Personalakquisition”, 2002.
[12] M. Hausknecht, “Value-Function Approximations for Partially Observable Markov Decision Processes”, Journal of Artificial Intelligence Research 13 (2000), pp. 33-94.
[13] Sandholm T.W. “eMediator: A Next Generation Electronic Commerce Server”, Department of ComputerScience, Washington University, 1999.
[14] E. Rasmusen and Basil Blackwell, “Games
and Information”, 1989.