球员个体技术的学习及实现

第七章球员个体技术的学习及实现在Robocup机器人足球比赛中，球员的个人技术是很重要的。如果没有很好的个体技术，再完美的配合也形成不起来。所谓个体技术，主要是指球场上球员可以执行的一些动作，如传球、阻截球、带球、射门、盯人、守门员扑球、铲球等；当然这些动作有的是不能直接发送给Server的，它们是由更低级的Server可识别的原子动作（dash、kick、turn、tackle等）组成，在发送的时候是发送这些原子动作序列。这些个人技术依赖于球员所观察到的世界状态，以世界状态为基础，简化后提取世界状态的特征，根据一定的算法和数学模型做出合适的行为决定。提高球员的个体技术是我们的目标，一般是通过机器学习（MachineLearning，简称ML）、合适的数学模型进行解析和经验式来达到这一目标的。其中数学解析的方法主要是建立各个动作的数学模型，然后用解析几何的方法进行求解；这种方法是建立在对问题的深入分析的基础上面的，因此它的效率较高，当由于在比赛当中存在噪音精确性有时达不到理想的效果，同时也不是所有问题都可以转化成合适的、便于求解的数学模型。而经验式的方法纯粹是根据设计者的经验，通过类似if....then...的结构来设计行为模式；这种方式的优点是可以充分利用人的经验，但是他参数的调节比较繁琐，并且鲁棒性也不是很好。而机器学习的方法优点则比较明显，下面我们就介绍一下机器学习的方法和机器人足球中是如何应用机器学习的。7.1机器学习简介“机器学习”一般被定义为一个系统自我改进的过程。但仅仅从这个定义来理解和实现机器学习是困难的。从最初的基于神经元模型以及函数逼近论的方法研究，到以符号演算为基础的规则学习和决策树学习的产生，之后到认知心理学中归纳、解释、类比等概念的引入，乃至最新的计算学习理论和统计方法学习（主要是指贝叶斯学习和基于马尔可夫过程的强化学习）的兴起，机器学习一直在包括人工智能学科在内的相关学科的实践应用中起着主导地位。然而，根据学习的条件和领域的不同，具体的学习理论和算法也各不相同。本节列举了常见的机器学习理论和相关的学习算法。如：概念学习、决策树、神经网络、贝叶斯学习、基于实例的学习、遗传算法、规则学习、分析学习（基于解释的学习）和强化学习等。（1） 概念学习所谓概念学习就是指通过给定某一类别的若干正例和反例，从中得出该类别一般定义的学习方法。它是一个从许多特例归纳而形成表示一般函数的方法。所以说，概念学习可以看成是搜索预定义潜在的假设空间过程。是归纳法的一种。它的主要设计过程是从一般到特殊序然后形成假设空间的过程。这个概念最初是由Bruneretal.在1957年就提出了，在1970年Winston的博士论文［33］中将概念学习看成是包含泛化和特化操作的搜索过程。Simon和LeaW］在1973年将该学习的过程看成是一个在假设空间搜索的过程。（2） 决策树学习决策树学习是应用最广的归纳推理算法之一。它是一种逼近离散值函数的方法，一般该函数被表示成一颗树，树一般包含多个if-then规则。这种学习方法对噪音数据有很好的健壮性。决策树通过把实例从根节点排列（sort）到某个叶子节点来分类实例。叶子节点即为所属的分类。树上的每个节点说明了对实例的某个属性的测试，并且该节点的每个后继分支对应于该属性的一个可能值。分类实例的方法是从这棵树的根节点开始，测试这个节点指定的属性，然后按照给定实例的该属性值对应的树枝向下移动，一直遍历到叶子。决策树学习可以解决具有以下特征的问题：实例是由“属性-值”对表示的；.目标函数具有离散的输出值；.可能需要析取的描述；.训练数据可以包含错误；.训练数据可以包含缺少属性值的实例。决策树学习的关键是对决策树的构造，典型的构造决策树的方法是ID3算法和C4.5算法。这些算法是都是根据属性的重要性来依次把各个属性分配到相应的结点上面去。人工神经网络人工神经网络学习方法对于逼近实数值、离散值和向量值的目标函数提供了一种健壮性很强的方法。它是通过模拟人类大脑的神经元，形成具有输入和输出的单元结构。对于某些类型的问题，如学习解释复杂的现实世界的传感器数据，人工神经网络是目前最为有效的方法。具有以下特征的问题我们都可以用神经网络来解决：.实例是用很多“属性-值”对表示的；.目标函数的输出可能是离散值、实数值或者由若干实数属性或离散属性组成的向量；.训练数据可能包含错误；.可容忍长时间的训练；.在实际应用的时候可能需要快速求出目标函数值；.人类能否理解学到的目标函数是不重要的。人工神经网络主要训练感知器以及由感知器构成的多层网络结构(包括前向和反馈网络)。在神经网络里面的典型的模型有：自适应共振、双向联想存储器、反向传递、对流网、认识机、感知器、自组织映射网等贝叶斯学习贝叶斯网络的学习是贝叶斯网络模型的构建和对已存在贝叶斯网络模型的优化。由于可以利用的数据日益增加和数据越来越容易获取，使得用数据来进行贝叶斯网络的结构学习和条件概率表的学习变得十分可行，贝叶斯网络的条件概率表的学习又常称为贝叶斯网络的参数学习。基于案例的学习前面的方法都是根据一系列的训练样本，然后形成一定的目标函数把训练样本一般化。而基于实例的学习则不然。基于实例的学习方法只是简单地把训练样本存储起来，从这些实例中泛化的工作被推迟到必须分类出新的实例时。每当学习器遇到一个新的查询实例，它分析这个新的实例与以前存储的实例之间的关系，并据此把一个目标函数值赋给新的实例。基于案例的学习方法主要包括最近邻法和局部加权回归法，它们都假定实例可以表示为欧氏空间的点。此外，基于案例的学习方法还包括基于案例的推理，它对实例采用复杂的符rz|—*号表示。基于案例的学习方法实际上是一个消极学习方法。遗传算法遗传算法是一种受生物进化过程启发的学习算法。遗传算法研究的问题是搜索候选假设空间并确定最佳的假设，一般是通过变异和交叉重组当前已知的最好假设来生成后续的假设。在遗传算法中，假设一般用二进制来表示(便于变异和交叉遗传算子)。

