常 见，任 雁
(河南林业职业学院a.信息与艺术设计系；
b.河南省果园管理特种机器人工程技术研究中心，洛阳 471002)
当前，路径规划是智能机器人研究领域的热点技术之一，其广泛应用于工业、医学和农业等各个领域[1-2]。路径规划的主要目的是根据特定标准在充满障碍物的环境中，在规定的起点和终点之间找到一条最佳或接近最佳的无碰撞路径[3]。在路径规划问题中，机器人路径规划的质量、效率及成功率，受机器人类型、环境条件、静态或动态障碍物等众多因素影响[4-5]。因此，要找到一条避免与障碍物干扰的平滑路径或最短路径是一个非常具有挑战的问题。
由于路径规划问题的复杂性，通常将其视为非确定性多项式难题[6]。在早期研究中，主要通过进化算法寻找路径规划的最佳解决方案[7]。但进化算法在环境建模时，要求网格的位置预先固定，会使得路径规划的灵活性受网格大小的限制[8]。其次，进化算法主要采用随机初始解决方案，将可能导致在多次迭代后找不到任何可行路径，特别是对于大型复杂环境。同时，进化算法为单目标路径规划，只能实现路径长度最小化规划，即找到起点和目标位置之间长度最短的路径[9]。在实际应用中随着机器人工作环境的限制，传统的单目标路径规划方法已无法满足机器人路径规划需求[10]。
为解决上述问题，众多专家学者对此开展了大量研究。王乐乐等[11]提出一种改进快速扩展随机树的机器人路径规划算法，通过建立搜索树模型提高机器人路径感知能力，能够有效解决机器人在复杂环境下的路径规划问题。QU等[12]提出了一种混合灰狼路径规划优化算法，通过简化计算阶段加快收敛速度并保留种群探索能力，从而获得有效的最佳运动路径，但上述方法路径规划效率相对较低，且易陷入局部极小点。阮晓钢等[13]提出了一种自适应启发式快速探索随机树路径规划方法，通过在起点、目标点、子目标点等处分别生成随机树同时进行扩展搜索，提高路径规划效率。CHAYMAA等[14]提出了一种基于改进交叉遗传算法的自主移动机器人路径规划方法，通过对距离、安全性等条件进行优化，同时避开障碍物，可在两个位置之间找到一条有效且可行的路径。姚晓通等[15]提出一种基于改进蚁群算法的机器人路径规划方法，通过对蚂蚁状态转移策略的调整，改进个体在寻优的过程中的导向性，使路径规划的路径长度和迭代次数获得最优解，但上述方法存在初始解成功率低、运行时间长且路径不平滑等问题。
针对上述问题，本文提出了一种基于改进遗传算法的机器人路径规划方法。在路径长度、路径平滑度、路径困难度等约束条件下以栅格法构建环境模型，并采用周围点集法(surrounding point set，SPS)解决障碍物附近路径生成问题。同时引入删除算子、平滑算子和小生境法对传统遗传算法进行改进，提高路径的平滑度，避免算法陷入早熟，提高算法收敛速度。
如图1所示为采用栅格点所构建的机器人工作环境，该二维空间内包含有多个障碍物，分别为Ob1,Ob2,…,Obn，机器人工作起点为S，目标位置为T。
图1 机器人的工作环境
如式(1)所示为机器人的某一可行走路径：
P={p1,p2,p3,…,pn}，
p1=S，pn=T，pi∩Obj=∅
1≤i≤n，1≤j≤n
(1)
式中，n为机器人行走路径集合P所包含的节点数；
pi为路径上的某一i节点。
本文改进遗传算法下，机器人的行走路径为：
(2)
式中，m为路径集合P*中所包含的节点数量，该路径需要满足以下条件：
f(P*)=min{f1(P),f2(P),f3(P)}
(3)
式中，f1(P)、f2(P)、f3(P)分别见定义1、定义2、定义3。
定义1：f1(P)为衡量路径P*的总长度的长度指标，如式(4)所示。
(4)
式中，|pipi+1|为节点pi、pi+1的欧式距离。
定义2：f2(P)为平滑度指标，表征路径P*的平滑度，如式(5)所示。
(5)
式中，θ(pipi+1,pi+1pi+2)为pipi+1、pi+1pi+2之间的夹角。其中，0≤θ≤π，S为路径P*中线段数量；
C1为大于0的整数；
Ni为i次迭代所得路径中的节点数量。
定义3：f3(P)为路径P*的困难指数，如式(6)所示。
(6)
式中，d(xi)为机器人经过i节点的困难程度。
经过上述3个目标对象，本文可以得到一组帕累托最优路径即为本文算法为机器人规划的最优路径。
针对多约束条件下的机器人路径寻优能力差、搜索效率低的问题，本文对传统遗传算法进行了改进。
2.1 个体编码
传统遗传算法在处理问题时需要对初始种群当中的个体进行编码，通常根据需要处理问题的不同需要选择对应的编码方式。在遗传算法中二进制编码方式是一种较为常用且应用广泛的编码方式。
本文机器人的工作环境为由栅格点构建的均匀分布的二维空间，每个栅格点用坐标(xi,yi)表示，其中xi为路径节点横坐标，yi为路径节点纵坐标，不同节点构成的连线即为机器人的行驶路径，节点之间的路径长度总和即为机器人行驶的路径长度。当二维空间分布的障碍物不同，则机器人行驶的路径长度、节点数量、路径复杂度均不同。如图2所示为机器人可行路径编码示例。
图2 移动机器人可行路径编码
2.2 种群初始化
传统遗传算法的种群初始化是随机进行的，通常使用网格地图或者是自由空间中随机生成散布点来实现算法种群初始化。随机初始化的问题在于，在初始化后需要考虑这些随机生成的节点对于路径规划是否有用，当无用的节点过多时必然会导致算法的计算成本增加，甚至影响最优路径的获取。
为了解决上述种群随机初始化中存在的问题，对传统遗传算法种群初始化进行了改进，具体步骤如下：
步骤1：在机器人工作的二维空间中，首先确定机器人的起点和目标点。其中，机器人所处的位置位于起点；
步骤2：假设起点和目标点无障碍物，则移动机器人从起点根据最短直线距离方向向目标位置进行移动，如果移动途中有障碍物，则在障碍物周围通过SPS算法生成点集，如图3所示为该过程示意图；
图3 SPS算法生出初始路径
步骤3：通过Dijkstra算法对SPS算法生成的路径点的可行性进行测试，如果可行则继续行走，如果路径点不可行，则将栅格点的宽度进行缩减，而后返回步骤2；
步骤4：判断机器人坐标是否已经到达目标位置，如果已经到达了，就保存当前从起点到目标点的路径，如果没有达到目标位置，那么就返回步骤2；
步骤5：计算种群中的个体的数量，如果种群数量大于等于2M，则结束迭代；
如果小于2M，则从步骤1开始重复上述步骤。
2.3 适应值评价与分配
2.3.1 适应度函数
适应度函数是表示种群当中个体适应度的一种函数，通常采用适应度函数对种群中个体适应值进行计算，且该函数可以决定遗传算法的搜索方向。考虑到机器人路径规划的复杂性，本文根据路径困难度、平滑度以及路径长度3个目标来确定适应度函数。其中主要考虑因素为路径的困难度和长度，其次考虑路径平滑度，式(4)～式(6)分别为对应的3个因素的目标函数。
2.3.2 适应值分配
适应值可以对算法迭代过程中的可行解的质量进行评估。本文使用SPEA2[16]方法对种群中的个体进行适应值分配，具体分配方法如下：
步骤1：种群初始化得到大小为N的种群P，另建一个大小为N′的空集合P′，而后将种群P复制至P′中；
步骤2：删除P′中受其他个体支配的个体，若P′个体数>N′，那么需要通过聚类算法处理集合P′使其个体数量减少；
步骤3：集合P′中的个体可以根据式(4)求解适应值。
(7)
式中，t为在集合P′中i可支配的P中的个体数。
步骤4：对种群P中的个体分配如式(8)所示的适应值。
f(i)=1+∑S(j)
(8)
式中，j为集合P′中可以支配个体i的个体；
S(j)为集合P′中个体j的适应值。
本文通过将P复制至P′的步骤来对重复解进行判断，如果有重复解，那么就进行删除，可以避免由于重复解导致的适应值高的个体因过度繁衍而造成的早熟收敛问题。
2.4 遗传算子
在遗传算子方面，本文主要是在传统算法的基础上增加了删除算子和平滑算子，同时引入了小生境法来避免算法陷入局部最优。具体如下：
(1)选择。首先，随机对种群中的个体进行分组；
其次，根据精英保留的方法计算所有个体适应值并根据该值筛选出每个分组中适应度值较优的个体，并让这个个体可以直接进入子代群体中而非通过遗传方式。
(2)交叉。随机选择两个个体，并对两个随机个体的相同路径点进行交叉，如果相同路径点大于等于2个，那么选择其中任意一个相同的路径点进行单点交叉；
若无相同路径点，则分别从两个个体各选择一个路径点，即交叉这两个个体上选择的路径点，若交叉后形成的路径为不连续路径，则通过SPS算法将断开的路径重新连接形成连续路径。
(3)变异。本文改进后遗传算法中种群初始化路径为可行路径，即使经过选择和交叉其仍为可行路径，所以本文变异处理即为对可行路径上点进行小概率小范围调整，以确保个体变异后路径仍可行。
图4 个体交叉的过程
(4)删除。经过变异处理后的路径，往往可能还需要大量的迭代才能使路径趋于平滑，因此本文增加了删除算子。如图5所示，如果在障碍物附近路径需要多次转折(见图5a)，则对其中转折点进行删除，即删除图5a中的pi，连接pi-1和pi+1，生成一条可行的直线路径段，通过这种方式一方面可以大大缩短机器人的行驶路径，另一方面可以有效提高算法的迭代效率。
(a) 删除前 (b) 删除后图5 删除算子对路径的处理
(5)平滑。为了提高机器人移动路径的平滑度，本文借鉴了粒子群算法，即每个粒子记录并跟踪自身位置、速度两个属性，记录历史最优值，同时在每次迭代中记录全局最优值，如此多次迭代直到满足迭代退出条件。将本文二维空间中路径节点代入到粒子群算法中，则路径节点的坐标对应于粒子位置，而后根据该节点前后节点的坐标对粒子速度进行计算，并由粒子群算法不断迭代计算最优值，最终得到更新后的新坐标点。如图6所示为机器人移动路径的平滑过程。
图6 路径平滑过程
在图6中，r1、r2∈random(0,1)，ω表示惯性权重，具体平滑过程如式(9)所示。
(9)
(6)小生境法。通过随机种群初始化、选择、交叉、删除等步骤可以使传统的遗传算法随机得到最优路径，但是其中存在种群单一、遗传早熟、进化较为缓慢等问题。针对上述问题，本文引入了小生境法，即首先将2M个种群分解为M个小生境，其中M个小生境中又包含两个个体相似度较高的种群。然后，同时让M个小生境进化，而后对每个小生境中的个体适应度值进行计算，选择两个最优的个体直接进入子代群体，并形成一个新的种群。通过这种方式可以有效保证种群遗传的多样性，进而提高算法的收敛性，避免了算法陷入局部最优。如图7所示为本文提出的改进遗传算法的流程图。
图7 改进遗传算法流程图
为评估所提改进型遗传算法的性能，进行了算法有效性验证实验和对比分析实验，两个实验均在MATLAB 2019仿真平台上实现的。其中有效性验证实验主要比较改进后的遗传算法较传统遗传算法的性能，而对比实验主要将本次提出的算法与当前的一些主流算法进行比较。在对比实验中，构建了6个地图环境，不同环境的大小、形状和障碍物数量各不相同。通过搭建不同的环境，为所提改进型遗传算法在路径长度、路径平滑度、运行时间和路径困难度等方面的性能进行对比分析。
实验中改进遗传算法的参数设置如表1所示。
表1 参数设置
3.1 有效性验证实验
如图8所示为所提算法与传统遗传算法的路径规划结果，其中灰色正方形为起点，灰色五角星为目的地。如图9所示为两种算法的收敛曲线。
图8 两种算法路径规划 图9 两种算法收敛曲线
从图8和图9可知，传统遗传算法算法更容易陷入局部最优解，收敛速度慢，规划的路径不够平滑且路径更长。在经过40次迭代后，传统遗传算法基本上收敛到最优解，而所提的改进遗传算法在20次迭代后即可收敛到最优解。另外，从路径的困难度上来看，传统遗传算法的路径困难度为76，而改进后的遗传算法路径困难度为59。由此表明，改进后的遗传算法在路径长度、路径平滑度以及路径困难度等性能上均优于传统遗传算法。
3.2 对比实验
选取A*、PRM、B-RRT和PSO算法与所提改进型遗传算法算法进行对比分析。如图10所示，为A*、PRM、B-RRT、PSO和所提改进型遗传算法的50次迭代执行的路径长度、平滑度、运行时间和路径困难度的平均值，其中Map2和Mpa3两个地图环境下B-RRT无法进行路径规划，因此在柱状图中采用空白代替。图11为所选取的几种对比算法在6个不同地图环境下的路径规划结果。
(a) 路径长度 (b) 运行时间
(a) Map1 (b) Map2 (c) Map3
由图10和图11可知，在6个地图环境中本文所提方法所获得的路径最短。同时，除路径长度为目标函数外，引入的删除和平滑算子使改进型遗传算法能够在除地图4外其他环境中实现最平滑的路径。其中地图4环境中，PRM虽能够获得最平滑的路径，但在所有环境中其路径长度都比改进型遗传算法长得多。因此，同时考虑路径长度、路径平滑度、运行时间和路径困难度，所提改进型遗传算法在所有环境中都表现出最佳性能。
为解决机器人在多约束条件下路径寻优能力差、搜索算法收敛速度慢等问题，提出了一种改进遗传算法的多机器人路径规划方法，并通过实验分析得出以下结论：
(1)所提方法通过在目标函数中添加删除算子和平滑算子可有效提高算法的迭代效率，获取平滑的寻优路径。
(2)与其他几种对比方法相比，在同时考虑路径长度、路径平滑度、运行时间和路径困难度的多目标函数下，所提方法在所有环境中均能够表现出最佳性能。
(3)所提方法仅考虑了静态障碍物，下一步研究将致力于将所提方法扩展到具有移动障碍物的环境中进行路径规划。
猜你喜欢障碍物遗传算法种群山西省发现刺五加种群分布今日农业(2022年15期)2022-09-20高低翻越动漫界·幼教365(中班)(2020年3期)2020-04-20SelTrac®CBTC系统中非通信障碍物的设计和处理铁道通信信号(2020年9期)2020-02-06中华蜂种群急剧萎缩的生态人类学探讨红土地(2018年7期)2018-09-26一种基于遗传算法的聚类分析方法在DNA序列比较中的应用中央民族大学学报（自然科学版）(2017年1期)2017-06-11基于遗传算法和LS-SVM的财务危机预测统计与决策(2017年2期)2017-03-20软件发布规划的遗传算法实现与解释现代计算机(2016年34期)2016-02-28基于改进的遗传算法的模糊聚类算法智能系统学报(2015年4期)2015-12-27岗更湖鲤鱼的种群特征当代畜禽养殖业(2014年10期)2014-02-27土钉墙在近障碍物的地下车行通道工程中的应用城市道桥与防洪(2014年5期)2014-02-27