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

秦 鋒,田 杰,程澤凱

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

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

秦 鋒,田 杰,程澤凱

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

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

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

1 概述

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

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

2 單因變量偏最小二乘法

2.1 偏最小二乘方法思想

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

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

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

Step 1 數據標準化。記F0(F0∈Rn)為單因變量y的標準化向量,E0是解釋變量數據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 數據建模

3.1.1 RoboCup日志文件

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

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

3.1.2 日志文件的解析

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

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

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

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

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

Input(rclfilename);

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

3.1.3 變量的選擇

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

表1 傳球類型分類距離區間 m

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

表2 一場比賽的解析結果

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

3.2 數據分析

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

表3 因變量與解釋變量的相關系數

3.3 PLS成分提取

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

圖1 成分提取

圖2 標準化回歸系數直方圖

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所示,所對應的數值大小如表5所示。

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

表5 解釋變量VIP值

從圖2可以可看出,除1類傳球差與比分差呈負相關外,其余都呈正相關;標準化回歸系數中最大的是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越多,說明進攻的態勢越強,破門得分的可能性也就越大;相反,如果HoldBall次數過多,就越容易被對手截球,在進攻時喪失進攻機會、防守時造成失誤,以至于被對方破門。所以,理論結果符合實際情況。

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

4 結束語

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

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

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

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

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

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

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

[6] 章小兵,劉艷春,陳 黎.基于傳球評價函數的RoboCup傳球策略[J].安徽工業大學學報,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] 周 強,歐陽一鳴,胡學鋼,等.數據挖掘中應用偏最小二乘法發現異常值[J].微電子與計算機,2005,22 (1):25-31.

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

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

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

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

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

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

[16] 王惠文.偏最小二乘回歸的線性與非線性方法[M].北京:國防工業出版社,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-),男,教授,主研方向:機器學習,人工智能,數據挖掘;田 杰,碩士研究生;程澤凱,副教授。

2013-09-09

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