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

PDF (PC)

1743

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.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] WANG Su-yu,<\sup>,AI Xing<\sup>,ZHAO Jun<\sup>,LI Zuo-li<\sup>,LIU Zeng-wen<\sup> . Milling force prediction model for highspeed end milling 3Cr2Mo steel[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(1): 1 -5 .
[2] LI Kan . Empolder and implement of the embedded weld control system[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2008, 38(4): 37 -41 .
[3] KONG Xiang-zhen,LIU Yan-jun,WANG Yong,ZHAO Xiu-hua . Compensation and simulation for the deadband of the pneumatic proportional valve[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(1): 99 -102 .
[4] CHEN Rui, LI Hongwei, TIAN Jing. The relationship between the number of magnetic poles and the bearing capacity of radial magnetic bearing[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2018, 48(2): 81 -85 .
[5] 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 .
[6] JI Tao,GAO Xu/sup>,SUN Tong-jing,XUE Yong-duan/sup>,XU Bing-yin/sup> . Characteristic analysis of fault generated traveling waves in 10 Kv automatic blocking and continuous power transmission lines[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(2): 111 -116 .
[7] . [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 27 -32 .
[8] WANG Li-ju,HUANG Qi-cheng,WANG Zhao-xu . [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2006, 36(6): 51 -56 .
[9] Yue Khing Toh1， XIAO Wendong2， XIE Lihua1. Wireless sensor network for distributed target tracking: practices via real test bed development[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 50 -56 .
[10] SUN Dianzhu, ZHU Changzhi, LI Yanrui. [J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2009, 39(1): 84 -86 .
Copyright 2018 © Editorial office of Journal of Shandong University (Engineering Science)
Supported by Beijing Magtech Co.Ltd