多约束条件下基于改进遗传算法的移动机器人路径规划

胡章芳，程 亮，张 杰，王春瑞

(重庆邮电大学 光电工程学院，重庆 400065)

0 引 言

机器人路径规划一直以来都是研究的热点。移动机器人路径规划的一个难点是在有障碍物的环境中确定从起始点到目标点的全局最优路径，同时要避免碰撞。依据不同的角度，可以对路径规划方法进行不同的分类，本文将其分为传统算法和智能算法，前者主要包括图搜索法[1]、人工势场法[2]和栅格法[3]等，这些方法搜索效率低，得到的优化结果也不太理想，后者主要包括遗传算法[4]、蚁群算法[5]、免疫算法[6]和神经网络算法[7]等，这些算法虽然使机器人路径规划在性能方面得到提升，但是存在着运算时间较长、搜索空间较大、效率较低等问题。传统算法大部分解决的是单个约束条件下的问题(如路径最短)，在实际环境中往往需要考虑多个约束条件以寻找到一条最优或次优路径，而这些约束条件往往是相互协调、相互竞争的，不存在使多个约束条件同时达到最优解的情况。机器人路径规划本质上是一个具有多个性能指标的NP(non-deterministic polynomial)完全问题，很难找到精确的解决方案。因此，在多约束条件下优化机器人行走路径具有非常重要的实际意义[8]。

近年来，已有不少专家学者对此进行大量研究并提出多种路径优化方法和策略，文献[9]提出一种在离散环境下进行移动机器人路径规划的新方法，主要是基于电场势理论和电场对电荷的影响并在此基础上，借鉴前人关于非凸数据聚类的研究成果，构造了一种基于路径规划的优化算法，该算法虽然计算简单，但容易陷入局部最优。

文献[10]提出了一种改进的交叉算子，用于求解静态环境下的遗传算法路径规划问题，该交叉算子使用具有良好适应度的双亲来提高后代的质量，同时使用适应度值较低的双亲来探索研究空间，确保种群之间的多样性，但在交叉过程中增加了算法的搜索时间，从而延长了算法的运行时间。

文献[11]针对移动机器人提出一种快速最优路径规划算法。该算法采用粒子群技术将收敛度控制到全局最小，并采用自定义算法生成搜索空间的坐标，以确定给定的2个端点位置之间的最短路径。该算法虽然能都较快寻找到一条最短路径且改善了粒子群算法在种群规模较小时表现不佳的问题，但不适用于处理离散的优化问题且容易陷入局部最优。

文献[12]利用蚁群算法对复杂环境中的移动机器人进行路径规划，针对不同工位、不同大小、不同形状的障碍物，对算法参数进行了分析和调整。该算法虽然在一定程度上改善了复杂环境下蚁群算法的性能，但是需要不断重复性的实验确定参数以获得一条最优或次优路径，耗费时间长，且在简单环境下该算法的性能会有所降低。

针对在多约束条件下移动机器人在路径规划中搜索效率低、收敛速度慢的缺点，本文研究一种多约束条件下基于改进的遗传算法应用于机器人路径规划领域，在生成初始种群的过程中，引入SPS (surrounding point set)算法，并用Dijkstra算法测试该路径是否可行；然后增加删除算子、平滑算子优化生成的路径，加快算法的收敛速度，以降低在多约束条件下机器人路径规划所耗费的时间；最后引入小生境法来保持种群多样性，避免算法陷入局部最优。

1 问题描述

为了方便起见，本文做如下描述和定义。

首先，机器人工作在均匀分布栅格点的二维空间，空间中分布着Ob1,Ob2,…,Obn等数目有限的静态障碍物，起始点记为S，目标点记为T，如图1。

图1 机器人工作环境Fig.1 Robot working environment

接着，机器人的可用路径表示为

P={p1,p2,p3,…,pn},

p1=S,pn=T,pi∩Obj=∅,

1≤i≤n,1≤j≤n

(1)

(1)式中：pi表示路径P的第i个节点；n表示一条可用路径节点的数量。

通过多约束条件下基于改进遗传算法得到的移动机器人行走路径表示为

(2)

