<%JournalFullName%> Vol.<%Volume%> No.<%Issue%><%IssueYear%>, Article ID:<%PaperID%>,<%PageCount%> pages <%DOI%>
The Research of Dynamic Obstacle Avoidance on Simulation Robot Soccer
Jiawei Hu, Yong Liu, Zhao Liu
School of Computer Science and Technology, Wuhan University of Science and Technology, Wuhan
Email: 1106207961@qq.com
Copyright © 2014 Jiawei Hu et al. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. In accordance of the Creative Commons Attribution License all Copyrights © 2014 are reserved for Hans and the owner of the intellectual property Jiawei Hu et al. All Copyright © 2014 are guarded by law and by Hans as a guardian.
Abstract: During the robot soccer game, it will be easily blocked when attacking because we are not able to choose a path to prevent the collision with opponent robot in time and accurately. In order to make attack not be blocked easily, an improved artificial potential field algorithm is proposed to choose path, so as to enhance the efficiency of the robot avoiding obstacles. It chooses the shortest path to reduce the time, so that it can lay a foundation for building up an attack. The algorithm improved the artificial potential field by increasing rotation force, so as to prevent falling into local optimal path selection. The simulation experiment results showed that the algorithm improved the robot obstacle avoidance validity and rationality, and it made the robot breach more easily.
动态避障在仿真机器人足球上的研究
胡镓伟，刘 勇，刘 钊
武汉科技大学计算机科学与技术学院，武汉
Email: 1106207961@qq.com
收稿日期：2013年12月12日；修回日期：2014年1月15日；录用日期：2014年1月26日
摘 要：在机器人足球比赛中，由于不能及时准确的选择一条路径防止和对方机器人碰撞，很容使得进攻受到阻碍。为使得进攻不容易被阻碍，提出了一种改进的人工势场路径选择算法，以此来增加机器人避开障碍物的高效性，选择一条最短路径，从而缩短了时间，为组织好进攻打下基础。以往的人工势场方法都容易陷入局部最优，本算法通过增加旋转力,对人工势场方法进行了改进，防止选择的路径陷入局部最优。算法进行了仿真实验，结果表明该算法提高了机器人避障的有效性和合理性，使得进攻更具有切入性。
关键词：机器人足球；人工势场；动态避障
1. 引言
机器人足球在人工智能领域是一个具有高可研究性的项目，目前世界上很多高校和科研机构都对机器人项目进行了各种研究，而且都取得了不错的效果并运用于实际应用当中。在对仿真机器人项目上的研
究过程当中，运用各种方法使得机器人的进攻更具威胁性，配合性和有效性是极为重要的。目前，各种人工智能算法，如聚类，K-means，神经网络算法等都对机器人进攻策略产生了巨大的作用[1]。
为使得机器人进攻不容易被截断，选择一条容易带球进攻的路线是至关重要的[2]。以往基于人工势场的方法在选择路径当中具有一定的作用[3,4]，但是容易陷入局部最小值，因此本文提出了一种基于人工势场的改进算法，防止所搜索的路线陷入局部最小值。在实际比赛中，假设机器人所处的位置和要到达的目标点如图1所示，其中F_out表示障碍物对我方机器人的斥力，F_attract表示目标点G对我方机器人的吸引力，F_circle即为引入的旋转力，防止陷入局部最小值。
人工势场法是由Khatbi提出的一种机器人路径规划算法。该算法将目标和障碍物分别看做对机器人有引力和斥力的物体，机器人沿引力与斥力的合力来进行运动。该法结构简单，便于低层的实时控制，在实时避障和平滑的轨迹控制方面，得到了广泛应用，其不足在于存在局部最优解，容易产生死锁现象[5,6]，因而可能使移动机器人在到达目标点之前就停留在局部最优点。为简化模型表示，将模型变为图2所示，其中增加了障碍物与我方夹角β，目标点和我方机器人的夹角α。
2. 算法流程图
机器人每次蔽障前都要先初始化各项数据，分为三步动态蔽障，1) 判断场地上的障碍物，2) 计算各个障碍物的layer，3) 根据势场模型计算出要蔽障的机器人受到的力的大小和方向，计算跑位点，然后跑向该方向。算法流程图如图3。
3. 单个机器人的蔽障算法
分析图中所表示的内容，可以知道，当β很小时旋转力应该很大，确保机器人跳出局部最优。吸引力应该确保为一个比较大的值，应正比于MG的长，排斥力则与MO成反比，三股力大小应该合理，不应该过大或者过小。为量化处理，下面给出力的具体表示公式：
(1)
(2)
(3)
其中dd计算公式如下：
(4)
其中k1，k2，c1，c2，a，b均为正数，layer描述障
Figure 1. The potential field model after introducing a rotational force
图1. 引入旋转力后的势场模型
Figure 2. The simplified model
图2. 简化之后的模型
Figure 3. Basic flow chart of the algorithm
图3. 算法基本流程
碍物挨在一起的程度，一般为1，ds表示M和O的相对速度。
算法步骤一：障碍物的判断
判断障碍物，可以为每个对方机器人设置一个危险区域，如果机器人在某个对方机器人的危险区域内，那么该机器人就是障碍物，危险区域为一个圆，半径公式：safe_dist[i]=5 + 6*ds[i](ds[i]是对方第i号机器人和我的相对速度)，障碍物危险区域简单描述如图4。
步骤二：确定障碍物的layer
确定障碍物的layer可以通过搜索障碍物周围的障碍物数量来确定。其中稀疏度计算方式如下：
将对方机器人下一次间距小于两倍机器人边长的归为一类，然后计算它们之间的平均距离avg_dist，该类中所有机器人的layer都等于avg_dist/k3 (k3为常数)，如果有落单的机器人，其layer设为1合适的k3满足avg_dist/k3 > 1。障碍物的layer示意图如图5。
步骤三：旋转方向的选择
旋转方向的选择就是F_circle到底应该顺时针还是逆时针，每个F_circle的方向都应该是合理的，对全局有利。为描述清楚，以图6为例说明选择的方法。
连接g，m，过o作gm的垂线，在垂线上选两个测试点p1，p2，满足|op1| = 机器人直径 = |op2|，如果pi点有机器人，那么pi点沿着垂线平移一个机器人直径的步长，直到找到空闲的位置，然后预测机器人经过pi点到g点的时间，选择耗时小的点，如果是p1，F_Circle顺时针，如果是p2，F_Circle逆时针。
步骤四：避障
先求合力，然后根据合力的方向计算跑位点，调用跑位函数即可。
求合力，其中Fx，Fy初始为0，i为对方机器人编号：
其中Fx表示合力在x轴方向上的投影，Fy表示合力在y轴方向上的投影，a1为MO与x轴的夹角，a2为垂直于MO与x轴的夹角，a3为MG与x轴的夹角。
计算跑位点：
Figure 4. Danger zone of obstacles
图4. 障碍物危险区域
Figure 5. Obstacle classification
图5. 障碍物层级划分
Figure 6. Method of rotating direction selection
图6. 旋转方向选择的方式
其中loc_now表示我方机器人的位置坐标，p_next为下一次要跑到的位置。P_next.x与p_next.y分别表示跑位点x轴坐标与y轴坐标。
4. 实验结果
算法在仿真平台测试后，实验效果图经简化处理，效果如图7~12所示，图中数字代表障碍物编号。
图中黄色机器人代表进攻方，蓝色标注的机器人代表敌方机器人，目标点为G，机器人每次确定的次目标点为G’，图中显示了进攻机器人六次选择的路径的位置，最终机器人找出一条合理的路径到达目标点。
可以从图中看出，经过对人工势场法的改进，机器人在运动过程中对障碍物的躲避能力有了明显的辨识，对于合理方向的选取也得到改善，不再出现抖
Figure 7. Initial location
图7. 初始位置
Figure 8. The second location
图8. 第二次所在位置
动问题。
5. 结论
近年来关于机器人路径规划的方法有很多，基于人工势场的算法起到了一定的引导作用，但是由于人工势场的方法存在一定的局限性，容易陷入局部最小值，所以单纯的人工势场方法并不能满足动态路径规
Figure 9. The third location
图9. 第三次所在位置
Figure 10. The forth location
图10. 第四次所在位置
Figure 11. The fifth location
图11. 第五次所在位置
Figure 12. The sixth location
图12. 第六次所在位置
划的需求。因此关于改进的人工势场方法层出不穷，本文所提出的正是一种改进的人工势场算法，在仿真平台上测试的效果显示该算法结果与预期效果符合，与其它改进的方法相比具有一定的优越性，相对简单易懂。
应用本文的思想，使得机器人在进攻组织方面性能得以提高，机动性更强，使得进攻得以顺利进行。
[1] 参考文献 (References)
[2] 李擎, 王丽君, 陈博, 周州, 尹怡欣 (2012) 一种基于6遗传算法参数优化的改进人工势场法. 北京科技大学学报, 2, 202-206.
[3] 卢恩超, 张邓澜, 宁雅男, 冯小海, 李莹 (2012) 改进人工势场法的机器人路径规划. 西北大学学报, 5, 735-738.
[4] 张琪, 杨宜明 (2002) 基于改进人工势场法的足球机器人避碰控制. 机器人, 1, 12-15.
[5] 樊晓平, 李双艳, 陈特放 (2005) 基于新人工势场函数的机器人动态避障规划. 控制理论与应用, 5, 703-707.
[6] 姜明洋, 范晓静 (2012) 基于改进人工势场法的移动机器人路径规划. 内蒙古民族大学学报, 2, 409-411.
[7] 张殿富, 刘福 (2013) 基于人工势场法的路径规划方法研究及展望. 计算机工程与科学, 6, 88-95.
Received: Dec. 12th, 2013; revised: Jan. 15th, 2014; accepted: Jan. 26th, 2014
Keywords: Robot Soccer; Artificial Potential Field; Dynamic Obstacle Avoidance
1. 引言
机器人足球在人工智能领域是一个具有高可研究性的项目，目前世界上很多高校和科研机构都对机器人项目进行了各种研究，而且都取得了不错的效果并运用于实际应用当中。在对仿真机器人项目上的研
究过程当中，运用各种方法使得机器人的进攻更具威胁性，配合性和有效性是极为重要的。目前，各种人工智能算法，如聚类，K-means，神经网络算法等都对机器人进攻策略产生了巨大的作用[1]。
为使得机器人进攻不容易被截断，选择一条容易带球进攻的路线是至关重要的[2]。以往基于人工势场的方法在选择路径当中具有一定的作用[3,4]，但是容易陷入局部最小值，因此本文提出了一种基于人工势场的改进算法，防止所搜索的路线陷入局部最小值。在实际比赛中，假设机器人所处的位置和要到达的目标点如图1所示，其中F_out表示障碍物对我方机器人的斥力，F_attract表示目标点G对我方机器人的吸引力，F_circle即为引入的旋转力，防止陷入局部最小值。
人工势场法是由Khatbi提出的一种机器人路径规划算法。该算法将目标和障碍物分别看做对机器人有引力和斥力的物体，机器人沿引力与斥力的合力来进行运动。该法结构简单，便于低层的实时控制，在实时避障和平滑的轨迹控制方面，得到了广泛应用，其不足在于存在局部最优解，容易产生死锁现象[5,6]，因而可能使移动机器人在到达目标点之前就停留在局部最优点。为简化模型表示，将模型变为图2所示，其中增加了障碍物与我方夹角β，目标点和我方机器人的夹角α。
2. 算法流程图
机器人每次蔽障前都要先初始化各项数据，分为三步动态蔽障，1) 判断场地上的障碍物，2) 计算各个障碍物的layer，3) 根据势场模型计算出要蔽障的机器人受到的力的大小和方向，计算跑位点，然后跑向该方向。算法流程图如图3。
3. 单个机器人的蔽障算法
分析图中所表示的内容，可以知道，当β很小时旋转力应该很大，确保机器人跳出局部最优。吸引力应该确保为一个比较大的值，应正比于MG的长，排斥力则与MO成反比，三股力大小应该合理，不应该过大或者过小。为量化处理，下面给出力的具体表示公式：
(1)
(2)
(3)
其中dd计算公式如下：
(4)
其中k1，k2，c1，c2，a，b均为正数，layer描述障
Figure 1. The potential field model after introducing a rotational force
图1. 引入旋转力后的势场模型
Figure 2. The simplified model
图2. 简化之后的模型
Figure 3. Basic flow chart of the algorithm
图3. 算法基本流程
碍物挨在一起的程度，一般为1，ds表示M和O的相对速度。
算法步骤一：障碍物的判断
判断障碍物，可以为每个对方机器人设置一个危险区域，如果机器人在某个对方机器人的危险区域内，那么该机器人就是障碍物，危险区域为一个圆，半径公式：safe_dist[i]=5 + 6*ds[i](ds[i]是对方第i号机器人和我的相对速度)，障碍物危险区域简单描述如图4。
步骤二：确定障碍物的layer
确定障碍物的layer可以通过搜索障碍物周围的障碍物数量来确定。其中稀疏度计算方式如下：
将对方机器人下一次间距小于两倍机器人边长的归为一类，然后计算它们之间的平均距离avg_dist，该类中所有机器人的layer都等于avg_dist/k3 (k3为常数)，如果有落单的机器人，其layer设为1合适的k3满足avg_dist/k3 > 1。障碍物的layer示意图如图5。
步骤三：旋转方向的选择
旋转方向的选择就是F_circle到底应该顺时针还是逆时针，每个F_circle的方向都应该是合理的，对全局有利。为描述清楚，以图6为例说明选择的方法。
连接g，m，过o作gm的垂线，在垂线上选两个测试点p1，p2，满足|op1| = 机器人直径 = |op2|，如果pi点有机器人，那么pi点沿着垂线平移一个机器人直径的步长，直到找到空闲的位置，然后预测机器人经过pi点到g点的时间，选择耗时小的点，如果是p1，F_Circle顺时针，如果是p2，F_Circle逆时针。
步骤四：避障
先求合力，然后根据合力的方向计算跑位点，调用跑位函数即可。
求合力，其中Fx，Fy初始为0，i为对方机器人编号：
其中Fx表示合力在x轴方向上的投影，Fy表示合力在y轴方向上的投影，a1为MO与x轴的夹角，a2为垂直于MO与x轴的夹角，a3为MG与x轴的夹角。
计算跑位点：
Figure 4. Danger zone of obstacles
图4. 障碍物危险区域
Figure 5. Obstacle classification
图5. 障碍物层级划分
Figure 6. Method of rotating direction selection
图6. 旋转方向选择的方式
其中loc_now表示我方机器人的位置坐标，p_next为下一次要跑到的位置。P_next.x与p_next.y分别表示跑位点x轴坐标与y轴坐标。
4. 实验结果
算法在仿真平台测试后，实验效果图经简化处理，效果如图7~12所示，图中数字代表障碍物编号。
图中黄色机器人代表进攻方，蓝色标注的机器人代表敌方机器人，目标点为G，机器人每次确定的次目标点为G’，图中显示了进攻机器人六次选择的路径的位置，最终机器人找出一条合理的路径到达目标点。
可以从图中看出，经过对人工势场法的改进，机器人在运动过程中对障碍物的躲避能力有了明显的辨识，对于合理方向的选取也得到改善，不再出现抖
Figure 7. Initial location
图7. 初始位置
Figure 8. The second location
图8. 第二次所在位置
动问题。
5. 结论
近年来关于机器人路径规划的方法有很多，基于人工势场的算法起到了一定的引导作用，但是由于人工势场的方法存在一定的局限性，容易陷入局部最小值，所以单纯的人工势场方法并不能满足动态路径规
Figure 9. The third location
图9. 第三次所在位置
Figure 10. The forth location
图10. 第四次所在位置
Figure 11. The fifth location
图11. 第五次所在位置
Figure 12. The sixth location
图12. 第六次所在位置
划的需求。因此关于改进的人工势场方法层出不穷，本文所提出的正是一种改进的人工势场算法，在仿真平台上测试的效果显示该算法结果与预期效果符合，与其它改进的方法相比具有一定的优越性，相对简单易懂。
应用本文的思想，使得机器人在进攻组织方面性能得以提高，机动性更强，使得进攻得以顺利进行。
参考文献 (References)
- 李擎, 王丽君, 陈博, 周州, 尹怡欣 (2012) 一种基于6遗传算法参数优化的改进人工势场法. 北京科技大学学报, 2, 202-206.
- 卢恩超, 张邓澜, 宁雅男, 冯小海, 李莹 (2012) 改进人工势场法的机器人路径规划. 西北大学学报, 5, 735-738.
- 张琪, 杨宜明 (2002) 基于改进人工势场法的足球机器人避碰控制. 机器人, 1, 12-15.
- 樊晓平, 李双艳, 陈特放 (2005) 基于新人工势场函数的机器人动态避障规划. 控制理论与应用, 5, 703-707.
- 姜明洋, 范晓静 (2012) 基于改进人工势场法的移动机器人路径规划. 内蒙古民族大学学报, 2, 409-411.
- 张殿富, 刘福 (2013) 基于人工势场法的路径规划方法研究及展望. 计算机工程与科学, 6, 88-95.