User:Cedric Buron/sandbox
Formal description
[edit]The formalization of the protocol can be performed through the speech act theory. In th 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 represente using the AUML formalism:
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 objectove are identical. In this situation, it is possible to make sur 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 maketlace organization, very similar to auctions[1].
Implementation
[edit]The protocol has been implemented by the FIPA in the ACL (Agent Communication Language), using the prformatives it provides[2].
The Contract Net Protocol has been implemented for vaious problems and contexts. The original article describes a sensor network use case. Subsequent work showed its utilisty in this context [3]. It has also been used for Multi-Robot Task Allocation [4]. It has also been used as a negotiation protocol both for e commerce marketplaces [5] and for supply chains [6].
Issues and extensions
[edit]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 use 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 a AUML diagram [7]
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 [8].
Références
[edit]- ^ Horling, Bryan; Lesser, Victor (2005-11-11). "A survey of multi-agent organizational paradigms". The Knowledge Engineering Review. 19 (04): 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. (2012-7). "The contract net based task allocation algorithm for wireless sensor network". 2012 IEEE Symposium on Computers and Communications (ISCC): 000600–000604. doi:10.1109/ISCC.2012.6249362.
{{cite journal}}: Check date values in:|date=(help) - ^ 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: 256–262.
- ^ (Roger) Jiao, Jianxin; You, Xiao; Kumar, Arun (2006-7). "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.
{{cite journal}}: Check date values in:|date=(help) - ^ "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). ICMAS 1995: 328–335.