JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE) ›› 2016, Vol. 46 ›› Issue (2): 51-56.doi: 10.6040/j.issn.1672-3961.1.2015.218

Previous Articles     Next Articles

Mulit-Agent dynamic task allocation based on improved contract net protocol

LI Ming1,2, LIU Wei1,2, ZHANG Yanduo1,2   

  1. 1.School of Computer Science and Engineering, Wuhan Institute of Technology, Wuhan 430073, Hubei, China;
    2. Hubei Key Laboratory of Intelligent Robot(Wuhan Institute of Technology), Wuhan 430073, Hubei, China
  • Received:2015-05-12 Online:2016-04-20 Published:2015-05-12

Abstract: To apply the multi-agent system task allocation algorithm to dynamic environment, an improved contract net protocol was proposed. First, the agent capability model and the tasks description of agent execution were studied. Secondly, the agent changed its capability dynamically by putting the executing tasks out to tender, so that the tasks could be redistributed. Finally, the feasibility and effectiveness of the proposed method were proposed by building a simulation system of AGV warehouse. The results of simulation indicated that the proposed method could reduce the total time for fulfilling the tasks effectively, improve the overall efficiency of the system and improve the capability of multi-agent system to adapt to dynamic environment.

Key words: capability model, improved contract net protocol, dynamic environment, multi-agent system, task allocation

CLC Number: 

  • TP311
