移動機器人路徑規劃的混合差分進化算法

范柄堯，張春美

(太原科技大學電子信息工程學院，太原 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算法運行過程中產生的不可行路徑點進行修正。實驗結果顯示，混合差分進化算法可以獲得很好的收斂性能以及高質量的解，有效解決移動機器人在復雜環境下的路徑尋優問題。