李开荣, 胡倩倩

(扬州大学信息工程学院, 江苏 扬州 225127)

近年来, 移动机器人被广泛应用于各种生活场景．路径规划作为移动机器人实现自主运动的关键技术,是当前移动机器人领域最活跃的研究方向之一[1]．遗传算法(genetic algorithm,GA)因其良好的扩展性、鲁棒性及快速随机的搜索能力而成为移动机器人路径规划研究的热点方法[2]．然而,传统的遗传算法不仅收敛速度慢,而且易陷入早熟收敛．Zhang[3]通过对矩阵编码和改进变异算子,提出一种基于可见空间的改进遗传算法;Lamini等[4]提出一种改进的同邻域交叉算子求解机器人路径规划问题,有效避免了算法早熟收敛;宋宇等[5]采用快速扩展随机树(rapidly-exploring random trees, RRT)算法生成初始路径,并提出一种插入优化算子有效改进了传统遗传算法,得到不同环境下的全局最优路径;易欣等[6]提出一种基于元启发式-自适应遗传算法,利用随机Dijkstra算法创建初始种群,并采用自适应算子代替常规选择算子,有效避免了路径规划中的局部收敛问题．由于生产实际对移动机器人运行路径的平滑性和安全性提出了更高要求,故越来越多的国内外学者在移动机器人的路径规划研究中引入曲线思想．Costanzi等[7]以移动机器人的平面路径规划为研究对象,结合Bezier曲线,根据长度和曲率对计算出的路径进行优化,得到更为平滑的最优路径;徐岩等[8]运用基于Q值的交互式遗传算法(Q-standard improved genetic algorithm,Q-IGA)动态搜索贝塞尔曲线控制点,同时进行路径与控制点搜索,使得规划出的路径是一条距离较短且与障碍物保持安全距离的合理路径,并降低机器人能耗,减少搜索时间;Ma等[9]基于Bezier曲线提出一种平滑路径规划算法(Bezier curve-smoothing algorithm, BCA),该算法在较长的运算时间下能够得出一条无碰撞的最优曲线运行路径．上述方法均未充分考虑算法的各个环节以及最优路径的平滑优化问题,且大部分改进算法的复杂度较高、运行效率较低．本文通过对Bezier曲线进行平滑优化处理,提出一种融合Bezier的改进遗传算法以期快速规划出移动机器人在运行环境中的最优可行路径和提高移动机器人的运行效率．

1 环境建模与路径编码

采用栅格法建立机器人的运行环境模型,并做如下规定[10]:

1) 将移动机器人视为一个质点, 并限定机器人的移动空间为二维平面;

2) 在构建的栅格地图中所有障碍物均为静态障碍物, 其大小和位置已知且不考虑其高度;

3) 如果障碍物大小不满一个栅格, 则将其铺满该栅格, 并视为一个完整的障碍栅格进行建模．

通过合理设计栅格的大小和数目, 建立如图1所示的地图模型, 其中栅格节点S,G分别为移动机器人运行的起始点和目标点,黑色为障碍栅格, 白色为自由栅格．由于整个栅格地图处于一个直角坐标系中, 故每一个栅格节点的序列号N均可与一个路径点坐标(x,y)对应．假设栅格图的大小为n×n, 则栅格序号和栅格坐标的对应关系为

图1 移动机器人运行环境模型Fig.1 Mobile robot running environment model

(1)

为了尽可能缩短编码长度,本文采用栅格节点的序列号进行编码,并规定任意一条可行路径的编码序号都不能包含重复序号和障碍栅格所对应的序号．由图1可见,某一条可行路径可表示为S-41-70-G．

2 本文算法

2.1 算法设计流程

首先对传统遗传算法的部分环节进行改进,然后在改进遗传算法的基础上引入Bezier曲线的概念,具体流程如下:

1) 初始化参数, 采用栅格法建模,对节点序列号编码;

2) 利用启发式中值插入法建立初始种群, 生成M条初始可行路径;