(2)式中，m表示通过本文算法得到的行走路径的数量，该路径需要满足

f(P*)=min{f1(P),f2(P),f3(P)}

(3)

(3)式中，f1(P),f2(P),f3(P)分别由定义1—定义3给出。

定义1长度指标是指路径的总长度，用f1(P)表示为

(4)

(4)式中，|pipi+1|是路径节点pi到路径节点pi+1的欧式距离。

定义2平滑度指标是指路径中所有相邻矢量线段的角度之和，用f2(P)表示为

(5)

定义3困难度指标是指机器人经过路径中每一个节点的困难指数之和，用f3(P)表示为

(6)

(5)式中：xi表示路径中第i个节点；d(xi)表示机器人通过该节点的困难指数。

最后，本文提出的机器人路径规划是在前面定义的3个目标对象上得到的一组帕累托最优路径。

2 基于多约束条件下改进的遗传算法

针对在多约束条件下移动机器人在路径规划中的搜索效率低、收敛速度慢的问题，本文设计的改进遗传算法流程图如图2。

图2 改进遗传算法流程图Fig.2 Flow chart of improved genetic algorithm

2.1 个体编码

遗传算法在给定问题上需要对初始种群的潜在个体进行遗传编码，不同的问题需要选择不同的编码方式，其中二进制编码方式在遗传算法中应用最广泛。

本文机器人工作于均匀分布的二维栅格点的空间中，空间中的每个点都有自己的坐标，恰好适用于二维编码：(x1,y1)→(x2,y2)→…→(xn,yn)，其中xi和yi是二维坐标中潜在路径节点的横坐标与纵坐标，且路径节点的数量和长度是可变的，这取决于空间中障碍物分布的复杂程度，在障碍物密集区域，路径节点的长度和数量都会增加，使路径更加顺畅和安全，在障碍物稀疏区域，路径节点的长度和数量会相应减少，这种编码方式可以增加搜索的精度和灵活性。图3是一个路径编码示例。

图3 可行路径的染色体表示Fig.3 Chromosome representations of feasible path

2.2 产生初始种群

传统遗传算法[13]采用的群体初始化方法是随机的。许多研究都是通过在自由空间中随机散布点或在网格地图中考虑所有点来生成点。这些方法存在这样的问题，即在路径生成阶段必须考虑对于最优路径而言不必要的点，这导致很高的计算成本，并且还可能无法生成最优路径，因为这些生成的点在狭窄或很小的空间内是不可用的。随机点生成方法在每个独立的运行中特别容易返回不一致的解决方案。此外，由于元启发式算法通过随机操作来工作，存在随机性，因此减少最终解发生变化的可能性非常重要。

针对路径规划中的种群初始化问题，也有些学者提出了一些改进方法。例如，文献[14]认为，起点和目标点都是已知的，因此当环境中没有障碍物时，连接2点的线将是最短、最平滑的路径。在这种启发式信息的帮助下，利用随机方法在直线附近生成了一些初始路径。这种方法在相对理想的环境中效果较好，但在复杂的环境中尤其是在有障碍物定位起点与目标点连线的情况下，效率较低。

考虑到机器人路径规划的特点，生成初始种群的具体步骤如下[15]。

步骤1在二维栅格点图中，设置机器人的初始点坐标和目标点坐标，并将机器人放置起始点。

步骤2机器人朝着目标点沿直线行走，若碰到障碍物，则采用SPS算法在障碍物的周围产生点集。

步骤3用Dijkstra算法测试产生的路径点是否可行，若可行，则继续前进；若不可行，则减小栅格点宽度，重复步骤2。

步骤4判断是否到达目标点，若已到达，则把当前产生的路径保存下来，若未到达，则重复步骤2和步骤3。

步骤5判断个体数目达到种群数目2M，若达到，则结束；若没达到，则重复以上步骤。

图4是根据SPS算法在MATLAB R2016a中仿真出的初始路径图(一个障碍物)。

图4 仿真图(一个障碍物)Fig.4 Simulated diagram (an obstacle)

通过周围点集法产生初始路径不仅搜索效率高，收敛速度快，没有很高的计算成本，且所产生的初始路径都是可行的，减小了产生初始路径的随机性，使得最终解发生变化的可能性很小。

