Contract Net Protocol

Last updated September 23, 2020

The Contract Net Protocol (CNP) is a task-sharing protocol in multi-agent systems, introduced in 1980 by Reid G. Smith.^[1] It is used to allocate tasks among autonomous agents. It is close to sealed auctions protocols. It mainly relies on the Subcontractor: a manager proposes a task to several agents. The latter make a proposal among which the manager chooses to allocate the task. This task can then be divided and subcontracted.

Formal description

The formalization of the protocol can be performed through the speech act theory. In this protocol, each agent can be either manager or contractor

The protocol is initialized by the manager, who sends a call-for-proposals to the contractors
The contractors can send either a proposal if they are interested or a reject if they are not. This proposal is provided with all the elements required by the manager to make its choice.
The manager chooses among the proposals the one that suits it best, and sends to the corresponding contractor an accept. It send a reject to the other contractors to inform them of its decision.
Once the contract has been accomplished, the contractor informs the manager using an inform message. If there is a result to communicate, it is also communicated through the inform message. If the contractor cannot fulfill its engagement, it informs the manager through a cancel message.

The Contract Net Protocol can be represented using the AUML formalism:

Contract Net Protocol AUML Diagram CNP.svg — Contract Net Protocol AUML Diagram

This protocol can be used to implement hierarchical organizations, where a manager assigns tasks to contractors, who in turn decompose into lower level task and assign them to the lower level. This kind of organization can be used when agents are cooperative, i.e. when their objectives are identical. In this situation, it is possible to make sure that the contractors do not lie to the manager when they make their proposal. When the agents are competitive, the protocol ends up in a marketplace organization, very similar to auctions.^[2]

Implementation

The protocol has been implemented by the FIPA in the ACL (Agent Communication Language).^[3]

The Contract Net Protocol has been implemented for various problems and contexts. The original article describes a sensor network use case. Subsequent work showed its utility in this context.^[4] It has also been used for Multi-Robot Task Allocation.^[5] It has also been used as a negotiation protocol both for e commerce marketplaces ^[6] and for supply chains.^[7]

Issues and extensions

Reid G Smith identified several issues related to its protocol. In particular, he proposes to create only short messages, and to interact only with agents that could be relevant to the proposed task in order to avoid overloading the network communication in terms of exchanged messages. In order to limit the number of interactions, in the case where a manager knows with which contractor it would like to contract, it can contact it directly to make an offer, that the contractor can accept or not.

A second issue is related to the occupation rate of the contractor when there are many tasks. Indeed, in this case, it may be complicated for the manager to find available contractors. In order to solve this problem, the contractor can answer a call for proposals even if they are already working for another contract. This trick can be used to prevent a situation where the manager makes call for proposals without getting any answer because the contractors are all busy. In this case, the contractors add to their proposal the moment when they'll be ready to seal with the proposal from the manager. Similarly in this situation, it is possible to keep a list of all available contractors so that the manager can contact them first. This trick makes it possible to avoid a network overload due to the managers sending their call for proposals to all the agents over and over again while ensuring that they will eventually find a contractor to contract on the proposed task. This information is directly sent to the managers by the contractors.

Beyond extensions proposed by the author, several works have extended the Contract Net Protocol. One of the issues raised by it is the fact that the manager cannot precise what it values most. It must choose among the proposals it receives from the contractors. In the case where each contractor can make a range of proposals, this can lead to suboptimal solutions. To address this issue, the FIPA also proposes an iterated version of the protocol in which the manager can make a new call for proposal some of the contractors that answered it, and refuse others, eventually accepting one of them. The resulting protocol can be compared with the iterated auction protocols. As the CNP, this protocol can be represented as an AUML diagram ^[8]

Another issue of the protocol is actually dealing with the task. In the original protocol, a contractor that makes a proposal commits to accomplish the task it has made a proposal on, whatever it takes. The failure of the task is only taken in consideration through the cancel message informing the manager that the task won't be addressed, without any sanction for the contractor. In the case where the agent are selfish, they therefore may have an incentive to make as many proposals as they can, and only fulfill the most profitable ones. In a collaborative context, the agent have no way to know if opting out from a task in order to commit to another one is good for the overall system. An extension of the protocol has been released in 1995 by Tuomas Sandholm and Victor Lesser in order to take these elements into account and define beforehand a commitment cost for the contractor to pay if they cannot accomplish the task.^[9]

