程澤凱，凌兆龍，秦 鋒

（安徽工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 馬鞍山243002）

一種新的RoboCup陣型分析方法

程澤凱，凌兆龍，秦 鋒

（安徽工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，安徽 馬鞍山243002）

在RoboCup仿真2D中，目前的陣型編輯工具fedit2無(wú)法從全局和對(duì)比的角度去分析球員在整個(gè)球場(chǎng)不同區(qū)域的位置排列。對(duì)此，提出了一種新型陣型分析方法。該方法使用數(shù)據(jù)挖掘的思想從RoboCup陣型文件中分別提取出球和每個(gè)球員的位置數(shù)據(jù)，結(jié)合Delaunay三角網(wǎng)絡(luò)理論進(jìn)行建模，通過分析對(duì)比得出陣型背后的信息。分析結(jié)論應(yīng)用在球隊(duì)陣型設(shè)計(jì)和決策中，并在RoboCup世界杯及中國(guó)公開賽上證明了其有效性。

RoboCup；陣型；fedit2；數(shù)據(jù)挖掘；Delaunay三角網(wǎng)絡(luò)

RoboCup（Robot World Cup），即機(jī)器人世界杯足球錦標(biāo)賽，它涉及到人工智能、智能控制、機(jī)器人學(xué)、通訊傳感、視覺技術(shù)以及制造材料技術(shù)等多領(lǐng)域的前沿研究和技術(shù)融合。仿真2D作為RoboCup的傳統(tǒng)項(xiàng)目之一，比賽過程需要球隊(duì)間整體高效的合作及多個(gè)智體之間的默契配合，由于球隊(duì)以陣型為基礎(chǔ)進(jìn)行架構(gòu)，且每個(gè)球員智能體以陣型點(diǎn)為基礎(chǔ)進(jìn)行決策，因此，陣型是球隊(duì)建設(shè)中至關(guān)重要的因素之一。

國(guó)內(nèi)外先后有多位學(xué)者對(duì)陣型進(jìn)行研究，CMUnited［1-2］提出了關(guān)門協(xié)議（Locker-Room Agreement），根據(jù)比賽結(jié)果和剩余時(shí)間動(dòng)態(tài)改變陣型，并通過基于吸引子和排斥子的策略跑位（strategic position by attraction and repulsion，SPAR）。FCPotugal［3］在CMUnited的基礎(chǔ)上提出SBSP［4］陣型策略，球員根據(jù)球場(chǎng)上的形勢(shì)以及球員自身的策略特性來修正基本位置，得到球員的策略站位點(diǎn)，并且球員可以動(dòng)態(tài)轉(zhuǎn)換角色。UVA_Trilearn［5］在前人工作的基礎(chǔ)上引入球?qū)η騿T的吸引因子，通過球?qū)Σ煌巧奈蜃釉O(shè)計(jì)陣型點(diǎn)，并依據(jù)球的位置和球的被控制情況進(jìn)行陣型維護(hù)。TinghuAeolus［6-7］在原有智能體跑位分配的基礎(chǔ)上，吸收了FC Portugal陣型中角色的概念，提出了基于角色分配陣型的陣型方案，并通過引力模型對(duì)其進(jìn)行在線調(diào)整。Hidehisa Akiyama［8］等提出使用Delaunay Triangulation幾何計(jì)算方法設(shè)計(jì)陣型，是對(duì)SBSP方法的改進(jìn)和擴(kuò)充，即把原來球的位置到球員位置映射的線性函數(shù)變?yōu)榉蔷€性函數(shù)，使球員在整個(gè)球場(chǎng)的可移動(dòng)區(qū)域劃分的更小更多。此外，還有從神經(jīng)網(wǎng)絡(luò)［9］等角度對(duì)陣型進(jìn)行研究，陣型設(shè)計(jì)方法已經(jīng)比較成熟，而陣型分析方法還有待改進(jìn)。