遗传算法的设计有一个共同点：算法迭代更新一个假设池（也称之为群体）。每一次迭代中根据适应度函数评估群体中的所有成员，然后从当前群体中用概率方法选取适应度最高的个体产生新一代群体。在这些选取的个体中，一部分保持原样进入下一代群体，其他通过交叉和变异等遗传的方法产生新的个体作为下一代群体的一部分。（7） 规则学习对学习得到的假设，最具有表征力的和最能为人类所理解的表示方法之一为if-then规则的集合。而规则学习实际上就是学习这样的规则。规则一般包括不含变量和含有变量的。不含变量的很容易理解和得到。最为重要的是学习含有变量的规则集合（也称之为Horn子句集合）。由于一阶Horn子句集合可以被解释为逻辑编程语言中的程序，所以学习的过程经常被称之为归纳逻辑编程（InductiveLogicProgramming，简称ILP）。（8） 分析学习（基于解释的学习）前面的方法都是归纳学习方法。这些归纳学习器在实践中都有一个关键的限制就是学习实例的数据不足时性能较差（这已经被证明，参见文献［35第七章）。而分析学习使用先验知识和演绎推理来扩大训练样本提供的信息，因此，它不受数据不足的影响或影响较小。分析学习的典型方法是基于解释的学习（Explanation-BasedLearning，简称EBL）。它包括2个阶段，分析阶段、泛化阶段。具体来说，首先使用先验知识来分析（或解释）观察到的学习样本是如何满足目标概念的。得出训练样本中哪些特征是相关的，哪些是无关的，然后案例（样本）就可以基于逻辑推理进行泛化，而不必经过统计推理得出。（9） 强化学习强化学习的过程实际上就是给要学习的主体-Agent一个任务，Agent通过不断感知环境，然后根据环境做出动作的选择；如果成功，就对相应的动作做出奖赏，如果失败，就对相应的动作做出惩罚；通过不断的学习，最后会达到一个稳态（以后Agent在相应的环境下一定会做相应动作）。强化学习一个最突出的优点就是不要求有任何的先验知识。这是它跟前面的所有学习算法最根本的不同。以上提到的绝大多数算法都是可以应用到Robocup机器人足球仿真比赛当中，但使用不同的学习算法得到的效果是不一样。但是如果仅仅使用其中的一种，效果可能也达不到要求，因而可能需要不同的方法交叉使用，或根据不同的情况选择特定的方法。7.2个体技术的实现在Robocup中，设计球员的个体技术如带球、传球、截球、射门的时候一般是由更低级的动作组成。有时候还要在这两者之间还要加上一个中间层。就针对于这些基本动作我们具体介绍一下它们的实现方法。7.2.1截球（intercept）1.问题描述截球问题可以归纳成如图5.1的一个简单的场景：白圆圈代表球，黑色的圆圈代表球员，dist为球员到球的距离，a为球到球员之间的连线和球运动方向的夹角，speed为球的即时的运动速度。球的速度随运动衰减。截球问题归结为给定dist、a和speed，决策出队员正确的截球角度8，或者是当截到球时，球运动的距离，并给出对截球所可能花的时间的估计。具体的运动模型见2.7.2.8相关的球员和球的运动模型。2.解决方法1） 解析法通过示意图和前面介绍的运动模型我们可以通过列出关于时间的方程，然后采用Newton迭代法求出方程的根，可以求出认为可以求出3个根，显然第三个根的价值不是很大，目前关注的是前2个根，然后根据高层策略选择在哪个根对应的点（前点和后点）进行截球。TsinghuAeolus目前采用的就是这种方法。2） 通过机器学习的方法进行离线学习目前这是一种简单并且通用的方法，典型的方式是通过搜集大量成功的截球样本（反应为一些特征变量集），在使用这些样本通过离线学习的方法形成一个决策函数。离线学习主要采用贝叶斯网络和神经网络；其中BP网络目前比较通用。CMU99和Hfut目前采用这种方法。简要介绍一下BP网络：BP网络的特点是信号由输入层单向传输到输出层，同一层神经元之间不传递信息，每个神经元与邻层所有神经元相连，连结权重用①..表示，各神经元的作用函数为Sigmoid函数：/（x）=1/（1+。7）。同时它正向传播信号，反向传播误差。BP网络如下图。隐含层是BP网络的基本特征之一，事实上如果没有隐含层也就无所谓误差的反向传播了。但对隐含层节点个数的选择到目前为止还没有确定的规则，根据经验公式BP网络示意图顼mXn+110（m、n表示输入输出节点的个数），由于我们这儿有3个输入，所以我们选择了8个节点。中间隐含层也是使用了1层，包括输入和输出总共3层。在图4.2所示的bp网络结构中，设网络输入为气,%，x3，输出为＞。输入层各神经元的激发函数选用比例系数为1的线性函数，则网络输入层的输出分别是气,%，X3，隐层神经元的输入是：I=^®.尤.（i=1,2,3,...7,8,） （公式4.1），=i神经元的输出为：（公式4.2）O=1/(1+e-i,),（公式4.2）i",为输出层神经元与隐层神经元，的连接权，则网络输出为:（公式4.3）y=rvO（公式4.3）i=1在由①甘v.组成的连接权向量W初始化之后，就可以在给定一组网络输入后，由上述式子求出网络的输出y，此为正向信号传播过程。对某样本(叫，x,x；;)，p为样本数，由正向计算得到y，定义网络输出误差为:1P2p3pp Pdp=tp—yp (公式4.4)误差函数为ep=1/2Xdp2 (公式4.5)一般的，W值随机给出，求得>后，误差值较大，网络计算精度不高。在确定网络P中隐层神经元数目m的情况下，通过调整W的值，逐步降低误差dp，以提高计算精度。在反向计算中，沿着误差函数为e随"变化的负梯度方向对W进行修正。设W的修正值为iw: pde（公式4.6）UW=—n——pdW（公式4.6）n为学习率，取0-1间的数。该修正方法的弱点是收敛速度慢，并存在能量函数局部最小值，在此对其增加附加动量项进行修正，即取：de（公式4.7）AW(n)=-n—+OAW(n-1)dW（公式4.7）AW(n)为第n次迭代计算时连接权的修正值，1W(n-1)为前一次迭代计算时所得的连接权的修正值，口为动量因子。将公式4.4、4.5公式4.7，并加以推导，求得对于样本p时，AW中各元素为：dyAv(n)=nd~~v+以Av(n-1)=ndO+以Av(n-1) (公式4.8)idyAw(n)=nd——l+aw(n-1)=ndvO(1-O)X+aAw(n-1)

