5. Négociation dans les systèmes multi-agents
5.4 Négociation pour l'allocation des tâches
5.4.1 Allocation des tâches par réseau contractuel
Jusqu'à maintenant on a discuté des protocoles de négociation
entre agents egocentrés, c'est à dire entre agents ayant
leurs propres buts. Dans cette section nous allons présenter des
protocoles de négociation qui ont été conçus
principalement en vue de la coordination des agents coopératifs,
ayant les mêmes buts, qui partagent et résolvent ensemble
des problèmes.
Le protocole réseau contractuel
("Contract Net" en anglais) a été une des premières
approches utilisées dans les systèmes multi-agents pour
résoudre le problème d'allocation des tâches (Davis
et Smith, 1983). Le protocole s'appuie sur une métaphore organisationnelle:
les agents coordonnent leurs activités grâce à l'établissement
de contrats afin d'atteindre des buts spécifiques.
Dans le protocole réseau contractuel, les agents peuvent prendre
deux rôles: gestionnaire et contractant.
L'agent qui doit exécuter une tâche (le gestionnaire) commence
par décomposer cette tâche en plusieurs sous-tâches.
Le gestionnaire annonce chaque sous-tâche sur un réseau d'agents
(les contractants). Les agents qui reçoivent une annonce de tâches
à accomplir évaluent l'annonce. Les agents qui ont les ressources
appropriées, l'expertise ou l'information requise pour accomplir
la tâche, envoient au gestionnaire des soumissions ("bids"
en anglais) qui indiquent leurs capacités à réaliser
la tâche. Le gestionnaire rassemble toutes les propositions qu'il
a reçues et alloue la tâche à l'agent qui a fait la
meilleure proposition. Ensuite, le gestionnaire et les contractants échangent
les informations nécessaires durant l'accomplissement des tâches.
Par exemple, le contractant annoncera au gestionnaire quand l'exécution
de la tâche sera terminée. Dans des cas exceptionnels, un
gestionnaire peut annuler le contrat: annoncer au contractant qu'il faut
abandonner l'exécution de la tâche.
Figure 3. Etapes du protocole réseau contractuel
Les rôles des agents ne sont pas spécifiés d'avance.
N'importe quel agent peut agir comme un gestionnaire et annoncer une tâche;
n'importe quel autre agent peut être un contractant pour une annonce
qu'on a faite. Cette flexibilité permet de nouvelles décompositions
des tâches: un contractant pour une tâche spécifique
peut agir comme un gestionnaire en décomposant sa tâche et
en annonçant les sous-tâches à d'autres agents. Les
liens entre les gestionnaires et les contractants pour diverses tâches
et sous-tâches forment un réseau contractuel hiérarchique
qui permet la division des tâches et la synthèse des résultats.
Le langage de communication FIPA
(présenté dans le chapitre 4
) fournit, en plus d'une série de primitives de communication et
d'une sémantique associée, une série de protocoles
d'interaction. Une partie des protocoles d'interaction fournis par FIPA
est énumérée ici:
FIPA-Request
FIPA-Querry
FIPA-Request-When
FIPA-Contract-Net
FIPA-Iterated-Contract-Net
FIPA-Auction-English
FIPA-Auction-Dutch
FIPA-Brokering
FIPA-Recruiting
FIPA-Subscribe
FIPA-Propose
Par exemple, dans le protocole de FIPA-Request (FIPA-Demande) un agent
demande à un autre agent d'exécuter une action, comme décrit
dans la figure 4. Le récepteur (en bleu dans la figure) peut consentir
ou peut refuser d'exécuter l'action ou encore répondre qu'il
n'a pas compris. En cas de refus, l'agent récepteur est obligé
de déclarer la raison du rejet.
Figure 4. Le protocole FIPA-Request
Les protocoles FIPA-Contract-Net (FIPA-Reseau-Contractuel) et FIPA-Iterated-Contract-Net
utilisent le protocole réseau contractuel pour permettre aux agents
l'exécution de la négociation. La figure 5 présente
le protocole FIPA-Contract_Net. Le gestionnaire (en rouge dans la figure)
fait une requête d'action; chaque contractant peut refuser ou faire
une proposition (propose(p2)) en réponse; le gestionnaire peut
accepter ou rejeter la proposition p2.
Figure 5. Le protocole FIPA-Contract-Net
Un problème qui peut survenir avec le réseau contractuel
est qu'une tâche puisse être attribuée à un
contractant moins qualifié pour la résoudre si un contractant
plus qualifié est occupé au moment de l'annonce des tâches.
Le protocole réseau contractuel a été utilisé
pour la résolution coopérative des problèmes, c'est
à dire la résolution des problèmes par des agents
coopératifs. Récemment, le protocole a été
généralisé pour le cas des agents egocentrés
aussi. Si tel est le cas, un agent qui reçoit une annonce de tâche
(contractant potentiel) avec, par exemple, un coût associé,
fera une soumission pour cette tâche uniquement si son coût,
à lui, pour l'exécution de la tâche est inférieur
à la valeur annoncée. De même, le gestionnaire, s'il
est capable d'exécuter lui-même la tâche, annoncera
la tâche à un coût inférieur à son propre
coût pour l'exécution de la tâche. Cette approche est
en accord avec le principe de la rationalité individuelle qu'on
a rencontré aussi dans le cas des enchères.
 Question:
Est-ce que le gestionnaire peut annuler un contrat dans un système
multi-agents avec agents egocentrés?
Cliquer ici pour voir
la réponse.
|