隨著RoboCup技術(shù)的發(fā)展，陣型的合理性對(duì)于高層決策的影響越來越重要，甚至決定著比賽的勝負(fù)。目前的陣型編輯工具fedit2提供了一個(gè)非常方便設(shè)計(jì)，調(diào)整以及查看陣型的平臺(tái)。在使用fedit2去查看陣型時(shí)，對(duì)于陣型中的11名球員位置只有通過滑動(dòng)球的位置用經(jīng)驗(yàn)去判斷球員的位置是否合理，無(wú)法從全局和對(duì)比的角度去分析，fedit2的缺陷正在于此，有時(shí)甚至需要通過許多場(chǎng)比賽來測(cè)試陣型的合理性，同時(shí)，在調(diào)整或者設(shè)計(jì)陣型點(diǎn)時(shí)，11名球員的排列組合又是一個(gè)NP-Hard問題，因此，如何找到一種快捷有效的分析方法是文中的研究目的。文中使用數(shù)據(jù)挖掘的思想對(duì)陣型文件中球和球員的位置數(shù)據(jù)進(jìn)行提取，結(jié)合Delaunay三角網(wǎng)絡(luò)理論，使用Matlab工具進(jìn)行畫圖，將球和球員的所有位置直接反映到圖中，通過分析對(duì)比得出陣型背后的信息。分析結(jié)論應(yīng)用在球隊(duì)陣型設(shè)計(jì)和決策中，并在RoboCup世界杯及中國(guó)公開賽上證明其有效性。

1 陣型編輯工具fedit2及其不足

1.1 RoboCup陣型文件

現(xiàn)如今參加RoboCup仿真2D比賽的大部分球隊(duì)以Agent2D_Base為基礎(chǔ)進(jìn)行研發(fā)，對(duì)陣型進(jìn)行了或多或少的調(diào)整。Agent2D_Base中將球和球員位置數(shù)據(jù)以坐標(biāo)的形式單獨(dú)存放在conf格式的文件中，每一個(gè)坐標(biāo)點(diǎn)即為一個(gè)Delaunay三角網(wǎng)絡(luò)的頂點(diǎn)。陣型文件包括defense-formation.conf，normal-formation.conf，offensive-formation.conf等多種陣型文件，比賽時(shí)球員根據(jù)場(chǎng)上不同形勢(shì)讀取對(duì)應(yīng)的陣型文件，通過球的位置獲取對(duì)應(yīng)的球員自身的位置，即本位點(diǎn)，再根據(jù)場(chǎng)上形勢(shì)對(duì)自身的本位點(diǎn)進(jìn)行調(diào)整。

1.2 fedit2查看陣型文件

陣型編輯工具fedit2可以通過讀取陣型文件來查看陣型的合理性，并對(duì)于不合理的地方進(jìn)行調(diào)整，同時(shí)也可以完全重新設(shè)計(jì)陣型。不同球隊(duì)的陣型點(diǎn)個(gè)數(shù)不同，但都以覆蓋整個(gè)球場(chǎng)為最終目的。圖1是陣型編輯工具fedit2對(duì)Agent2D_Base中陣型文件defense-formation.conf的查看，從圖中可以看出，共有115個(gè)球位置的樣本點(diǎn)覆蓋了整個(gè)球場(chǎng)，每一個(gè)三角形即為一個(gè)球位置的Delaunay三角網(wǎng)絡(luò)。而球員本位點(diǎn)的Delaunay三角網(wǎng)絡(luò)在fedit2中是看不到的。

圖1 fedit2查看陣型文件

圖2 插值算法

1.3 fedit2中對(duì)于球員本位點(diǎn)的定位

從fedit2中可以看出，球員的本位點(diǎn)是根據(jù)球的位置來確定的，但是陣型文件中只有115個(gè)點(diǎn)，似乎不能完全涉及整個(gè)球場(chǎng)上的點(diǎn)。這里，Agent2D_Base中將球員的本位點(diǎn)定位分為2種情形來考慮場(chǎng)上對(duì)應(yīng)的所有位置坐標(biāo)：

（1）球的坐標(biāo)為Delaunay三角網(wǎng)絡(luò)的頂點(diǎn)。對(duì)于每一個(gè)頂點(diǎn)來說，當(dāng)三角形的頂點(diǎn)恰好為球的坐標(biāo)點(diǎn)時(shí)，則輸出球員對(duì)應(yīng)點(diǎn)位在陣型文件中的坐標(biāo)，此點(diǎn)即為球員的本位點(diǎn)。

