基于改进CMA-ES 的双足机器人踢球算法设计*

周鼎宇 梁志伟

（南京邮电大学自动化与人工智能学院 南京 210023）

1 引言

RoboCup 作为足球机器人的重要比赛平台之一，极大地促进了人工智能和智能机器人学科的发展。其中，标准平台组（Standard Platform League）的研究包括多仿人机器人的分布式管理、运动规划和路径规划等方面［1～2］。由于实时动态环境下双足机器人对运动加速度的变化很敏感，运动状态的改变极易影响自身的平衡，引起机器人的倒地。所以踢球动作的优劣是赢得比赛的关键技术之一。

目前国内外对此已经有了较为成熟的研究，美国德州大学的UT队设计了一种基于黑盒优化算法的踢球方法［3］，通过利用机器学习对踢球的距离和速度进行优化，目前在RoboCup3D仿真组中得到了很好的效果；葡萄牙的HTWK团队使用关键帧插入法［4～5］，通过预先设定的关节角度集合执行踢球动作，但这种方法必须等到所有关键帧结束才可以执行下一个动作，在实际中效果并不连贯；德国B-Human 团队开发了一种基于倒立摆模型的在线踢球轨迹生成方法［6］，利用ZMP判据有效提高了踢球时的稳定性，但执行起来速度较慢并且踢球距离较短。

为了保证机器人可以稳定有效地进行踢球动作，本文主要采用基于改进的协方差自适应进化策略（CMA-ES）算法的足球机器人射门运动规划规划最优的踢球路径以及腿部轨迹。并将该方法应用于标准平台组的实际比赛中验证该方法的有效性和局限性。

2 改进的CMA-ES算法

2.1 CMA-ES算法基本原理

CMA-ES［7］属于分布式估计算法（EDA）的一种，是一种演化策划算法。它是基于统计的方式使用多元高斯分布在问题优化的解空间中采样，并通过适应度函数来评估每个采样参数，完成所有候选采样集的评估后，下一代采样集的生成会偏向上一代成功的搜索方向。通过采样、更新等的多次迭代完成优化过程。

CMA-ES 算法的每代进化都从多元正态分布N（m，σ2C）在D 维的S 空间中采样得到后代λ，m是当前概率分布的估计值的平均值，σ是搜索步长，C是高斯分布的协方差矩阵。然后再对样本进行适应度函数f(x)进行运算，选择出适应度最好的部分样本更新参数m，C，σ生成下一代。多元高斯分布涉及随机变量的任何优先序列x1，x2，…xk，该分布通过最大似然法拟合，生成公式为

2.2 Tent混沌映射

针对CMA-ES 算法容易陷入局部最优解的缺点，将Tent 混沌映射［8］的方法引入到CMA-ES 的算法中。混沌是一种普遍的非线性现象，具有随机性，遍历性和内在规律性的特点。Tent混沌映射属于线性映射，分布均匀且计算简单，搜索效率较高。当1 ＜u＜2 时，其迭代表达式如下：

混沌序列的第n维服从均匀分布的随机数是xn，n∈[1，N]，xn∈[0，1]。x的初值和u的初值不能相当，否则迭代更新方程将出现周期状态而不是混沌状态。图1 为x初值为0.8，u为1.5 时，对初值进行500次迭代映射的分布图。

图1 Tent混沌映射分布图

将混沌变量映射到解空间：

其中Ld和Ud分别为第n维变量对应搜索的上下限，原均值第n维参数加上Δmd即可实现对均值的混沌映射。

2.3 莱维飞行随机数

莱维飞行［9］指的是步长的概率分布为重尾分布的随机行走，即在随机行走的过程中有相对较高的概率出现大跨步。莱维飞行服从莱维分布的随机搜索路径，通过短距离行走和偶尔长距离行走的结合，达到更广的随机范围。莱维飞行能够扩大搜索范围、增加种群多样性，相比于其他随机算法，更容易跳出局部最优解，更快地达到全局最优解。

