基于一种混合遗传算法的移动机器人路径规划

裴以建 杨亮亮 杨超杰

摘  要： 移动机器人路径规划问题一直是机器人学研究的核心内容之一，而遗传算法作为智能仿生学算法在路径规划中得到了广泛的应用。针对传统遗传算法存在局部搜索能力差的问题，文中研究在已知环境下运用一种基于遗传算法和模拟退火算法相结合的技术对移动机器人进行最优路径的规划方法。算法采用栅格法对环境建立模型，同时在遗传算子中添加插入算子和删除算子以优化路径。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）