顯然，若是能夠?qū)⑶騿T本位點(diǎn)的Delaunay三角網(wǎng)絡(luò)在圖中進(jìn)行顯示，通過分析對(duì)比定能得出陣型背后的大量信息。

2 結(jié)合Dalaunay網(wǎng)絡(luò)理論進(jìn)行陣型分析

2.1 使用Matlab工具進(jìn)行數(shù)據(jù)建模

以Agent2D_Base，Gliders2014，Helios2014，Marlik2012為例，使用C++對(duì)各隊(duì)defense-formation.conf中球和每個(gè)球員的Delaunay三角網(wǎng)絡(luò)相關(guān)數(shù)據(jù)進(jìn)行提取，再使用Matlab工具對(duì)數(shù)據(jù)進(jìn)行建模。如圖3-圖11 的Delaunay三角網(wǎng)絡(luò)圖所示，其余的normal-formation.conf，offensive-formation.conf等限于篇幅在此略去。其中4號(hào)角色是邊后衛(wèi)，7號(hào)角色是進(jìn)攻中鋒，9號(hào)角色是邊前鋒，2號(hào)角色和3號(hào)角色是中后衛(wèi)，6號(hào)角色是防守中鋒，11號(hào)角色是中前鋒，4號(hào)、7號(hào)、9號(hào)分別與5號(hào)，8號(hào)，10號(hào)對(duì)稱。

（1）Agent2D_Base的4號(hào)、7號(hào)、9號(hào)如圖3所示，2號(hào)、3號(hào)、6號(hào)、11號(hào)如圖4所示。

圖3 Agent2D_Base的4、7、9號(hào)陣型圖

圖4 Agent2D_Base的2、3、6、11號(hào)陣型圖

（2）Gliders2014的4號(hào)、7號(hào)、9號(hào)如圖5所示，2號(hào)、3號(hào)、6號(hào)、11號(hào)如圖6所示。

圖5 Gliders2014的4、7、9號(hào)陣型圖

圖6 Gliders2014的2、3、6、11號(hào)陣型圖

（3）Helios2014的4號(hào)、7號(hào)、9號(hào)如圖7所示，2號(hào)、3號(hào)、6號(hào)、11號(hào)如圖8所示。

圖7 Helios2014的4、7、9號(hào)陣型圖

圖8 Helios2014的2、3、6、11號(hào)陣型圖

（4）Marlik2012的4號(hào)、7號(hào)、9號(hào)如圖9所示，2號(hào)、3號(hào)、6號(hào)、11號(hào)如圖10所示。

圖9 Marlik2012的4、7、9號(hào)陣型圖

圖10 Marlik2012的2、3、6、11號(hào)陣型圖

（5）Marlik2012的2號(hào)如圖11所示。

2.2 結(jié)合Delaunay三角網(wǎng)絡(luò)理論進(jìn)行分析

圖11 Marlik2012的2號(hào)陣型圖

（1）從圖3、圖5、圖7、圖9分析出Marlik2012的陣型相對(duì)于其他球隊(duì)，Marlik2012的7號(hào)在球場(chǎng)上的覆蓋范圍明顯更大，即防守范圍更廣。

（2）從圖3、圖5、圖7、圖9分析出Marlik2012的4、7、9號(hào)在邊路的x<-50區(qū)域防守點(diǎn)要相對(duì)密集一些。而這也是Marlik2012防守強(qiáng)大的原因之一。

（3）從圖3、圖5、圖7、圖9分析出在邊路的y<-20區(qū)域，Helios2014，Gliders2014，Marlik2012這些球隊(duì)均有較好的區(qū)域防守，特別如圖7的標(biāo)注①所示，而底層則在此區(qū)域出現(xiàn)大面積的防守空缺。

（4）從圖4、圖6、圖8、圖10分析出Helios2014，Gliders2014，Marlik2012均在Agent2D_Base基礎(chǔ)上調(diào)整了陣型點(diǎn)，其中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））（圖中均用加粗線條標(biāo)出）。以上球隊(duì)均在上述區(qū)域重點(diǎn)設(shè)防。而Agent2D_Base的防守點(diǎn)則比較均勻，沒有相對(duì)明顯的防守線。