3) 根据多目标适应度函数计算每条初始路径的适应度值F(N);

4) 对路径适应度值排序,采用分层法选择优势路径个体并直接遗传至下一代;

5) 根据交叉概率选择一定数量的路径个体进行单点交叉操作;

6) 根据变异概率选择一定数量的路径个体进行八邻域单点变异操作;

7) 初始可行路径在经过遗传操作后生成子代路径．计算子代路径个体的适应度值,判断改进遗传算法是否达到终止条件,若达到, 则该子代个体为最优折线路径,否则回到步骤3)循环遗传操作;

8) 采用平滑优化操作,以最优折线路径的路径序列点作为Bezier曲线的控制点生成一条平滑曲线路径;

9) 若平滑曲线路径与障碍物发生碰撞, 则启动重规划操作并新增控制点使曲线不断贴近原折线路径,直到消除曲线与障碍物的碰撞情况;

10) 输出单移动机器人的无碰撞最优曲线路径．

步骤1)～7)的目的是根据改进遗传算法生成最优折线路径, 步骤8)～10)则基于Bezier曲线对改进遗传算法生成的最优折线路径进行平滑优化操作, 输出结果即全局最优曲线路径．由此可见, 融合Bezier遗传算法的时间复杂度由遗传算子、适应度函数以及平滑操作共同决定, 整个算法的时间复杂度为O(OF(Ops+Opc+Opm)+OS), 其中OF为适应度函数的复杂度,Ops,Opc,Opm分别为选择、交叉、变异操作的时间复杂度,OS为平滑操作的时间复杂度．本文提出的分层选择法较传统轮盘赌算法的时间复杂度小, 适应度函数虽考虑了多个指标, 但每个指标的衡量方法都较精简, 且平滑操作仅针对改进遗传算法生成的最优解; 因此, 融合Bezier遗传算法的时间复杂度仅在传统遗传算法的基础上增加了1次OS．

2.2 初始化种群

采用一种启发式中值插入法建立初始种群, 避免随机生成法所致不可行路径比重过大的问题, 具体过程如下:

1) 确定种群大小M;

2) 确定栅格地图的大小n×n、移动机器人路径规划的起始点S、目标点G以及障碍栅格的数目f;

3) 生成M个从起始点S到目标点G的路径染色体:

① 随机生成一个栅格序号Ni(Ni不属于起点、终点或障碍栅格), 此时机器人的路径可表示为S-Ni-G;

② 判断路径中相邻节点是否连续:

Δ=max{|xi+1-xi|, |yi+1-yi|},

(2)

其中(xi,yi), (xi+1,yi+1)分别为两个相邻路径点Ni和Ni+1的直角坐标．如果Δ=1, 则Ni和Ni+1是连续的, 否则两点不连续．此时, 通过中值法选择下一个插入点填补间断路径,计算式如下:

(3)

图2 八邻域节点Fig.2 Eight neighborhood nodes

其中(x′i,y′i)为候补栅格坐标,d为栅格的行或列数,N′i为候补栅格序号．如果计算所得N′i为自由栅格,则直接插入Ni与Ni+1之间, 否则随机选取N′i的八邻域节点中的自由栅格作为新插入的节点．节点N四周灰色区域即其八邻域, 如图2所示．若N′i的八邻域中没有自由栅格, 则表明本次操作无效, 可直接舍弃该个体．重复上述插入步骤, 以生成一条连续的可行路径;

③ 不断进行以上操作,直至产生一个有M条不重复染色体的初始种群．

2.3 适应度函数

为了在确保算法复杂度较小的同时加快遗传算法的收敛, 并维持个体间的合理差距,找出能够平稳避开障碍物且快速到达目标点的最优路径,现设计基于路径长度L(N)、路径安全性S(N)和路径能耗E(N)的多目标适应度函数:

(4)

其中a,b,c分别为指标L(N),S(N),E(N)的权重,a+b+c=10．路径长度为所有相邻节点间的欧氏距离之和,

