基于改进遗传算法的移动机器人路径规划
2019-04-28宋宇王志明
宋宇 王志明
摘要：将遗传算法用于路径规划时，传统算法虽然简单，但不适用转弯情况较多的复杂地图。针对这一问题，首先将RRT算法用于栅格环境下产生初始路径，其次提出一种新的插入算子，最后进行路径优化。根据不同地图与其他文献中的改进遗传算法，进行对比研究与分析，制定路径长度与算法用时2个指标来评判算法的优劣。仿真结果表明，改进算法得到的路径长度缩短了70%，路径长度达到最优的用时减少了8%。
关键词：移动机器人;遗传算法;路径规划;算法评判;插入算子;路径优化
中图分类号：TN820.4-34;TP301.6
文献标识码：A
文章编号：1004-373X（2019）24-0172-04
遗传算法是一种模拟自然界选择进化的全局优化算法，利用遗传算法求解最优问题是通过选择交叉变异算子不断迭代来实现的。采用遗传算法路径规划的文献并不少见[1-5]。文献[1]提出了人工势场法与遗传算法相结合的方法，使得算法得到的路径平滑度较高;文献[2]采用了Dijstar算法初始化种群，用遗传算法得到了安全度较高的路径;文献[5]提出了根据种群的适应度方差自适应选择的选择策略;文献[6]在遗传算法得到的路径上重新排列基因优化了路径长度与路径平滑度;文献[7]采用了在当前点附近产生个体的方法，以距离为适应度函数，用遗传算法进行了路径规划。
1 基于改进遗传算法的路径规划
在传统遗传算法栅格路径规划的基础上提出了新的初始化方式、变异方式以及插入方式，改善了全局寻优效果。
1.1 栅格模型
首先将给定地图栅格化，将障碍物所占的栅格用黑色栅格表示，自由空间用白色栅格表示，图1中黑色曲线表示一条典型的栅格环境路径，该路径是由从起点到终点的一系列路径点组成的路径规划算法的任务，即寻找从起点到终点的一系列连续路径点，使得连接路径点的路径长度或安全度最优。路径点的位置可以用直角坐标或栅格序号表示，给定栅格中心点的栅格序号P（i，j）与直角坐标[X（i，j ），Y（i，j）]的转换关系如下：
X（i，j）= mod （P（i，j），10）- 0.5
Y（i，j）= floor （P（i，J），10）+ 0.5
（1）
P（i，j）=X（i，j）+0.5+10（1，（i，j）一0.5）
图1中的路径点组成的路径点集合为{1，12，23，24，25，26，36，46，56，67，68，69，80，90，1001，移动机器人的起点序号为1，终点序号为100。遗传算法中的个体用路径序号组成的向量表示，1个个体代表一条无碰撞路径。
1.2 遗传算法初始化
传统遗传算法用于栅格路径规划时，在初始化中采用较多的是中点插值法，即随机产生一定数量的路径点，在每两个路径点之间采用中点插值的方式进行路径插补。文中将RRT算法用于遗传算法种群的初始化，给定起点与终点，从起点开始产生随机树并不断生长，直到此随机树到达终点。
文中算法产生一条路径的具体步骤如下：
1）将起点坐标（如图1中的[1，1]）加入随机树中;
2）在地图范围内以50%的概率产生1个随机点作为目标点，其余50%的概率以终点为目标点，计算得到距离此目标点最近的树节点P（x，y）;
3）在P（x，y）所在栅格的邻居栅格中选出所有非障碍物栅格，若P（x，y）的所有邻居栅格都在障碍物中，则跳到步骤2）;
4）在步骤3）产生的满足条件的邻居栅格中，选择距离步骤2）产生的随机点最近的栅格中心点，若此点已经在树中，跳到步骤2），若此点不在树中，将此点作为树节点，即将此距离最近的点加入树中。
5）檢查步骤4）新加入树中的点的所有邻居栅格，若终点在这些邻居栅格内，算法结束。若终点不在栅格内，跳到步骤2）。
按照上述算法产生种群数量的路径，初始化结束。
1.3 适应度函数
文中适应度函数选择为路径长度。
1.4 选择算子
文中采用文献[5]提出的自适应选择算法，个体被选择的概率为：
P=α （1- a）i-l（2）式中：i为按个体距离长度排序后的个体序号值;α为：
产生个体概率后，使用随机遍及取样（SUS）算法选择个体。
1.5 交叉算子
文中采用单点交叉算法，即在种群内随机选择2个待交叉个体，找到这两个个体的除起点与终点外的公共点，随机选择公共点中的一个点，交换这两个个体选择到的点的后半部分路径点产生两个新的个体。个体交叉示意图如图2所示，图中前两个地图中的个体在序号为56的点处交叉，产生后两个个体。
1.6 变异算子
文中提出的变异算子步骤如下：
1）在种群中随机选择一个个体，在此个体中随机选择除起点与终点外的一个路径点[X，Y]，此路径点将个体分为前半段路径与后半段路径;
2）以50%的概率选择坐标X进行变异，其余50%的概率选择坐标Y进行变异，即在点[x，y]的同行或同列中选择一个非障碍物栅格作为变异后的点;
3）在前半段路径中随机选择一个路径点[X1，Y1]，在后半段路径中随机选择一个路径点[X2，Y2]，使用插入算子连接[X1，Y1]与[X，Y]，[X，Y]与[X2，Y2】，若两段路径都连接成功，将原个体中的起点到点[X1，Y1]的路径与[X1，Y1]与[x，y]的路径和[X，Y]与[X2，Y2]与原个体中的点[X2，Y2]到终点的路径拼接产生变异后的新个体，若两段路径有1段连接失败，则令新个体与原个体相同。
1.7 插入算予
对于给定的两个点，称为start点与goal点，令start点为当前点，创建一个邻居列表（此时为空数组），创建一个与地图同型的考察标志矩阵（此时只有start点处的值为1，其余为0），创建一个路径点列表（此时为空）。
1）检查当前点的8个邻居栅格，将不在障碍物中且未考察过的点加入邻居列表，同时令这些点的考察标志为1。
2）如果邻居列表为空，则插入失败，算法结束，否则继续执行步骤3）。
3）如果goal点在邻居列表中，插入成功，算法结束;如果goal点不在邻居列表中，从邻居列表中选择距离goal点最近的点P，将点P从邻居列表删除。
4）若点P与当前点是相邻栅格，则令点P为当前点，同时将点P加入路径点列表，跳到步骤1）;若点P与当前点不是相邻栅格，连接失败，算法结束。
1.8 删除算子
删除算子是将个体中相同路径点之间的路径点与这两个相同路径点中的一个删除，去除了冗余路径点。
1.9 优化算子
优化算子是检查个体中连接第i个路径点（path（i））的前一个路径点（path（i-l））与后一个路径点（path（i+l））的直线是否经过障碍物栅格，若不经过，则将此指定点从个体中删除。优化算子的伪代码如下：
flag=1;
while flag==l
for i=2： size（ path， 2）-1
if deletable（i，path）
delete path（i）from path
flag=1;
break
end
flag=0;
end
end
其中deletable（i，path）指的是判断第i个路径点是否可删除。
1.10 改进遗传算法栅格法路径规划流程
1）路径初始化，产生给定数量的个体;
2）使用选择算子产生下一代个体;
3）从种群中随机选择2个个体，使用交叉算子进行交叉;
4）从种群中随机选择一个个体，使用变异算子进行变异;
5）对种群中所有个体分别调用删除算子，优化算子，若未达到指定迭代次数，跳到步骤2），否则，算法结束。
2 仿真
在Matlab 2014a，13 -4000M的CPU环境下进行仿真。仿真部分比较了文中算法与文献[3]算法在3个地图环境下得到的路径长度与路径达到最优所用时间（算法效率），如图3、表1所示。
起点为左下角栅格，终点为右上角栅格，种群大小为5，迭代次数500。在地图3中，由于文献[3]算法初始化方法只选择固定几个方向进行移动，故对转弯过多的环境不适用，从地图3可以看出文中算法在复杂环境下的可行性。
3 结语
根据本文提出的初始化方式，变异及插入与优化算子，在Matlab中与文献[3]中的改进遗传算法对比，仿真结果表明本文提出的算法在不同环境下得到的路径可行、有效。
注：本文通讯作者为王志明。
参考文献
[1]乔莎莎，吴勇，张建东，等，基于遗传算法和人T势场法的路径规划[J]现代电子技术，2012，35（12）：75-78.
QIAO Shasha. WU Yong， ZHANG Jiandong， et aI.Path plan-ning based on genetic algorithm and artificial potential fieldmethod[J]. Modern electronics technique， 2012， 35（ 12）： 75-78.
[2]卢月品，赵阳，孟跃强，等.基于改进遗传算法的狭窄空间路径规划[J]计算机应用研究，2015，32（2）：413-418.
LU Yuepin. ZHAO Yang， MENG Yueqiang， et al.Path plan-ning in narrow space by improved genetic algorithm [J]. Appli-cation research of computers， 2015， 32（2）：413-418.
[3]田欣，刘广瑞，周文博，等.基于改进白适应遗传算法的机器人路径规划研究[J]机床与液压，2016，44（ 17）：24-28.
TIAN Xin. LIU Guangrui， ZHOU Wenbo. et al.Research ofrobot path planning based on improved adaptive genetic algo-rithm [J]. Machine tool and hydraulics， 2016. 44（17） ： 24-28.
[4]杨献峰，付俊辉 .移动机器人路径规划的仿真研究[J]. 计算机仿真， 2012.29（ 7） ：223-226.
YANG Xianfeng， FU Junhui. Mobile robot path planning basedon grid algorithm and CGA [J]. Computer simulation. 2012， 29（7） ： 223-226.
[5] KARAMI A H. HASANZADEH M. An adaptive genetic algo-rithm for robot motion planning in 2D complex environments[J]. Computers & electrical engineering， 2015. 43 ： 317-329.
[6] 11 M F， WANG C J， CHEN Z Q， et al. Pathplanning of mo-hile rohot based on genetic algorithm and gene rearrangement[C]// Chinese Automation Congress. Jinan： IEEE， 2017： 6999- 7004.
[7] ARORA T， GIGRAS Y， ARORA V. Robotic path planning us-ing genetic algorithm in dynamic environment [J]. Internationaljournal of computer applications ， 2014. 89（ 11 ） ： 8-12.
[8] FU B. CHEN L， ZHOU Y T， et al. An improved A' algorithmfor the industrial robot path planning with high success rateand shortlength [J]. Robotics & autonomous systems. 2018，106： 26-37.
[9] PATLE B K. PARHI D R K. JAGADEESH A. et al. Matrix-Binary codes based Genetic Algorithm for path planning of mo-bile robot [J]. Computers & electrical engineering， 2017. 45 ： 1-
[10] ISLAM F， NASIR J. MALIK U. et al. RRT#-Smart： Rapidconvergence implementation of RRT* towards optimal solution[C]// International Conference on Mechatronics and Automa-tion. Chengdu ： IEEE . 2012 ： 1651-1656.
作者简介：宋宇（1969-），男，黑龙江呼兰人，教授，主要研究领域为嵌入式系统设计與研究。
王志明（1991-），男，山西神池人，硕士研究生，主要研究领域为路径规划。
