基于改进遗传算法的机器人路径规划

徐梦颖,王娇娇,刘宝,马良,柴林杰,向丽,周杰

(石河子大学信息科学与技术学院,新疆 石河子832003)

提高路径规划效率逐渐成为移动机器人领域中的研究热点,其任务在于已知起点和终点,探寻出一条无碰撞的最优路径[1-3]。遗传算法是现今应用最为广泛的最优解处理算法[4-6],传统算法容易陷入局部最优解,通过改进传统遗传算法提升机器人路径规划效率[8-9]。解决路径规划的问题,首先要对环境进行建模[10-13],栅格法是研究人员解决机器人路径规划问题并建立环境模型使用的主要方法[14-15]。目前,一些学者提出了许多智能算法,ZHANG J H[16]使用粒子群算法(Particle Swarm Optimization,PSO)提高运动效率,该算法能够有效优化路径长度、路径的平滑度和安全程度,然而算法容易出现早熟收敛的问题;巩敦卫等[17]提出了一种模拟退火算法(Simulated Annealing,SA)能有效避免节点布置中一些路径暴露问题;混合遗传算法容易陷入进化停滞,导致得到的解集质量较低。

为了解决寻找最短路径时存在解的质量较低的问题,本文提出一种免疫克隆自适应遗传算法(Immune Clone Adaptive Genetic Algorithm,ICAGA),通过建立栅格模型对栅格进行编码,再进行选择、交叉、变异,计算出最短路径,并使用Matlab对其进行仿真实验验证,并与SA、PSO进行比较。

1 基于ICAGA的最优路径规划

1.1 路径规划模型

路径规划是指如何让移动机器人依照特定指标完成从起始点到终点而且能够避开途中障碍物的一种技术。栅格法是解决路径规划问题的重要方法[18],机器人所处的栅格有可行动栅格和障碍栅格2种。

图1表示二维空间的栅格模型,模型中的圆形为障碍栅格,该模型中共有5个障碍。图形左下角第1个栅格为1号栅格,按照从下到上、从左往右的顺序依次根据标号对栅格进行命名。二维空间左下角的序号是1,二维空间右上角的序号是100。机器人从第1个栅格出发,随机得到一条可行的不可重复的连续路径,最后到达第100号栅格。机器人的所有运动轨迹全部存储在一个数组中,障碍物的位置也记录下来,通过计算染色体的总长并对其进行比较,最后将最优个体求解出来。

图1 栅格模型

当移动机器人到达第h号格子时,此时机器人可选择的下一步可行格子的序号分别为h+1、h-1、h+10、h-10。若移动机器人运动到整个栅格平面的边缘,则只有邻近的3个栅格可以选择,当机器人运动到栅格平面的顶点处,则只有2个栅格可以选择。同时所经过的栅格不得重复。

栅格分为自由栅格和障碍栅格,在式(1)中,栅格分别用0、1来表示,二进制环境矩阵E表示栅格环境的全部信息,其中0代表自由栅格,1代表障碍栅格。

式(2)中S为一条可行路径,其中{s1,s2,……}分别对应路径上的栅格序号。

针对路径规划问题,本文设计了适应度函数求路径长度。适应度函数f通过计算染色体的长度表示:

用栅格法建立模型应遵从以下规则:不用考虑机器人以及障碍物的高度影响,把机器人当成为一个质点放在二维空间来运行;机器人在栅格中做匀速直线运动,且机器人每次都处于每个栅格的正中心,它与其他栅格中心连线不经过障碍物即认为两者之间可以直线到达,第1号栅格与最后一个栅格不可设置障碍。

1.2 路径规划算法

遗传算法(Genetic Algorithm,GA)[19]自20世纪提出后不断用于解决一些实际问题,也取得了很多成果,但是该算法存在一些缺陷,主要是容易陷入局部最优,不利于优化机器人运动路径长度。本文研究在传统GA算法的基础上加入免疫克隆算子和自适应算子,组成一种新的算法ICAGA,通过免疫克隆算子和自适应算子可加快算法的收敛速度,从而找到优质路径。ICAGA可以通过以下步骤优化机器人运动路径。

