基于偏最小二乘法的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