2.3 适应值评价与分配

2.3.1 适应度函数

适应度函数是度量种群中每个个体适应度的函数，是由目标函数确定的。一旦形成初始种群，遗传算法必须要根据适应度函数来确定每个个体的性能，该函数能够为每个可行解分配一个反映其质量的适应值。它是遗传算法在进化过程中的一个重要组成部分，适当选择适应度函数将使搜索朝着最优解的方向发展。适应度函数必须要考虑一些标准，比如路径的长度、安全度以及平滑度等，因为遗传算法需要使用该函数的值来选择个体并通过交叉变异繁衍后代，直到算法结束时选择最终群体的最优解。

本文适应度函数需要考虑3个标准：路径长度、路径平滑度以及路径困难度。其中将路径长度和路径困难度作为主要标准，路径平滑度作为次要标准，并将(4)—(6)式分别作为它们的目标函数。

2.3.2 适应值分配

本文采取SPEA2[16]的适应值分配方法，该方法在为每个个体分配适应值的时候，既考虑了支配该个体的数目，也考虑了受该个体支配的数目。主要流程如下。

步骤1生成初始种群集合P，大小为N，建立一个空集合P′，大小为N′，并将集合P复制到集合P′中。

步骤2从P′中删除受其他个体支配的个体，即Pareto Front为1的个体，若P′中个体数目大于N′，则采用聚类算法减少P′中个体的数目。

步骤3为P′中的个体分配适应度值得

(7)

(7)式中：i表示的是P′中的个体；t表示的是P′中的个体i支配P中个体的数量。

步骤4为P中的个体分配适应度值得

f(i)=1+∑S(j)

(8)

(8)式中：j表示在P′中支配i的个体；S(j)为个体j在P′中的适应度值。

本文对该方法进行改进，从集合P复制到P′的过程中，判断是否有重复的解，若有则删除，可以有效地防止适应度好的个体迅速繁衍而导致的早熟收敛。

2.4 遗传算子

1)选择。本文采用锦标赛法进行选择，即对种群中的个体进行随机分组，每组根据个体的适应度值选择适应度值最低的个体进入子代种群。并采用精英保留策略，按一定比例将适应度最优的个体不需要经过遗传直接复制到子代种群。

2)交叉。本文采用单点交叉方式，即随机选择2个个体，找出路径相同点进行交叉，这样可以保证路径的连续性，如图5所示过程，如果不止一个路径相同点，则随机选取任意一个进行路径交叉，如果没有路径相同点，则从2个个体中随机选取2个点进行交叉，如果交叉后不是连续的路径，则将上半段的最后一个点和下半段的第1个点作为起始点和目标点，运用障碍物的周围点集进行修补使其成为一条连续的路径。

3)变异。本文的研究方法产生的初始路径一定是可行的，且经过选择和交叉之后亦是如此，所以本文对路径上点的坐标依据概率进行小范围调整即可，从而保证变异后路径的可行性。

图5 交叉过程Fig.5 Cross process

4)删除。在没有增加删除算子之前，可能会出现图5的情况，则需要更多的迭代次数使路径趋近于平滑。所以本文增加了删除算子，如果一条路径中存在如图6a的情况，删除pi后，pi的前一个路径点pi-1与后一个路径点pi+1相连后是可行路径段，则删除pi，连接pi-1与pi+1产生一条新的路径，如图6b，从而在一定程度上加快了算法的收敛速度，减少了算法的运行时间。

图6 删除前后路径Fig.6 Path of before and after deletion

5)平滑。该路径的平滑度算法是受到粒子群算法的启发，在粒子群算法中每个粒子都有位置和速度2个属性，在迭代过程中每个粒子需要跟踪自己的历史最优值和全局最优值，直到满足终止条件。本文路径中的每个坐标点相当于粒子群算法中粒子的位置，根据该坐标点的前后坐标计算出粒子的速度，根据位置更新公式和速度更新公式，计算出新的坐标点，经过多次迭代后使路径更平滑。过程如图7。

图7中：ω是惯性权重，表示的是前一时刻速度对当前速度的影响程度；r1和r2是0和1之间的随机数。各参数含义为