1.2.1 个体编码

在ICAGA中,编码策略需要路径规划问题而定。二进制字符串较长会影响算法的运行时间,在ICAGA中采用十进制编码方法。在进行算法处理时,必须将机器人经过的路径节点逐一取出放入数组中,从而形成一条完整的路径。图1中个体S表示为{1,2,3,13,12,22,23,24,25,35,36,46,45,55,56,57,58,68,67,77,87,97,98,99,100},在这些运动节点上,关于该运动路径以及算法的实现步骤,均在这些路径节点上进行。

1.2.2 初始化种群

在ICAGA中,由于每条路径的长度是不确定的,所以染色体长度也是不等的,每个染色体的起点和终点相同。具体操作是:先定义种群的数量,将起始点和终点定义成个体的第一位基因与最后一位基因,从起点开始,随机选择上、下、左、右4个方向的可行栅格,由这些栅格组成的线段形成一条可行路径,机器人在寻找下一可行栅格时不可重复选择,不可碰壁,否则该个体被视为不可行路径被舍弃。

1.2.3 选择

在种群中选择机器人运动长度较短个体,舍弃运动长度较长个体,通过计算适应度获得每条路径被遗传到下一代的概率。选择是为了提升较短路径遗传到下一代的概率。

轮盘赌算法是选择操作的主要方法之一,该方法主要用于选择较短路径。每一个可行路径是轮盘上大小不一的扇形区域,区域的面积通过计算每一个个体的路径长度与种群总长度的比值可得。根据适应度可以确定该染色体被选择并遗传到后代的概率。在选择时,按照每一次轮盘指针旋转之后所指向的位置随机选择相应个体。

式(4)中,n为可行路径的个数,f(i)是一个可行路径的路径长度;式(5)、(6)、(7)中,pi为第i个可行路径长度占总长度的概率大小,Pi为第i-1个个体到第i个个体的概率累加和,rand为0～1之间的随机数。

在路径规划中,适应度越小则路径越短,被选择的概率越大。由式(3)可知,路径长度越长,该个体被选择的概率就越大;通过式(4)转换可知,f(i)越大,F(i)越小,通过该转换方法选择最短路径。轮盘赌算法的主要过程如下:

(1) 计算每一个可行路径的长度,将f(i)转换为F(i),计算所有F(i)的总和;

(2) 计算F(i)与所有F(i)总和的比值,得到每一个可行路径在轮盘中能够被挑选出来的概率;

(3) 在(0,1)区间上产生随机数rand。

(4) 通过式(7)与随机数作比较,如果随机数落在第i-1个盘子和第i个盘子之间,则i个个体被选中;

(5) 重复步骤(3)、(4),直到筛选的数目达到要求。

1.2.4 交叉

ICAGA算法采用单点交叉的方法,将母本在随机产生的位置断开,父本也在其对应的同一位置断开,将母本前一部分与父本后一部分组合,母本后一部分与父本前一部分组合,形成2个新的个体。根据机器人的路径规划特性,本文设计的机器人交叉过程具体为:2条路径中同一栅格后的所有栅格节点交换形成2条新的路径。

一个可行路径中若有n个栅格就有n-1个交叉点,可行路径中的交叉操作可以通过以下方法表示。如图2所示,S1、S2分别表示为2条可行路径,首先在S1、S2中随机产生一个共同交叉位置,即选择S1和S2中的相同路径节点进行交叉;其次,S1和S2在交叉点之前的路径节点不改变位置,交叉点之后的栅格互换位置,生成新的路径;最后判断这是否是一条可行路径,若不是一条可行的连续的路径,则丢弃该路径,父代个体依旧作为可行路径遗传到下一代。

图2 交叉

在传统遗传算法的遗传操作中,采用的是完全随机的方式,但是在机器人路径规划问题上,完全随机操作极有可能产生不可行路径。具体操作步骤如下:

(1)随机选择2个个体间的共同交叉点作为父代;

(2)交换2个个体交叉点后的栅格路径形成新的个体;

(3)计算新个体的适应度。

1.2.5 变异

变异是模拟生物界进化遗传过程中染色体的基因突变过程,使用变异算子可以使种群在迭代的过程中不断引入新基因,得到新的路径,从而增加路径规划的多样性。根据机器人的路径规划特性设计了路径变异方式,具体变异过程如图3所示。

图3 变异

首先在种群中随机选择一条机器人的运动路径,按照变异的概率在这条路径上随机选择一个变异栅格,例如要变异图1中第23号栅格,则需要在第22号栅格周围的12、21、23、32这4个位置中随机选择一个栅格作为变异栅格,使变异后的路径成为一条连续、可行且不重复的路径,若该路径不连续则丢弃该路径,将父代个体遗传到下一代;若可行则保留并计算适应度。变异的具体步骤如下:

(1)随机选取一条可行路径;

(2)根据变异概率随机选取该路径上的一个栅格作为变异栅格;

(3)将变异栅格变异为其周围的上、下、左、右中任意可行的不重复的自由栅格,并形成一个新的可行路径;

(4)计算该可行路径的适应度函数。

1.2.6 计算适应度

ICAGA中计算适应度可以确定机器人运动的轨迹长度,适应度f可通过式(3)计算可得。

1.2.7 免疫克隆算子

ICAGA中免疫克隆算子用于提高解的质量,加快ICAGA的收敛速度。将待优化的最短路径问题表示为抗原,路径优化中的一个可行路径可以表示为一个抗体。为了方便选择、交叉和变异,抗原和抗体编码均通过十进制编码的方式,在ICAGA中把一条可行路径对应一个抗体,将式(3)中的f当成评价机器人运动路径亲和度的指标数。ICAGA基本算法过程如下:

(1) 初始化。路径优化中的一个可行路径可以表示为一个抗体,有多少可行路径就有多少抗体。

(2) 评价和选择。将n个可行路径分解成2组,分别为记忆集抗体和剩余部分,把记忆集中的抗体看作较优路径。

(3) 克隆。在机器人运动路径较短的可行路径中选择k个路径克隆,解被克隆的数量与其路径长度成反比,机器人运动路径的长度长短将会决定个体被克隆的次数。

(4) 变异。针对克隆后的可行路径,需要继续对该路径变异,通过一个变异概率随机选取一条可行路径从而生成一个新的个体。

(5) 评价和选择。针对变异后的可行路径求解路径长度,若克隆和变异操作后的可行路径比原路径的长度还短,根据优胜劣汰原则,机器人运动较长的个体将被替换掉并生成新的记忆集。

1.2.8 自适应算子

GA中参数的设置是固定的,ICAGA中通过加入自适应算子根据适应度自动调节交叉概率和变异概率,可避免因参数设置不当导致算法陷入局部最优。本文通过研究机器人运动路径的长度设计自适应算子自动调整交叉概率Pa与变异概率Pb,调整公式为式(8)、式(9):

式(8)、式(9)中,f是将要变异的染色体的路径长度,f′是2个交叉路径中路径长度较短个体的路径长度,fmin是机器人所有可行路径中的最短路径,favg是种群中平均路径长度,q1、q2、q3、q4分别是0～1之间的常数。

1.2.9 终止条件的设定

终止条件有很多方式,如迭代次数、是否收敛等。在ICAGA中,当迭代次数达到最大遗传次数时停止迭代,并得到最优路径。

2 仿真实验

2.1 方法

仿真实验采用Windows10系统进行,CPU使用2.0 GHz的i7处理器,内存为16.0 GB,仿真软件使用Matlab R2014a的版本。根据建立的数学模型设置障碍物个数,在ICAGA、PSO、SA中,个体数量设置为50,最大迭代次数为100次,最大实验次数为50次。ICAGA的参数由多次仿真实验的经验可得,其中交叉概率为0.9,变异概率为0.05。障碍物的数量分别设为5、10、15、20。仿真实验中针对求解路径规划问题对ICAGA和PSO、SA这3种算法进行对比。

