Protocolo de red contractual

El Protocolo de Red de Contratos (CNP) es un protocolo de reparto de tareas en sistemas multiagente , introducido en 1980 por Reid G. Smith. ^{[ 1 ]} Se utiliza para asignar tareas entre agentes autónomos. Es similar a los protocolos de subastas selladas . Se basa principalmente en el Subcontratista : un gestor propone una tarea a varios agentes. Estos últimos hacen una propuesta, entre las cuales el gestor elige para asignar la tarea. Esta tarea puede entonces dividirse y subcontratarse.

La formalización del protocolo puede realizarse mediante la teoría de los actos de habla . En este protocolo, cada agente puede ser gerente o contratista.

1. El protocolo lo inicia el gerente, quien envía una solicitud de propuestas a los contratistas.
2. Los contratistas pueden enviar una propuesta si están interesados ​​o rechazarla si no lo están. Esta propuesta incluye todos los elementos necesarios para que el gerente tome su decisión.
3. El gerente elige entre las propuestas la que mejor se ajusta a sus necesidades y envía una aceptación al contratista correspondiente . A los demás contratistas les envía un rechazo para informarles de su decisión.
4. Una vez finalizado el contrato, el contratista informa al gerente mediante un mensaje informativo . Si hay algún resultado que comunicar, también se comunica a través del mismo mensaje. Si el contratista no puede cumplir con su compromiso, informa al gerente mediante un mensaje de cancelación .

El protocolo Contract Net se puede representar utilizando el formalismo AUML :

Este protocolo puede utilizarse para implementar organizaciones jerárquicas, donde un gerente asigna tareas a contratistas, quienes a su vez las descomponen en tareas de nivel inferior y las asignan al nivel inferior. Este tipo de organización puede utilizarse cuando los agentes cooperan, es decir, cuando sus objetivos son idénticos. En esta situación, es posible garantizar que los contratistas no mientan al gerente al presentar su propuesta. Cuando los agentes compiten, el protocolo desemboca en una organización de mercado, muy similar a las subastas. ^{[ 2 ]}

El protocolo ha sido implementado por la FIPA en el ACL (Agent Communication Language). ^{[ 3 ]}

El Protocolo de Red de Contratos se ha implementado para diversos problemas y contextos. El artículo original describe un caso de uso de red de sensores. Trabajos posteriores demostraron su utilidad en este contexto. ^{[ 4 ]} También se ha utilizado para la asignación de tareas a múltiples robots. ^{[ 5 ]} Asimismo, se ha utilizado como protocolo de negociación tanto para mercados de comercio electrónico ^{[ 6 ]} como para cadenas de suministro. ^{[ 7 ]}

Reid G. Smith identificó varios problemas relacionados con su protocolo. En particular, propone crear solo mensajes cortos e interactuar únicamente con agentes que puedan ser relevantes para la tarea propuesta, a fin de evitar la sobrecarga de la red en términos de mensajes intercambiados. Para limitar el número de interacciones, si un gerente sabe con qué contratista desea contratar, puede contactarlo directamente para hacerle una oferta, que el contratista puede aceptar o rechazar.

Un segundo problema se relaciona con la tasa de ocupación del contratista cuando hay muchas tareas. De hecho, en este caso, puede resultar complicado para el gerente encontrar contratistas disponibles. Para solucionar este problema, el contratista puede responder a una solicitud de propuestas incluso si ya está trabajando en otro contrato. Este truco puede utilizarse para evitar que el gerente solicite propuestas sin obtener respuesta porque todos los contratistas están ocupados. En este caso, los contratistas añaden a su propuesta el momento en que estarán listos para firmar con la propuesta del gerente. Asimismo, en esta situación es posible mantener una lista de todos los contratistas disponibles para que el gerente pueda contactarlos primero. Este truco permite evitar la sobrecarga de la red debido a que los gerentes envían repetidamente su solicitud de propuestas a todos los agentes, asegurando que finalmente encontrarán un contratista para la tarea propuesta. Esta información es enviada directamente a los gerentes por los contratistas.

Más allá de las extensiones propuestas por el autor, varios trabajos han ampliado el Protocolo de Red de Contratos (CNP). Uno de los problemas que plantea es que el gestor no puede precisar qué valora más. Debe elegir entre las propuestas que recibe de los contratistas. En el caso de que cada contratista pueda presentar diversas propuestas, esto puede dar lugar a soluciones subóptimas. Para abordar este problema, la FIPA también propone una versión iterada del protocolo en la que el gestor puede realizar una nueva convocatoria de propuestas a algunos de los contratistas que respondieron y rechazar a otros, aceptando finalmente a uno de ellos. El protocolo resultante puede compararse con los protocolos de subasta iterados. Al igual que el CNP, este protocolo puede representarse como un diagrama AUML ^{[ 8 ].}

Otro problema del protocolo radica en la gestión de la tarea. En el protocolo original, un contratista que realiza una propuesta se compromete a completarla, cueste lo que cueste. El incumplimiento de la tarea solo se considera mediante un mensaje de cancelación que informa al gerente de que la tarea no se abordará, sin ninguna sanción para el contratista. En el caso de que el agente sea egoísta, podría tener un incentivo para realizar tantas propuestas como sea posible y solo cumplir con las más rentables. En un contexto colaborativo, el agente no tiene forma de saber si renunciar a una tarea para comprometerse con otra es beneficioso para el sistema en general. En 1995, Tuomas Sandholm y Victor Lesser publicaron una extensión del protocolo para tener en cuenta estos elementos y definir de antemano un costo de compromiso que el contratista debe pagar si no puede completar la tarea. ^{[ 9 ]}

• Sistema multiagente
• Agente inteligente
• Modelo basado en agentes