（5）圖11為單個(gè)球員與球的Delaunay三角網(wǎng)絡(luò)圖，從圖11中，分析出Marlik2012的2號(hào)球員的單個(gè)Delaunay三角網(wǎng)絡(luò)應(yīng)該和與之相對(duì)應(yīng)的球的Delaunay三角網(wǎng)絡(luò)是相似的（圖中用填充三角網(wǎng)絡(luò)標(biāo)示）。

2.3 結(jié)論

（1）一個(gè)好的陣型首先Delaunay三角網(wǎng)絡(luò)的面積分布比較均勻，這樣球員不會(huì)因?yàn)镈elaunay三角網(wǎng)絡(luò)過大而無(wú)法跑到本位點(diǎn)；（2）在球場(chǎng)的邊路上，要有陣型點(diǎn)的涉及，因?yàn)榈讓拥谋∪觞c(diǎn)之一就是會(huì)被對(duì)手帶球下底傳中后射門；（3）應(yīng)該在自己半場(chǎng)上設(shè)有幾道防線，可以大大削弱對(duì)手的穿越傳球等相關(guān)進(jìn)攻；（4）球員的單個(gè)Delaunay三角網(wǎng)絡(luò)應(yīng)該和與之相對(duì)應(yīng)的球的Delaunay三角網(wǎng)絡(luò)盡量相似，這樣才能更加有利于去封堵對(duì)方的進(jìn)攻。

同時(shí)，結(jié)合RoboCup2014巴西世界杯中Gliders2014與Helios2014的log比賽錄像。Gliders2014進(jìn)的Helios2014兩球都是球員帶球下底從邊路傳中后打進(jìn)的，筆者再結(jié)合Helios2014的4號(hào)Delaunay三角網(wǎng)絡(luò)截圖，可以明顯的發(fā)現(xiàn)Helios2014的4號(hào)在邊路在x=-50之后存在防守空隙，而且Helios2014的4號(hào)在這附近的Delaunay三角網(wǎng)絡(luò)區(qū)域明顯過大（如圖8中的標(biāo)注②所示），最終導(dǎo)致Helios2014在此區(qū)域的防守薄弱。而Helios2014的穿越傳球非常兇悍，眾所周知，在面對(duì)Gliders2014時(shí)，由于Gliders2014存在上述的四道防線，從而導(dǎo)致穿越傳球無(wú)法突破Gliders2014的防守。

3 結(jié)語(yǔ)

文中創(chuàng)新使用數(shù)據(jù)挖掘的思想，結(jié)合Delaunay三角網(wǎng)絡(luò)理論提出新型陣型分析方法，重點(diǎn)在研究Agent2D_Base，Gliders2014，Helios2014，Marlik2012的陣型基礎(chǔ)上，發(fā)現(xiàn)其內(nèi)在規(guī)律，從而制定出一套適合球隊(duì)策略的陣型并運(yùn)用在YuShan球隊(duì)的開發(fā)中，同時(shí)在實(shí)際比賽中證明了方法的有效性，球隊(duì)獲得了RoboCup2013世界杯季軍、RoboCup2014世界杯第六名并蟬聯(lián)了RoboCup2013和RoboCup2014中國(guó)公開賽兩屆亞軍。

從目前RoboCup仿真2D的發(fā)展趨勢(shì)來看，各個(gè)強(qiáng)隊(duì)對(duì)于陣型的研究日趨加強(qiáng)，并且都在該領(lǐng)域中作出了嘗試。在YuShan的下一步開發(fā)中，主要研究解決的問題是如何加強(qiáng)智能體的在線分析對(duì)手陣型功能，使其能對(duì)對(duì)手的陣型策略作出對(duì)自己的整體策略進(jìn)行在線調(diào)整。

［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īng)網(wǎng)絡(luò)的陣型策略［J］.系統(tǒng)仿真學(xué)報(bào)，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插值方法在圖像放大中的應(yīng)用研究［J］.計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào)，2003（8）：1004-1007.

責(zé)任編輯：艾淑艷

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

安徽省自然科學(xué)研究重大項(xiàng)目（KJ2014ZD05）

程澤凱（1975-），男，安徽巢湖人，副教授，碩士，研究方向：人工智能，數(shù)據(jù)挖掘。