Related Research Articles

The Dynamic Host Configuration Protocol (DHCP) is a network management protocol used on Internet Protocol (IP) networks, whereby a DHCP server dynamically assigns an IP address and other network configuration parameters to each device on the network, so they can communicate with other IP networks. A DHCP server enables computers to request IP addresses and networking parameters automatically from the Internet service provider (ISP), reducing the need for a network administrator or a user to manually assign IP addresses to all network devices. In the absence of a DHCP server, a computer or other device on the network needs to be manually assigned an IP address, or to assign itself an APIPA address, the latter of which will not enable it to communicate outside its local subnet.

A real-time operating system (RTOS) is an operating system (OS) intended to serve real-time applications that process data as it comes in, typically without buffer delays. Processing time requirements are measured in tenths of seconds or shorter increments of time. A real-time system is a time-bound system which has well-defined, fixed time constraints. Processing must be done within the defined constraints or the system will fail. They either are event-driven or time-sharing. Event-driven systems switch between tasks based on their priorities, while time-sharing systems switch the task based on clock interrupts. Most RTOSs use a pre-emptive scheduling algorithm.

The Simple Mail Transfer Protocol (SMTP) is a communication protocol for electronic mail transmission. As an Internet standard, SMTP was first defined in 1982 by RFC 821, and updated in 2008 by RFC 5321 to Extended SMTP additions, which is the protocol variety in widespread use today. Mail servers and other message transfer agents use SMTP to send and receive mail messages. SMTP servers commonly use the Transmission Control Protocol on port number 25.

Simple Network Management Protocol (SNMP) is an Internet Standard protocol for collecting and organizing information about managed devices on IP networks and for modifying that information to change device behaviour. Devices that typically support SNMP include cable modems, routers, switches, servers, workstations, printers, and more.

The Address Resolution Protocol (ARP) is a communication protocol used for discovering the link layer address, such as a MAC address, associated with a given internet layer address, typically an IPv4 address. This mapping is a critical function in the Internet protocol suite. ARP was defined in 1982 by RFC 826, which is Internet Standard STD 37.

Link-state routing protocols are one of the two main classes of routing protocols used in packet switching networks for computer communications, the other being distance-vector routing protocols. Examples of link-state routing protocols include Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS).

SIMPLE, the Session Initiation Protocol for Instant Messaging and Presence Leveraging Extensions, is an instant messaging (IM) and presence protocol suite based on Session Initiation Protocol (SIP) managed by the Internet Engineering Task Force. Contrary to the vast majority of IM and presence protocols used by software deployed today, SIMPLE is an open standard like XMPP.

CNP may refer to:

Secure multi-party computation is a subfield of cryptography with the goal of creating methods for parties to jointly compute a function over their inputs while keeping those inputs private. Unlike traditional cryptographic tasks, where cryptography assures security and integrity of communication or storage and the adversary is outside the system of participants, the cryptography in this model protects participants' privacy from each other.

In computer networking, a reliable protocol is a communication protocol that notifies the sender whether or not the delivery of data to intended recipients was successful. Reliability is a synonym for assurance, which is the term used by the ITU and ATM Forum.

Agent Communication Language (ACL), proposed by the Foundation for Intelligent Physical Agents (FIPA), is a proposed standard language for agent communications. Knowledge Query and Manipulation Language (KQML) is another proposed standard.

The processes of government procurement in the United States enable federal, state and local government bodies in the United States to acquire goods, services, and interests in real property.

Paxos is a family of protocols for solving consensus in a network of unreliable or fallible processors. Consensus is the process of agreeing on one result among a group of participants. This problem becomes difficult when the participants or their communications may experience failures.

The core idea of Artificial Intelligence systems integration is making individual software components, such as speech synthesizers, interoperable with other components, such as common sense knowledgebases, in order to create larger, broader and more capable A.I. systems. The main methods that have been proposed for integration are message routing, or communication protocols that the software components use to communicate with each other, often through a middleware blackboard system.

Java Agent Development Framework, or JADE, is a software framework for the development of intelligent agents, implemented in Java. JADE system supports coordination between several agents FIPA and provides a standard implementation of the communication language FIPA-ACL, which facilitates the communication between agents and allows the services detection of the system. JADE was originally developed by Telecom Italia and is distributed as free software.