[1] 唐苏,朱一凡,李群,等.多Agent系统任务分配方法综述[J].系统工程与电子技术,2010, 32(10):2155-2161. TANG Su, ZHU Yifan, LI Qun.Survey of task allocation in multi agent systems[J].System Engineering and Electronics, 2010, 32(10):2155-2160.
[2] SMITH R G. The contract net protocol. High level communication and control in ditributed problem solver[J].IEEE Transaction on Computers, 1980, 29(12):1104-1113.
[3] 杨颖,武健,魏鹏.基于多智能体和合同网的巡 航导弹自主任务分配[J].战术导弹技术,2014, 2014(1):63-64. YANG Ying, WU Jian, WEI Peng. Autonomous task assignment of cruise missile base on multi-agent and CNP[J].Tactical Missile Technology, 2014, 2014(1):63-66.
[4] 秦久峰,曾凡明,陈于涛. 基于改进合同网的多Agent系统协作机理研究[J].武汉理工大学学报,2014,38(5):1065-1069. QIN Jiufeng, ZENG Fanming, CHEN Yuntao. Research on cooperation mechanism of multi-agent system based on improved Contract Net[J].Journal of Wuhan University of Technology, 2014, 38(5):1065-1069.
[5] LI Rui, WANG Hangyu. Research on the multiplatform cooperative guidance tasks allocation based on contract net protocol[J]. Affective Computing and Intelligent Interaction Advances in Intelligent and Soft Computing, 2012(137):561-569.
[6] QIN Ling, KAN Shuilin. Production dynamic scheduling method based on improved contract net of multiagent[C] //2012 International Conference of Intelligence Computation and Evolutionary Computation.New York, USA:Springer, 2013:929-936.
[7] 张琦琮,杨公平.基于Agent的银行业务排队系 统仿真研究[J].山东大学学报(工学版), 2011, 41(4):68-72. ZHANG Qizong, YANG Gongping. Study on an agent based simulation of banking queuing system[J].Journal of Shangdong University(Engineering Science), 2011, 41(4):68-72.
[8] SANDBOLM T W, LESSER V R. Issues in automated negotiation and electronic commerce:extending the contract net framework[C] //First International Conference on Multiagent system.San Fransisco,USA:Morgan Kaufmann, 1998:66-73.
[9] 张海俊, 史忠植. 动态合同网协议[J].计算机工程,2004,30(21):44-57. ZHANG Haijun, SHI Zhongzhi. Dynamic contract net protocol[J]. Computer Engineering, 2004, 30(21):44-57.
[10] 陈坚, 廖守忆,邓方林. 一种基于多Agent的计算机生产兵力协作方法[J].计算机仿真,2010,27(2):113-117. CHEN Jian, LIAO Shouyi, DENG Fanglin. A collaboration algorithm for computer generated forces based on multiagent systems[J].Computer Simulation, 2010, 27(2):113-117.
[11] 贺利坚. 多Agent系统中信任和信誉模型的研究[D].北京:北京交通大学,2011. HE Lijian. Research on trust and reputation model in multi-agent system[D]. Beijing:Beijing Jiaotong University, 2011.
[12] HAMAGAMI T, SHINJI H T. Multiagent based autonomous power distribution network restoration using contract net protocol[J].Electrical Engineering in Japan, 2009, 166(4):56-63.
[13] ZHANG Jin, CAO Yaoqin. Research on coorperation of multiple-agent based on contractnet protocol[C] //International Conference on Industrial Control and Electronics Engineering. Xi'an:IEEE, 2012:1945-1949.
[14] 李新亮,翟江涛,戴跃伟.动态环境下基于改进合同网的多Agent任务分配算法[J].科学技术与工程, 2013,12(27):8014-8019. LI Xinliang, ZHAI Jiangtao, DAI Yuewei. A task allocation algorithm base on improved contract net protocol under the dynamic environment[J].Science Technology and Engineering, 2013, 12(27):8014-8019.
[15] TOSHIHARU S, KENSUKE F, TOSHIO H. Effect of alternative distributed task allocation strategy based on local observations in contract net protocol[C] //Principles and Practice of Multi-Agent System Lecture Note in Computer Science. New York, USA:Springer, 2012:90-104.
[16] DORU P, CARLOS P. An extended contract net protocol with direct negotiation of managers[J].Service Orientation in Holonic and Multi-Agent Manufacturing and Robotics Studies in Computational Inteligence, 2014(544):81-95.
[17] AMAR K G, GUY E G.Equivalence class verification of the contract net protocol extension[J].International Journal on Software Tools for Technology Transfer, 2015, 2015(17):1-22.
[18] OZKIL A G, FAN Z, DWIDS S. Service robots for hospitals: a case study of transp-ortation tasks in a hospital[C] //Proceedings of the 2009 IEEE International Conference on Automation and Logistics. Arizona, USA:IEEE, 2009:289-294.
[19] HOU Chengi, HUANG Hanchen, LAN Tiansyung. The development of LOHAS automated guiding vehicle[J].Telkomnika-Indonesian Journal of Electrical Engineering, 2013, 11(11):6825-6830.
[20] TIBOR B, CATHOLIJN M, JO NKER, J T.Requirements analysis of an agents reasoning capability[C] //7th International Bi-Conference Workshop.New York,USA:Springer, 2006:48-63.
[21] JORGE A, MIGUELR CARLOS C, VICENTE J. Agent capability taxonomy for dynamic environments[C] //Hybrid Artificial Intelligent Systems: 7th International Co-nference. New York, USA:Springer, 2012:37-48.
[22] GIUSEPPE C, MARCELLO F, GIACOME L. A net-work flow based heuristic approach for optimizing AGV movements[J].Journal of Intelligent Manufacturing, 2013, 24(2):405-419.
[23] BUEHLER J, PAGNUCCO M.A framework for task planning in heterogeneous multirobot systems based on robot capabilities[C] //Proceedings of the National Conference on Artificial Intelligence. California, USA:AAAI, 2014:2527-2533.
[24] 马巧云. 基于多Agent系统的动态任务分配研究[D].武汉:华中科技大学,2006. MA Qiaoyun. Research on dynamic task allocation based on MAS[D]. Wuhan: Huazhong University of Science and Technology, 2006.
[25] SHARAD C S, ALOK K S, SURENDRA K M.Development of an intelligent agent-base AGV controller for a flexible manufac turing system[J].The International Jo urnal of Advanced Manufacturing Technology, 2008, 36(7):780-797.
[1] CUI Yang, ZHANG Ke, JIANG Bin. Fault estimation design for linear multi-agent systems with switching topologies [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(5): 263-270.
[2] WU Yanming, WANG Ruiyun, WANG Zhanshan. Fault detection for multi-agent systems based on intermediate observer [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(5): 96-102.
[3] YE Dan, ZHANG Tianyu, LI Kui. Adaptive fault-tolerant containment control for multi-agent systems with unknown global information [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2017, 47(5): 1-6.
[4] YU Zhen-mei1, YANG Rong-rong2, QI Feng-mei3, ZHANG Hui3, LIU Feng-ming4. A load balance model for Web services based on  immune stability maintenance [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2012, 42(3): 39-44.
Full text



[1] LI Ke,LIU Chang-chun,LI Tong-lei . Medical registration approach using improved maximization of mutual information[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(2): 107 -110 .
[2] YUE Yuan-Zheng. Relaxation in glasses far from equilibrium[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(5): 1 -20 .
[3] CHENG Daizhan, LI Zhiqiang. A survey on linearization of nonlinear systems[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 26 -36 .
[4] WANG Yong, XIE Yudong. Gas control technology of largeflow pipe[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 70 -74 .
[5] LIU Xin 1, SONG Sili 1, WANG Xinhong 2. [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 98 -100 .
[7] CHEN Huaxin, CHEN Shuanfa, WANG Binggang. The aging behavior and mechanism of base asphalts[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(2): 125 -130 .
[9] LI Shijin, WANG Shengte, HUANG Leping. Change detection with remote sensing images based on forward-backward heterogenicity[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(3): 1 -9 .
[10] ZHAO Ke-Jun, WANG Xin-Jun, LIU Xiang, CHOU Yi-Hong. Algorithms of continuous top-k join query over structured overlay networks[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(5): 32 -37 .