基于改进合同网协议的多Agent动态任务分配
|
摘要
为了使多Agent系统的任务分配更能适用于动态环境,提出一种改进的合同网协议的多Agent动态任务分配方法。该方法首先建立Agent能力模型和Agent执行的任务描述,在此基础上改进合同网中的招标阶段,Agent通过将正在执行的任务进行招标来动态改变自身能力以进行任务的再分配。最后,通过建立AGV(automatic guilded vehicle)物流仓库搬运仿真系统以验证改进方法的可行性和有效性。仿真结果表明,该方法能有效减少系统完成任务的总时间,提高了系统的整体效率,并且提高多Agent系统适应动态环境的能力。
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.
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.
引文
[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 agents 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 network flow based heuristic approach for optimizing AGVmovements[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.
[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 agents 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 network flow based heuristic approach for optimizing AGVmovements[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.
© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号 地址：北京市海淀区学院路29号 邮编：100083 电话：办公室：(+86 10)66554848；文献借阅、咨询服务、科技查新：66554700 |