Contract Net Protocol

Le protocole s'appuie sur la formalisation des interactions sous la forme d'actes de langage.

Les agents peuvent jouer deux rôles, manager ou contractor :

1. le protocole est initialisé par le manager, qui envoie un appel à proposition (en anglais call for proposal) ;
2. les contractors génèrent des propositions (en anglais proposals) indiquant tous les éléments pertinents pour que le manager fasse son choix et le lui envoient ;
3. le manager choisit la proposition qu'il préfère et envoie une notification d'acceptation (accept) au contractor ayant emporté l'enchère. Il envoie aussi une notification de rejet (reject) aux autres contractors ;
4. enfin, une fois la tâche exécutée, le contractor en informe le manager. Si le contrat comprenait un résultat à communiquer, il lui envoie également ce résultat (inform). Si le contrat a échoué, il l'en informe (cancel).

Le Contract Net Protocol peut être représenté en utilisant le formalisme AUML.

Diagramme AUML du Contract Net Protocol

Le protocole peut être utilisé pour implémenter des organisations de type hiérarchique, où un manager assigne des tâches à des contractors, qui eux-mêmes les décomposent en sous-tâches et les assignent au niveau suivant et ainsi de suite. Cette organisation est utilisée lorsque les agents sont coopératifs, c'est-à-dire lorsque leurs objectifs sont identiques. On peut ainsi être sûr que les contractors ne mentent pas au manager lorsqu'ils font une proposition. Lorsque les agents sont compétitifs, le protocole aboutit à une organisation de type marché, de manière identique aux enchères[2].

Le protocole a été implémenté par la FIPA dans son langage ACL (Agent Communication Language), à l'aide des primitives fournies par le langage[3].

Le Contract Net procotol a été utilisé dans des contextes très divers. L'article originel décrit un cas d'application pour un réseau de senseurs. Des travaux ultérieurs ont effectivement montré son utilité dans un tel contexte[4]. Il a également été utilisé pour l'allocation de tâches multi-robots[5], mais aussi comme mécanisme de marché dans des places de marché de commerce en ligne[6] et dans le domaine des chaînes logistiques[7].

Reid G Smith a identifié plusieurs problématiques soulevées par son protocole. En particulier, il propose de ne créer que des messages courts et de n'interagir qu'avec les agents pertinents afin d'éviter une saturation du réseau en termes de messages échangés. Afin de limiter le nombre d'interactions, dans le cas où un manager sait à quel contractor il souhaite déléguer son contrat, il peut également le contacter directement en lui faisant une offre.

Une seconde problématique concerne l'occupation des contractors dans le cas où il y a beaucoup de tâches. En effet, dans ce cas, il peut être compliqué pour le manager de trouver des contractors disponibles. Pour pallier ce problème, les contractors peuvent être dotés de la capacité de répondre à un appel à proposition même s'ils sont déjà occupés, afin d'éviter qu'un manager ayant fait un appel ne se retrouve sans aucune réponse faute d'agent disponible. Dans ce cas, ils répondent en indiquant quand ils seront disponibles pour traiter la tâches qui leur est soumise. De même, il est possible de garder une trace des contractors disponibles afin de permettre aux managers de les contacter en priorité. Cela permet à la fois d'éviter que les managers ne contactent tous les contractors, risquant ainsi de saturer le réseau, tout en s'assurant qu'ils trouveront un contractor pour traiter leur tâche. Cette information est directement transmise par les contractors aux managers.

Au-delà des extensions proposées par l'auteur, plusieurs travaux ont été menés afin d'étendre le Contract Net Protocol. L'une des problématique posée par le protocole est qu'il ne permet pas au manager de spécifier quelles sont ses attentes : il doit se contenter de choisir parmi les propositions qui lui sont faites par les contractors. Pour répondre à ce besoin, la FIPA propose également une version itérée du protocole, où le manager peut faire un nouvel appel à proposition à certains contractors lui ayant répondu en plus d'accepter ou refuser les propositions faites par les contractors. Il s'ensuit une négociation identique à des enchères itérées. Ce protocole peut également être représenté sous la forme d'un diagramme AUML[8] :

Diagramme AUML de l'Iterated Contract Net Protocol

Un autre problème soulevé par ce protocole est l'accomplissement de la tâche. Dans la conception originelle du protocole, un contractor qui fait une offre s'engage à accomplir cette dernière à tous prix. L'échec de la tâche n'est abordé que sous la forme d'un message informant le manager, mais aucune contre-mesure n'est prise vis-à-vis du contractor. Dans le cas où le protocole est utilisé avec des agents compétitifs, les contractors peuvent donc avoir une incitation à faire des offres pour tous les appels, n'accomplissant que les tâches lui rapportant le plus. Dans un cadre collaboratif, les agents n'ont pas de moyen de savoir si se désengager d'une tâche pour en accomplir une autre est rentable. Une version du protocole, publiée en 1995 par Tuomas Sandholm et Victor Lesser propose de définir en amont du contrat un coût de désengagement pour les contractors, qu'ils devront payer si jamais ils ne sont pas en mesure d'accomplir cette dernière[9].

• Agent intelligent
• Système multi-agents