一般通过Mantegna 算法来模拟莱维飞行。其更新公式为

表示xi第t代的位置，⊕表示点对点乘法，α表示步长控制量，Levy(λ)表示随机搜索路径，且满足Levy～u=t-（λ1 ＜λ≤3）。

步长s计算公式为

其中u、v都为正态分布，β为定常数通常取1.5。

图2 为Matlab 中莱维飞行进行1000 步的模拟图，可以看出在不确定环境下莱维飞行具有更广泛的搜索范围和更快的全局搜索寻优能力。

图2 莱维飞行模拟图

3 基于改进CMA-ES算法的踢球算法

基于改进CMA-ES算法具体步骤如下。

步骤一：机器人接收到踢球指令，通过踢球代价函数选择最佳踢球点；

步骤二：利用贝塞尔曲线优化最佳踢球点的行走路径，并用三次样条插值法确定踢球时腿部的轨迹曲线；

步骤三：在传统的CMA-ES算法中加入Tent混沌映射和莱维飞行随机数优化迭代过程，满足停止条件后跳出；

步骤四：基于优化的参数，通过逆运动学反向求解各个关节角度；

步骤五：通过ZMP 判据判定该参数是否稳定，如果稳定，执行踢球动作，如果不稳定，转步骤三。

算法流程图如图3所示。

图3 基于改进CMA-ES的算法流程

3.1 最佳踢球点选择

踢球点的选择需要考虑机器人与球的相对位置，包括机器人与球之间的距离和矢量角，以及球到目标之间的矢量。以比赛环境为例，机器人和球的相对位置如图4所示。

图4 踢球点选择示意图

为了防止机器人在行走的过程中误碰到球产生不必要的耗时和误差，本文选择将球以偏移量R为半径进行虚拟膨胀，引入代价函数CKick对虚拟圆上所有的可行踢球点（K1，K2…Kn）计算其踢球代价，当CKick取最小值时即为最佳踢球点。

最佳踢球点选择分为角度旋转和路径规划，所以踢球代价函数CKick为旋转代价分量Cturn和距离代价分量Cdist之和。

3.1.1 旋转代价分量Cturn

如图4 所示，机器人的朝向与向量r→形成的夹角为α，行走向量d→与向量r→形成的夹角为β，转身代价分量Cturn为

3.1.2 距离代价分量Cdist

机器人可以通过视觉参数获取到球相对于机器人的坐标，根据图4，Cdist大小等于，已知机器人与球心位置所构成的矢量r→与偏移位置，可算出距离代价分量Cdist：

根据比赛情况设定权重值ωd、ωt，进而可得CKick：

3.2 贝塞尔曲线优化轨迹

3.2.1 最佳踢球点行走轨迹优化

在传统方法中，机器人会先补偿旋转代价分量Cturn然后沿→方向径直走向K2踢球点，最后调整对齐至K1最佳踢球点。

为了解决传统方法中行走效率低、拐点不平滑的缺陷，本文采用贝塞尔曲线进行路径规划，使机器人到达最佳踢球点时自身的朝向就是踢球的方向。设机器人初始点为P1，最佳踢球点为P′，中间点P2在机器人初始朝向的延长线上，中间点P3在最佳踢球点和球门中心连线的延长线上。用式（13）的三阶贝塞尔曲线［10～11］生成的路径轨迹如图5所示。

图5 基于贝塞尔曲线的路径轨迹规划

3.2.2 踢球腿部轨迹优化

由于足球机器人的躯干节距旋转量基本在3.0°范围内，所以本文假设机器人在踢球运动的过程中上半身保持直立。踢球运动时腿部动作主要分为抬腿、踢球和收腿三个阶段。在执行动作的过程中腿部各个关节的位姿时刻都在发生变化，根据其运动轨迹得到三条曲线，如图6所示。

