秦 鋒,田 杰,程澤凱

(安徽工業(yè)大學(xué)計(jì)算機(jī)學(xué)院,安徽馬鞍山243000)

基于偏最小二乘法的RoboCup傳球研究

秦 鋒,田 杰,程澤凱

(安徽工業(yè)大學(xué)計(jì)算機(jī)學(xué)院,安徽馬鞍山243000)

傳球動作是RoboCup仿真足球比賽得以進(jìn)行的紐帶,進(jìn)球并贏得比賽是球隊(duì)的最終目標(biāo),分析傳球與比賽勝負(fù)的關(guān)系,采用數(shù)據(jù)挖掘的思想,用C語言程序解析仿真比賽日志文件的方法來收集所需的傳球數(shù)據(jù),基于距離將傳球分為5種類型,以5種類型的傳球作為解釋變量,以比分作為因變量,采用偏最小二乘法搭建數(shù)學(xué)模型,用SIMCA-P軟件進(jìn)行仿真實(shí)驗(yàn),并采用相關(guān)圖形進(jìn)行分析與說明。在包含解釋變量72.8%、因變量74.4%信息量的情況下,5個解釋變量對因變量的投影重要性指標(biāo)值分別為0.081 14,0.996 66,1.028 9,1.088 06,1.325 73。實(shí)驗(yàn)結(jié)果表明,對傳球來說,長傳球?qū)Ρ荣悇儇?fù)的影響最大。

多智能體系統(tǒng);日志文件;數(shù)學(xué)建模;偏最小二乘法;回歸分析;多重共線性

1 概述

RoboCup仿真足球比賽是個多智能體協(xié)作與對抗的平臺,它提供的是一個動態(tài)的、有干擾的實(shí)時環(huán)境,雙方比賽的執(zhí)行采用C/S模式,各有11個Client與Server之間通過 UDP/IP協(xié)議進(jìn)行信息交互[1]。RoboCup仿真比賽充分體現(xiàn)了人類足球的特點(diǎn),它為分布式人工智能(Distributed Artificial Intelligence,DAI)和多智能體系統(tǒng)(Multi-Agent System,MAS)的理論發(fā)展提供了一個重要的實(shí)驗(yàn)平臺,用戶可以在不同的操作系統(tǒng)下使用不同的編程語言,運(yùn)用包括數(shù)學(xué)建模、搜索推理、機(jī)器學(xué)習(xí)、動態(tài)規(guī)劃等各種知識、技術(shù)來構(gòu)建球隊(duì),并通過該平臺進(jìn)行實(shí)踐和檢驗(yàn)[2]。

在仿真比賽中,智能體之間最基本的協(xié)同動作是傳球,傳球無論是在進(jìn)攻態(tài)還是在防守態(tài)都起著至關(guān)重要的銜接作用。通過查閱文獻(xiàn),目前多數(shù)學(xué)者都是以基于工程的思想來對傳球模型進(jìn)行優(yōu)化,文獻(xiàn)[3]采用幾何建模的方法提高精確度。文獻(xiàn)[4]把Q學(xué)習(xí)與神經(jīng)網(wǎng)絡(luò)相結(jié)合,采用離線學(xué)習(xí)的方法來訓(xùn)練傳球。文獻(xiàn)[5]采用決策樹算法定位出傳球成功率最大的球員。文獻(xiàn)[6]采用建立傳球評估函數(shù)的方法確定有利于球隊(duì)進(jìn)攻并且安全的傳球方向。文獻(xiàn)[7]采用模糊邏輯算法和啟發(fā)式搜索算法來規(guī)劃傳球線路,這使得對傳球動作的研究仍局限于底層決策范圍之內(nèi)。智能體之間協(xié)作策略的優(yōu)劣很大程度上決定了球隊(duì)的強(qiáng)弱,本文基于數(shù)據(jù)挖掘的思想,通過對傳球數(shù)據(jù)的挖掘分析,得出一些內(nèi)在的、隱含的信息,為球隊(duì)能夠做出高效率的高層決策提供可靠的理論指導(dǎo)。

