移动机器人路径规划的混合差分进化算法

范柄尧，张春美

(太原科技大学电子信息工程学院，太原 030024)

移动机器人是指在有障碍物存在的情况下通过环境感知以及行为规划控制等方式自主地向目标移动的一类机器人[1]。移动机器人路径规划的目的有以下两点：1)通过算法找到机器人从当前位置移动到目标位置的一条不与障碍物发生碰撞最优路径；2)通过算法找到的机器人运动路径要符合机器人拟真运动特性，即所行路径要尽量平滑，拐弯幅度要小等[2]。目前，移动机器人全局路径规划问题得到学者的广泛关注，针对不同的路径规划问题提出相应的求解方案[3-4]。人工势场法是指环境中存在一种虚拟的势场力影响机器人的运动，由Khatib[5]首次提出，由于其结构简单、直观等优点，在机器人运动轨迹优化和避障等方面得到了广泛的运用，但存在目标点不可达或陷入局部极小点而停止运动问题。文献[6]通过设置虚拟目标点解决人工势场法局部极小点问题来对机器人路径问题进行规划,但该方法并没有得到最短路径。文献[7]引入速度矢量和距离调节因子改进引力和斥力函数，并采用模糊控制方法调节斥力场系数来解决人工势场法目标不可达问题，但引入速度矢量后并没有考虑速度改变时加速度对路径规划问题的影响。差分进化 (Differential Evolution，DE)算法[8]是由Storn和Price提出的一种基于种群的智能优化算法，主要解决连续领域的优化问题。该算法在全局、并行搜索过程中具有鲁棒性强，操作原理简单以及寻优性能良好等优点，已经成为进化领域的研究热点[9-12]。

鉴于差分进化算法在连续域的突出表现，本文将其与人工势场法相结合设计混合差分进化算法，用于解决移动机器人的无碰撞最短路径规划问题。首先，针对差分进化算法的变异因子采用适应性调节的方式，使变异因子能够根据实际优化过程进行适应性调节以满足优化过程中对变异因子的需求。同时针对差分进化算法交叉操作中产生的不可行解利用人工势场法进行修正，并提出相应的修正策略。实验结果显示，针对障碍物数量不同的情况，所提混合差分进化算法在收敛性及解的质量方面均能得到满意效果[13-14]。

1 移动机器人路径规划问题描述

1.1 问题模型

针对移动机器人路径规划问题，设计使移动机器人从起始点到目标点的路径模型。本文将移动机器人缩小为一个质点，将各个障碍物设置成不同半径的圆，移动机器人运行的最短无碰撞路径模型如下：

(1)

S.t.

(2)

(3)

Sdk=Rk+δ

(4)

b=(xn+1-x0)/(n+1)

(5)

上式中，f表示机器人运行的最短无碰撞路径；设起始位置坐标为(x0,y0)，目标坐标为(xn+1,yn+1)，x1，x2，…xn为将x0和xn+1关于x轴n+1等分后的n个点，b为x0和xn+1的n+1等分值。y1，y2，…yn为x1，x2，…xn所对应的路径点；考虑到相邻两路径点连线可能与障碍物相交而形成不可行路径，使用惩罚函数ωi处理这种情况。ε>1为惩罚因子，可以使不可行路径变长；Ski表示障碍物k的圆心到相邻两路径点yiyi-1所在直线的垂直距离；Sdk表示第k个障碍物的影响范围，Rk为第k个障碍物的半径，δ=rand(0,0.1)为一个较小的数；Sk表示线段yiyi-1是否与第k个障碍物相交，相交Sk=0，否则Sk=1.

1.2 路径编码

针对机器人路径规划问题，本文采用路径点序列编码方式，将平面坐标轴中二维路径点坐标简化为一维的y轴坐标。具体操作为将初始点Y0(x0,y0)与终止点Yn+1(xn+1,yn+1)作等分x轴的n+2条垂线，由于x0和xn+1是已知的初始点与终止点在x轴方向的横坐标值，x1,x2,…,xn为将x0和xn+1n+1等分的关于x轴的值，由于其中任意横坐标点xi=x0+i·b是已知的，此时只需要确定对应的y轴坐标y1,y2,…,yn的值即可确定机器人在每一路径点的具体位置。将包括初始点和目标点在内的n+2个坐标点连接即构成一条机器人路径。其中n个坐标点y1,y2,…,yn形成一个个体，每个个体代表一条路径，在进化过程中，得到的最优个体为不经过障碍物的最短路径。

