足球机器人避障及防侧翻问题研究

薛 丹, 孙喜庆, 白文峰*

(1.长春工业大学 电气与电子工程学院， 吉林 长春 130012；2.长春理工大学光电信息学院， 吉林 长春 130114)

足球机器人避障及防侧翻问题研究

薛 丹1,2, 孙喜庆1, 白文峰1*

(1.长春工业大学 电气与电子工程学院， 吉林 长春 130012；2.长春理工大学光电信息学院， 吉林 长春 130114)

应用扩展地图,采用改进遗传算法以及蚁群与遗传结合算法相结合来优化机器人运行路径的长度、平滑性和安全性3个目标。

机器人； 路径规划； 扩展地图； 遗传算法； 蚁群遗传算法

0 引 言

近年来，足球机器人各方面的研究工作不断深入，其中路径规划问题可以分为传统方法和智能方法。传统方法有图形搜索、人工势场、网格方法等，这些传统的研究方法尽管可以较好地解决路径规划问题，但是搜索效率低[1-3]。智能算法以蚁群算法、遗传算法、神经网络为代表，因其效率高而得到广泛的应用，当然智能算法在应用过程中也有其相应的缺点。

因足球机器人不是单一的机器人运动，所以，足球机器人路径规划不是只求长度最短的单一目标的优化。在机器人进行足球比赛过程中，会遇到很多随机的问题，主要是足球机器人之间的碰撞，足球机器人自身的侧翻[4]。对于碰撞问题可分为动态障碍物和静态障碍物，所以，在大多数现实情况下，机器人与障碍物一定要保持有效的安全空间。此外，机器人在应用时，还要考虑到路径中可能存在的小夹角，如果存在这样的夹角，机器人的车轮可能遭到一定的磨损，严重一点的会使得机器人不再沿着规划的轨迹行驶，甚至可能导致机器人的侧翻，因此，机器人路径规划问题是有多个最优解的，并且是难以找到精确解的[5]。对此，提出了能有效地使机器人可以从起点无碰撞且无翻滚的运动到终点的解决方法，尽管这些解决方法存在着一些缺点，但是已经取得了一些研究成果。

因足球机器人路径规划要考虑到路径的长度、平滑性、安全性，所以这是一个多目标优化问题。此问题首先考虑机器人的碰撞和翻滚，此时可考虑应用扩展碰撞地图[4]。

1 问题描述

将每个机器人假设为一个平移和转动被独立控制的轮式驱动机器人，因此无翻滚状态下的机器人描述如下[6]：

kXb-kYb-kZb是一个机器人框架，机器人的宽度、重心的高度分别为wb和h。此时平移速度v由足球机器人从起点到目标点采用的梯形速度曲线决定。

但是考虑到安全问题，在机器人行进过程中可以加入偏移速度Δv，此时的无翻滚状态即被描述为：

换句话说，只要足球机器人的运行速度被控制在式(2)的上限和下限之间，它就不会在运动中翻滚。对于固定障碍物的无碰撞路径，可以先将机器人运行环境假定为一个有边界的二维场地，其中分布着若干静态障碍物Ox1,Ox2,…,Oxn，机器人应在每一个节点(障碍物附近)处有效的停止，并且转向下一个节点，由此便产生从起点到终点的由几条直线组成的无翻滚路径。这里起点设为A，终点设为B。多目标路径设为L={l1,l2,…,ln}，li是指规划路径L的i节点，且

足球机器人路径规划是多目标优化，将路径简化为

满足

对于f1(l),f2(l),f3(l)我们用如下方程作出定义。

定义1表示路径总长度的长度指数由下式确定：

定义2表示所有向量路径段角度和的平滑指数由下式确定：

定义3表示每个路径段和障碍物之间最短距离和的安全指数由下式获得：

当满足这4个条件：

机器人将无翻滚地完成路径的寻优。在这4个条件中，条件(a)是对机器人速度范围的限定，机器人在此速度范围内运动，才可能保持稳定的状态，不会在运动过程中未碰上障碍物的情况下翻滚；条件(b)、(c)、(d)是机器人在条件(a)的范围内运动所要求的目标函数，当3个函数都是极小值时，所得曲线是机器人路径规划的最优目标。

