基于改进合同网协议的多Agent动态任务分配

doi:10.6040/j.issn.1672-3961.1.2015.218

山东大学学报(工学版) ›› 2016, Vol. 46 ›› Issue (2): 51-56.doi: 10.6040/j.issn.1672-3961.1.2015.218

基于改进合同网协议的多Agent动态任务分配

李明^1,2,刘玮^1,2,张彦铎^1,2

1. 武汉工程大学计算机科学与工程学院, 湖北武汉 430073;2. 智能机器人湖北省重点实验室(武汉工程大学), 湖北武汉 430073

收稿日期:2015-05-12 出版日期:2016-04-20 发布日期:2015-05-12
通讯作者: 刘玮(1981— ),男,湖北武汉人,副教授,博士,主要研究方向为需求工程软件演化.E-mail:liuwei@wit.edu.cn E-mail:westkash@qq.com
作者简介:李明(1991— ),男,湖北咸宁人,硕士研究生,主要研究方向为多代理系统.E-mail:westkash@qq.com
基金资助:
国家自然科学基金资助项目(61502355,61272115);湖北省自然科学基金资助项目(2014CFB779);武汉工程大学科学研究基金资助项目(K201475)

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

LI Ming^1,2, LIU Wei^1,2, ZHANG Yanduo^1,2

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

摘要： 为了使多Agent系统的任务分配更能适用于动态环境,提出一种改进的合同网协议的多Agent动态任务分配方法。该方法首先建立Agent能力模型和Agent执行的任务描述,在此基础上改进合同网中的招标阶段,Agent通过将正在执行的任务进行招标来动态改变自身能力以进行任务的再分配。最后,通过建立AGV(automatic guilded vehicle)物流仓库搬运仿真系统以验证改进方法的可行性和有效性。仿真结果表明,该方法能有效减少系统完成任务的总时间,提高了系统的整体效率,并且提高多Agent系统适应动态环境的能力。

关键词: 改进合同网, 动态环境, 任务分配, 多代理系统, 能力模型

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

中图分类号:

TP311

李明,刘玮,张彦铎. 基于改进合同网协议的多Agent动态任务分配[J]. 山东大学学报(工学版), 2016, 46(2): 51-56.

LI Ming, LIU Wei, ZHANG Yanduo. Mulit-Agent dynamic task allocation based on improved contract net protocol[J]. JOURNAL OF SHANDONG UNIVERSITY (ENGINEERING SCIENCE), 2016, 46(2): 51-56.

参考文献

[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.

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed

基于改进合同网协议的多Agent动态任务分配

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

PDF (PC)

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

多维度评价

本文评价

推荐阅读 10

[1]	何东之, 张吉沣, 赵鹏飞. 不确定性传播算法的MapReduce并行化实现[J]. 山东大学学报(工学版), 0, (): 22-28.
[2]	王换,周忠眉. 一种基于聚类的过抽样算法[J]. 山东大学学报(工学版), 2018, 48(3): 134-139.
[3]	读习习,刘华锋,景丽萍. 一种融合社交网络的叠加联合聚类推荐模型[J]. 山东大学学报(工学版), 2018, 48(3): 96-102.
[4]	杨天鹏,徐鲲鹏,陈黎飞. 非均匀数据的变异系数聚类算法[J]. 山东大学学报(工学版), 2018, 48(3): 140-145.
[5]	沈冀,马志强,李图雅,张力. 面向短文本情感分析的词扩充LDA模型[J]. 山东大学学报(工学版), 2018, 48(3): 120-126.
[6]	肖卓宇,何锫,余波,黎妍,胡振涛. 基于FCA与CBR的设计模式检测[J]. 山东大学学报(工学版), 2016, 46(2): 22-28.
[7]	王会青,孙宏伟,张建辉. 基于Map/Reduce的时间序列相似性搜索算法[J]. 山东大学学报(工学版), 2016, 46(1): 15-21.
[8]	陈宏兴, 周风余, 田天, 姜志飞, 陈竹敏. 服务机器人云计算平台SOA接口层模型设计[J]. 山东大学学报(工学版), 2015, 45(4): 31-39.
[9]	姚华传, 王丽珍, 吴萍萍, 邹目权. AC_SAR:基于强关联规则的可行动分簇算法[J]. 山东大学学报(工学版), 2014, 44(6): 38-46.
[10]	周风余, 赵文斐, 田天, 陈宏兴, 陈竹敏. 陪护机器人云存储系统设计及实现[J]. 山东大学学报(工学版), 2014, 44(5): 1-6.
[11]	刘金岭1, 王新功2, 周泓1. 基于短信文本信息流的多热点事件挖掘[J]. 山东大学学报(工学版), 2013, 43(3): 7-12.
[12]	张欣怡,翟玉庆*. 基于证据理论的信任模型中冲突证据[J]. 山东大学学报(工学版), 2013, 43(1): 48-53.
[13]	仲晓敏. 基于相似度的软件可信性评估方法[J]. 山东大学学报(工学版), 2012, 42(6): 13-18.
[14]	蔡虹,黄霞. 一种基于聚类算法的缺陷语句定位技术[J]. 山东大学学报(工学版), 2012, 42(6): 19-24.
[15]	张永军1,刘金岭2,于长辉3. 基于词贡献度的垃圾短信分类方法[J]. 山东大学学报(工学版), 2012, 42(5): 87-90.