Multi-Agent协作模型及其在RoboCup中的应用
|
摘要
机器人足球世界杯以多智能体系统和分布式人工智能为主要研究背景。其主要目的是通过提供一个标准的比赛平台，促进机器人学和人工智能的研究与发展。为了能让一个机器人球队真正能够进行足球比赛，必须集成各种各样的技术，包括自治智能体的设计准则、多智能体合作、策略获取、实时推理、机器人学以及传感器信息融合等。
本论文以仿真机器人足球比赛中的多个智能体为研究对象，对多智能体系统中的多个智能体之间的协作问题进行了分析和研究。
在智能体的体系结构方面，为了使智能体既具有反应性又具有慎思性，本文采用基于行为的双层动态智能体结构：第一层为基本行为层，这层的目的是提高智能体的反应性：第二层为高级行为层，这层的目的是提高智能体的智能性。连接基本行为层和高级行为层的桥梁是自信度。
在智能体的决策算法方面，本文提出了一种新颖的基于行为的多智能体决策算法来提高智能体的灵敏性和智能性，该算法分为个体决策和团队决策，个体决策是让智能体完成比较简单的任务，满足智能体对实时性的要求：团队决策则可用来完成比较复杂的任务。
在多智能体协作模型方面，为了让多个智能体能够协同工作来完成复杂的任务，本文提出多智能体层次协作模型，它包括全局层、局部层和个体层。全局层管理场上的所有队员，并根据对手建模和场上状态来选择合适的静态阵形和动态阵形，提高了智能体的可适应性；局部层包含3-5个智能体，根据阵形本文将一队智能体分为进攻、防守和中间等三个局部层，降低了智能体之间协作的难度：个体层管理智能体的行为，这些行为包括清理球、射门、拦截、传球、盘带、到定点、盯人、面向球等。
基于本文思想构建的中南大学云麓队在2002年中国机器人比赛仿真组中获得第三名，真实比赛的结果验证了以上研究的有效性。
Being the main research background of Multi-Agent Systems and Distributed Artificial Intelligence, Robot Soccer World Cup(RoboCup) supplies a standard tournament bed in order to foster the research and development of Robotics and Artificial Intelligence. To make a robot team play effectively, various technologies including design principles of autonomous agents, multi-agent coordination, strategy acquisition, real-time reasoning, robotics, and sensor-fusion must be incorporated.
Using the multiple agents in RoboCup as research target, this dissertation analyzes the coordination among multiple agents in Multi-Agent Systems.
As far as the architecture of the agent is concerned, this dissertation introduces behavior-based dual dynamic agent architecture in order to make the agents have both reactivity and deliberation. The first layer is elementary behavior layer whose purpose is to enhance the reactivity of the agents; the second is high-level behavior one with the purpose to improve the deliberation of the agents. And the joint between the two layers is confidence value.
As far as the decision algorithm is concerned, this dissertation puts forward a novel behavior-based decision algorithm to make the agent act promptly and intelligently. This algorithm can be divided into individual decision and team decision. The former can make the agents achieve the relatively easy tasks and the latter accomplishes the complicated tasks.
And the third point is about the coordination model. The multi-agent layered coordination model brought up in this dissertation promotes the collaborative agents to accomplish complex tasks. This model includes global layer, local layer and individual layer. The global layer supervises all the players in the field and decides the static formation or dynamic formation according to the modeling of the opponent and the present condition, this strategy improves the adaptability of the agents. Local layer includes three to five agents. According to formation, this dissertation separates a robot team into offense unit, defense unit and neutral one, in order to decrease the difficulty of coordination among agents. And individual layer supervises actions of agents, Such as clearing, shooting, intercepting, passing, dribbling, locating and facing ball, etc.
The CSU_Yunlu team, using these strategies of the dissertation, won the 3rd Robocup2002 (simulation league) Chinese Championships. Actual results validate the above researches in the simulated robotic soccer domain.
本论文以仿真机器人足球比赛中的多个智能体为研究对象，对多智能体系统中的多个智能体之间的协作问题进行了分析和研究。
在智能体的体系结构方面，为了使智能体既具有反应性又具有慎思性，本文采用基于行为的双层动态智能体结构：第一层为基本行为层，这层的目的是提高智能体的反应性：第二层为高级行为层，这层的目的是提高智能体的智能性。连接基本行为层和高级行为层的桥梁是自信度。
在智能体的决策算法方面，本文提出了一种新颖的基于行为的多智能体决策算法来提高智能体的灵敏性和智能性，该算法分为个体决策和团队决策，个体决策是让智能体完成比较简单的任务，满足智能体对实时性的要求：团队决策则可用来完成比较复杂的任务。
在多智能体协作模型方面，为了让多个智能体能够协同工作来完成复杂的任务，本文提出多智能体层次协作模型，它包括全局层、局部层和个体层。全局层管理场上的所有队员，并根据对手建模和场上状态来选择合适的静态阵形和动态阵形，提高了智能体的可适应性；局部层包含3-5个智能体，根据阵形本文将一队智能体分为进攻、防守和中间等三个局部层，降低了智能体之间协作的难度：个体层管理智能体的行为，这些行为包括清理球、射门、拦截、传球、盘带、到定点、盯人、面向球等。
基于本文思想构建的中南大学云麓队在2002年中国机器人比赛仿真组中获得第三名，真实比赛的结果验证了以上研究的有效性。
Being the main research background of Multi-Agent Systems and Distributed Artificial Intelligence, Robot Soccer World Cup(RoboCup) supplies a standard tournament bed in order to foster the research and development of Robotics and Artificial Intelligence. To make a robot team play effectively, various technologies including design principles of autonomous agents, multi-agent coordination, strategy acquisition, real-time reasoning, robotics, and sensor-fusion must be incorporated.
Using the multiple agents in RoboCup as research target, this dissertation analyzes the coordination among multiple agents in Multi-Agent Systems.
As far as the architecture of the agent is concerned, this dissertation introduces behavior-based dual dynamic agent architecture in order to make the agents have both reactivity and deliberation. The first layer is elementary behavior layer whose purpose is to enhance the reactivity of the agents; the second is high-level behavior one with the purpose to improve the deliberation of the agents. And the joint between the two layers is confidence value.
As far as the decision algorithm is concerned, this dissertation puts forward a novel behavior-based decision algorithm to make the agent act promptly and intelligently. This algorithm can be divided into individual decision and team decision. The former can make the agents achieve the relatively easy tasks and the latter accomplishes the complicated tasks.
And the third point is about the coordination model. The multi-agent layered coordination model brought up in this dissertation promotes the collaborative agents to accomplish complex tasks. This model includes global layer, local layer and individual layer. The global layer supervises all the players in the field and decides the static formation or dynamic formation according to the modeling of the opponent and the present condition, this strategy improves the adaptability of the agents. Local layer includes three to five agents. According to formation, this dissertation separates a robot team into offense unit, defense unit and neutral one, in order to decrease the difficulty of coordination among agents. And individual layer supervises actions of agents, Such as clearing, shooting, intercepting, passing, dribbling, locating and facing ball, etc.
The CSU_Yunlu team, using these strategies of the dissertation, won the 3rd Robocup2002 (simulation league) Chinese Championships. Actual results validate the above researches in the simulated robotic soccer domain.
引文
[1] http://robocup.ai.ustc.edu.cn/resource/Simulation/Documents, RoboCupOV2.zip, May, 2002
[2] RoboCup: The World Cup Robot Soccer. http://robocup.ai.ustc.edu.cn/simulation/, Sep,2001
[3] Peter Stone and Manuela Veloso. Communication in domains with unreliable single channels low bandwidth communication. In Alexis Drogoul, Milind Tambe, and Toshio Fukuda editors, Collective Robotics, pp.85-97, Springer Verlag, Berlin, July, 1998
[4] Milind Tambe. Towards Flexible Teamwork. Journal of Artificial Intelligence Research, 1997, 7(1):83-124
[5] M.Tambe, et al. ISIS: Using an Explicit Model of Teamwork in RoboCup'97. In Proceedings of IJCAI-97
[6] M.Tambe, G.Kaminka, I.Muslea, S.Marsella, and T.Raines. Two fielded team and two experts: A RoboCup challenge response from the trenchs. In Proceedings of the 16th International Jiont Conference on Artificial Intelligence, Aug,1999
[7] Geoff Nitscke. Cooperating Air Traffic Control Agents. Applied Artificial Intelligence, pp.209-235, 2001
[8] N. Jennings. Controlling cooperative problem solving in industrial multi-agent systems using joint intentions. Artificial Intelligence, 75, 1995
[9] Yao Jinyi, Chen Jiang, Cai Yunpeng, and Li Shi. Architecture of TsinghuAeolus. http:/www.lits.tsinghua.edu.cn/robocup/robo CHI/software/software doc.html, May, 2002
[10] Luís Paulo Reis, Nuno Lau and Eugénio Costa Oliveira. Situation Based Strategic Positioning for Coordinating a Team of Homogeneous Agents. http://www.ieeta.pt/robocup/archive.htm, May, 2002
[11] 张波，蔡庆生，陈小平等．基于智能团队的RoboCup仿真球队．Proceeding of the 3rd World Congress on Intelligebt Control and Automation, Jun 28-July 2,2000, Hefei, P.R.China.
[12] 仵博，吴敏，曹卫华．一种基于行为的Multi-Agent决策算法及其在RoboCup中的应用．机器人技术与应用，2002，2(1)：36-39
[13] 刘金琨，王树青．多智能体系统联合行动的形式化研究及其应用．控制与决策，2000，15(1)：6-10
[14] 康小强，石纯一．基于BDI的多Agent交互．计算机学报，1999，22(11)：1166-1171
[15] 李毅，罗翊，石纯一．多agent系统的一种交互策略模型．软件学报，1999，10(7)：702-708
[16] Stacy Marsella,Jafar Adibi,Yease Al-Onaizan. On being a teammate: Experiences acquired in the design of RoboCup teames. Information Sciences Institute and Computer Science Department, University of Southern California, USA. 2000
[17] 马光伟，徐晋晖，石纯一．Agent思维状态模型．软件学报，1999，10(4)：342-348
[18] P.Stone, P.Riley, M.Veloso. The CMUnited-99 Champion Simulator Team. In Manula Veloso, Enrico Pagello, and Hiroaki Kitano, editors, RoboCup-99: Robot Soccer World Cup Ⅲ.Springer, Berlin,2000
[19] F.Girault,S.Stinckwich. Footux Team Description: A Hybrid recursive based agent architechure. Robocup-99 Team Description: Simulation League. 1999. http://www.ep.liu.se/ea/cis/1999/007,Sep, 2001
[20] Frieder Stolzenburg,Oliver Obst,Jan Murray, Bjrn Bremer. RoboLog Koblenz: Spatial Agents Implemented in a Logical Expressible Language. Robocup-99 Team Description: Simulation League, 1999. http://www.ep.liu.se/ea/cis/1999/007, Sep, 2001
[21] A.S.Rao,M.P.Georgeff. Modeling rational agents within a BDI-architecture. In Proceeding of Knowledge Represenation and reasoning(KR&R-91),pp.473-484,1991
[22] R.Brooks. A robust layered control system for a mobile robot. IEEE J. Robotics and Automation 2,1986
[23] T. Balch, R.Arkin, Behavior-based formation control for multi-agent robot teams. Proc. 1995 International Conference on Multiagent System,1995
[24] Barry Brian Werger. Cooperation without deliberation: a minimal behavior-based approach to multi-robot teams. Artificial Intelligence, 1999, 12(110):293-320
[25] 陈宗海，詹昌辉．基于“感知-行为”的职能模拟技术的现状及展望．机器人，2001，23(3)：187-192
[26] Wu Bo(仵博)，Wu Min(吴敏)，Cao Weihua(曹卫华)．Behavior-based Dual Dynamic Agent Architecture. 《Journal of Central South University of Technology》(已录用待发表)
[27] Mihal Badjonski, Kay Schr□oter, Jan Wendler, Hans-Dieter Burkhard. Learning of Kick in Artificial Soccer, http://robocup.ai.ustc.edu.cn/. May,2001
[28] Peter Stone and Manuela Veloso. The CMUnited-98 Champion Simulator Team. In "RoboCup-98: Robot Soccer World Cup Ⅱ", M. Asada and H. Kitano (eds.),Springer Verlag, Berlin, 1999
[29] Peter Stone, Patrick Riley and Manuela Veloso. Defining and Using Ideal Teammate and Opponent Agent Models, AT&T Labs.http://www.research.att.com/~pstone. May,2001
[30] 郭戈，柴天佑．基于需求的多机器人决策算法，机器人，2001，6(1)：23-27
[31] P.Stone. Layered Learning in Multi-agent Systems. Ph.D. Thesis. Carnegie Mellon university, CMU-CS-98-187 (1998)
[32] Itsuki Noda, Hitoshi Matsubara, Kazuo Hiraki, and Ian Frank. Soccer server: A Tool for Research on Multiagent Systems. Applied Artificial Intelligence, 1998,12(2):233-250
[33] 李实，徐旭明，叶榛，孙增圻．综述：国际机器人足球比赛及其相关技术，机器人ROBOT，2000，9(22)：420-426
[34] Shuhei Kinoshita, Yoshikazu Yamamoto. Team 11monkeys Description, RoboCup-99Team Descriptions, Simulation League, Team 11monkeys, pp. 154-156
[35] Song Zhiwei,Zhang Bo, Chen Xiaoping,Wang Xufa. Layered Decision-making and Planning in ShaoLing Team, Proceedings of the 3rd World Congress on Intelligent Control and Automation, Jun28-July2,2000, Hefei,P.R.China
[36] Peter Stone and Manuela Veloso. Task Decomposition and Dynamic Role Assignment for Real-Time Strategic Teamwork, Computer Science Department, Carnegie Mellon University Pittsburgh, PA 15213, USA. http://www.research.att.com/~pstone. May,2001
[37] 王敏启，周明天，姚绍文．动态网络环境下的多AGENT移动合作系统．计算机研究与发展，2001，38(12)：1454-1459
[38] Cohen P R, Lecesque H J, Intention is choice with commitment. Artificial Intellegence. 1990,42(3):213-261
[39] Bo Zhang,Xiaoping Chen,Guiquan Liu,Qingsheng Cai. Agent Architecture:A Survey onRoboCup-99 Simulator Teams.Proceeding of the 3rd World Congress on Intelligebt Control and Automation, Jun 28-July 2,2000, Hefei, P.R.China
[40] Andrea Omicini and George A.Papadopoulos. Editorial: why coordination models and langua ge in AI. applied artifical intelligence,2001,15(1): 1-11
[41] Jose M.Vidal, PaulA.Buhler,Michael N.Huhns. Inside an agent, internet computering,IEEE. NO. 1, February,2001.pp.82-86
[42] Cai yunpeng, Chen Jiang, Yao Jinyi, and Li Shi. Global Planning from Local Eyeshot: An Implementation of Observation-based Plan Coordination in RoboCup Simulation Games. http://www.lits.tsinghua.edu.cn/robocup/robo CHI/software/software doc.html,May,2001
[43] Jan Pfeifer, Jacques Wainer. Multi-Agent Plan: Analysis and Implementation. http://www.lti.pcs.usp.br/mappel/meeting/mappel-jan.ps.gz, May,2002
[44] 汤哲，孙增圻．机器人足球中的协作．第四届全球智能与自动化大会论文集，2002(6)：(469-473)，中国上海
[45] 蓝鹰队开发成员．球场调试工具SoccerDoctor. http://www.wrighteagle.org/,May,2002
[2] RoboCup: The World Cup Robot Soccer. http://robocup.ai.ustc.edu.cn/simulation/, Sep,2001
[3] Peter Stone and Manuela Veloso. Communication in domains with unreliable single channels low bandwidth communication. In Alexis Drogoul, Milind Tambe, and Toshio Fukuda editors, Collective Robotics, pp.85-97, Springer Verlag, Berlin, July, 1998
[4] Milind Tambe. Towards Flexible Teamwork. Journal of Artificial Intelligence Research, 1997, 7(1):83-124
[5] M.Tambe, et al. ISIS: Using an Explicit Model of Teamwork in RoboCup'97. In Proceedings of IJCAI-97
[6] M.Tambe, G.Kaminka, I.Muslea, S.Marsella, and T.Raines. Two fielded team and two experts: A RoboCup challenge response from the trenchs. In Proceedings of the 16th International Jiont Conference on Artificial Intelligence, Aug,1999
[7] Geoff Nitscke. Cooperating Air Traffic Control Agents. Applied Artificial Intelligence, pp.209-235, 2001
[8] N. Jennings. Controlling cooperative problem solving in industrial multi-agent systems using joint intentions. Artificial Intelligence, 75, 1995
[9] Yao Jinyi, Chen Jiang, Cai Yunpeng, and Li Shi. Architecture of TsinghuAeolus. http:/www.lits.tsinghua.edu.cn/robocup/robo CHI/software/software doc.html, May, 2002
[10] Luís Paulo Reis, Nuno Lau and Eugénio Costa Oliveira. Situation Based Strategic Positioning for Coordinating a Team of Homogeneous Agents. http://www.ieeta.pt/robocup/archive.htm, May, 2002
[11] 张波，蔡庆生，陈小平等．基于智能团队的RoboCup仿真球队．Proceeding of the 3rd World Congress on Intelligebt Control and Automation, Jun 28-July 2,2000, Hefei, P.R.China.
[12] 仵博，吴敏，曹卫华．一种基于行为的Multi-Agent决策算法及其在RoboCup中的应用．机器人技术与应用，2002，2(1)：36-39
[13] 刘金琨，王树青．多智能体系统联合行动的形式化研究及其应用．控制与决策，2000，15(1)：6-10
[14] 康小强，石纯一．基于BDI的多Agent交互．计算机学报，1999，22(11)：1166-1171
[15] 李毅，罗翊，石纯一．多agent系统的一种交互策略模型．软件学报，1999，10(7)：702-708
[16] Stacy Marsella,Jafar Adibi,Yease Al-Onaizan. On being a teammate: Experiences acquired in the design of RoboCup teames. Information Sciences Institute and Computer Science Department, University of Southern California, USA. 2000
[17] 马光伟，徐晋晖，石纯一．Agent思维状态模型．软件学报，1999，10(4)：342-348
[18] P.Stone, P.Riley, M.Veloso. The CMUnited-99 Champion Simulator Team. In Manula Veloso, Enrico Pagello, and Hiroaki Kitano, editors, RoboCup-99: Robot Soccer World Cup Ⅲ.Springer, Berlin,2000
[19] F.Girault,S.Stinckwich. Footux Team Description: A Hybrid recursive based agent architechure. Robocup-99 Team Description: Simulation League. 1999. http://www.ep.liu.se/ea/cis/1999/007,Sep, 2001
[20] Frieder Stolzenburg,Oliver Obst,Jan Murray, Bjrn Bremer. RoboLog Koblenz: Spatial Agents Implemented in a Logical Expressible Language. Robocup-99 Team Description: Simulation League, 1999. http://www.ep.liu.se/ea/cis/1999/007, Sep, 2001
[21] A.S.Rao,M.P.Georgeff. Modeling rational agents within a BDI-architecture. In Proceeding of Knowledge Represenation and reasoning(KR&R-91),pp.473-484,1991
[22] R.Brooks. A robust layered control system for a mobile robot. IEEE J. Robotics and Automation 2,1986
[23] T. Balch, R.Arkin, Behavior-based formation control for multi-agent robot teams. Proc. 1995 International Conference on Multiagent System,1995
[24] Barry Brian Werger. Cooperation without deliberation: a minimal behavior-based approach to multi-robot teams. Artificial Intelligence, 1999, 12(110):293-320
[25] 陈宗海，詹昌辉．基于“感知-行为”的职能模拟技术的现状及展望．机器人，2001，23(3)：187-192
[26] Wu Bo(仵博)，Wu Min(吴敏)，Cao Weihua(曹卫华)．Behavior-based Dual Dynamic Agent Architecture. 《Journal of Central South University of Technology》(已录用待发表)
[27] Mihal Badjonski, Kay Schr□oter, Jan Wendler, Hans-Dieter Burkhard. Learning of Kick in Artificial Soccer, http://robocup.ai.ustc.edu.cn/. May,2001
[28] Peter Stone and Manuela Veloso. The CMUnited-98 Champion Simulator Team. In "RoboCup-98: Robot Soccer World Cup Ⅱ", M. Asada and H. Kitano (eds.),Springer Verlag, Berlin, 1999
[29] Peter Stone, Patrick Riley and Manuela Veloso. Defining and Using Ideal Teammate and Opponent Agent Models, AT&T Labs.http://www.research.att.com/~pstone. May,2001
[30] 郭戈，柴天佑．基于需求的多机器人决策算法，机器人，2001，6(1)：23-27
[31] P.Stone. Layered Learning in Multi-agent Systems. Ph.D. Thesis. Carnegie Mellon university, CMU-CS-98-187 (1998)
[32] Itsuki Noda, Hitoshi Matsubara, Kazuo Hiraki, and Ian Frank. Soccer server: A Tool for Research on Multiagent Systems. Applied Artificial Intelligence, 1998,12(2):233-250
[33] 李实，徐旭明，叶榛，孙增圻．综述：国际机器人足球比赛及其相关技术，机器人ROBOT，2000，9(22)：420-426
[34] Shuhei Kinoshita, Yoshikazu Yamamoto. Team 11monkeys Description, RoboCup-99Team Descriptions, Simulation League, Team 11monkeys, pp. 154-156
[35] Song Zhiwei,Zhang Bo, Chen Xiaoping,Wang Xufa. Layered Decision-making and Planning in ShaoLing Team, Proceedings of the 3rd World Congress on Intelligent Control and Automation, Jun28-July2,2000, Hefei,P.R.China
[36] Peter Stone and Manuela Veloso. Task Decomposition and Dynamic Role Assignment for Real-Time Strategic Teamwork, Computer Science Department, Carnegie Mellon University Pittsburgh, PA 15213, USA. http://www.research.att.com/~pstone. May,2001
[37] 王敏启，周明天，姚绍文．动态网络环境下的多AGENT移动合作系统．计算机研究与发展，2001，38(12)：1454-1459
[38] Cohen P R, Lecesque H J, Intention is choice with commitment. Artificial Intellegence. 1990,42(3):213-261
[39] Bo Zhang,Xiaoping Chen,Guiquan Liu,Qingsheng Cai. Agent Architecture:A Survey onRoboCup-99 Simulator Teams.Proceeding of the 3rd World Congress on Intelligebt Control and Automation, Jun 28-July 2,2000, Hefei, P.R.China
[40] Andrea Omicini and George A.Papadopoulos. Editorial: why coordination models and langua ge in AI. applied artifical intelligence,2001,15(1): 1-11
[41] Jose M.Vidal, PaulA.Buhler,Michael N.Huhns. Inside an agent, internet computering,IEEE. NO. 1, February,2001.pp.82-86
[42] Cai yunpeng, Chen Jiang, Yao Jinyi, and Li Shi. Global Planning from Local Eyeshot: An Implementation of Observation-based Plan Coordination in RoboCup Simulation Games. http://www.lits.tsinghua.edu.cn/robocup/robo CHI/software/software doc.html,May,2001
[43] Jan Pfeifer, Jacques Wainer. Multi-Agent Plan: Analysis and Implementation. http://www.lti.pcs.usp.br/mappel/meeting/mappel-jan.ps.gz, May,2002
[44] 汤哲，孙增圻．机器人足球中的协作．第四届全球智能与自动化大会论文集，2002(6)：(469-473)，中国上海
[45] 蓝鹰队开发成员．球场调试工具SoccerDoctor. http://www.wrighteagle.org/,May,2002