xt+1,i(p)=xt,i(p)+vt+1,i(p)

图7 平滑过程Fig.7 Smoothing process

6)小生境法[17]。传统的遗传算法虽然能随机寻找问题的最优解，但是在应用过程中单一的种群个体很难保证种群的多样性，容易出现早熟现象，且遗传算法在本质上是串行运行的，进化过程相对比较缓慢。为了避免上述问题的产生,本文把2M个种群个体分解为M个小生境，每个小生境由2个相似的种群个体组成，种群的相似度由海明距离决定，海明距离越小，相似度越高。接着将M个小生境同时进化和繁衍，然后在每个小生境中选择2个优良个体进入下一代，最终由每个小生境中选择适应度高的个体形成新的种群进行进化和繁衍，从而保持了种群的多样性，在一定程度上加快了算法的运行速度。

3 实验与分析

3.1 仿真环境

本文采用MATLAB R2016a构建仿真平台，设置仿真环境如图8，为了验证本文算法的有效性，把它分别与文献[10]、文献[12]中的算法以及传统的遗传算法进行了比较，设置障碍物分布在栅格点宽度为10的500×500的栅格点矩阵中，机器人的起点为(10,10)，如图8左上角的点，终点为(490,490)，如图8右下角的点，图8中黑色表示障碍物。

3.2 参数设置

种群规模N为50，最大迭代次数T=300，前T/2中，交叉概率Pc=0.5，变异概率Pm=0.5，删除概率Pd=0.4，平滑概率Ps=0.1；后T/2中，交叉概率Pc=0.2，变异概率Pm=0.1，删除概率Pd=0.4，平滑概率Ps=0.6。

3.3 结果分析

图8表示的是多约束条件下由4种算法找到的从起点(10,10)到终点(490,490)的路径，表1表示的是4种算法在路径长度、路径平滑度、路径困难度与时间成本方面运行结果的数据对比，图9表示的是4种算法迭代100次的收敛曲线。

图8 4种算法路径图Fig.8 Path graph of four algorithms

图9 4种算法收敛曲Fig.9 Convergence curves of four algorithm

表1为4种算法50次运行结果对比，由表1可以看出，相比于传统的遗传算法，本文改进的算法在路径长度、路径平滑度、路径困难度以及时间成本方面都明显优于对方，即使与较新的文献[10]算法相比，仍然略优于对方。传统遗传算法的平均运行时间是14.69 s,文献[10]算法的平均运行时间10.58 s，本文改进算法仅用了8.57 s，比传统遗传算法的运行时间缩短了1.7倍，相比于文献[10]算法，运行时间缩短了1.23倍，且本文改进的遗传算法相比于与文献[10]、文献[12]中的算法以及传统的遗传算法，在路径长度、路径平滑度以及路径困难度方面均具有一定的优势。

由图9可以看出，本文改进的遗传算法相比于传统的遗传算法，收敛的速度得到一定的提升，而且最终收敛的值也小于传统算法(在路径规划中，寻找最优路径所付出的代价越小越好)；本文改进的遗传算法相比于其他2种算法，虽然最终收敛的值非常接近，但收敛速度却得到略微的提升。所以本文改进的遗传算法具有较高的搜索效率，加快了算法的收敛速度，在一定程度上有利于防止算法陷入局部最优。

表1 4种算法50次运行结果对比

4 结束语

针对在多约束条件下移动机器人在路径规划中的搜索效率低、收敛速度慢的缺点，本文提出了一种多约束条件下基于改进遗传算法的智能移动机器人路径规划方法，综合考虑了路径长度、路径平滑度和路径困难度这3种因素的影响，改进初始种群的生成方式，并在此基础上增加了删除算子和平滑算子，同时结合了小生境法，在相同的环境中和文献[10]、文献[12]以及传统遗传算法相比较，本文提出的算法能够在较短时间内找到最优路径且收敛速度较快，表明本文提出的算法具有一定的优越性。本文改进的算法主要是在静态环境中进行路径规划，并没有考虑到有动态障碍物的情况，这是本文的不足和以后研究的重点。