Contract Net Protocol

Le Contract Net Protocol ou protocole de réseau contractuel est un protocole d'interaction utilisé dans les systèmes multi-agents, introduit en 1980 par Reid G. Smith.

Il est utilisé pour faire de l'allocation de tâches parmi des agents autonomes, au sein d'une architecture fondée sur le parallélisme. Il est proche des protocoles d'enchères scellées. Il repose principalement sur le principe de sous-traitance des tâches : un émetteur propose à plusieurs agents une tache, qui formulent une proposition, laquelle est choisie par l'émetteur initial pour allouer la réalisation de celle-ci.

Description

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.

Mise en œuvre

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

Le Contract Net protocol 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. Il a également été utilisé pour l'allocation de tâches multi-robots, mais aussi comme mécanisme de marché dans des places de marché de commerce en ligne et dans le domaine des chaînes logistiques.

Complications et extensions

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âche 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 :

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.

Notes et références

Articles connexes

• Agent intelligent
• Système multi-agents