The Better Approach To Mobile Adhoc Networking (B.A.T.M.A.N.) is a routing protocol for multi-hop mobile ad hoc networks which is under development by the German "Freifunk" community and intended to replace the Optimized Link State Routing Protocol (OLSR).

In distributed computing, leader election is the process of designating a single process as the organizer of some task distributed among several computers (nodes). Before the task is begun, all network nodes are either unaware which node will serve as the "leader" of the task, or unable to communicate with the current coordinator. After a leader election algorithm has been run, however, each node throughout the network recognizes a particular, unique node as the task leader.

Agent-oriented programming (AOP) is a programming paradigm where the construction of the software is centered on the concept of software agents. In contrast to object-oriented programming which has objects at its core, AOP has externally specified agents at its core. They can be thought of as abstractions of objects. Exchanged messages are interpreted by receiving "agents", in a way specific to its class of agents.

Gbcast is a reliable multicast protocol that provides ordered, fault-tolerant (all-or-none) message delivery in a group of receivers within a network of machines that experience crash failure. The protocol is capable of solving Consensus in a network of unreliable processors, and can be used to implement state machine replication. Gbcast can be used in a standalone manner, or can support the virtual synchrony execution model, in which case Gbcast is normally used for group membership management while other, faster, protocols are often favored for routine communication tasks.

MaSMT is a free, lightweight Multi-agent system development framework, design through the Java environment. The MaSMT3 framework provides three types of agents, namely ordinary agent and managing agent and root agent. The managing agent capable to handle set of ordinary agent and the root agent capable to handle set of manager agents. MaSMT3.0 includes few features than the previous versions. MaSMT 3.0 includes root agent to handle swam of agents, Environment handling features to dynamically store agent's ontology, and notice board has been introducing to see required messages and events. In addition to these main features, agent status monitor has been introducing to view transporting messages. Multi-agent technology is modern software palindrome that capable of handling the complexity of a software system and providing intelligent solutions through the power of agent communication. A framework is a useful tool to develop multi-agent system and it saves lot of programmer's time and provides standards for the agent development.

References

↑ Smith (December 1980). "The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver". IEEE Transactions on Computers. C-29 (12): 1104–1113. doi:10.1109/TC.1980.1675516. ISSN 0018-9340.
↑ Horling, Bryan; Lesser, Victor (2005-11-11). "A survey of multi-agent organizational paradigms". The Knowledge Engineering Review. 19 (4): 281. doi:10.1017/S0269888905000317. ISSN 0269-8889.
↑ "FIPA Contract Net Interaction Protocol Specification". fipa.org. Retrieved 2019-04-09.
↑ Chen, L.; Xue-song, Q.; Yang, Y.; Gao, Z.; Qu, Z. (July 2012). "The contract net based task allocation algorithm for wireless sensor network". 2012 IEEE Symposium on Computers and Communications (ISCC). pp. 000600–000604. doi:10.1109/ISCC.2012.6249362. ISBN 978-1-4673-2713-8.
↑ Grabovskis, Arvids; Lavendelis, Egons; Liekna, Aleksis (2012-11-08). "Experimental analysis of contract net protocol in multi-robot task allocation". Applied Computer Systems. 13 (1): 6–14. doi: 10.2478/v10312-012-0001-7 .
↑ Sandholm, Tuomas (1993). "An implementation of the contract net protocol based on marginal cost calculations" (PDF). AAAI-93 Proceedings. pp. 256–262.
↑ (Roger) Jiao, Jianxin; You, Xiao; Kumar, Arun (July 2006). "An agent-based framework for collaborative negotiation in the global manufacturing supply chain network". Robotics and Computer-Integrated Manufacturing. 22 (3): 239–255. doi:10.1016/j.rcim.2005.04.003.
↑ "FIPA Iterated Contract Net Interaction Protocol Specification". fipa.org. Retrieved 2019-04-09.
↑ Sandholm, Tuomas; Lesser, Victor (1995). "Issues in automated negotiation and electronic commerce: Extending the contract net framework" (PDF). Proceedings of the First International Conference on Multiagent Systems. pp. 328–335.