多主体仿真系统的战术库设计
|
摘要
国际人工智能协会组织的机器人世界杯RoboCup(The Robot World Cup Soccer Games and Conferences)仿真比赛系统，是人工智能和机器人研究的一种集中表现，它的仿真比赛融合了决策与对策、神经网络、人工生命与智能控制等学科内容，是研究多智能体的一个很好的平台。
这篇论文首先介绍了多智能体系统，同时回顾了机器人足球世界杯的以往赛事，随后又给出了其仿真系统及其主要模型。而本论文的研究主要都建立在UvA_Trilearn_2003的基础上，除了对其结果的诸多改善外，我们做的主要工作如下：
给出了Agent具体的组织结构；
针对Winglet2005的特点设计了Agent的详细流程；
借用BP算法的思想设计了一种新的传球策略；
给出了决策树在不同角色下的具体的实现；
提出了一种具体的Agent消减算法，并在其基础上实现非通讯多Agent之间的协作；
设计了一个完整的战术库，并给出了战术库的具体实现。
本文所完成的工作，都在Winglet2005仿真球队中进行了实现，并对其进行相应的实验，同时证明了相关方法的可行性和有效性。
最后还对当前的工作做了简单的总结，并展望了将来的工作。希望能够给类似的研究和工作提供一定的参考。
RoboCup ( The Robot World Cup Soccer Games and Conferences ) simulation game system is a good sample of the research of artificial intelligence and robot. The simulation game includes such contents as decision-making 、 neural network and intelligent control. It is a good research platform for the research of MAS and has aroused the enthusiasm of many people.
After presenting the concept of Multi-Agent System and the background of RoboCup. this paper introduces soccer server and some important models in detail. In addition to much improvement based on the UvA_Trilearn_2003. the main contents and related original achievement of this paper are as follow:
This paper presents the framework of agent in detail;
The flow of agent is developed in Winglet2005:
A new strategy of pass is introduced based on BP algorithm;
Different roles of decision-making tree are implemented;
This paper has designed an agent-minify algorithm in detail, and implemented non-communicative multi-agent collaboration on it:
This paper puts forward the concept of tactics system, and develops a complete tactics system.
All the works in this paper have been implemented in Winglet 2005 simulation team. The experiment result shows that the approaches are valid and efficient.
In the end, this paper makes a conclusion of the work that has been done and should have done. I hope this thesis can give help to others who are interested in this field.
这篇论文首先介绍了多智能体系统，同时回顾了机器人足球世界杯的以往赛事，随后又给出了其仿真系统及其主要模型。而本论文的研究主要都建立在UvA_Trilearn_2003的基础上，除了对其结果的诸多改善外，我们做的主要工作如下：
给出了Agent具体的组织结构；
针对Winglet2005的特点设计了Agent的详细流程；
借用BP算法的思想设计了一种新的传球策略；
给出了决策树在不同角色下的具体的实现；
提出了一种具体的Agent消减算法，并在其基础上实现非通讯多Agent之间的协作；
设计了一个完整的战术库，并给出了战术库的具体实现。
本文所完成的工作，都在Winglet2005仿真球队中进行了实现，并对其进行相应的实验，同时证明了相关方法的可行性和有效性。
最后还对当前的工作做了简单的总结，并展望了将来的工作。希望能够给类似的研究和工作提供一定的参考。
RoboCup ( The Robot World Cup Soccer Games and Conferences ) simulation game system is a good sample of the research of artificial intelligence and robot. The simulation game includes such contents as decision-making 、 neural network and intelligent control. It is a good research platform for the research of MAS and has aroused the enthusiasm of many people.
After presenting the concept of Multi-Agent System and the background of RoboCup. this paper introduces soccer server and some important models in detail. In addition to much improvement based on the UvA_Trilearn_2003. the main contents and related original achievement of this paper are as follow:
This paper presents the framework of agent in detail;
The flow of agent is developed in Winglet2005:
A new strategy of pass is introduced based on BP algorithm;
Different roles of decision-making tree are implemented;
This paper has designed an agent-minify algorithm in detail, and implemented non-communicative multi-agent collaboration on it:
This paper puts forward the concept of tactics system, and develops a complete tactics system.
All the works in this paper have been implemented in Winglet 2005 simulation team. The experiment result shows that the approaches are valid and efficient.
In the end, this paper makes a conclusion of the work that has been done and should have done. I hope this thesis can give help to others who are interested in this field.
引文
[1] Http://www.robocup.org, 2003-9-12/2006-4-12.
[2] 贺建立．多智能体系统的开发[D]．合肥：安徽大学硕士论文，2004．
[3] Hewitt, Carl. Protection and Synchronization in Actor Systems [J], IBM Technical Disclosure Bulletin, 1974-11-1.
[4] 余澄丹．RoboCup智能体的开发和应用[D]．合肥：安徽大学硕士论文，2005．
[5] Genesereth, M. and Steven P. Ketchpel. Software Agents [J]. Communications of the ACM, 1994, 37(7).
[6] 史忠植．智能主体及其应用[M]．北京：科学出版社，2001．
[7] 杨增光．智能Agent的研究与实践[D]．合肥：安徽大学硕士论文，2004．
[8] 杜陶钧，黄鸿．多智能主体协作规划理论及其在RoboCup中的应用[J]．计算机仿真．2004，21(7)：125～128．
[9] 李静，陈兆乾等．多Agent Teamwork研究综述[J]．计算机研究与发展．2003，40(3)：422～429．
[10] 吴丽娟，翟玉人，徐心和．足球机器人系统中角色分配策略的设计[J]．基础自动化，2000，(01)：4～6．
[11] G. Liu and X. Chen, Multi-agent collaborative planning and its applications in RoboCup[R], Proc. of the 3rd world Congress on Intelligent Control and Automation, 2000, 18: 4～88.
[12] Peter Stone and Manuela Veloso. Task Decomposition, Dynamic Role Assignment, and Low-Bandwidth Communication for Real-Time Strategic Teamwork[J]. Artificial Intelligence, 1999, 110(2): 241～273.
[13] Kitano H., Kandiyohi. Y, Noda I. Asada M., Matsubara H. and Osawa E. RoboCup: A challenge problem for AI[J]. AI Magazine. 1997, 18(1): 73～85.
[14] Tan M. Multi-agent reinforcement learning: Independent vs. cooperative agents [R]. In Proceedings of the Tenth International Conference on Machine Learning, 1993, 2: 330～337.
[15] Itsuki Noda, Hitoshi Matsubara. Kazuo Hiraki, and Ian Frank. Soccer server: A tool for research on multi-agent systems [J]. Applied Artificial Intelligence, 1998, 12: 250～333.
[16] 李实，陈江，孙增圻．清华机器人足球队的结构设计与实现[J]．清华大学学报(自然科学版)．2001，41(7)：94～97．
[17] 阎宏．Java与模式．软件工程研究院[M]．电子工业出版社 2004．
[18] 邓静，马传松，李振坤．BP神经网络的C++实现及讨论[J]．微机发展，2003，13(7)：93～96．
[19] 吉孔诗，潘昊．基于神经网络的专家系统体系结构[J]．微机发展，2001，3(06)：11～13．
[20] 胡金滨，唐旭清．人工神经网络的BP算法及其应用[J]．信息技术，2004，28(4)：1～4．
[21] 张颖霞，杨宜民，陈波，岑汉彬．多智能体团队合作在机器人足球赛中的应用[J]．微机发展，2004，14(7)：112～114．
[22] 陈荣，徐用懋，兰鸿森．多层前向网络的研究——遗传BP算法和结构优化策略[J]．自动化学报，1997，23(1)：43～49．
[23] 夏卫峰，费敏锐．遗传算法及其在RoboCup中的应用[J]．系统仿真学报．2002，14(6)：707～709．
[24] Quinlan J R. Induction of decision trees [J]. Machine Learning, 1986, 1(1): 86～106.
[25] 秦文．分类技术中的决策树算法分析[J]．深圳信息职业技术学院学报，2004，8(1)：61～65．
[26] 肖勇，陈意云．用遗传算法构造决策树[J]．计算机研究与发展，1998，35(1)：50～53．
[27] 咸鹤群，孟庆春，殷波，张继军，李占宾．多Agent系统中潜在角色值研究[J]．哈尔滨工业大学学报，2003，35(9)：1089～1092．
[28] 祁正华，任勋益．基于MAS的智能决策支持系统研究[J]．微机发展，2004，14(9)：14～16．
[29] 陈进才．多Agent系统的形式化理论研究[D]．西安：西安交通大学博士论文，2000．
[30] Jelle R. Kok, Matthijs T. J. Spaan, Nikos Vlassis, Non-communicative multi-robot coordination in dynamic environments [J], Robotics and Autonomous Systems. 2005. 50: 99～114.
[31] Guestrin. C, Koller. D, Parr. R, Multi-agent planning with factored MDPs [R], in: Advances in Neural Information Processing Systems. vol. 14, MIT Press. 2002: 1523～1530.
[32] 李镇宇．多主体系统决策问题研究及在RoboCup中的应用[D]．合肥：中国科学技术大学硕士论文．2005．
[33] 孙鹏．动态环境下多机器人行为规划[D]．合肥：中国科学技术大学硕士论文，2005．
[34] Ball, D., G. Wyeth. and D. Cusack. Design of a Team of Soccer Playing Robots [R]. In Autonomous Minirobots in Research and Edutainment. 2003. Brisbane, Australia.
[35] D'Andrea, R., T. Kalmar-Nagy, and P. Ganguly. The Cornell RoboCup Team [R]. In RoboCup 2000 Competitions and Symposium. 2000.
[36] Bowling. M., et al. Plays as team plans for coordination and adaptation [R]. In Proceedings of seventh RoboCup International Symposium. 2003.
[2] 贺建立．多智能体系统的开发[D]．合肥：安徽大学硕士论文，2004．
[3] Hewitt, Carl. Protection and Synchronization in Actor Systems [J], IBM Technical Disclosure Bulletin, 1974-11-1.
[4] 余澄丹．RoboCup智能体的开发和应用[D]．合肥：安徽大学硕士论文，2005．
[5] Genesereth, M. and Steven P. Ketchpel. Software Agents [J]. Communications of the ACM, 1994, 37(7).
[6] 史忠植．智能主体及其应用[M]．北京：科学出版社，2001．
[7] 杨增光．智能Agent的研究与实践[D]．合肥：安徽大学硕士论文，2004．
[8] 杜陶钧，黄鸿．多智能主体协作规划理论及其在RoboCup中的应用[J]．计算机仿真．2004，21(7)：125～128．
[9] 李静，陈兆乾等．多Agent Teamwork研究综述[J]．计算机研究与发展．2003，40(3)：422～429．
[10] 吴丽娟，翟玉人，徐心和．足球机器人系统中角色分配策略的设计[J]．基础自动化，2000，(01)：4～6．
[11] G. Liu and X. Chen, Multi-agent collaborative planning and its applications in RoboCup[R], Proc. of the 3rd world Congress on Intelligent Control and Automation, 2000, 18: 4～88.
[12] Peter Stone and Manuela Veloso. Task Decomposition, Dynamic Role Assignment, and Low-Bandwidth Communication for Real-Time Strategic Teamwork[J]. Artificial Intelligence, 1999, 110(2): 241～273.
[13] Kitano H., Kandiyohi. Y, Noda I. Asada M., Matsubara H. and Osawa E. RoboCup: A challenge problem for AI[J]. AI Magazine. 1997, 18(1): 73～85.
[14] Tan M. Multi-agent reinforcement learning: Independent vs. cooperative agents [R]. In Proceedings of the Tenth International Conference on Machine Learning, 1993, 2: 330～337.
[15] Itsuki Noda, Hitoshi Matsubara. Kazuo Hiraki, and Ian Frank. Soccer server: A tool for research on multi-agent systems [J]. Applied Artificial Intelligence, 1998, 12: 250～333.
[16] 李实，陈江，孙增圻．清华机器人足球队的结构设计与实现[J]．清华大学学报(自然科学版)．2001，41(7)：94～97．
[17] 阎宏．Java与模式．软件工程研究院[M]．电子工业出版社 2004．
[18] 邓静，马传松，李振坤．BP神经网络的C++实现及讨论[J]．微机发展，2003，13(7)：93～96．
[19] 吉孔诗，潘昊．基于神经网络的专家系统体系结构[J]．微机发展，2001，3(06)：11～13．
[20] 胡金滨，唐旭清．人工神经网络的BP算法及其应用[J]．信息技术，2004，28(4)：1～4．
[21] 张颖霞，杨宜民，陈波，岑汉彬．多智能体团队合作在机器人足球赛中的应用[J]．微机发展，2004，14(7)：112～114．
[22] 陈荣，徐用懋，兰鸿森．多层前向网络的研究——遗传BP算法和结构优化策略[J]．自动化学报，1997，23(1)：43～49．
[23] 夏卫峰，费敏锐．遗传算法及其在RoboCup中的应用[J]．系统仿真学报．2002，14(6)：707～709．
[24] Quinlan J R. Induction of decision trees [J]. Machine Learning, 1986, 1(1): 86～106.
[25] 秦文．分类技术中的决策树算法分析[J]．深圳信息职业技术学院学报，2004，8(1)：61～65．
[26] 肖勇，陈意云．用遗传算法构造决策树[J]．计算机研究与发展，1998，35(1)：50～53．
[27] 咸鹤群，孟庆春，殷波，张继军，李占宾．多Agent系统中潜在角色值研究[J]．哈尔滨工业大学学报，2003，35(9)：1089～1092．
[28] 祁正华，任勋益．基于MAS的智能决策支持系统研究[J]．微机发展，2004，14(9)：14～16．
[29] 陈进才．多Agent系统的形式化理论研究[D]．西安：西安交通大学博士论文，2000．
[30] Jelle R. Kok, Matthijs T. J. Spaan, Nikos Vlassis, Non-communicative multi-robot coordination in dynamic environments [J], Robotics and Autonomous Systems. 2005. 50: 99～114.
[31] Guestrin. C, Koller. D, Parr. R, Multi-agent planning with factored MDPs [R], in: Advances in Neural Information Processing Systems. vol. 14, MIT Press. 2002: 1523～1530.
[32] 李镇宇．多主体系统决策问题研究及在RoboCup中的应用[D]．合肥：中国科学技术大学硕士论文．2005．
[33] 孙鹏．动态环境下多机器人行为规划[D]．合肥：中国科学技术大学硕士论文，2005．
[34] Ball, D., G. Wyeth. and D. Cusack. Design of a Team of Soccer Playing Robots [R]. In Autonomous Minirobots in Research and Edutainment. 2003. Brisbane, Australia.
[35] D'Andrea, R., T. Kalmar-Nagy, and P. Ganguly. The Cornell RoboCup Team [R]. In RoboCup 2000 Competitions and Symposium. 2000.
[36] Bowling. M., et al. Plays as team plans for coordination and adaptation [R]. In Proceedings of seventh RoboCup International Symposium. 2003.