2 混合差分进化算法的路径规划

2.1 差分进化算法

2.1.1 种群初始化

差分进化算法的初始化种群设置如下为：yi=(yi,1,yi,2,···,yi,D)，i=(1,2,···,NP)，其中NP为种群规模，D为维数(在本文中，D为路径点个数n，即D=n)。初始种群中初始个体的选择会影响子代个体的性能以及算法收敛速度，当机器人的初始点和目标点分别为(x0,y0)和(xn+1,yn+1)时，算法初始个体的选择方式如下，计算起始点与目标点关于x轴的长度为L=|xn+1-x0|，比较y0和yn+1的大小，两者中数值较大的为ymax，数值较小的为ymin.则算法种群上界为ymax+L/2，种群下界为ymin-L/2.在确定好x1，x2，…xn后，即可依次随机选取节点形成路径点。

2.1.2 变异操作

DE算法的变异策略较多，本文采用的变异方式为DE/rand/1，此变异操作是指在每一代种群中选择三个互异的个体yr1,g、yr2,g和yr3,g，把其中两个个体yr2,g和yr3,g进行差分处理并经过缩放因子F(0

vi,g=yr1,g+F·(yr2,g-yr3,g)

(6)

其中g为进化代数，r1≠r2≠r3≠i且i=(1,2,…,NP)，F为缩放因子。

在差分进化算法中，F的作用[13]是对种群内每一个体所对应的的差分变异向量进行缩放，确定当前个体的搜索范围。为了避免早熟现象出现，借鉴文献[14]的方式对F进行适应性处理，使F在(0.5,1)内随机的取值，在算法初始时F取较大的值，保持个体多样性，在算法后期F取接近0.5的值，保留优良信息，避免最优解遭到破坏，增加搜索到全局最优解的概率，如式(7)所示。

F=Fmin+(Fmax-Fmin)·r

(7)

2.1.3 交叉操作

交叉操作通过对初始目标向量yi,j,g与变异向量vi,j,g进行交叉生成试验向量ui,j,g，采用二项式交叉方式进行操作，试验向量中至少有一个分量由变异向量产生。具体操作如式(8)所示：

(8)

其中j=1,2,…,D,CR∈(0,1)为交叉率，jrand为[1,D]内随机选择的整数。

2.1.4 选择操作

为产生下一代种群，根据目标向量yi,g和试验向量ui,g的适应值f(·)来选择最优个体，具体操作如式(9)所示：

(9)

式中yi,g+1为下一代的目标向量。

2.2 混合人工势场-差分进化算法

差分进化算法在障碍物数目增多时不能有效得到全局最优路径且算法收敛速度会变缓慢，这是因为试验向量ui,j,g进化到第g代时，通过交叉操作产生的交叉种群中的第i个个体的第j个元素(其中每个个体i各代表一条路径，元素j代表这条路径中的第j个路径点)为劣质元素(即不可行路径点)，如图1.

在图1中，路径点yi,j在障碍物半径范围内，此路径点yi,j-1到yi,j的路径为不可行路径，需要对不可行路径点yi,j进行处理，使得算法在找到真正全局最优路径的同时加快算法收敛速度。

图1 不可行路径
Fig.1 Infeasible path

针对差分进化算法在交叉操作过程中产生的不可行路径点，采用路径修正策略将此不可行点移动到障碍物影响范围外，通过人工势场法对此不可行路径点的上一路径点进行受力分析，确定不可行路径点的移动方向，从而提高算法的寻优能力。混合人工势场-差分进化算法流程如图2.

图2 算法流程图
Fig.2 Algorithm flow chart

2.3 不可行路径点修正策略

人工势场法的基本思想是环境中存在一种虚拟的势场力会影响机器人的运动状态。其中各个障碍物对机器人产生的斥力和目标点对机器人产生的引力所形成的的合力控制机器人下一步的运动。假设环境中机器人的当前位置坐标为Y(xr,yr)，目标点位置Yn+1(xn+1,yn+1)，此时机器人所受到的合力为F=FG+F0，其中吸引力FG和斥力F0分别为机器人所受到引力场势函数和斥力场势函数的负梯度。

采用改进人工势场法对DE算法产生的不可行路径点进行优化处理，假设某一障碍物k圆心为Yk(xk，yk)，半径为rk，陷入障碍物k的不可行路径点坐标为Yi(xi，yi)，此不可行路径点的上一点坐标为Yi-1(xi-1，yi-1)，目标点G坐标为Yn+1(xn+1，yn+1)。根据人工势场法，机器人每一步的位置都由在上一步位置所受引力和斥力的合力来决定，故欲修正不可行路径点Yi， 需要对机器人在Yi-1位置的受力情况进行分析：

FG=-kρ(Yi-1-Yn+1)

(10)

(11)

其中FG为目标对机器人在Yi-1位置的吸引力，F0为障碍物k对机器人在Yi-1位置的斥力，kρ为引力增益系数，η为斥力增益系数，ρ为机器人在Yi-1位置与障碍物k圆心距离，ρ0是一个常数，代表障碍物k影响的最大距离范围。

此时机器人在Yi-1位置所受合力F为：

F=F0+FG

(12)

图3 修正策略示意图
Fig.3 Sketch map of correction strategy

(13)

其中,yk为障碍物k的纵坐标值；a为控制参数，若机器人在Yi-1位置经人工势场法得到下一位置的纵坐标Yf小于障碍物k的纵坐标值yk则a=-1，否则a=1；rk为障碍物k的半径；α=rand(0,1)为逃离值。

3 实验仿真

针对移动机器人无碰撞最短路径规划问题，将所提混合差分进化算法与基本差分进化算法(DE/rand/1/bin)进行仿真实验，为了保证测试公平性，两种算法的运行环境和参数设置保持一致，具体设置如下：

运行环境设置：①环境1中障碍物为2个半径为1，坐标原点为(2，-0.5)、(8，0.5)的圆；②环境2中障碍物为5个半径为1，坐标原点为(2，0.5)、(2，-0.5)、(4，2)、(4，-2)和(6，0)的圆；③环境3中障碍物为6个半径为1，坐标原点为(2，0)、(4，2)、(4，-2)和(6，0.5)、(6，-0.5)和(7，2)的圆。机器人在三种环境中初始点坐标为(0，0)，目标点为(10，0).

参数设置：①针对差分进化算法，种群规模NP=10D，终止条件为NFE=5·103,根据文献[14]，CR与F设置如下：CR=0.9，Fmin=0.5，Fmax=0.9；②针对人工势场法，根据文献[6]：kρ与η均为1，ρ0为2.

利用差分进化算法进行路径规划时，算法中每一个体的维数D和机器人路径点数目有关，用不包括出发点和目标点的路径点数量n表示(D=n)，路径点数量n与路径点间隔d有关，关系式如下：

(14)

其中x0为出发点横坐标，xn+1为目标点横坐标。

3.1 实例分析

表1 数值比较
Tab.1 Numerical comparison

基本DE混合DE人工势场环境1max10.222110.222010.6059min10.222010.222010.6059mean10.222010.222010.6059std3.299e-67.425e-71.872e-15环境2max11.806410.777112.5021min11.805910.776612.5021mean11.806010.776712.5021std1.449e-41.440e-41.273e-9环境3max11.329211.129212.8739min11.286811.129212.8739mean11.315011.129212.8739std2.348e-11.872e-151.437e-7

在路径点间隔d取0.5,算法运行环境及参数设置不变的情况下，将所提混合算法和基本DE以及人工势场法在三种环境中单独运行10次所得最优值的数值进行比较结果见表1.

表1结果表明，在环境1中采用基本DE和混合DE均能得到相同的最小值和平均值，且均优于人工势场法，但混合DE的最大值和标准方差略优于基本DE.而在环境2中，本文所提混合算法在最大值、最小值、平均值和标准方差方面明显优于基本DE和人工势场法，证明此混合算法在不同环境下的寻优性能优于基本DE和人工势场法。

(a) 环境1，基本DE

(b)环境1，混合DE

(c) 环境2，基本DE

(d)环境2，混合DE

(e) 环境3，基本DE

环境3，混合DE

图4 最优路径及收敛比较图
Fig.4 Comparison of optimal paths and convergence

图4为基本DE与混合DE的最优路径图，针对环境1，2种算法均能找到最优路径。如图4(a)，(b)所示，针对环境2和环境3这种障碍物较多的情况，混合DE能够找到优于基本DE的最优路径。这是因为在混合DE中加入了修正策略，使得算法得到改进，混合DE从第4个路径点开始能够找到全局最优路径，而基本DE从第4个路径点开始只能找到次优路径，此实例分析证明d取0.5时，本文所提混合DE在不同复杂环境下均能得到优于基本DE的最优路径。

3.2 数值与收敛性比较

为了测试本文所提混合算法的有效性，将其在不同路径点间隔(d取0.2，0.5，1.0，1.5)及不同环境下与基本差分进化算法进行比较。表2给出了2种算法分别在环境1和环境2中以及在不同路径点间隔(d取0.2，0.5，1.0，1.5)条件下的优化结果。每种情况均运行10次，所取得最大值、最小值、平均值和标准方差见表2.

表2d取不同值时数值比较
Tab.2 Numerical comparisons whendtakes different values

环境1环境2基本DE混合DE基本DE混合DEmaxd=0.214.085211.209912.727012.3386d=0.510.222110.222011.808610.7771d=1.010.228710.228711.846611.8486d=1.510.285010.285011.935411.9354mind=0.212.490210.506510.991210.8528d=0.510.222010.222011.805910.7766d=1.010.228710.228710.843210.8428d=1.510.285010.285010.996310.9963meand=0.213.251610.858411.531811.3411d=0.510.222010.222011.806010.7767d=1.010.228710.228711.545811.0443d=1.510.285010.285011.653711.6537stdd=0.25.030e-12.385e-15.505e-14.687e-1d=0.53.299e-67.425e-71.449e-41.440e-4d=1.03.48e-165.92e-164.844e-14.228e-1d=1.51.67e-161.77e-165.536e-13.959e-1

表2结果显示，在环境1中，d=0.5，d=1.0和d=1.5时，混合DE所取得的最大值、最小值、平均值和标准方差与基本DE基本相当，而d=0.2时混合DE所得到的最大值、最小值、平均值和标准方差优于基本DE.环境2中，针对最大值，d=0.2，d=0.5时，混合DE得到的值优于基本DE，d=1.0，d=1.5时，混合DE所得到的值与基本DE相等。针对最小值，除了d=1.5时两种算法取得的值相等之外，其他情况下混合DE得到的值均优于基本DE.对于平均值和标准方差，混合DE在不同路径点间隔下得到的值均优于基本DE.以上结果充分说明，混合DE更适合于求解环境较为复杂情况之下的路径规划问题。

为了测试所提混合算法的收敛性能，将其与基本DE在不同路径点间隔条件下对环境1和环境2进行优化比较，将2种算法在上述情况下各自单独运行10次，记录每次优化结果中的11个点，取11个点各自的平均值构成收敛曲线。算法的收敛性能比较图如图5.

由图5可知，在环境1中，对于d取0.2，0.5，1.0和 1.5，混合DE都有较好的收敛性能，且在d取1.0和1.5时混合算法在较小的计算次数就能寻求到较好的解，d取0.5时混合DE在计算次数较小时开始收敛，且收敛速度优于基本DE.在环境2中，对于d取0.5，1.0和 1.5，混合DE不仅能搜索到最优解，而且具有良好的收敛速度。在环境1和环境2中，d取0.2时，混合DE在到达最大计算次数5·103时，仍具有继续寻求最优解的能力。

图5 不同环境及间隔点下算法收敛性比较
Fig.5 Convergence comparisons of algorithms under different environments and intervals

由上述数值比较和收敛性分析可知，针对不同环境，混合算法能取得优于基本差分进化算法和人工势场法的解；针对不同环境和路径点间隔，混合算法与基本DE相比，不仅具有良好的收敛性能，而且能搜索到高质量的解，是一种有效的路径规划方法。

4 结束语

本文提出了一种人工势场-差分进化混合算法用于解决移动机器人在复杂环境下的无碰撞最短路径规划问题。通过在DE算法中加入人工势场法对DE算法运行过程中产生的不可行路径点进行修正。实验结果显示，混合差分进化算法可以获得很好的收敛性能以及高质量的解，有效解决移动机器人在复杂环境下的路径寻优问题。