ij pdw ij piipipjp ij(公式4.9)最后采用迭代式即+AW-W对原W进行修正计算，得到新的连接权向量即。对于所有的学习样本，均按照样本排列顺序进行上述的计算过程，从而求出学习样本的能量函数值:E」epPT利用E值对网络计算精度进行评价，当E值满足E<0.00001时，停止迭代计算，否则，进行新一轮的迭代计算。训练时，我们构造出各种情况的截球场景（传球队员固定位置，离散传球速度和传球队员和截球队员之间的相对坐标x,y），截球队员使用各种角度截球，当成功的截球时，就将成功的数据记下。采集到的成功的数据送入神经网络用BP算法进行训练。神经网络作为一个记忆的载体记录下这些成功的例子，能够进行实际各种场景的截球决策。3）强化学习的方法进行在线学习在使用强化学习的时候关键是确定状态空间、动作空间、目标状态、策略函数（代价函数）以及价值函数。首先是确定状态空间（s），也就是worldstate，一般状态空间都很大，在计算和存储方面就存在很多困难，这也是目前强化学习往机器人足球中应用的难点地方；这就需要进行简化和处理。然后就是确定动作集，一般把原子动作作为动作集。目标状态是停止学习的终止条件，在学习的时候一般把得到球作为目标状态。所谓策略函数就是在当前的状态在选择动作的函数，这样的函数学要自己去设计，原则是能够把代价最小、利益最大的动作选择出来。而价值函数是在选择一个特定动作以后，是成功还是失败，相应的对这个状态下的这个动作的代价（利益）进行相应的修正，一般是加上（成功）、减去（失败）一个值，经过足够长的时间的学习就能达到一个稳态（也就是价值函数的性能较好）。7.2.2传球（pass）问题描述相对截球而言，传球更加复杂的一种动作，主要原因是在传球的时候实际上已经引入2个球员进行协作的问题了。在设计时一般考虑2种方式进行传球：传给某一特定的人和传到某一点。对传球进行描述的时候，可以采用这种方式：描述传球队员的周围环境，用状态S表示周围的环境或提取环境的一些特征属性向量A（a1,a2,…,an）。根据这些S或A来选择合适的传球方向和出球速度。解决方法根据上面对传球的描述，我们可以使用决策树学习算法，也可以使用基于神经网络的计算学习方法。（1）.决策树学习算法：CMU使用的就是这种学习算法，具体使用了C4.5算法，在选择下面的特征属性：.传球球员到接球者的距离和方向（2个）。.传球队员到其他队友（不包括接球队员）的距离和方向（20个）。.球球队员到对手的队员的距离和方向（22个）。.经排序（按距离）以后的接球队员到队友的距离和方向（20个）。.经排序（按距离）以后的接球队员到对手的距离和方向（22个）。

