5. Négociation dans les systèmes multi-agents

5.1. Qu'est que la négociation?

Dans un système multi-agents les agents interagissent en vue de réaliser des tâches ou d'atteindre des buts. L'interaction a lieu, d'habitude dans un environnement commun où les agents ont diverses zones d'influence, notamment diverses parties de l'environnement sur lesquelles ils peuvent agir. Ces zones peuvent être disjointes mais, dans la plupart des cas, elles se superposent - l'environnement est partagé par les agents. Rappelez-vous aussi la classification des situations d'interactions possibles entre agents en fonction de leurs buts, ressources et compétences qu'on a discutées dans la section 1.2.2 du chapitre 1. En interagissant dans un tel environnement partagé, les agents doivent coordonner leurs actions et avoir des mécanismes pour la résolution des conflits. La coordination et la résolution des conflits sont surtout nécessaire dans le cas des agents egocentrés (des agents ayants leurs propres buts, désirs, préférences, etc.) ou compétitifs mais aussi bien, parfois, dans le cas des agents coopératifs pour la communication des changements des plans ou l'allocation des tâches (voir le chapitre 6).

Le mécanisme favori pour la résolution des conflits et la coordination, inspiré du modèle des humains, est la négociation.

Dans le cas des agents intelligents et dans les systèmes multi-agents, la négociation est une composante de base de l'interaction surtout parce que les agents sont autonomes (Jenning e.a. 2000); il n'y a pas de solution imposée à l'avance et les agents doivent arriver à trouver des solutions dynamiquement, pendant qu'ils résolvent les problèmes.

Figure 1. Interaction et zones d'influence dans un système multi-agents.

On peut citer plusieurs définitions pour la négociation. David et Smith (1980) disent que:

"Par négociation, on entend une discussion dans laquelle des individus intéressés échangent des informations et arrivent à un accord en commun."

Pruitts (1981) donne une définition qui s'appui sur des considérations psychologiques et pour laquelle le conflit est l'élément de base.

"La négociation est le processus par lequel plusieurs individus prennent une décision commune. Les participants expriment d'abord des demandes contradictoires, puis ils essaient de trouver un accord par concession ou par la recherche de nouvelles alternatives."

Si on regarde les deux définitions citées, on peut identifier deux aspects essentiels de la négociation: la communication et la prise de décisions.

Pour modéliser la négociation dans un logiciel multi-agents il faut alors prendre en compte les aspects suivants:

• Le langage de négociation - le langage utilisé par les agents pour échanger des informations pendant la négociation; le langage de négociation est composé d'un ensemble de primitives de communication.
  
  
• Le protocole de négociation - l'ensemble des règles qui régit la négociation: les participants possibles dans la négociation, les propositions légales que les participants peuvent faire, les états de la négociation (par exemple l'état initial où commence la négociation, l'état où on accepte des soumissions ou la fin de la négociation) et une règle pour déterminer quand on est arrivé à un accord ou quand il faut s'arrêter parce qu'aucun accord n'a pas n'a pu être trouvé .
  
  
• L'objet de négociation - un objet abstrait qui comprend les attributs qu'on veut négocier; dans certains cas il s'agit de négocier uniquement le prix, mais dans d'autres cas il faut aussi négocier plusieurs attributs comme le temps nécessaire pour satisfaire une commande, la qualité des produits, etc.
  
  
• Le processus de décision - le modèle que l'agent utilise pour prendre des décisions pendant la négociation. La partie la plus importante de la prise des décisions dans ce cas est la stratégie de négociation qui permet de déterminer quelle primitive de négociation l'agent doit choisir à un certain moment. Le processus de décision revient à répondre à la question: "Que dois-je faire maintenant?", par exemple liciter enchérir, abandonner, etc. Pour prendre une décision adéquate, un agent doit être capable de faire un raisonnement stratégique, notamment raisonner en tenant compte de ce que font/décident les autres agents et, s'il parvient à le savoir ou à le supposer, quel est le modèle de décision des autres agents.
  

Le protocole établit les règles de négociation. Par exemple, une négociation peut avoir lieu en un seul tour, comme l'enchère premier-prix offre-cachée, ou en plusieurs tours avec les participants faisant des offres (soumission) à chaque tour. L'exemple qui suit (qui peut avoir lieu aussi bien entre agents humains que logiciels) montre une négociation avec plusieurs tours.

Le nombre de participants et les interactions possibles peuvent aussi varier:

• négociation un-à-un: un agent négocie avec un autre, par exemple dans le cas ou on essaie de négocier le prix d'achat d'une maison avec le représentant d'une agence immobilière
  
  
• négociation un-à-plusieurs: un seul agent négocie avec plusieurs autres agents, par exemple les enchères où un agent veut vendre un objet
  
  
• négociation plusieurs-à-plusieurs: plusieurs agents négocient avec plusieurs d'autres agents en même temps, par exemple les participants à des enchères électroniques comme celles organisées par eBay (http://www.ebay.com).

Question: Quel type de protocole du point de vue du nombre de participants on a dans l'exemple avec l'agent A et l'agent B et quel est l'objet de la négociation?

Cliquer ici pour voir la réponse.