一种新的RoboCup阵型分析方法

程泽凯，凌兆龙，秦 锋

（安徽工业大学 计算机科学与技术学院，安徽 马鞍山243002）

一种新的RoboCup阵型分析方法

程泽凯，凌兆龙，秦 锋

（安徽工业大学 计算机科学与技术学院，安徽 马鞍山243002）

在RoboCup仿真2D中，目前的阵型编辑工具fedit2无法从全局和对比的角度去分析球员在整个球场不同区域的位置排列。对此，提出了一种新型阵型分析方法。该方法使用数据挖掘的思想从RoboCup阵型文件中分别提取出球和每个球员的位置数据，结合Delaunay三角网络理论进行建模，通过分析对比得出阵型背后的信息。分析结论应用在球队阵型设计和决策中，并在RoboCup世界杯及中国公开赛上证明了其有效性。

RoboCup；阵型；fedit2；数据挖掘；Delaunay三角网络

RoboCup（Robot World Cup），即机器人世界杯足球锦标赛，它涉及到人工智能、智能控制、机器人学、通讯传感、视觉技术以及制造材料技术等多领域的前沿研究和技术融合。仿真2D作为RoboCup的传统项目之一，比赛过程需要球队间整体高效的合作及多个智体之间的默契配合，由于球队以阵型为基础进行架构，且每个球员智能体以阵型点为基础进行决策，因此，阵型是球队建设中至关重要的因素之一。

国内外先后有多位学者对阵型进行研究，CMUnited［1-2］提出了关门协议（Locker-Room Agreement），根据比赛结果和剩余时间动态改变阵型，并通过基于吸引子和排斥子的策略跑位（strategic position by attraction and repulsion，SPAR）。FCPotugal［3］在CMUnited的基础上提出SBSP［4］阵型策略，球员根据球场上的形势以及球员自身的策略特性来修正基本位置，得到球员的策略站位点，并且球员可以动态转换角色。UVA_Trilearn［5］在前人工作的基础上引入球对球员的吸引因子，通过球对不同角色的吸引因子设计阵型点，并依据球的位置和球的被控制情况进行阵型维护。TinghuAeolus［6-7］在原有智能体跑位分配的基础上，吸收了FC Portugal阵型中角色的概念，提出了基于角色分配阵型的阵型方案，并通过引力模型对其进行在线调整。Hidehisa Akiyama［8］等提出使用Delaunay Triangulation几何计算方法设计阵型，是对SBSP方法的改进和扩充，即把原来球的位置到球员位置映射的线性函数变为非线性函数，使球员在整个球场的可移动区域划分的更小更多。此外，还有从神经网络［9］等角度对阵型进行研究，阵型设计方法已经比较成熟，而阵型分析方法还有待改进。

随着RoboCup技术的发展，阵型的合理性对于高层决策的影响越来越重要，甚至决定着比赛的胜负。目前的阵型编辑工具fedit2提供了一个非常方便设计，调整以及查看阵型的平台。在使用fedit2去查看阵型时，对于阵型中的11名球员位置只有通过滑动球的位置用经验去判断球员的位置是否合理，无法从全局和对比的角度去分析，fedit2的缺陷正在于此，有时甚至需要通过许多场比赛来测试阵型的合理性，同时，在调整或者设计阵型点时，11名球员的排列组合又是一个NP-Hard问题，因此，如何找到一种快捷有效的分析方法是文中的研究目的。文中使用数据挖掘的思想对阵型文件中球和球员的位置数据进行提取，结合Delaunay三角网络理论，使用Matlab工具进行画图，将球和球员的所有位置直接反映到图中，通过分析对比得出阵型背后的信息。分析结论应用在球队阵型设计和决策中，并在RoboCup世界杯及中国公开赛上证明其有效性。

1 阵型编辑工具fedit2及其不足

1.1 RoboCup阵型文件

现如今参加RoboCup仿真2D比赛的大部分球队以Agent2D_Base为基础进行研发，对阵型进行了或多或少的调整。Agent2D_Base中将球和球员位置数据以坐标的形式单独存放在conf格式的文件中，每一个坐标点即为一个Delaunay三角网络的顶点。阵型文件包括defense-formation.conf，normal-formation.conf，offensive-formation.conf等多种阵型文件，比赛时球员根据场上不同形势读取对应的阵型文件，通过球的位置获取对应的球员自身的位置，即本位点，再根据场上形势对自身的本位点进行调整。

1.2 fedit2查看阵型文件

阵型编辑工具fedit2可以通过读取阵型文件来查看阵型的合理性，并对于不合理的地方进行调整，同时也可以完全重新设计阵型。不同球队的阵型点个数不同，但都以覆盖整个球场为最终目的。图1是阵型编辑工具fedit2对Agent2D_Base中阵型文件defense-formation.conf的查看，从图中可以看出，共有115个球位置的样本点覆盖了整个球场，每一个三角形即为一个球位置的Delaunay三角网络。而球员本位点的Delaunay三角网络在fedit2中是看不到的。

