基于粒子群算法的机器人足球中进攻队员的路径优化.doc

实验报告 基于粒子群算法的机器人足球中进攻队员的路径优化 实验人：周琦 学号 1 机器人足球问题 4 2 主要原理 5 2.1 路径的描述 5 2.2 优化目标 6 2.2.1 最大化射门角度 6 2.2.2 最小化路径长度 7 2.2.3 截断判定 8 2.2.4 出界判定 10 2.2.5 优化代价函数 11 2.3 三种不同的防守策略以及理想防守策略 11 2.3.1 无智能防守策略 11 2.3.2 防守队员朝进攻队员的当前位置移动 12 2.3.3 理想防守策略——防守队员根据进攻队员当前移动方向进行预判 13 2.3.4 防守队员根据进攻队员上一步的移动方向进行预判 15 2.4 粒子群算法 16 3 实验结果 17 3.1 实验设置 17 3.1.1 足球场模型的参数设置 17 3.1.2 粒子群算法的参数设置 17 3.2 防守策略一下的实验结果 18 3.3 防守策略二下的实验结果 18 3.4 防守策略三下的实验结果 19 3.5 理想防守策略下的实验结果 20 3.6 结论与分析 21 4 下一步工作 21 4.1 启发式信息——关于禁忌角度的问题 21 4.2 速度可变性 23 4.3 离散问题 23 4.4 一种新的防守策略 24  机器人足球问题 足球作为一项风靡世界的运动，有着悠久的历史以及较为完备的规则。对机器人踢足球进行模拟仿真是一个非常有趣且有挑战性的问题，存在着大量复杂的影响因素。在这里我们仅考虑对进攻队员的路径优化问题。我们给出机器人足球模型如下： 如图1-1所示，在足球场上分别有一名进攻队员A（红色圆圈的圆心）和n名防守队员D={D1,D2…Dn}（蓝色圆圈的圆心），球场两侧为双方球门，当前情况下，黄色方框内为防守方球门。在任意时刻，进攻队员的移动速度和移动方向分别为和，防守队员的移动速度和移动方向分别为和，在这里我们假设进攻队员以及防守队员的速度都相同且为定值||v||，即。每个防守队员有一个防守半径r。在时刻，进攻队员可以获得防守队员的位置以及之前的运动方向，并做出决策以确定进攻队员下一步的移动方向（在后面，我们将其简记为），此时，在不同的防守策略下，防守队员也会确定自己的下一步方向（系统根据不同的策略自动调整）。在时刻之间，球场上所有队员均作匀速直线运动。在任意时刻，当进攻队员和任意一名防守队员之间的距离小于防守半径r时，我们认为进攻队员被截断。 进攻队员的路径优化问题的目标就是：在不同的防守策略下（在后面我们给出了三种防守策略以及理想防守策略），找到一条路径。该路径满足如下四个条件: 在该路径的末端，进攻球员的射门角度尽可能的大。 该路径的长度尽可能的短。 在进攻队员沿着该路径行进的整个过程中，不会被任意一名防守队员所截断。 在进攻队员沿着该路径行进的整个过程中，进攻队员不会越出边界。 图1-1：机器人足球简化模型示意图，其中红色圆圈A的圆心代表进攻队员，蓝色圆圈D1,D2,D3,D4的圆心分别代表四名防守队员，黄色方框内为防守方球门。 很容易可以看出，该问题是一个多目标带约束问题。它的两个目标分别为最大化射门角度以及最小化路径长度。它的两个约束分别为该路径不会越界且不会被防守队员截断。 主要原理 路径的描述 前面已经提到，我们假设进攻队员在任意时间间隙内做的是匀速直线运动，因此我们可以使用攻击队员的起始点以及一个长度为k的方向向量来描述他的进攻路径，这是一段分段连续的路径，其中表示第i步的方向（以绝对方向表示），如图2-1所示。 图2-1：机器人足球进攻队员路径优化问题的一条路径 我们令每段路径的长度，那么，在时刻的坐标为 其中 而在任意时刻时的坐标为 其中 ? 优化目标 最大化射门角度 我们给出进攻球员的射门角度的定义如下： 分别连接进攻队员和对方球门的两个门柱，所得到的两条线段之间夹角即为进攻队员的射门角度。假设进攻队员以随机的任意一个角度射门，且足球为匀速直线运动，在不考虑其他干扰的情况下，进球的概率可以近似表示为。显然，进攻队员的射门角度越大，其进球概率也就越大。如图2-1所示，A1和A2表示进攻队员所处的位置，D1和D2是对方球门门柱的位置。当进攻队员处于A1点时，其射门角度为；当进攻队员处于A2点时，其射门角度为，显然，在A2处进球的概率要大于在A1处进球的概率。这与实际情况也比较吻合。 图2-1：进攻队员的射门角度。 给定进攻队员A坐标，门柱D1和D2的坐标分别为，，那么进攻队员的射门角度可由余弦定理求的。