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

秦 鋒,田 杰,程澤凱

(安徽工業(yè)大學計算機學院,安徽馬鞍山243000)

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

秦 鋒,田 杰,程澤凱

(安徽工業(yè)大學計算機學院,安徽馬鞍山243000)

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

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

1 概述

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

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

2 單因變量偏最小二乘法

2.1 偏最小二乘方法思想

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

2.2 單因變量偏最小二乘算法推導

單因變量偏最小二乘算法推導步驟如下:

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

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

2.3 交叉有效性判別

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

2.4 變量投影重要性分析

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

3 實驗結果與分析

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

3.1.1 RoboCup日志文件

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

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

3.1.2 日志文件的解析

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

Step 1 導入RCG文件名,獲取隊名、比分及球的信息

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

Call anaballpos(rcgfilename,bp);//把球坐標的信息存于結構體數(shù)組bp中

Step 2 導入RCL文件名,獲取Kick動作的信息

Input(rclfilename);

解析當前周期cycle及隊名tn;

3.1.3 變量的選擇

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

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

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

表2 一場比賽的解析結果

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

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

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

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

3.3 PLS成分提取

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

圖1 成分提取

圖2 標準化回歸系數(shù)直方圖

3.4 精度分析

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

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

3.5 重要指標分析

3.5.1 解釋變量與因變量關系分析

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

圖3 t1-u1二維圖

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

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

圖4 各解釋變量的投影重要指標值直方圖

表5 解釋變量VIP值

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

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

經理論結合實際可得出結論,對于傳球來說,長傳球是關乎比賽勝負的關鍵。

4 結束語

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

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

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

[2] 中國科學技術大學藍鷹仿真2D球隊.仿真機器人足球:設計與實現(xiàn)[EB/OL].(2013-07-04).http:// wenku.baidu.com/view/ae0c20ee6294dd88d0d26be0. html.

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

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

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

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

[7] 李繼耀,陳 瑋,張 祺.智能算法在機器人足球控制仿真中的應用[J].控制理論與應用,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] 周 強,歐陽一鳴,胡學鋼,等.數(shù)據(jù)挖掘中應用偏最小二乘法發(fā)現(xiàn)異常值[J].微電子與計算機,2005,22 (1):25-31.

[10] 羅 為,劉 魯.基于偏最小二乘法的軍用無人機研制費用預測[J].北京航空航天大學學報,2010,36 (6):667-670.

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

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

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

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

[15] 王惠文.偏最小二乘回歸方法及其應用[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

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

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

2013-09-09

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