(5)

其中n为路径节点的数量．路径安全性函数

(6)

其中Si为节点i的安全性惩罚值．以路径节点的八邻域作为衡量该点与周围障碍物之间的安全距离标准, 如果某一路径节点的八邻域中不存在障碍栅格, 则该点为安全移动点; 否则,该点存在安全隐患,Si惩罚值加1．路径能耗函数

(7)

图3 移动机器人拐弯方向对应象限图Fig.3 Quadrant map of mobile robot turning direction

其中Ei为节点i的能耗惩罚值,l表示路径段．移动机器人拐弯方向对应象限如图3所示．由图3可见, 如果机器人在i点拐弯, 则以i点为原点,i点的横纵坐标所在方向即分界线划分象限．机器人发生拐弯且前进方向在第二象限,Ei能耗惩罚值加1; 机器人前进方向在第一象限或第四象限,Ei能耗惩罚值加3; 机器人前进方向在第三象限,Ei能耗惩罚值加10．

2.4 遗传操作

1) 选择．初始化种群后共生成M个个体, 根据适应度函数计算每个个体的适应度值并按降序排列．将种群分为3等份, 每一份为一层．按序将第一层适应度值较大的一等份复制2份, 将第二层适应度值中等的一等份复制1份, 最后一层适应度较小的不复制, 从而形成子代种群．这样既能保证优秀的个体能够遗传到下一代, 又能维持种群的多样性．其选择方式如图4所示．

图4 选择操作示意图Fig.4 Select operation diagram

2) 交叉． 交叉操作的本质是染色体的基因重组[11],即通过交换父代染色体的部分基因生成新的子代染色体．现采用单点交叉的方式进行处理．随机选取两个父代个体中的一个相同序列号(起始点S和目标点G除外),在此点处进行交叉．如果两个父代个体中不存在相同的序列号,则不进行交叉操作．

3) 变异． 变异操作是将某一个体染色体上的任意一个基因进行变异处理生成一个新的染色体, 从而维持种群的多样性[12]．传统的单点变异或多点变异等处理方法极易产生不可行路径,导致算法的运行效率低下, 故笔者采用八邻域单点变异的方法．随机选取待变异路径个体中的一个变异点Ni(起始点S和目标点G除外), 在该变异点的八邻域中随机确定一个非障碍栅格N′i替换原有节点．按照初始路径的生成方法, 将Ni-1到N′i以及N′i到Ni+1连接为无间断路径．若变异点的八邻域中没有可以选取的自由栅格或无法生成一条可行的无间断路径, 则按变异失败处理, 即跳出此次变异操作并重新选取下一条待变异路径个体及其变异点．

2.5 终止条件

终止条件是衡量遗传算法是否能够结束运行的一个标准．本文终止条件如下:达到给定的进化代数阈值50; 连续40次进化种群的最优适应度值不变; 算法运行时间超过5 min, 满足条件之一即终止运行．

2.6 Bezier曲线平滑操作

1) Bezier曲线． Bezier曲线[13]主要由数据点和控制点等节点与线段构成, 其中数据点用于确定曲线的起始与结束位置, 控制点确定曲线的弯曲程度．考虑n阶Bezier曲线, 其控制点表达式P(t)及n次伯恩斯坦多项式Bi,n(t)分别为:

(8)

(9)

图5 Bezier曲线生成示意图Fig.5 Schematic diagram of Bezier curve generation

当n=1时, 一阶Bezier曲线是一条含2个节点的直线; 当n=2时, 二阶Bezier曲线是一条含3个节点的抛物线; 当n≥3时, 是一条含n+1个节点的高阶Bezier曲线．二阶Bezier曲线的生成原理如图5所示．