.从传球队员到接球队员之间的一些分布统计属性（90个）。如以传球队员为中心，由接球队员以及其他队友构成的扇形区域内对方球员的数量等等。.球员所在的区域特性（44个）。训练的时候，首先设定传球队员的位置，随机设置接球和其他队员的位置；传球队员确认要传球；其他队员进行跑位;传球队员根据决策树确定接球队员。接球队员和其他队员（指对手球员）都采用已经训练好的截球动作去获得控球权。接球队员获得控球权就认为是一次成功的传球，否则，就认为失败。（2）基于神经网络的计算学习计算学习一直是机器学习的重要研究内容，它主要是通过计算的方法将那些错的很离谱的假设排除出去形成，通过计算机的快速计算能力得出最有可能的假设并把该假设认为是可能近似正确（probablyapproximatelycorrect，PAC）。另一方面，神经网络集成作为一种新兴的神经计算方法，具有比单一神经网络系统更强的泛化能力，因此，如果将神经网络集成与计算学习相结合，将可望获得更好的效果。在这一思想的基础上，提出了一种基于神经网络集成的计算学习算法，以神经网络集成作为计算学习的前端，首先利用其产生计算学习所用的数据集，在产生数据集时，采用能够较好地反映神经网络集成性能的数据生成方式，使得用于计算学习的示例能够受益于神经网络集成的强泛化能力，以最终获得较高的预测精度。在使用计算学习来进行传球训练的时候，首先是确定在特定传球路线上的传球速度的选择。我们参考了清华［23的对传球时穿越速度的概念。如图4.4,假设白圆圈表示的1号队员要把球传给用黑圆圈表示的2号队员，X表示对手。线L为对手和截球队员的垂直平分线。显然对于垂直平分线与球轨迹的交点p以内的点，对方队员能比我方队员能先跑到；反之，交点以外的点，我方队员先跑到。如果传球队员踢出速度大小合适的球，使得对手在交点以内都无法截到球，那么我方队员就必然可以比对方先截到球。如果以此速度踢出球，此队员不能在该点以前截到球，而且以小于此速度的任何速度踢出球，对手都可能在该点以内截到球,那么这个速度称为对于某个队员穿越在球运动轨迹上的某一点的穿越速度。也就是说，我们只要而且必须要以大于穿越速度的速度传球，球就能传到队友脚下。注意到这个分析基于图4.4队友在对手后面的情况。如果反过来，队友在对手前，则传球者应该以小于队友的穿越速度的速度传球，以保证队友在交点以前截到球。对图4.4的情景，我们把p点以前的区域称为对手的接球区域，p点以后的称为队友的接球区域。对于队友，穿越对手的穿越速度为传球给他的速度的下限。如果考虑队友后面可能有一个对手，则给他一个传球速度上限的限制。图4.4考虑了一个队友和一个对手的简单传球场景，多个对手和队友的场景也有类似的分析。在一条传球线路上，每个队员（包括对手和队友）或者没有接球区域，或者有一个接球的区域和一个传球速度的上、下限。首先，我们利用人工神经网络中的BP网络，训练得到在特定传球路线上面传给每个球员的穿越速度。第一步，采集样本。确定传球队员的位置和随机置接球队员的初始位置。在训练中传球者从一个较小的速度开始，沿传球线路传球，接球者利用训练好的截球技能进行截球，如果截球点在图4.4的p点以前，则传球者提高速度，继续尝试；否则，穿越速度为该次训练的传球速度。如此这样收集传球队员和接球之间不同的距离和角度情况下的穿越速度。第二