Experimental analysis of contract net protocol in multi-robot task allocation

Aleksis Liekna; Egons Lavendelis; Arvids Grabovskis

doi:10.2478/v10312-012-0001-7

.blurhash-client-img { display: none !important; }

Experimental analysis of contract net protocol in multi-robot task allocation

Applied Computer Systems

Volume 13 (2012): Issue 1 (October 2012)

By: Aleksis Liekna, Egons Lavendelis and Arvids Grabovskis

Open Access

|Nov 2012

Abstract

- This paper focuses on the experimental analysts of Contract NET protocol for Multi-Robot task allocation. The problem domain consists of multiple vacuum cleaning robots that need to cooperate for cleaning an area that is beyond the capabilities of a single robot. A robot simulator has been used to experiment with various area and robot locations, and the summary of the effort required to process the tasks has been recorded. Experimental results show that using Contract NET protocol alone is not sufficient to achieve optimal results in task allocation. A more advanced strategy with or without involving the Contract NET protocol is required. Possible strategies are outlined and their analysis is the subject of the future work.

References

[1] J. S. Rosenschein and G. Zlotkin, Rules of Encounter: DesigningConventions for Automated Negotiation among Computers. MIT Press, Cambridge, MA., 1994.
Search in Google Scholar
[2] M. Wooldridge, An Introduction to MultiAgent Systems - SecondEdition, John Wiley & Sons, May 2009.
Search in Google Scholar
[3] “FIPA Interaction Protocol Specifications”. [Online] Available: http://www.fipa.org/repository/ips.php3 [Accessed: Sept 26.2011].
Search in Google Scholar
[4] C. La Fournie, Cooperation using Negotiations and the Contract-Net Protocol. Available online: http://pages.cpsc.ucalgary.ca/~laf/601.72/Negotiaion&ContractNet.pdf [Accessed Sept 26, 2011].
Search in Google Scholar
[5] E. Lavendelis et al., “Multi-agent Robotic System Architecture for Effective Task Allocation and Management.” In Recent Researches inCommunications, Electronics, Signal Processing & Automatic: Proceedings of the 11th WSEAS International Conference on Signal Processing, Robotics and Automation (ISPRA '12), United Kingdom, Cambridge, February 22-24, 2012. - pp 167-174.
Search in Google Scholar
[6] M.T., Ribes, “Optimization of Floor Cleaning Coverage Performance of a Random Path-Planning Mobile Robot.” Universitat de Lleida. Escola Politècnica Superior. Enginyeria en Informàtica, 2007..
Search in Google Scholar
[7] R. C.Arkin, T. Balch, and E. Nitz, “Communication of behavioural state in multi-agent retrieval tasks.” In Proceedings of the IEEE Intl. Conf. onRobotics and Automation (ICRA’, Atlanta, Georgia, 1993, pp. 588-594.
Search in Google Scholar
[8] P. Stone and M. Veloso, “Task Decomposition, Dynamic Role Assignment, and Low-Bandwidth Communication for Real-Time Strategic Teamwork”, Artificial Intelligence 110(2), 1999, pp. 241-273.10.1016/S0004-3702(99)00025-9
Search in Google Scholar
[9] B. P. Gerkey, “On Multi-Robot Task Allocation.” PhD Dissertation. University of Southern California Computer Science Department, August 2003.
Search in Google Scholar
[10] M.B. Dias, TraderBots: “A New Paradigm for Robust and Efficient Multirobot Coordination in Dynamic Environments.” Doctoral Dissertation, Robotics Institute, Carnegie Mellon University, 2004.
Search in Google Scholar
[11] J.-L. Deneubourg., G. Theraulaz and R Beckers, “Swarm-made architectures”. In Proceedings of the European Conference on ArtificialLife (ECAL), 1991, Paris, France, pp. 123-133.
Search in Google Scholar
[12] J.A. Kensler and A.Agah, “Neural networks-based adaptive bidding with the contract net protocol in multi-robot systems”. Journal AppliedIntelligence archive Vol. 31 (3), December 2009, pp. 347-362.10.1007/s10489-008-0131-1
Search in Google Scholar
[13] “FIPA Contract Net Interaction Protocol Specification.” Foundation for Intelligent Physical Agents, 2002. [Online] Available: http://www.fipa.org/specs/fipa00029/ [Accessed: Sept 26, 2011].
Search in Google Scholar
[14] R.G. Smith, “The Contract Net Protocol: High-Level Communication and Control in a Distributed Problem Solver.” In IEEE Transactions onComputers, Vol. C-29, No. 12, December 1980. pp. 1104-1113.10.1109/TC.1980.1675516
Search in Google Scholar
[15] Bellifemine F. et al., Developing Multi-Agent Systems With JADE, Wiley, 2004. 286 p.
Search in Google Scholar
[16] F.-S. Hsieh and C.Y. Chiang, “Workflow Planning in Holonic Manufacturing Systems with Extended Contract Net Protocol.” In Next-Generation Applied Intelligence, Lecture Notes in Computer Science, 2009, Vol. 5579/2009, pp. 701-710.
Search in Google Scholar
[17] J.S. Kinnebrew and G. Biswas, “Efficient Allocation of Hierarchically- Decomposable Tasks in a Sensor Web Contract Net.” In Proceedings ofthe 2009 IEEE/WIC/ACM International Joint Conference on WebIntelligence and Intelligent Agent Technology - Volume 02 (WI-IAT '09), Vol. 2. 2009. pp. 225-232.10.1109/WI-IAT.2009.154
Search in Google Scholar
[18] K. Goswami and A. Gupta, “Resource Selection in Grids Using Contract Net.” In Proceedings of the 6th Euromicro Conference on Parallel,Distributed and Network-Based Processing (PDP 2008), pp. 105-109, 2008.10.1109/PDP.2008.66
Search in Google Scholar
[19] U. Deshpande, A Gupta and A. Basu. “Performance Improvement of the Contract Net Protocol Using Instance Based Learning.” In DistributedComputing - IWDC 2003. Lecture Notes in Computer Science, 2003, Vol. 2918/2003, pp. 290-299.
Search in Google Scholar
[20] C. Dellarocas, M. Klein and J.A. Rodriguez-Aguilar. “An exceptionhandling architecture for open electronic marketplaces of contract net software agents.” Proceedings of the 2 ACM Conference on ElectronicCommerce, Minneapolis, MN, October 17-20, 2000.10.1145/352871.352896
Search in Google Scholar
[21] Sandholm, T. “An Implementation of the Contract Net Protocol Based on Marginal Cost Calculations.” In Proceedings of Eleventh NationalConference on Artificial Intelligence, pp. 256-262. January 1993.
Search in Google Scholar
[22] J. Kodama et al, “Multi-agent-based autonomous power distribution network restoration using contract net protocol.” In ElectricalEngineering in Japan, 166, 2009. pp. 56-63.10.1002/eej.20661
Search in Google Scholar
[23] M. Golfarelli, D. Maio and S. Rizzi. “A Task-Swap Negotiation Protocol Based on the Contract Net Paradigm.” Technical Report CSITE, No. 005-97, 1997.
Search in Google Scholar
[24] S. Paurobally and J. Cunningham. “Verifying the Contract Net Protocol: A Case Study in Interaction Protocol and Agent Communication Language Semantics.” In Proceedings of the second internationalworkshop on Logic and Communication in Multi-Agent Systems(LCMAS 2004), Nancy, France 16-20 August, 2004, pp. 98-117.
Search in Google Scholar
[25] B. Moore, et al., Eclipse Development using the Graphical EditingFramework and the Eclipse Modeling Framework, IBM Redbooks, 2004, [Online]. Available: http://www.redbooks.ibm.com/redbooks/pdfs/sg246302.pdf [Accessed April 12, 2012].
Search in Google Scholar

Articles in this issue

DOI: https://doi.org/10.2478/v10312-012-0001-7 | Journal eISSN: 2255-8691 | Journal ISSN: 2255-8683

Journal RSS Feed

Language: English

Page range: 6 - 14

Published on: Nov 8, 2012

Published by: Riga Technical University

In partnership with: Paradigm Publishing Services

Publication frequency: Volume open

Keywords:

Contract NET protocol,

Related subjects:

Artificial intelligence,

Information technology,

Project management,

Software development

© 2012 Aleksis Liekna, Egons Lavendelis, Arvids Grabovskis, published by Riga Technical University
This work is licensed under the Creative Commons License.

Volume 13 (2012): Issue 1 (October 2012)