2 改进型遗传算法的多目标路径规划

2.1 个体编码

对于个体固定长度的编码方法主要采用一组固定的一维坐标尺寸，也就是将机器人工作领域的X轴分成n段，保证了每个独立节点在X轴上都有其固定的坐标[8]。这种编码方法可以简单而直接地看作在Y轴的一维编码。但是由于在X轴上独立节点总数和每个节点间的距离是固定的，所以缺乏灵活性。因此，采用可变长度的二维浮点数编码：(x1,y1)→(x2,y2)→…→(xnc,ync)。个体编码长度是可变的，其值取决于机器人工作领域中障碍物分布的复杂度。在集中的地区增加障碍物数量，使路径更加平滑和安全，但在只有几个障碍物的地区将会减小自适应。这种编码方式将会加强搜索的精度和灵活性。此外，一定要保证每个独立节点的X坐标在个体编码中是有序增殖的，这样才能保证在进化过程中路径是保持向需要的方向进化的[8]。

2.2 种群初始化

种群初始化的方法是根据遗传算法随机选择的。但是，随着机器人路径规划在有随机障碍物的环境中进行，随机初始化路径在进化过程中总是无效的。为了解决路径规划中的种群初始化问题，学者们提出了多种改进方法。例如，申晓宁[9]等认为，因为起点和终点是已知的，当环境中没有障碍物的时候，两点间的直线最短，此时该直线应该是最短且最平滑的路径。在此类信息的启发下，这条直线附近将随机生成一些初始化路径。然而，只在比较理想的环境中这种方法才可以获得较好的效果，一旦应用在复杂环境中，特别是在起点和终点间有障碍物的情况下，这种方法的有效性是很低的。

2.3 蚁群遗传算法

机器人路径问题可看做是一个组合优化的问题，以S=S1,S2,…,Sn为基本组成部分的问题。一个子集C代表一个解决方案：F是可行解的集合，当且仅当C∈F时，C是可行解。在解的范围上定义成本函数Y，Y：2s→R，最终找出最优解C*，C*∈F，且Y(C*)≤Y(C)，C∈F。他们采用基于双参数的随机局部决策策略移动，也就是路径和生物信息素。通过移动，每个蚂蚁构建一个问题的解决方案[5]。

即使所有机器人都找到了可行解，因赛场上的信息具有时变性，所以得到的可行解未必是最优解，因此，必须根据局部信息和全局信息对生物信息素进行更新，并要满足以下原则[10]：

式中:Lk----机器人走过的路径长度。

应用蚁群遗传算法进行机器人路径规划主要包括以下流程[11]：

1)初始化。

①设置系统的初始参数：出发点、目标点、迭代次数。

②设置初始的信息素挥发系数：各条路径上的信息素强度、各障碍物信息素值。

③将每个机器人(蚂蚁)放置在初始状态节点上。

2)主回路(迭代次数的总数)。

①构建蚁群决策方案：计算每只蚂蚁的路径选择概率；每只蚂蚁应用转移函数构建路径，从一个节点移动到另一个节点。

②通过局部搜索计算蚂蚁爬行路径的优化函数。

③检测最佳路径：根据信息的动态更新，及时进行路径寻优。

④更新轨迹：此轮路径规划结束。调整每条路径上的信息素比例，完成每个蚂蚁的信息素更新。

⑤根据信息素步道，确定所选路径是否为最优解，若是，则输出最优解；否则继续进行机器人路径规划。

在没有障碍物的情况下，足球机器人按式(1)和式(2)确定平移的速度和框架。

3 计算机仿真

本系统的计算机仿真是应用MS Visual Studio环境编程实验的。规划路径如图1所示。

图1 文中算法得到的路径

由于路径段与障碍物之间的间隙过小，在运动过程中，可能会发生碰撞。文中所用算法得到的路径长度短、平滑，与障碍物之间也有一些安全间隙，以此来保证一定的安全性。

蚁群遗传算法仿真路径如图2所示。

图2 蚁群遗传算法仿真路径

由图2可以得出蚁群遗传算法仿真路径简化曲线，如图3所示。

图3 蚁群遗传算法仿真路径简化曲线