2) Bezier曲线的平滑优化． 将改进遗传算法规划所得折线路径上的路径节点作为Bezier曲线的控制点生成曲线路径．根据Bezier曲线的性质可知规划所得曲线路径不会与控制点连接而成的特征多边形的外部障碍物发生碰撞．然而,控制点选取的疏密会导致原路径与现路径形成的特征多边形内部障碍物未发生碰撞,而平滑操作后的曲线路径却与相应的内部障碍物发生碰撞的情况．故可重规划使得曲线路径更贴近原路径, 如图6所示．选取发生碰撞情况的4个控制点,在这4个点所形成的3条边的中点处新增3个控制点,根据这6个控制点重新平滑优化．重复上述过程直至曲线路径与障碍物无碰撞可能．

图6 重规划示意图Fig.6 Re-planning diagram

图7 融合Bezier遗传算法规划路径Fig.7 Path planning based on Bezier-genetic algorithm

图7为融合Bezier遗传算法的规划路径示意图, 其中虚折线为改进遗传算法生成的最优折线路径,空心圆圈为路径序列点,曲实线则为根据路径序列点生成的最优曲线路径．由图7可见, 融合Bezier曲线生成的路径更短且更平滑．

3 仿真分析

图8 3种环境下的最优运行路径Fig.8 Optimal operating path in three environments

仿真实验在10 m×10 m、15 m×15 m、20 m×20 m等3种栅格环境模型中展开, 以验证算法的通用性．参数设置如下: 种群数量M=100, 最大进化代数为50, 交叉概率为0.8, 变异概率为0.2, 路径长度权重a=6, 路径安全性权重b=1, 路径能耗权重c=3．融合Bezier遗传算法的规划结果如图8所示, 其中虚折线代表改进遗传算法规划得出的初始折线运行路径, 折线路径上的空心点为路径序列点, 即生成Bezier曲线的初始控制点, 实曲线代表最终生成的最优曲线路径．

表1为融合Bezier曲线前后改进遗传算法所规划的路径长度对比结果．由图8及表1可知: 融合Bezier遗传算法生成的曲线路径更短且路径平滑度高, 完全解决了大角度转弯的问题, 在直线运行的区域曲线路径也近似直线; 融合Bezier遗传算法规划得出的最优运行路径更加符合实际场景的需求．

表1 融合Bezier前后改进遗传算法规划的路径长度Tab.1 Comparison of path length between Bezier-genetic algorithm and improved genetic algorithm

表2 融合Bezier遗传算法与BCA算法对比结果Tab.2 Comparison results of Bezier-genetic algorithm and BCA algorithm

图9 2种算法在环境4中的最优运行路径Fig.9 The optimal running path of the two algorithms in environment 4

现采用本文算法与BCA算法[9]在参数相同的情况下于环境4分别独立执行30次仿真实验, 以消除随机因素的影响, 结果如表2和图9所示．由表2和图9可知: 融合Bezier遗传算法的最优运行路径更为平缓且仅在控制点与障碍物相切处发生小曲率偏折; 本文算法的路径长度较BCA算法低6.7%, 算法运行时间为BCA算法的10-6, 其原因为本文算法仅对改进遗传算法生成的最优解进行平滑操作, 而BCA算法则对每一个初始种群都生成Bezier曲线再进行遗传迭代．

4 结论

本文设计了一种融合Bezier遗传算法的移动机器人路径规划问题．在初始种群的创建过程中采用启发式中值插入法,有效提高了初始种群的质量,加快了算法的收敛速度．以路径长度、路径安全性和路径能耗为评价指标,建立多目标适应度函数,在尽可能减小路径长度的同时确保机器人始终朝着目标点的方向前进,避免无谓的路径能耗,一定程度上提高了规划路径的安全性．通过改进的遗传操作预防算法过早陷入局部最优,并以改进遗传算法生成的折线路径的序列点作为Bezier曲线的控制点,得出更符合实际应用的平滑曲线路径．结果表明,本文算法能够在不同规模和复杂程度的环境中高效运行,且收敛速度更快、路径更短．本文算法在移动机器人的路径规划问题领域具有一定的可行性与优越性,今后将进一步运用至三维动态环境．