Further extensions of FIPA Contract Net Protocol: threshold plus DoA

ABSTRACT

Being easily understood and implemented for resource allocation or task assignment, FIPA Contract Net Protocol (CNP) has been widely applied to kinds of Multi-Agent System (MAS). Basing on a typical extension to the original CNP, which was named as Contract Net with Confirmation Protocol (CNCP), this paper made two further extensions to CNP by the ideas of Threshold and Degree of Availability (DoA). CNCP enabled the agents to make proposals or accept offers in a continuous time, but it also increased the risk of getting sub-optimal deal or nothing for individual agent. Our research is just aiming at relieving this risk. The idea of threshold comes from the fact that: no matter how much proposals one agent sent out, it will get only one task to do at last. By setting a proper threshold, we can save many unnecessary computational costs in making or evaluating proposals. The concept of DoA is derived from the principle of Maximum Expected-Utility (MEU). With this concept, one agent will evaluate proposals not only by the required costs, it also takes the DoA of a participant as an important factor in choosing its best deal, so initiators can act in a more rational way. We also presented an under-consideration idea "Deadline", which might become another feasible way to increase system effectiveness and efficiency.

REFERENCES

• 1: Mark d'Inverno , Michael Luck, Formalising the contract net as a goal-directed system, Proceedings of the 7th European workshop on Modelling autonomous agents in a multi-agent world : agents breaking away: agents breaking away, p.72-85, February 1996, Einhoven, The Netherlands
• 2: FIPA Contract Net Interaction Protocol Specification. FIPA TC Communication. http://www.fipa.org/specs/pesspecs.tar.gz.
• 3: FIPA Iterated Contract Net Interaction Protocol Specification. FIPA TC Communication. http://www.fipa.org/specs/pesspecs.tar.gz
• 4: M. Fisher, M. Wooldridge. Specifying and Executing Protocols for Cooperative Action. In S. M. Deen, editor, CKBS-94-Proceedings of the Second International Working Conference on Cooperating Knowledge-Based Systems. Springer-Verlag, 1994.
• 5: Boris Kötting , Frank Maurer, A Concept for Supporting the Formation of Virtual Corporations through Negotiation, Proceedings of the 8th Workshop on Enabling Technologies on Infrastructure for Collaborative Enterprises, p.40-47, June 16-18, 1999
• 6: T. Knabe, M. Schillo, K. Fisher. Improvements to the FIPA Contract Net Protocol for Performance Increase and Cascading Applications. http://citeseer.nj.nec.com/542858.html
• 7: R. J. Rabelo , L. M. Camarinha-Matos , H. Afsarmanesh, Multiagent perspectives to agile scheduling, Proceedings of the 3rd IEEE/IFIP international conference on Intelligent systems for manufacturing : multi-agent systems and virtual organizations: multi-agent systems and virtual organizations, p.51-66, September 1998, Prague, Czech Republic
• 8: Stuart J. Russell , Peter Norvig, Artificial intelligence: a modern approach, Prentice-Hall, Inc., Upper Saddle River, NJ, 1995
• 9: T. Sandholm. An Implementation of the Contract Net Protocol Based on Marginal Calculations. In Eleventh National Conference on Artificial Intelligence, pages 256--262, 1993.
• 10: T. Sandholm, V. R. Lesser. Advantages of a Leveled Commitment Contracting Protocol. In AAAI, 126--133. 1996.
• 11: T. Sandholm, Y. Zhou. Surplus Equivalence of Leveled Commitment Contracts. Artificial Intelligence, 2002.
• 12: M. Schillo, K. Fischer, C. Kray. The Contract-Net with Confirmation Protocol: A solution to a fundamental problem of DAI. DFKI Technical Memo. 15, 2000.
• 13: M. Schillo, B. Fley, and M. Florian Self-Organization in Multi-Agent Systems: From Agent Interaction to Agent Organization. http://citeseer.nj.nec.com/schillo02selforganization.html,2002.
• 14: R. G. Smith. The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver. IEEE Transactions on Computers, Series C-29 (12): 1104--1113, 1980.
• 15: Eric Werner, Cooperating agents: a unified theory of communication and social structure, Distributed Artificial Intelligence (Vol. 2), Morgan Kaufmann Publishers Inc., San Francisco, CA, 1989

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence

Keywords:
CNCP, Contract Net Protocol, DoA, MEU, Multi-Agent System, deadline, threshold