摘 要： 移动机器人路径规划问题一直是机器人学研究的核心内容之一，而遗传算法作为智能仿生学算法在路径规划中得到了广泛的应用。针对传统遗传算法存在局部搜索能力差的问题，文中研究在已知环境下运用一种基于遗传算法和模拟退火算法相结合的技术对移动机器人进行最优路径的规划方法。算法采用栅格法对环境建立模型，同时在遗传算子中添加插入算子和删除算子以优化路径。Matlab仿真实验结果表明，该算法相对于基本遗传算法的收敛速度，搜索质量等有了明显的提高。
关键词： 移动机器人; 遗传算法; 模拟退火算法; 栅格法; 路径规划; Matlab
中图分类号： TN830.1⁃34; TP242 文献标识码： A 文章编号： 1004⁃373X（2019）02⁃0183⁃04
Mobile robot path planning based on a hybrid genetic algorithm
PEI Yijian， YANG Liangliang， YANG Chaojie
（School of Information， Yunnan University， Kunming 650500， China）
Abstract： The path planning problem of the mobile robot is always one of the core contents of robotics research， and the genetic algorithm， as an intelligent bionics algorithm， has been widely used in path planning. In allusion to the poor local search capability problem of the traditional genetic algorithm， the mobile robot optimal path planning method is researched in this paper by using the genetic algorithm and simulated annealing algorithm combined technology in a known environment. In the algorithm， the grid method is used to construct the environmental model. The insert operator and delete operator are added in genetic operators to optimize the path. The experimental results of the Matlab simulation show that in comparison with the basic genetic algorithm， the algorithm has an obvious improvement in convergence speed and search quality.
Keywords： mobile robot; genetic algorithm; simulated annealing algorithm; grid method; path planning; Matlab
0 引 言
移動机器人是一种集环境感知、动态决策与规划、行为控制与执行等多项功能于一体的高智能化机器系统[1]。2013年美国提出制造业回归，规划机工业机器人作为先进产业，机器人革命成为第三次工业革命的切入点和重要增长点。在实际生活中，移动机器人在面对各种复杂的障碍物环境，主要依靠机器人对环境的感知，自行设计一条最优或者次优的路线达到指定的目的点[2]。路径规划主要解决移动机器人的两个主要问题：选择合理的途径是机器人能够达到指定位置;优化机器人到达指定位置所用的时间、精确度、路径是否最短等条件。机器人路径规划图如图1所示。
由图1可知，机器人的路径规划主要是对现实问题建立一种抽象化模型，根据符合条件的路径搜索算法寻求一种合适的路径。目前应用广泛的路径算法有人工势场法[3]、栅格法[4]、神经网络算法[5]等。凭借各自的优势在路径规划中经常使用，但是这些算法也存在着局部极小值、计算量大等缺点。遗传算法作为路径规划方面研究的热点，遗传算法策略的设计从微观上主要讨论群体的规模、参数的设计以及遗传算子的方法对求解能力的影响，宏观上主要以遗传算法为基础，加入其他算法形成混合遗传算法以提高遗传算法的寻优能力。基本遗传算法虽然具有良好的寻优能力，但由于早熟现象以及收敛速度慢等影响着性能。为解决遗传算法的缺陷，本文采用栅格法建立模拟环境模型，增加插入算子和删除算子，把具有很强的局部搜索能力的模拟退火算法引入遗传算法中以改善机器人的搜索能力。
1 环境模型的建立
本文的机器人使用的环境模型采用文献[6]提出的网格理论，如何确定网格的大小是主要问题，较小的网格对障碍物的描述更精确，但会影响计算机存储空间，导致算法变得复杂，因此需要综合考虑网格的大小[7]。在考虑机器人的工作环境模型时，通常做一些假设：
1） 在工作空间中移动不应考虑机器人的大小，在二维空间中移动。
2） 所构建的地图网格大小一样，用数字“1”标记障碍物网格，可用数字“0”标记机器人的路径可行区域。
3） 机器人在运动过程中，障碍物的大小和位置不会改变。
如图2所示，描述网格相对位置方面优势的直角坐标法能够计算分析路径长度和路径的可行性。另外，序列法占用的内存空间相对较少，常用在遗传操作。本文将这两种方法相结合，当然在算法过程中这两种方法需要运用换算公式进行转换。
[xi=Ni%nyi=Ni/n， i=1，2，…，n] （1）
式中：（[xi]，[yi]）表示路径点坐标;[Ni]表示网格序列;n表示坐标长度。
2 遗传模拟退火算法设计
2.1 路径编码方式
遗传算法中，影响计算时间的原因有编码长度和搜索空间，编码长度过长及空间太大会增加計算时间，常用的编码方法有二进制编码、浮点数编码或符号编码等。考虑到遗传算法在编码、交叉和变异时容易操作，本文路径个体的产生采用序号编码方式，考虑到障碍物在栅格中的序号问题，所以在规划路径时应当排除和障碍物一样的序号。如图3所示，序号编码能使个体长度变短，机器人在到达目标点时得到的长度有所不同，所以会产生可变长度的个体。
2.2 初始种群生成
全局最优解的收敛受初始种群规模的影响，规模太大会使进化时间变长，规模太小会导致在搜索路径中提前结束。遗传算法中常采用简单的随机生成种群的方法，但是过多的不可行路径增加了计算时间，降低了搜索速度。本文在进行种群初始化时，所产生的路径点和障碍物的序列号不相同，排除了路径点不可行状态，这样移动机器人到达目的地时可生成一条无障碍路径。
2.3 适应度函数
适应度函数是用来度量群体中各个个体在优化计算中接近最优解的优良程度[8]。假设障碍物大小是经过碰撞处理的，也就是说存在一个安全距离使得机器人在临界状态不发生碰撞，将机器人看作一个质点，那么最优路径应满足两个条件：最优路径应没有碰撞障碍;路径长度应为最短。
假设Si，Si+1为路径中的两点，Oj表示一个障碍物，则适应度函数满足：
[fit1=1，SiSi+1⋂Oj=∅，i=1，2，…，m;j=1，2，…，n0，others] （2）
式中：m为路径上的点;n为障碍物的个数。如果不发生碰撞则其适应度为1，反之为0。
要求机器人的行走路径是最短的，可用如下关系式表示：
[fit2=i=1n-1Pi1+1num-1] （3）
式中：[Pi]表示路径中第i段直线段的长度;num表示初始种群的数量。
最后得到的适应度函数为：
[fit=fit1×fit2] （4）
2.4 模拟退火算法
模拟退火算法在基于梯度的优化方法难以解决的复杂优化问题上能够显示出优良的特性，可以抑制遗传算法的早熟现象，能够跳出局部最优解[9]。模拟退火算法在和遗传算法结合时，主要解决以下问题：
1） 合理的选择初始温度T0和较好的温度更新函数;
2） 如何防止遗传算法的早熟现象。
2.4.1 温度更新函数
为了确保算法从起始就有很强的遍历性，初始温度T0的选取足够高以保证避免陷入局部最优解。温度更新函数用于修改外循环中的温度T的值，本文采用的更新函数为：
[T（t）=T01+αt] （5）
式中：[T0]为初始温度;[α]为常数。随着遗传代数的增加，遗传前期物种的生存压力较小，弱势个体可以生存;遗传后期物种生存压力大，降温速度较小，便于选择最优个体。
2.4.2 个体接收准则
新个体产生后，需要判断哪些优良个体是否加入种群中生存。如果父代个体i生成子代新个体i′，需要构造目标函数以保证变异生成过的个体具有优良的特性被接收。
[SA_R（i）=j=0n-1（xj+1-xj）2+（yj+1-yj）2] （6）
[P（i⇒i′）=exp-SA_R（i′）-SA_R（i）t，SA_R（i′）>SA_R（i）1，SA_R（i′）≤SA_R（i）] （7）
式中：SA_R（i）表示路径长度;[P（i⇒i′）]为新子代个体被遗传的概率;t为温度参数。
2.5 遗传算子
2.5.1 选择算子
依照“优胜劣汰”的原则，从当前群体中选择一些优良的个体遗传到下一代群体，通常采用轮盘赌法[10]，根据个体的适应度值，依据概率函数选择个体是否进入下一代，适应度值越小，被选择的概率就越高。通过选择可以使优秀个体增加。设种群的大小为n，则个体被选中的概率为：
[Pi=1fit（i）i=1n1fit（i）] （8）
2.5.2 交叉算子
交叉操作直接影响算法的收敛性，交叉是通过对父代个体信息间的交换增加种群个体的多样性。采用单点交叉的方式，若存在相同的交叉点，则一定的概率交换其中的部分基因，交叉的原则如图4a）所示;经交换后的形成新的个体如图4b）所示。交叉过的新个体为了保证优良性，满足以下条件可遗传到下一代：
1） 若SA_R（i′）<SA_R（i），产生的新个体的路径长度小部分遗传到下一代种群;
2） 若SA_R（i′）>SA_R（i），根据产生的随机数random<[P（i⇒i′）]，以一定的概率遗传到下一代种群;否则保留上一代个体，这样可以保证优良个体遗传的几率增大。
2.5.3 变异算子
为了增加种群多样性，以概率Pm对个体在非首尾端进行变异操作，经过变异后的个体为非障碍物区域的路径点，以保证路径的可行性，防止得到局部最优解。
2.5.4 插入算子和删除算子
为了保证路径的可行性，需要对栅格进行插入操作，插入的遵循原则为：保证路径完整性;栅格不能是障碍物点;插入的栅格点是否为最短。若满足：
[max（abs（xi-xi+1），abs（yi-yi+1））≈1] （9）
即路径的索引点不连续时执行插入操作。插入的方式为：
[（x′，y′）=（xi，yi）+（xi+1，yi+1）2， i=0，1，2…，n-1] （10）
在執行插入的过程中，个体会产生不必要的相同栅格序号，影响机器人的搜索路径;所以要进行删除算子操作，将其中一个的相同栅格点去掉，这样能够保证得到一条较优的无障碍路径。
2.6 算法描述
Step1：初始化。T←T0，GA（进化代数Count，个体数N，交叉和遗传概率Pc，Pm）。
Step2：T>Tfinal，执行以下各步，否则返回最优解。
Step3：若i（循环次数）>Count，执行以下各步，否则，T←Ti+1，T>Ti+1，返回Step2。
Step4：评价p（i）中各条路径适应值：fp1，fp2，…，fpn←fitness[p（i）]。
Step5：从种群中选择n对个体作为父代，对每一对父代做以下操作：对父代使用交叉、突变算子进化子代;根据模拟退火原理进行选择优良个体;对产生的个体进行插入、删除优化得到新的个体。
Step6：返回Step3。
3 仿真结果分析
为了验证本文路径方法的有效性，根据第1节理论建立的环境模型（见图2），机器人的起点序号为0，目标点序号为99。在Matlab仿真中，算法的相关参数如下：初始温度T0为97，种群规模N为100，进化迭代次数为100，变交叉概率Pc为0.75，变异概率Pm为0.01，选定参数后，对标准遗传算法和新算法进行仿真实验。
仿真实验结果如图5所示，标准遗传算法的路径长度为13.899 5，改进后的路径长度为13.311 7。对比图6中的适应度函数曲线可知，标准遗传算法在75代时陷入了局部最优解，并没有达到预期的效果，而改进后的算法在62代时候趋于稳定状态，说明了遗传算法在和模拟退火算法混合后能够克服收敛速度较慢，易陷入局部最优解的缺点，改进后的算法对移动机器人的静态最优路径优于标准遗传算法。
4 结 语
本文提出的基于遗传算法的移动机器人路径规划的混合算法，采用序号编码降低算法的复杂性，引入模拟退火算法的准则，能够有效避免遗传算法收敛较慢，寻优能力差的缺点。仿真实验表明，应用改进的算法对移动机器人的路径规划是有效可行的，通过它们之间的优势互补达到预期的收敛速度和规划效果。
注：本文通讯作者为杨亮亮。
参考文献
[1] ZHOU X， WAN X， GUO X， et al. Research on path planning and obstacle avoidance for tunnel mobile robot based on visual navigation [C]// Proceedings of the 4th International Conference on Mechanical Materials and Manufacturing Engineering. Wuhan： Atlantis Press， 2016： 3⁃6.
[2] SCHWARTZ J T， SHARIR M. A survey of motion planning and related geometric algorithms [J]. Artificial intelligence， 1988， 37（1）： 157⁃169.
[3] MONTIEL O， OROZCO⁃ROSAS U， SEPÚLVEDA R. Path planning for mobile robots using bacterial potential field for avoiding static and dynamic obstacles [J]. Expert systems with applications， 2015， 42（12）： 5177⁃5191.
[4] 李天成，孙树栋，高扬，等.基于扇形栅格地图的移动机器人全局路径规划[J].机器人，2010，32（4）：547⁃552.
LI Tiancheng， SUN Shudong， GAO Yang， et al. Fan⁃shaped grid based global path planning for mobile robot [J]. Robot， 2010， 32（4）： 547⁃552.
[5] 朱大奇，孙兵，李利.基于生物启发模型的AUV三维自主路径规划与安全避障算法[J].控制与决策，2015，30（5）：798⁃806.
ZHU Daqi， SUN Bing， LI Li. Algorithm for AUV′s 3D path planning and safe obstacle avoidance based on biological inspired model [J]. Control and decision， 2015， 30（5）： 798⁃806.
[6] HOWDEN W E. The sofa problem [J]. The computer journal， 1968， 11（3）： 299⁃301.
[7] LI G， SHI X. A novel immune⁃genetic based algorithm for mobile robot′s path planning [C]// Proceedings of International Conference on Computer Application and System Modeling. Taiyuan： IEEE， 2010： 131⁃134.
[8] 葛继科，邱玉辉，吴春明，等.遗传算法研究综述[J].计算机应用研究，2008，25（10）：2911⁃2916.
GE Jike， QIU Yuhui， WU Chunming， et al. Summary of genetic algorithms research [J]. Application research of computers， 2008， 25（10）： 2911⁃2916.
[9] PENG Y， WEI W. A new trajectory planning method of redundant manipulator based on adaptive simulated annealing genetic algorithm [C]// Proceedings of International Conference on Computational Intelligence and Security. Guangzhou： IEEE， 2007： 262⁃265.
[10] LIAO W， ZHOU X. Soccer robot path planning based on genetic algorithms in dynamic environment [J]. Journal of Jimei University （Natural science）， 2012（1）： 64?68.
推荐访问： 遗传 机器人 算法 路径 混合