RoboCup2D日志文件数据挖掘研究及应用

宋　园，刘　乾，王　灿，程泽凯

(1. 马鞍山职业技术学院 电子信息系，安徽 马鞍山 243002；2.安徽工业大学 计算机学院，安徽 马鞍山 243002)



RoboCup2D日志文件数据挖掘研究及应用

宋园1，刘乾2，王灿2，程泽凯2

(1. 马鞍山职业技术学院 电子信息系，安徽 马鞍山 243002；2.安徽工业大学 计算机学院，安徽 马鞍山 243002)

摘要：机器人世界杯足球赛RoboCup是近年发展迅速的一种国际学术竞赛项目，RoboCup仿真2D项目是影响面最大的项目之一，通常情况下，开发者多使用基于工程化的思想开发球队代码，基于数据挖掘技术可以快速开发出质量更高的球队代码。文中将数据挖掘技术应用到仿真2D球队的开发中，选取比赛中产生的日志文件作为数据源。通过对日志文件进行数据挖掘分析，将得到的隐含的有趣模式应用于球队的进攻跑位策略设计中。仿真比赛证明使用日志文件数据挖掘的方法能够有效提高仿真2D球队的开发效率。

关键词：机器人足球；日志文件；数据挖掘；主动跑位

RoboCup即机器人世界杯足球赛，其目的是促进分布式人工智能和智能机器人的研究和发展。RoboCup仿真2D项目(下文简称仿真2D)是其中的一项比赛项目，每个球员是一个分布式存在的Agent(智能体)，球员维护着不准确的环境信息，且通讯受限。比赛环境是一个庞大的复杂多变的实时系统，存在着巨大的球场状态空间，因此仅仅依靠人工经验手工编码来处理多个球员Agent之间行为的方法是复杂且低效的。

各种多智能体技术与机器学习方法被运用到仿真球队的开发中。美国卡耐基—梅隆大学的CMU球队提出了层次学习的概念，设计球员智能体之间的分层次学习[1]。葡萄牙球队FCPortugal提出了战术和球员类型的概念，并设计了SBSP基于形势的策略跑位[2]和高层战术的通用框架体系[3]。日本球队Helios将计算几何的方法应用到球队的开发中，使用Voronoi图与Delaunay三角形来维护球员的阵型，并使用动作链系统进行球员决策动作的生成与执行[4]。厦门大学AmoyNQ使用神经网络的方法进行阵型学习与截球策略设计[5]。中南大学CSU_YunLu在解决多智能体之间的协作时提出了双层MAS协作模型框架和基于行为预测的多智能体协作模型[6]。安徽大学DreamWing使用决策树学习的方法对球员进行行为选择能力训练[7],并使用Q学习的方法进行前场局部进攻训练[8]。中国科技大学蓝鹰队使用行动驱动的马尔可夫决策过程，通过马尔科夫转移矩阵对球队的决策进行动态规划,实现实时的决策规划[9]。

RoboCup仿真2D比赛的过程中，会产生记录比赛详细数据的日志文件(下文简称仿真2D日志文件)。通常，开发者通过日志文件进行比赛回放，而忽略了日志文件本身可作为数据挖掘数据源的事实。本文提出了一种基于仿真2D日志文件数据挖掘的仿真球队开发思路，将仿真2D日志文件作为数据挖掘的数据源，使用频繁模式挖掘的方法获取到隐含的有趣模式，最后将该模式应用于仿真2D球队的跑位策略开发中，增强了球队的进攻和针对性防守能力。

1问题描述和概念定义

近年来，数据挖掘技术因能解决从大量数据中发掘有用信息的问题而得到了快速的发展。数据挖掘是从大量数据中挖掘隐含的有趣模式和知识的过程[10]。有趣模式指从数据中发现的新颖、有用，且易被人理解的模式。频繁模式是有趣模式的一种，对仿真2D日志文件的数据挖掘分析，可以作为频繁模式挖掘的问题进行研究。

设I= {i1,i2…im} 是由m个不同的项组成的集合，I的子集被称为项集。数据集D由多条事务记录所组成，每个事务记录T是I中若干项的集合，即T为项集。如果存在某一项集X，使得X⊆I且X⊆T，则认为事物记录T支持X。对项集X⊆I，数据集D中支持X的事务记录数目被称为项集X在数据集D上的支持度。频繁模式挖掘的任务就是找出给定数据集D上支持度超过给定阈值的所有项集，这些项集被称为频繁模式。频繁模式挖掘是数据挖掘中较为常用且有效的方法。