对于图3分析见表1。

表1 路径曲线图分析表

注：Ⅰ.红色曲线； Ⅱ.蓝色曲线； Ⅲ.绿色曲线。

经过分段比较：在长度指数方面，红色曲线长度最短，蓝色次之，绿色最长；在平滑指数方面，红色曲线最优，蓝色次之，绿色较差；在安全指数方面，红色和蓝色最优，绿色次之。综合考虑各项指数，红色最优，即文中所用算法得到的曲线最优。

4 结 语

对机器人运动过程中的无翻滚和无侧翻的路径规划,该方法有望应用于不平地形上侦查和勘测。而基于混合算法的多目标机器人路径规划算法也被提出，它将传统算法中单一的以路径最短为目标，扩展为3个目标：长度、安全性、平滑性。这种算法在寻求最优路径时是比较有效的。计算机仿真结果表明，虽然文中提出的智能算法还存在着一些有待提高的问题，但是它解决了一些传统算法的缺点，在实际情况下也是比较可行的，使得机器人路径的获得更加具有灵活性。

[1] C Alexopoulos, P M Griffin. Path planning for a mobile robot IEEE trans on system [J]. Man and Cybernetics,1992,22(2):318-322.

[2] Y Keron, J Borenstein. Potential field methods and their inherent limitation for mobile robot navigation [C]//Proceedings of the Internation Conference on Robotics and Automation. California: [s.n.],1991:1398-1404.

[3] 白文峰,刘纪阳,雷宇欣.微分进化优化神经网络KUKA机器人逆运动学求解[J].长春工业大学学报：2017,38(2):162-166.

[4] Jae Byung Park. Multiple mobile robot path planning for rollover prevention and collision avoidance [C]//2011 11thInternational Conference on Control,Automation and Systems. Korea: [s.n.],2011:1732-1734.

[5] S Geetha, G Muthu Chitra, V Jayalakshmi. Multi objective mobile robot path planning based on hybrid Algorithm [J]. [S.l.]: Anna University of Technology,2011:251-255.

[6] J B Park, J H Lee, B H Lee. Rollover-free navigation for a mobile agent in an unstructured environment [J]. IEEE Trans on SMC-Part B Cybernetics,2006，36(4)：835-848.

[7] Zheng Jinhua. Multi-objective evolutionary algorithm and its application[M]. [S.l.]: Science Press,2007.

[8] 魏厚忠，薛丹，焦立奇，等.基于KUKA6自由度机器人的误差分析与仿真[J].长春工业大学学报：自然科学版，2012,33(3):328-332.

[9] 申晓宁，郭毓，陈庆伟，等.基于多目标优化的挠性航天器姿态机动路径规划[J].南京理工大学学报，2006,30(6)：659-663.

[10] 潘攀.足球机器人路径规划算法的研究及其仿真[J].计算机仿真，2012,29(4)：181-184.

[11] M A Nada, AL-Salami. System evolving using ant colony optimization Algorithm[J]. Journal of Computer Science，2009,5(5):380-387.

Studyonobstacleavoidanceandrolloverofasoccerrobot

XUE Dan1,2, SUN Xiqing1, BAI Wenfeng1*

(1.School of Electrical & Electronic Engineering, Changchun University of Technology, Changchun 130012， China；2.College of Optical and Electronical Information Changchun University of Science and Technology, Changchun 130114， China)

With the extended map, the improved genetic algorithm and combined ant colony with genetic algorithm are used to optimize the following objects of a soccer robot such as path length, smoothness and safety.

robot； path planning； extended map； genetic algorithm； genetic algorithm and ant colony algorithm.

2017-01-25

薛 丹(1986-)，女，汉族，吉林长春人，长春工业大学硕士研究生，主要从事智能控制及轨道交通信号与控制方向研究,E-mail:273518365@qq.com. *通讯作者：白文峰(1962-)，男，汉族，吉林长春人，长春工业大学教授，硕士，主要从事智能仪器与智能控制方向研究,E-mail:baiwenfeng@ccut.edu.cn.

10.15923/j.cnki.cn22-1382/t.2017.5.12

TP 242.6

A

1674-1374(2017)05-0472-05