2 單因變量偏最小二乘法

2.1 偏最小二乘方法思想

偏最小二乘法(Partial Least Square,PLS)是一種新型的多元統(tǒng)計(jì)分析方法[8],它能解決以往普通多元回歸難以解決的問題,因而得到相關(guān)研究人員的重視,其實(shí)際應(yīng)用涉及化學(xué)、機(jī)械、生物、地質(zhì)、社會科學(xué)和經(jīng)濟(jì)學(xué)等多個領(lǐng)域。文獻(xiàn)[9]把PLS用于數(shù)據(jù)挖掘中發(fā)現(xiàn)異常值,結(jié)合實(shí)際數(shù)據(jù)建立了相應(yīng)的回歸分析模型,實(shí)驗(yàn)結(jié)論得到了合理的解釋。文獻(xiàn)[10]把PLS用于軍用無人機(jī)研制費(fèi)用預(yù)測,并與SMR、BP神經(jīng)網(wǎng)絡(luò)和RBF神經(jīng)網(wǎng)絡(luò)的預(yù)測結(jié)果進(jìn)行比較,結(jié)論表明采用 PLS模型準(zhǔn)確性更高。文獻(xiàn)[11]把PLS用于城市土地利用與交通發(fā)生量關(guān)系模型的研究,分析得出居住用地、建筑容積率、總建筑面積對交通發(fā)生量的影響最大,并通過現(xiàn)實(shí)物理數(shù)據(jù)對得出的預(yù)測模型進(jìn)行檢驗(yàn),結(jié)果表明基于PLS的交通發(fā)生量模型精度優(yōu)良。文獻(xiàn)[12]將PLS引入到大壩安全監(jiān)測變量及其影響因子分析中,解決了大壩安全監(jiān)測模型因子之間存在的多重共線性問題。文獻(xiàn)[13]把PLS用于分析影響魚類在繁殖階段超微弱生物發(fā)光的主要因素,通過對鯉魚超微弱發(fā)光偏最小二乘回歸模型的分析,發(fā)現(xiàn)影響鯉魚超微弱發(fā)光最顯著的指標(biāo)是溫度和性腺成熟系數(shù)。本文把PLS應(yīng)用于Robocup傳球數(shù)據(jù)的數(shù)學(xué)建模與回歸分析中,以達(dá)到提高解釋能力和克服解釋變量之間多重共線性問題的目的。

2.2 單因變量偏最小二乘算法推導(dǎo)

單因變量偏最小二乘算法推導(dǎo)步驟如下:

Step 1 數(shù)據(jù)標(biāo)準(zhǔn)化。記F0(F0∈Rn)為單因變量y的標(biāo)準(zhǔn)化向量,E0是解釋變量數(shù)據(jù)X的標(biāo)準(zhǔn)化矩陣[16]。

Step 4 檢查收斂性,若y對t1的回歸方程已達(dá)到了滿意的精度,則進(jìn)行下一步;否則,以E1代替E0,以F1代替F0重新轉(zhuǎn)到Step2對殘差矩陣進(jìn)行新成分的提取。

2.3 交叉有效性判別

在通常情況下,回歸模型并不需要提取所有的成分,可以通過考察增加一個新的成分后,能否對模型中解釋變量的解釋能力有明顯改進(jìn)來考慮。

2.4 變量投影重要性分析

xj在解釋y時作用的重要性,可以用變量投影重要性指標(biāo)VIP來度量。其中,whj是軸wh的第j個分量;Rd(y,th)=r2(y,th)表示th對y的解釋能力;Rd(y;t1,t2,…,tm)表示t1,t2,…,tm對y的累計(jì)解釋能力。

3 實(shí)驗(yàn)結(jié)果與分析

3.1 數(shù)據(jù)建模

3.1.1 RoboCup日志文件

在比賽中,Server會產(chǎn)生記錄仿真比賽的日志文件,它記錄了比賽過程中球場和球員的真實(shí)數(shù)據(jù)。通常情況下,開發(fā)人員用日志文件進(jìn)行比賽過程的回放,以檢查代碼控制Agent存在的問題或出現(xiàn)的誤差,然后再重新修改代碼。