数据挖掘通常要经过业务理解、数据准备、模式发现、模式评估和知识表现几个过程。业务理解需要对所要挖掘的事物进行分析，明确数据挖掘目的。数据准备包括数据源选择、数据理解和建模，是数据挖掘的核心部分。模式发现是从数据源中提取模式的过程。模式评估和知识表现，则是将提取到的模式进行评估，寻找有趣模式，并通过可视化或知识表示技术进行模式表示的过程。

文献13中证明了使用日志文件中的数据对球员动作进行分析的可行性。据此，可以将仿真2D文件作为数据源进行数据挖掘分析。

2仿真2D日志文件的数据理解与建模

仿真2D日志文件中记录着大量的比赛相关数据，但仅根据数据无法实现对球员策略的分析，需要将数据与球员的动作策略之间建立映射关系，从数据层面反映比赛中球员动作策略的执行情况。为了使用仿真2D日志文件作为数据挖掘的数据源，首先需对文件中的数据信息进行理解和建模。

日志文件中记录的动作可分为有效动作和无效动作，无效动作虽对策略无实际效果，但会被记录在文件中，导致策略分析的失败。所以首先要区分有效和无效动作。在策略中产生实际效果的动作被定义为有效动作。以KICK动作为例，有效KICK动作定义为仅当球位于某一球员可踢范围内，且该球员发送KICK命令之后，球速改变大小不等于球的惯性力改变大小，该KICK动作为有效动作。

使用日志文件数据表示球员策略时，因脱离了图像化的比赛过程，不能进行直观的判断。为使用统一的方式建立数据和球员策略和球场形势的联系，定义日志文件中检索到的基本动作和比赛状态的数据模型如表1所示：

表1　基本动作和比赛状态的数据模型(部分)

表1中，Side代表动作执行方，Unum代表执行动作的球员号码，Cycle代表动作周期,Pos代表球员位置。

日志文件中获取到的数据被记录为表1中的数据格式，并按照检索到的时间生成动作和状态序列，如有效踢球动作序列表示为KICKi，进球状态序列表示为GOALi。其中下标i代表检索到该动作或状态的时序，如KICKi和KICKi+1表明KICKi+1是KICKi的下一次相邻有效KICK。KICKi和GOALi+1表明，在KICKi之后检索到GOAL状态。

3基于日志文件数据源的进攻跑位数据挖掘分析

在球员策略中，球员的跑位策略非常重要。通常，球员的跑位策略设计使用人工经验对路线进行规划，根据肉眼观看到的实际效果进行策略修正。这种方法虽能设计出具有一定效果的跑位策略，但策略的设计周期长、随意性强、缺少数据参考，需要观看大量的比赛来对策略进行修正。日志文件中包含大量的位置信息，通过日志文件数据挖掘的方法来进行跑位的规划，可以快速有效的设计球员的跑位策略。

下文以进攻跑位为例，说明日志文件数据挖掘在仿真2D中的应用。

3.1进攻跑位分析的业务理解与数据准备

进攻以进球为目的，达到进球目的的进攻为有效的进攻，有效进攻反映出最佳的进攻跑位趋势，所以应只对有效进攻状态进行分析。

将安徽工业大学YuShan队、Agent-3.1.0底层和日本Helios2008队在内的多支球队进行循环比赛，从中选择76场比赛的日志文件进行数据提取，采集到323个进攻成功样本。并对每个样本数据进攻跑位建模，剔除不合理样本和样本中的脏数据。得到进攻跑位数据集D，对D中的所有数据按照球员号码进行分类，得到球员分类的跑位数据集{d1,d2,…d11}。其中d11代表11号球员的进攻跑位数据集。每个数据集中包含着323个进攻样本。

3.2进攻跑位分析的模式发现

为了更清晰的表达跑位数据集中的数据，对数据进行可视化处理。图1显示为左边锋球员在所有进攻样本中的移动轨迹，图2显示中前锋球员的移动轨迹。

图1　9号球员的进攻移动轨迹　　　　　　图2　11号球员进攻移动轨迹

对进攻跑位数据集D中的位置信息进行离散化处理，跑位坐标被归并到如图2中所示的2*2的单元区域，将整个球场x轴方向上分为64份，y轴分为34份，每个单元区域为支持有效进攻的一个项集，且拥有唯一的编号。在球员分类数据集{d1,d2…d11}中，统计每个单元区域的出现次数，并计算其在所有进攻样本中的频度p。设置最小支持度阈值T，当某一单元区域的频度p>T时，将其加入到频繁模式序列中。

设置T为0.6时，获取到有效进攻中球员跑位的频繁模式序列如表2所示。