图1 fedit2查看阵型文件

图2 插值算法

1.3 fedit2中对于球员本位点的定位

从fedit2中可以看出，球员的本位点是根据球的位置来确定的，但是阵型文件中只有115个点，似乎不能完全涉及整个球场上的点。这里，Agent2D_Base中将球员的本位点定位分为2种情形来考虑场上对应的所有位置坐标：

（1）球的坐标为Delaunay三角网络的顶点。对于每一个顶点来说，当三角形的顶点恰好为球的坐标点时，则输出球员对应点位在阵型文件中的坐标，此点即为球员的本位点。

显然，若是能够将球员本位点的Delaunay三角网络在图中进行显示，通过分析对比定能得出阵型背后的大量信息。

2 结合Dalaunay网络理论进行阵型分析

2.1 使用Matlab工具进行数据建模

以Agent2D_Base，Gliders2014，Helios2014，Marlik2012为例，使用C++对各队defense-formation.conf中球和每个球员的Delaunay三角网络相关数据进行提取，再使用Matlab工具对数据进行建模。如图3-图11 的Delaunay三角网络图所示，其余的normal-formation.conf，offensive-formation.conf等限于篇幅在此略去。其中4号角色是边后卫，7号角色是进攻中锋，9号角色是边前锋，2号角色和3号角色是中后卫，6号角色是防守中锋，11号角色是中前锋，4号、7号、9号分别与5号，8号，10号对称。

（1）Agent2D_Base的4号、7号、9号如图3所示，2号、3号、6号、11号如图4所示。

图3 Agent2D_Base的4、7、9号阵型图

图4 Agent2D_Base的2、3、6、11号阵型图

（2）Gliders2014的4号、7号、9号如图5所示，2号、3号、6号、11号如图6所示。

图5 Gliders2014的4、7、9号阵型图

图6 Gliders2014的2、3、6、11号阵型图

（3）Helios2014的4号、7号、9号如图7所示，2号、3号、6号、11号如图8所示。

图7 Helios2014的4、7、9号阵型图

图8 Helios2014的2、3、6、11号阵型图

（4）Marlik2012的4号、7号、9号如图9所示，2号、3号、6号、11号如图10所示。

图9 Marlik2012的4、7、9号阵型图

图10 Marlik2012的2、3、6、11号阵型图

（5）Marlik2012的2号如图11所示。

2.2 结合Delaunay三角网络理论进行分析

图11 Marlik2012的2号阵型图

（1）从图3、图5、图7、图9分析出Marlik2012的阵型相对于其他球队，Marlik2012的7号在球场上的覆盖范围明显更大，即防守范围更广。

（2）从图3、图5、图7、图9分析出Marlik2012的4、7、9号在边路的x<-50区域防守点要相对密集一些。而这也是Marlik2012防守强大的原因之一。

（3）从图3、图5、图7、图9分析出在边路的y<-20区域，Helios2014，Gliders2014，Marlik2012这些球队均有较好的区域防守，特别如图7的标注①所示，而底层则在此区域出现大面积的防守空缺。

（4）从图4、图6、图8、图10分析出Helios2014，Gliders2014，Marlik2012均在Agent2D_Base基础上调整了阵型点，其中Gliders2014有四道防线，分别在area1（x∈（-3.0，+3.0），y∈（-20.0，+20）），area2（x∈（-17，-14），y∈（-13，+13）），area3（x∈（-27，-23），y∈（-8，+8）），area4（x∈（-36，-33），y∈（-10，+10））。Helios2014也有四道防线，分别在area1（x∈（+16，+19），y∈（-10，+10）），area2（x∈（0，+5），y∈（-10，+10）），area3（x∈（-8，-4），y∈（-8，+8）），area4（x∈（-17，-14），y∈（-12，+12））。Marlik2012存在三道防线，分别在area1（x∈（0，+3），y∈（-17，+17）），area2（x∈（-23，-20），y∈（-14，+14）），area3（x∈（-38-34），y∈（-20，+20））（图中均用加粗线条标出）。以上球队均在上述区域重点设防。而Agent2D_Base的防守点则比较均匀，没有相对明显的防守线。

（5）图11为单个球员与球的Delaunay三角网络图，从图11中，分析出Marlik2012的2号球员的单个Delaunay三角网络应该和与之相对应的球的Delaunay三角网络是相似的（图中用填充三角网络标示）。

2.3 结论

（1）一个好的阵型首先Delaunay三角网络的面积分布比较均匀，这样球员不会因为Delaunay三角网络过大而无法跑到本位点；（2）在球场的边路上，要有阵型点的涉及，因为底层的薄弱点之一就是会被对手带球下底传中后射门；（3）应该在自己半场上设有几道防线，可以大大削弱对手的穿越传球等相关进攻；（4）球员的单个Delaunay三角网络应该和与之相对应的球的Delaunay三角网络尽量相似，这样才能更加有利于去封堵对方的进攻。

