机器人足球进攻队员的路径优化实验报告.docVIP

实验报告 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  代码测试及分析 优化途径 其中主要是尝试着通过如下途径对加载 尝试着去提高cash命中率和减少内存换页的次数。 根据数据的情况对一些判断的条件进行修改。 对一些数据结构 如std::map，boost::map进行了修改。 尝试着对一些重复的结构进行合并。 其他的一些想法及下一步工作 一开始的时候，我尝试着将array转换成数字，原因有两点 Array在进行比较的时候，相对较为耗时，以PBUID_def为例，执行1 300 000 000次比较需要3到5s， 这样在数据结构上，可以不使用map或者unordered map，而是直接使用一个数组——PBUID_def*[1 000 000]，用pbuid作为数组下标直接进行访问，由于PBUID一共只有6位，那么一共需要大小为106的数组，每个数组都是一个指针，占用的内存为4 000 000 = 4M左右，所需要的内存在可接受范围之内，符合设计原则中的时间效率高于空间 而另一方面，此时的查找只需要进行一次查找（比较），相对于map的红黑树的平均查找次数6（2700多个PBU，红黑树的深度为11左右），有着较大的提高，理论上效率应该有着较大的提高。同时，在这里使用的是数字进行比较，而不是array进行比较，速度应该会有提升。 2、不知道对boost的hashfunc进行修改，会不会对其效率进行改进。 1、尝试着去降低cach命中率和减少内存换页的次数 足球作为一项风靡世界的运动，有着悠久的历史以及较为完备的规则。对机器人踢足球进行模拟仿真是一个非常有趣且有挑战性的问题，存在着大量复杂的影响因素。在这里我们仅考虑对进攻队员的路径优化问题。我们给出机器人足球模型如下： 如图1-1所示，在足球场上分别有一名进攻队员A（红色圆圈的圆心）和n名防守队员D={D1,D2…Dn}（蓝色圆圈的圆心），球场两侧为双方球门，当前情况下，黄色方框内为防守方球门。在任意时刻，进攻队员的移动速度和移动方向分别为和，防守队员的移动速度和移动方向分别为和，在这里我们假设进攻队员以及防守队员的速度都相同且为定值||v||，即。每个防守队员有一个防守半径r。在时刻，进攻队员可以获得防守队员的位置以及之前的运动方向，并做出决策以确定进攻队员下一步的移动方向（在后面，我们将其简记为），此时，在不同的防守策略下，防守队员也会确定自己的下一步方向（系统根据不同的策略自动调整）。在时刻之间，球场上所有队员均作匀速直线运动。在任意时刻，当进攻队员和任意一名防守队员之间的距离小于防守半径r时，我们认为进攻队员被截断。 进攻队员的路径优化问题的目标就是：在不同的防守策略下（在后面我们给出了三种防守策略以及理想防守策略），找到一条路径。该路径满足如下四个条件: 在该路径的末端，进攻球员的射门角度尽可能的大。 该路径的长度尽可能的短。 在进攻队员沿着该路径行进的整个过程中，不会被任意一名防守队员所截断。 在进攻队员沿着该路径行进的整个过程中，进攻队员不会越出边界。 图1-1：机器人足球简化模型示意图，其中红色圆圈A的圆心代表进攻队员，蓝色圆圈D1,D2,D3,D4的圆心分别代表四名防守队员，黄色方框内为防守方球门。 很容易可以看出，该问题是一个多目标带约束问题。它的两个目标分别为最大化射门角度以及最小化路径长度。它的两个约束分别为该路径不会越界且不会被防守队员截断。 主要原理 路径的描