仿真比賽日志文件分為RCG和RCL 2種,它們的每一條記錄都以固定的規(guī)則用字符串形式來存儲,RCG文件記錄了每個周期的球場狀態(tài),包括球坐標(biāo)、球速度以及所有球員的坐標(biāo)、體能等一系列參數(shù);RCL文件主要記錄的是一些命令信息,包括球員發(fā)送給Server的命令以及教練發(fā)送給球員的命令,包括Kick,Turn,Say等命令參數(shù)。本文將對日志文件中豐富的數(shù)據(jù)加以利用。

3.1.2 日志文件的解析

為獲取傳球分析數(shù)據(jù),用C語言程序,根據(jù)日志文件的存儲規(guī)則,定義相應(yīng)的數(shù)據(jù)結(jié)構(gòu)來解析文件中的字符串。解析過程的偽代碼如下:

Step 1 導(dǎo)入RCG文件名,獲取隊(duì)名、比分及球的信息

Call anafilename(rcgfilename,team1name,team2name, goal);//通過filename得出兩隊(duì)隊(duì)名及比分

Call anaballpos(rcgfilename,bp);//把球坐標(biāo)的信息存于結(jié)構(gòu)體數(shù)組bp中

Step 2 導(dǎo)入RCL文件名,獲取Kick動作的信息

Input(rclfilename);

解析當(dāng)前周期cycle及隊(duì)名tn;

3.1.3 變量的選擇

根據(jù)研究目的,在解析日志文件時,先依據(jù)傳球距離經(jīng)驗(yàn)把傳球分為5種類型,具體距離區(qū)間大小如表1所示,再統(tǒng)計(jì)出各隊(duì)各類傳球的次數(shù)。

表1 傳球類型分類距離區(qū)間 m

例如,任意解析一場完整比賽,結(jié)果如表 2所示。

表2 一場比賽的解析結(jié)果

為研究各類傳球與比賽勝負(fù)的關(guān)系,把兩隊(duì)的數(shù)據(jù)做差,此時便得到一個有6個屬性的數(shù)據(jù)記錄。以比賽得分差作為因變量,用y表示;5類傳球作為解釋變量,分別用x1,x2,x3,x4,x5表示。

3.2 數(shù)據(jù)分析

在本文研究中,以55場仿真比賽日志文件的解析結(jié)果作為建模數(shù)據(jù)。首先對觀測數(shù)據(jù)作相關(guān)性分析,因變量和解釋變量相關(guān)系數(shù)矩陣如表3所示,從表中可以直觀看出,解釋變量之間存在多重共線性的問題,如:r(x2,x3)=0.820 9,r(x2,x4)=0.779 4,r(x3,x4)=0.831 5。

表3 因變量與解釋變量的相關(guān)系數(shù)

3.3 PLS成分提取

經(jīng)SIMCA-P軟件自動擬合,根據(jù)交叉有效性指標(biāo),選擇了2個PLS成分,如圖1所示。各解釋變量標(biāo)準(zhǔn)化回歸系數(shù)直方圖如圖2所示。所以,得到的標(biāo)準(zhǔn)化PLS回歸模型為:

圖1 成分提取

圖2 標(biāo)準(zhǔn)化回歸系數(shù)直方圖

3.4 精度分析

從表4可以看出,提取的2個成分已經(jīng)包含了解釋變量72.8%的變異信息,同時能解釋74.4%因變量y的變異信息。

表4 各成分對因變量和解釋變量的解釋精度

3.5 重要指標(biāo)分析

3.5.1 解釋變量與因變量關(guān)系分析

因?yàn)閠1和u1是X與y的第一主成分,所以在PLS分析中,t1與u1的關(guān)系就可表示解釋變量與因變量的關(guān)系[16],如圖3所示。t1、u1之間存在明顯的線性關(guān)系,也就是說因變量與解釋變量之間存在明顯的線性關(guān)系,說明建立的回歸模型合理。

圖3 t1-u1二維圖

3.5.2 解釋變量對因變量的重要程度分析