同时，结合RoboCup2014巴西世界杯中Gliders2014与Helios2014的log比赛录像。Gliders2014进的Helios2014两球都是球员带球下底从边路传中后打进的，笔者再结合Helios2014的4号Delaunay三角网络截图，可以明显的发现Helios2014的4号在边路在x=-50之后存在防守空隙，而且Helios2014的4号在这附近的Delaunay三角网络区域明显过大（如图8中的标注②所示），最终导致Helios2014在此区域的防守薄弱。而Helios2014的穿越传球非常凶悍，众所周知，在面对Gliders2014时，由于Gliders2014存在上述的四道防线，从而导致穿越传球无法突破Gliders2014的防守。

3 结语

文中创新使用数据挖掘的思想，结合Delaunay三角网络理论提出新型阵型分析方法，重点在研究Agent2D_Base，Gliders2014，Helios2014，Marlik2012的阵型基础上，发现其内在规律，从而制定出一套适合球队策略的阵型并运用在YuShan球队的开发中，同时在实际比赛中证明了方法的有效性，球队获得了RoboCup2013世界杯季军、RoboCup2014世界杯第六名并蝉联了RoboCup2013和RoboCup2014中国公开赛两届亚军。

从目前RoboCup仿真2D的发展趋势来看，各个强队对于阵型的研究日趋加强，并且都在该领域中作出了尝试。在YuShan的下一步开发中，主要研究解决的问题是如何加强智能体的在线分析对手阵型功能，使其能对对手的阵型策略作出对自己的整体策略进行在线调整。

［1］STONE P.Layered Learning in multi-agent systems［D］.Pittsburgh：Carnegie Mellon University，1998.

［2］STONE P，VELOSO M.Task decomposition，dynamic role assignment，and low-bandwidth communication for real-time strategic teamwork［J］.Artificail Intelligence，1999，110（2）：241-273.

［3］REIS L P，LAU N.FC Portugal Team Description［C］//STONE P，BALCH T，KAETZSCHMAR G.RoboCup 2000：Robot Soccer World Cup IV.In Melbourne，Austrilia.Berlin：Springer Verlag，2001：29-41.

［4］REIS L P，LAU N，OLIVEIRA E C.Situation based strategic positioning for coordinating a team of homogeneous agents［C］//STONE P，BALCH T，KAETZSCHMAR G.RoboCup 2000：Robot Soccer World Cup IV.In Melbourne，Austrilia.Berlin：Springer Verlag，2001：29-41.

［5］BOER R，KOK J，GROEN F.UvA Trilearn 2001 Team Description［C］//RoboCup 2001：Robot Soccer World Cup V.In Seattle，America.Berlin：Springer Verlag，2001：70-72.

［6］YAO J.Architecture of TsinghuAeolus［C］//BIRK A，CORADESHI S，TADOKORO S.RoboCup 2001：Robot Soccer World Cup V.In Seattle，America.Berlin：Springer Verlag，2002：201-203.

［7］CAI Yunpeng，CHEN Jiang.Global Planning from Local Eyeshot：An Implementation of Observation-Based Plan Coordination in RoboCup Simulation Games［C］//BIRK A，CORADESHI S，TADOKORO S.Robot Soccer World Cup V.In Seattle，America.Berlin：Springer Verlag，2002：165-168.

［8］蔡剑怀，吴顺祥，缪克华，等.RoboCup中基于神经网络的阵型策略［J］.系统仿真学报，2006（1）：237-239，242.

［9］AKIYAMA H，SHIMORA H，NODA I.HELIOS2008 Team Description Paper［C］//STONE P，BALCH T，KAETZSCHMAR G.RoboCup 2008：Robot Soccer World Cup XII.In Melbourne，Austrilia.Berlin：Springer Verlag，2009：55-60.

［10］胡敏，张佑生.Newton-Thiele插值方法在图像放大中的应用研究［J］.计算机辅助设计与图形学学报，2003（8）：1004-1007.

责任编辑：艾淑艳

A new analytical method of RoboCup formation

CHENG Zekai，LING Zhaolong，QIN Feng
（School of Computer Science and Technology，Anhui University of Technology，Ma'anshan 243032，China）

In the RoboCup simulation 2D，the fedit2 formation editing tool cannot be used to analyze the arrangement of the players in different regions of the stadium from the overall and comparative perspective.Therefore，we put forward a new analytical method.With the idea of data mining，we extracted the position data of the ball and players from RoboCup formation files.Then，we modeled them with the Delaunay Triangulation network theory and obtained the background information in the formation through comparative analysis.The results were applied in the team formation design and decision-making and proved to be effective in the RoboCup World Cup and China Open.

RoboCup；formation；fedit2；data mining；Delaunay Triangulation

TP311

A

1672-0687（2016）02-0041-04

2015-06-02

安徽省自然科学研究重大项目（KJ2014ZD05）

程泽凯（1975-），男，安徽巢湖人，副教授，硕士，研究方向：人工智能，数据挖掘。