图6 踢球腿部路径图

将曲线分为n个点代入式（13），通过三阶贝塞尔曲线保证运动的曲线函数是光滑的，以实现对腿部轨迹的优化。

3.3 逆运动学模块

机器人运动学是通过计算默认位置和各个部位之间的连接以及各关节的角度来确定位置。本文通过逆运动学设定机器人的端点来计算必要的关节旋转值以规划动作。即轨迹规划模块给出腿部轨迹曲线，输入到逆运动学模块算出下一时刻的关节值［12～13］。

输入值是齐次变换矩阵，包含了局部坐标系下的足部位置和方向。

相对于HipRot（臀部滚动关节）坐标系下的足部位姿：

式中ld表示站立状态下双腿的间距，Rotx(v)表示向量v沿着x轴的旋转值，Transy(v)表示向量v沿着y轴的平移值。

假设机器人大腿（lthigh）和小腿（llowerleg）之间形成一个三角形，并且已知的平移矢量，可以计算出膝关节角和踝关节角。

式中（x，y，z）是平移矢量的分量，atan2（y，x）定义x轴与点（x，y）之间的夹角。而髋关节的俯仰角、滚动角和偏转角是由唯一决定的：

其中是可用式（13）、（14）确定的。

4 实验分析

4.1 腿部轨迹验证实验

使用SimRobot 平台［14］进行踢球仿真实验并在实体机器人上进行验证，结果如图7 所示。图7 代表腿部仿真轨迹曲线，其中白色点的集合代表机器人关节所在的坐标系，灰色的曲线代表各关节在当前状态的运动轨迹，从左到右三组图分别对应踢球过程中最重要的三种状态：图7（a）是t=0.20s 时机器人向抬腿的瞬时位姿；图7（b）是t=0.31s 时踢球的瞬时位姿；图7（c）是t=0.45s 时机器人收腿复位的瞬时位姿。由图7 仿真结果可以得出，三种状态下仿真机器人不仅稳定且腿部轨迹平滑容易实现。

图7 踢球效果图

由ZMP 稳定判据［15～16］以及实体机器人的表现可知该方法稳定且可行。具体踢球效果将在实验4.2节进行分析。

4.2 踢球对比实验

将本文中改进的CMA-ES踢球算法与文献［6］中的踢球方法进行了实验比较，结果如组图8 所示。上半部分为使用了改进CMA-ES 踢球算法的效果，而下半部分为文献中［6］的踢球方法的效果。

图8 踢球效果对比图

由实验可知，在任意时刻，上半图球的滚动距离都要大于下半图。而从最终球停止位置来看，改进CMA-ES 的踢球算法可以实现一次性把球从己方禁区踢至对方中场，最大距离可达6.9m，而文献［6］的踢球实验最大距离为3.8m。分别使用本文方法和文献［6］的踢球方法，进行了100 次踢球实验测试，分别从踢球的距离、执行踢球动作所花的时间和踢球的稳定性三个方面进行对比，实验结果如表1 所示。得出本文方法的踢球距离平均为6.53m，文献［6］的踢球距离平均为3.76m。执行动作时间上，本文算法平均在2.80s，文献［6］平均在4.26s。从以上对比可以看出，本文方法在踢球距离和时间上均优于文献［6］的方法，但稳定性上略有不足。

表1 踢球实验对比

5 结语

本文主要介绍了标准平台组足球比赛中基于改进CMA-ES的踢球算法，该方法作为比赛的关键技术之一，对足球机器人的进攻与防守效率有较大的提升，并在实际比赛中表现良好，在2020 年RoboCup 机器人世界杯中国公开赛标准平台组项目中获得了一等奖。

但同时，在实际的踢球过程中可能会有敌方机器人的干扰，该方法的不足之处在于动作的鲁棒性有待提高。本文下一步工作是将强化学习理论应用到踢球的动作优化中，以进一步保证踢球过程中的鲁棒性。