2.2 结果与分析

图4～7为经过50次实验且每次实验迭代100次后ICAGA、PSO、SA这3种算法在障碍物数量为5、10、15和20时的平均适应度对比图。

由图4可知:障碍物数量为5时,ICAGA的平均适应度值远低于PSO和SA;ICAGA、PSO、SA的路径长度分别为20.08、22.19、23.76,ICAGA优化后的平均路径长度比PSO、SA分别降低了9.51%、15.49%。这表明:机器人在一个静态环境中寻找最优路径时,ICAGA的收敛速度更快,寻找最优解的效率更高。

图4b～d显示:当障碍物个数为10时,ICAGA、PSO、SA优化后的机器人平均运动路径长度分别为22.38、24.17、26.64,ICAGA优化后的路径长度与PSO、SA相比分别降低了7.41%、15.99%;当障碍物个数为15时,3种算法优化过的机器人平均运动路径长度分别为24.43、26.71、27.69,ICAGA优化后的路径长度与PSO、SA相比分别降低了8.54%、11.77%;当障碍物个数为20时,3种算法优化过的机器人平均运动路径长度分别为26.34、28.02、29.61,ICAGA优化后的路径长度与PSO、SA相比分别降低了5.99%、11.04%。上述结果表明:适应度越小,机器人由起点到终点的距离越短,将ICAGA与PSO、SA相比,ICAGA算法收敛速度更快,能够有效地找到最优解,该算法在提高机器人的运动效率和寻找最短的路径时更有优势。

图4 障碍物数量为5(a)、10(b)、5(c)、20(d)时算法适应度的对比

ICAGA、PSO、SA在不同障碍物数量且实验次数分别为1、20、50次时运行时间的对比结果(表1)表明:随着实验次数与障碍物数量的增加,算法的计算难度加大,因此算法运行时间也在不断提高。

表1 算法运行时间对比

3 讨论

(1)针对机器人寻找最短路径的问题,本文设计了栅格模型,该模型按照顺序对栅格进行标记,并设计了计算运动路径长度的适应度函数,再在GA基础上提出了一种新的算法ICAGA。在机器人运动的静态环境中,随机设置障碍物的位置,随着障碍物数量不断增加,机器人运动路径变长,路径规划复杂度提升。在迭代过程中,ICAGA不断收敛,在迭代后期算法的收敛速度降低。在障碍物数量增加至20时,ICAGA算法优化过的路径长度为26.34,与PSO、SA相比分别降低了5.99%、11.04%。在障碍物数量为5、10、15、20且ICAGA分别实验1、20、50次时,随着障碍物数量的增加,算法运行时间增大;当不断提高实验次数时,算法的计算难度加大,因此机器人寻找最优路径时间不断提高。

(2)由于传统PSO与SA具有收敛速度慢、易陷入局部最优的缺点,所以在达到最大迭代次数后,当障碍物数量增加至20时,PSO、SA优化后的路径长度分别为28.02、29.61,都大于ICAGA优化后的机器人运动路径长度,而且与ICAGA相比,PSO与SA运行时间更长,机器人路径规划效率更低。

4 结论

(1)本文提出的ICAGA使用免疫克隆算子将种群中最优个体复制到下一代能提高种群的寻优能力,并通过加入自适应算子在迭代的过程中不断调整交叉概率与变异概率而提高种群的收敛速度,降低路径搜索的盲目性并缩短路径长度。

(2)与PSO、SA算法相比,ICAGA寻优能力更强,有效缩短了机器人的运动路径长度。

(3)ICAGA具有良好的静态避障性能,能有效降低机器人的运动路径长度,且收敛速度更快,能实现路径规划的高效寻优,为机器人的应用提供可靠依据。