各解釋變量投影重要性指標(biāo)VIPj的直方圖如圖4所示,所對應(yīng)的數(shù)值大小如表5所示。

圖4 各解釋變量的投影重要指標(biāo)值直方圖

表5 解釋變量VIP值

從圖2可以可看出,除1類傳球差與比分差呈負(fù)相關(guān)外,其余都呈正相關(guān);標(biāo)準(zhǔn)化回歸系數(shù)中最大的是x5,最小的是x1,按從大到小排序依次為x5,x4,x2,x3,x1。從圖4可看出,解釋變量x5對y的作用最大,x1對y的作用最小,按從大到小排序依次為x5,x4,x3,x2,x1。

結(jié)合實(shí)際比賽場景,x5(dis≥25)相當(dāng)于比賽中長傳球,x1(dis=0)相當(dāng)于比賽中Holdball。長傳球更多的就代表Through Pass,Through Pass越多,說明進(jìn)攻的態(tài)勢越強(qiáng),破門得分的可能性也就越大;相反,如果HoldBall次數(shù)過多,就越容易被對手截球,在進(jìn)攻時喪失進(jìn)攻機(jī)會、防守時造成失誤,以至于被對方破門。所以,理論結(jié)果符合實(shí)際情況。

經(jīng)理論結(jié)合實(shí)際可得出結(jié)論,對于傳球來說,長傳球是關(guān)乎比賽勝負(fù)的關(guān)鍵。

4 結(jié)束語

本文將偏最小二乘法引入到Robocup仿真2D研究領(lǐng)域中,以數(shù)據(jù)挖掘的思路,挖掘出長傳球是比賽勝負(fù)關(guān)鍵的結(jié)論,并結(jié)合相關(guān)圖表對模型的合理性進(jìn)行了分析。下一步工作是將此結(jié)論作為高層決策的依據(jù),在sample_field_evaluator.cpp文件中(本文研究以Agent2D底層代碼為例),對傳球動作評估部分的代碼作適當(dāng)調(diào)整,有意識地在函數(shù)中加大ThroughPass執(zhí)行的weight值,以期望YuShan隊(duì)在今后其他賽事中取得理想的成績。在做此研究之前,通過對仿真比賽的觀察,目測結(jié)果是4類傳球?qū)Ρ荣悇儇?fù)的貢獻(xiàn)最大,而理論結(jié)果卻是5類傳球,造成結(jié)論的誤差可能是源于以下因素:(1)采樣的觀測數(shù)據(jù)量還不夠大,對結(jié)果會有一定影響;(2)傳球類型的距離區(qū)間是根據(jù)經(jīng)驗(yàn)來劃分的,如果能把數(shù)據(jù)離散化工作處理得更好,則能得到更加精確的結(jié)論。雖然存在一些不足,但本文重點(diǎn)是對Robocup2D的研究提供了一種新的思路,即數(shù)據(jù)挖掘。

偏最小二乘法采用數(shù)據(jù)信息量分解的思路,根據(jù)整體數(shù)據(jù)的變異程度將信息重組,可以有效剔除重疊無意義的變量,用這種方法來對數(shù)據(jù)進(jìn)行降維,在當(dāng)今海量數(shù)據(jù)處理困難的形勢下有較大的應(yīng)用價值。

[1] Stone P.Layered Learning in Multi-agent Systems[D]. Pittsburgh,USA:Carnegie Mellon University,1998.

[2] 中國科學(xué)技術(shù)大學(xué)藍(lán)鷹仿真2D球隊(duì).仿真機(jī)器人足球:設(shè)計(jì)與實(shí)現(xiàn)[EB/OL].(2013-07-04).http:// wenku.baidu.com/view/ae0c20ee6294dd88d0d26be0. html.

[3] 郭 博,程家興.RoboCup仿真組的傳球策略[J].計(jì)算機(jī)技術(shù)與發(fā)展,2006,16(2):129-131.

[4] 周 勇,劉 鋒.基于改進(jìn)的Q學(xué)習(xí)的RoboCup傳球策略研究[J].計(jì)算機(jī)技術(shù)與發(fā)展,2008,18(4):63-67.