表2　球员跑位的频繁模式序列(前锋球员部分)

3.3进攻跑位分析的模式评估和知识表现

使用数据可视化的方法将所得到的频繁模式序列进行可视化表现。图3所示为前锋球员进攻跑位频繁模式区域图：

图3　前锋球员进攻跑位频繁模式区域图

图3中，蓝色区域代表左边前锋的跑位频繁模式区域，描绘了在323次有效进攻样本中左边前锋跑位的关键路线。右边前锋和左边前锋移动相对称，这与球队设计中一般将两个边前锋设计为互相对称的跑位策略有关。中前锋的跑位频繁模式区域分散在前场中央位置。

由图3可以在进攻跑位中发现如下规律：

1)边前锋球员多从C2和D31区域发起进攻。

2)中前锋禁区外移动范围较广，进入禁区后移动范围明显缩小。

3)V14，U20及其周边区域为进攻结束区域，多数情况一次有效的进攻在此区域射门。

4)中前锋在中路进入禁区后向两边移动V14，U20移动概率较大。

5)边前锋移动的移动策略和阵型一般相对球场Y轴对称。

依据这些规律重新设计球员的进攻跑位和针对防守策略，并对球队阵型文件进行修改。该策略加入到原球队中，保持其余策略不变，生成改进版本球队。将改进球队与原球队进行15场比赛。作为对比在相同环境下原球队之间也进行15场比赛。比赛结果如表3所示。

表3　测试比赛结果

由表4可以看出，改进后的球队在进攻能力上有较大的提升，相比原始球队，场均进球和胜率都有较大的提高，证明通过数据挖掘获得到的频繁模式可以为球队提供数据参考，提高球队开发效率。

4结语

本文使用数据挖掘的方法对仿真2D日志文件进行分析，并将分析结果应用到进攻跑位策略的设计中，实际比赛证明，该方法能有效提高仿真2D球队开发效率。未来工作首先要对日志文件数据和球员策略之间的映射关系进行更深入的分析，使日志文件数据可以表达出更为复杂的球员策略。其次在已有模型基础上，对防守站位，射门，传接球等策略进行数据分析，利用日志文件中的数据来优化球员的基本动作和策略。

[参考文献]

[1]PeterStone,ManuelaVeloso.LayeredLearning[C].MACHINELEARNING:ECML2000LectureNotesinComputerScience, 2000, 1810(2000):369-381.

[2]LuisPauloReis,NunoLau,EugénioCostaOliveira.SituationBasedStrategicPositioningforCoordinatingaTeamofHomogeneousAgents[C].LectureNotesinComputerScience, 2001, 2103(2001):175-197.

[3]LuisMota,NunoLau,LuisPauloReis.CoordinationinRoboCup2DSimulationLeague:SetPlaysasflexible,MultiRobotplans[C].IEEEConferenceonRoboticsAutomationandMechatronicsSingapore2010:362 - 367.

[4]HidehisaAkiyama,LtsukiNoda.Multi-agentPositioningMechanismintheDynamicEnvironment[C].LectureNotesinComputerScience, 2008, 5001(2008):377-384.

[5]蔡剑怀,李茂青,吴顺祥.RoboCupSoccer中多机器人协作截球策略[J]. 计算机工程与应用,2010,46(16):1-5.

[6]彭军.多智能体协作模型及其在机器人足球仿真中的应用[D].中南大学博士学位论文, 2005.

[7]徐怡,李龙澍,李学俊.改进的决策树生成算法及其在RoboCup中的应用[J].计算机工程与应用, 2007,43(2):57-59.

[8]章惠龙.RoboCup仿真2D中的Agent智能决策系统[D].安徽大学硕士学位论文, 2012.

[9]FengWu,ShlomoZilberstein,XiaopingChen.OnlinePlanningforMulti-AgentSystemswithBoundedCommunication[J],ArtificialIntelligence, 2011, 175( 2):487-511.

[10]韩家炜，裴健. 数据挖掘概念与技术[M].3版.北京:机械工业出版社， 2012.

中图分类号：TP242

文献标识码：A

文章编号：2095-0063(2015)06-0031-04

收稿日期：2015-09-12

基金项目：国家自然科学基金项目(61300059)；安徽省教育厅自然科学研究重大项目编号(KJ2014ZD05)；安徽高校省级自然科学研究基金项目(KJ2011A039)。

作者简介：宋园(1982-)女，安徽马鞍山人，讲师，从事人工智能、机器学习和数据挖掘研究。

DOI10.13356/j.cnki.jdnu.2095-0063.2015.06.008