[5] 張家旺,韓光勝,張 偉.C5.0算法在RoboCup傳球訓(xùn)練中的應(yīng)用研究[J].計(jì)算機(jī)仿真,2006,23(4): 132-135.

[6] 章小兵,劉艷春,陳 黎.基于傳球評價函數(shù)的RoboCup傳球策略[J].安徽工業(yè)大學(xué)學(xué)報(bào),2011,28(2): 171-174.

[7] 李繼耀,陳 瑋,張 祺.智能算法在機(jī)器人足球控制仿真中的應(yīng)用[J].控制理論與應(yīng)用,2007,26(9): 7-9.

[8] Wold S,Martens H,Wold H.The Multivariate Calibration Problem in Chemistry Solved by the PLS Method[C]//Proc.of Conference on Matrix Pensils. Berlin,Germany:Springer-Verlag,1983:286-293.

[9] 周 強(qiáng),歐陽一鳴,胡學(xué)鋼,等.數(shù)據(jù)挖掘中應(yīng)用偏最小二乘法發(fā)現(xiàn)異常值[J].微電子與計(jì)算機(jī),2005,22 (1):25-31.

[10] 羅 為,劉 魯.基于偏最小二乘法的軍用無人機(jī)研制費(fèi)用預(yù)測[J].北京航空航天大學(xué)學(xué)報(bào),2010,36 (6):667-670.

[11] 戚浩平,張 利,王 煒,等.基于偏最小二乘回歸法的城市土地利用與交通發(fā)生量關(guān)系模型研究[J].公路交通科技,2011,28(3):138-143.

[12] 楊 杰,吳中如.觀測數(shù)據(jù)擬合分析中的多重共線性問題[J].四川大學(xué)學(xué)報(bào),2005,37(5):19-24.

[13] 劉桂雄,林緒虹.魚類超微弱發(fā)光的偏最小二乘回歸分析與建模[J].華南理工大學(xué)學(xué)報(bào),2006,34(11): 29-32.

[14] 何曉群.應(yīng)用統(tǒng)計(jì)分析[M].北京:中國人民大學(xué)出版社,2012.

[15] 王惠文.偏最小二乘回歸方法及其應(yīng)用[M].北京:國防工業(yè)出版社,1999.

[16] 王惠文.偏最小二乘回歸的線性與非線性方法[M].北京:國防工業(yè)出版社,2006.

編輯 顧逸斐

Research on RoboCup Passing Ball Based on Partial Least Square Method

QIN Feng,TIAN Jie,CHENG Ze-kai
(College of Computer,Anhui University of Technology,Maanshan 243000,China)

Passing ball action runs through the RoboCup simulation games,both teams spare no effort to win the game. The paper studies the connection between passing ball action and the game deeply.It puts forward to adopt the idea of data mining,analyzes games'log files by C language program in order to collect the required passing ball data,divides passing ball into 5 types which are seen as independent variables and see score as dependent variable,then establishes mathematical model combining with Partial Least Square(PLS).A few relevant figures are used to analyze and verify the experimental result which comes from SIMCA-P.The result shows that with 72.8%of independent variables information and 74.4% of dependent variable information,the VIP values of 5 independent variables to dependent variable are as follows:0.081 14,0.996 66,1.028 9,1.088 06,1.325 73.After linking theoretical result with practical scene,it is concluded that long pass plays a major role in a game for passing ball.

Multi-Agent System(MAS);log file;mathematical modeling;Partial Least Square(PLS);regression analysis;multi-collinearity

1000-3428(2014)09-0275-05

A

TP18

10.3969/j.issn.1000-3428.2014.09.055

安徽高校省級自然科學(xué)研究基金資助項(xiàng)目(KJ2011A039)。

秦 鋒(1962-),男,教授,主研方向:機(jī)器學(xué)習(xí),人工智能,數(shù)據(jù)挖掘;田 杰,碩士研究生;程澤凱,副教授。

2013-09-09

2013-11-06E-mail:tianjie333@126.com