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

范柄堯，張春美

(太原科技大學(xué)電子信息工程學(xué)院，太原 030024)

移動機器人是指在有障礙物存在的情況下通過環(huán)境感知以及行為規(guī)劃控制等方式自主地向目標移動的一類機器人[1]。移動機器人路徑規(guī)劃的目的有以下兩點：1)通過算法找到機器人從當(dāng)前位置移動到目標位置的一條不與障礙物發(fā)生碰撞最優(yōu)路徑；2)通過算法找到的機器人運動路徑要符合機器人擬真運動特性，即所行路徑要盡量平滑，拐彎幅度要小等[2]。目前，移動機器人全局路徑規(guī)劃問題得到學(xué)者的廣泛關(guān)注，針對不同的路徑規(guī)劃問題提出相應(yīng)的求解方案[3-4]。人工勢場法是指環(huán)境中存在一種虛擬的勢場力影響機器人的運動，由Khatib[5]首次提出，由于其結(jié)構(gòu)簡單、直觀等優(yōu)點，在機器人運動軌跡優(yōu)化和避障等方面得到了廣泛的運用，但存在目標點不可達或陷入局部極小點而停止運動問題。文獻[6]通過設(shè)置虛擬目標點解決人工勢場法局部極小點問題來對機器人路徑問題進行規(guī)劃,但該方法并沒有得到最短路徑。文獻[7]引入速度矢量和距離調(diào)節(jié)因子改進引力和斥力函數(shù)，并采用模糊控制方法調(diào)節(jié)斥力場系數(shù)來解決人工勢場法目標不可達問題，但引入速度矢量后并沒有考慮速度改變時加速度對路徑規(guī)劃問題的影響。差分進化 (Differential Evolution，DE)算法[8]是由Storn和Price提出的一種基于種群的智能優(yōu)化算法，主要解決連續(xù)領(lǐng)域的優(yōu)化問題。該算法在全局、并行搜索過程中具有魯棒性強，操作原理簡單以及尋優(yōu)性能良好等優(yōu)點，已經(jīng)成為進化領(lǐng)域的研究熱點[9-12]。

鑒于差分進化算法在連續(xù)域的突出表現(xiàn)，本文將其與人工勢場法相結(jié)合設(shè)計混合差分進化算法，用于解決移動機器人的無碰撞最短路徑規(guī)劃問題。首先，針對差分進化算法的變異因子采用適應(yīng)性調(diào)節(jié)的方式，使變異因子能夠根據(jù)實際優(yōu)化過程進行適應(yīng)性調(diào)節(jié)以滿足優(yōu)化過程中對變異因子的需求。同時針對差分進化算法交叉操作中產(chǎn)生的不可行解利用人工勢場法進行修正，并提出相應(yīng)的修正策略。實驗結(jié)果顯示，針對障礙物數(shù)量不同的情況，所提混合差分進化算法在收斂性及解的質(zhì)量方面均能得到滿意效果[13-14]。

1 移動機器人路徑規(guī)劃問題描述

1.1 問題模型

針對移動機器人路徑規(guī)劃問題，設(shè)計使移動機器人從起始點到目標點的路徑模型。本文將移動機器人縮小為一個質(zhì)點，將各個障礙物設(shè)置成不同半徑的圓，移動機器人運行的最短無碰撞路徑模型如下：

(1)

S.t.

(2)

(3)

Sdk=Rk+δ

(4)

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

(5)

上式中，f表示機器人運行的最短無碰撞路徑；設(shè)起始位置坐標為(x0,y0)，目標坐標為(xn+1,yn+1)，x1，x2，…xn為將x0和xn+1關(guān)于x軸n+1等分后的n個點，b為x0和xn+1的n+1等分值。y1，y2，…yn為x1，x2，…xn所對應(yīng)的路徑點；考慮到相鄰兩路徑點連線可能與障礙物相交而形成不可行路徑，使用懲罰函數(shù)ωi處理這種情況。ε>1為懲罰因子，可以使不可行路徑變長；Ski表示障礙物k的圓心到相鄰兩路徑點yiyi-1所在直線的垂直距離；Sdk表示第k個障礙物的影響范圍，Rk為第k個障礙物的半徑，δ=rand(0,0.1)為一個較小的數(shù)；Sk表示線段yiyi-1是否與第k個障礙物相交，相交Sk=0，否則Sk=1.

1.2 路徑編碼

針對機器人路徑規(guī)劃問題，本文采用路徑點序列編碼方式，將平面坐標軸中二維路徑點坐標簡化為一維的y軸坐標。具體操作為將初始點Y0(x0,y0)與終止點Yn+1(xn+1,yn+1)作等分x軸的n+2條垂線，由于x0和xn+1是已知的初始點與終止點在x軸方向的橫坐標值，x1,x2,…,xn為將x0和xn+1n+1等分的關(guān)于x軸的值，由于其中任意橫坐標點xi=x0+i·b是已知的，此時只需要確定對應(yīng)的y軸坐標y1,y2,…,yn的值即可確定機器人在每一路徑點的具體位置。將包括初始點和目標點在內(nèi)的n+2個坐標點連接即構(gòu)成一條機器人路徑。其中n個坐標點y1,y2,…,yn形成一個個體，每個個體代表一條路徑，在進化過程中，得到的最優(yōu)個體為不經(jīng)過障礙物的最短路徑。

2 混合差分進化算法的路徑規(guī)劃

2.1 差分進化算法

2.1.1 種群初始化

差分進化算法的初始化種群設(shè)置如下為：yi=(yi,1,yi,2,···,yi,D)，i=(1,2,···,NP)，其中NP為種群規(guī)模，D為維數(shù)(在本文中，D為路徑點個數(shù)n，即D=n)。初始種群中初始個體的選擇會影響子代個體的性能以及算法收斂速度，當(dāng)機器人的初始點和目標點分別為(x0,y0)和(xn+1,yn+1)時，算法初始個體的選擇方式如下，計算起始點與目標點關(guān)于x軸的長度為L=|xn+1-x0|，比較y0和yn+1的大小，兩者中數(shù)值較大的為ymax，數(shù)值較小的為ymin.則算法種群上界為ymax+L/2，種群下界為ymin-L/2.在確定好x1，x2，…xn后，即可依次隨機選取節(jié)點形成路徑點。

2.1.2 變異操作

DE算法的變異策略較多，本文采用的變異方式為DE/rand/1，此變異操作是指在每一代種群中選擇三個互異的個體yr1,g、yr2,g和yr3,g，把其中兩個個體yr2,g和yr3,g進行差分處理并經(jīng)過縮放因子F(0

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

(6)

其中g(shù)為進化代數(shù)，r1≠r2≠r3≠i且i=(1,2,…,NP)，F(xiàn)為縮放因子。

在差分進化算法中，F(xiàn)的作用[13]是對種群內(nèi)每一個體所對應(yīng)的的差分變異向量進行縮放，確定當(dāng)前個體的搜索范圍。為了避免早熟現(xiàn)象出現(xiàn)，借鑒文獻[14]的方式對F進行適應(yīng)性處理，使F在(0.5,1)內(nèi)隨機的取值，在算法初始時F取較大的值，保持個體多樣性，在算法后期F取接近0.5的值，保留優(yōu)良信息，避免最優(yōu)解遭到破壞，增加搜索到全局最優(yōu)解的概率，如式(7)所示。

F=Fmin+(Fmax-Fmin)·r

(7)

2.1.3 交叉操作

交叉操作通過對初始目標向量yi,j,g與變異向量vi,j,g進行交叉生成試驗向量ui,j,g，采用二項式交叉方式進行操作，試驗向量中至少有一個分量由變異向量產(chǎn)生。具體操作如式(8)所示：

(8)

其中j=1,2,…,D,CR∈(0,1)為交叉率，jrand為[1,D]內(nèi)隨機選擇的整數(shù)。

2.1.4 選擇操作

為產(chǎn)生下一代種群，根據(jù)目標向量yi,g和試驗向量ui,g的適應(yīng)值f(·)來選擇最優(yōu)個體，具體操作如式(9)所示：

(9)

式中yi,g+1為下一代的目標向量。

2.2 混合人工勢場-差分進化算法

差分進化算法在障礙物數(shù)目增多時不能有效得到全局最優(yōu)路徑且算法收斂速度會變緩慢，這是因為試驗向量ui,j,g進化到第g代時，通過交叉操作產(chǎn)生的交叉種群中的第i個個體的第j個元素(其中每個個體i各代表一條路徑，元素j代表這條路徑中的第j個路徑點)為劣質(zhì)元素(即不可行路徑點)，如圖1.

在圖1中，路徑點yi,j在障礙物半徑范圍內(nèi)，此路徑點yi,j-1到y(tǒng)i,j的路徑為不可行路徑，需要對不可行路徑點yi,j進行處理，使得算法在找到真正全局最優(yōu)路徑的同時加快算法收斂速度。

圖1 不可行路徑
Fig.1 Infeasible path

針對差分進化算法在交叉操作過程中產(chǎn)生的不可行路徑點，采用路徑修正策略將此不可行點移動到障礙物影響范圍外，通過人工勢場法對此不可行路徑點的上一路徑點進行受力分析，確定不可行路徑點的移動方向，從而提高算法的尋優(yōu)能力。混合人工勢場-差分進化算法流程如圖2.

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

2.3 不可行路徑點修正策略

人工勢場法的基本思想是環(huán)境中存在一種虛擬的勢場力會影響機器人的運動狀態(tài)。其中各個障礙物對機器人產(chǎn)生的斥力和目標點對機器人產(chǎn)生的引力所形成的的合力控制機器人下一步的運動。假設(shè)環(huán)境中機器人的當(dāng)前位置坐標為Y(xr,yr)，目標點位置Yn+1(xn+1,yn+1)，此時機器人所受到的合力為F=FG+F0，其中吸引力FG和斥力F0分別為機器人所受到引力場勢函數(shù)和斥力場勢函數(shù)的負梯度。

采用改進人工勢場法對DE算法產(chǎn)生的不可行路徑點進行優(yōu)化處理，假設(shè)某一障礙物k圓心為Yk(xk，yk)，半徑為rk，陷入障礙物k的不可行路徑點坐標為Yi(xi，yi)，此不可行路徑點的上一點坐標為Yi-1(xi-1，yi-1)，目標點G坐標為Yn+1(xn+1，yn+1)。根據(jù)人工勢場法，機器人每一步的位置都由在上一步位置所受引力和斥力的合力來決定，故欲修正不可行路徑點Yi， 需要對機器人在Yi-1位置的受力情況進行分析：

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

(10)

(11)

其中FG為目標對機器人在Yi-1位置的吸引力，F(xiàn)0為障礙物k對機器人在Yi-1位置的斥力，kρ為引力增益系數(shù)，η為斥力增益系數(shù)，ρ為機器人在Yi-1位置與障礙物k圓心距離，ρ0是一個常數(shù)，代表障礙物k影響的最大距離范圍。

此時機器人在Yi-1位置所受合力F為：

F=F0+FG

(12)

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

(13)

其中,yk為障礙物k的縱坐標值；a為控制參數(shù)，若機器人在Yi-1位置經(jīng)人工勢場法得到下一位置的縱坐標Yf小于障礙物k的縱坐標值yk則a=-1，否則a=1；rk為障礙物k的半徑；α=rand(0,1)為逃離值。

3 實驗仿真

針對移動機器人無碰撞最短路徑規(guī)劃問題，將所提混合差分進化算法與基本差分進化算法(DE/rand/1/bin)進行仿真實驗，為了保證測試公平性，兩種算法的運行環(huán)境和參數(shù)設(shè)置保持一致，具體設(shè)置如下：

運行環(huán)境設(shè)置：①環(huán)境1中障礙物為2個半徑為1，坐標原點為(2，-0.5)、(8，0.5)的圓；②環(huán)境2中障礙物為5個半徑為1，坐標原點為(2，0.5)、(2，-0.5)、(4，2)、(4，-2)和(6，0)的圓；③環(huán)境3中障礙物為6個半徑為1，坐標原點為(2，0)、(4，2)、(4，-2)和(6，0.5)、(6，-0.5)和(7，2)的圓。機器人在三種環(huán)境中初始點坐標為(0，0)，目標點為(10，0).

參數(shù)設(shè)置：①針對差分進化算法，種群規(guī)模NP=10D，終止條件為NFE=5·103,根據(jù)文獻[14]，CR與F設(shè)置如下：CR=0.9，F(xiàn)min=0.5，F(xiàn)max=0.9；②針對人工勢場法，根據(jù)文獻[6]：kρ與η均為1，ρ0為2.

利用差分進化算法進行路徑規(guī)劃時，算法中每一個體的維數(shù)D和機器人路徑點數(shù)目有關(guān)，用不包括出發(fā)點和目標點的路徑點數(shù)量n表示(D=n)，路徑點數(shù)量n與路徑點間隔d有關(guān)，關(guān)系式如下：

(14)

其中x0為出發(fā)點橫坐標，xn+1為目標點橫坐標。

3.1 實例分析

表1 數(shù)值比較
Tab.1 Numerical comparison

基本DE混合DE人工勢場環(huán)境1max10.222110.222010.6059min10.222010.222010.6059mean10.222010.222010.6059std3.299e-67.425e-71.872e-15環(huán)境2max11.806410.777112.5021min11.805910.776612.5021mean11.806010.776712.5021std1.449e-41.440e-41.273e-9環(huán)境3max11.329211.129212.8739min11.286811.129212.8739mean11.315011.129212.8739std2.348e-11.872e-151.437e-7

在路徑點間隔d取0.5,算法運行環(huán)境及參數(shù)設(shè)置不變的情況下，將所提混合算法和基本DE以及人工勢場法在三種環(huán)境中單獨運行10次所得最優(yōu)值的數(shù)值進行比較結(jié)果見表1.

表1結(jié)果表明，在環(huán)境1中采用基本DE和混合DE均能得到相同的最小值和平均值，且均優(yōu)于人工勢場法，但混合DE的最大值和標準方差略優(yōu)于基本DE.而在環(huán)境2中，本文所提混合算法在最大值、最小值、平均值和標準方差方面明顯優(yōu)于基本DE和人工勢場法，證明此混合算法在不同環(huán)境下的尋優(yōu)性能優(yōu)于基本DE和人工勢場法。

(a) 環(huán)境1，基本DE

(b)環(huán)境1，混合DE

(c) 環(huán)境2，基本DE

(d)環(huán)境2，混合DE

(e) 環(huán)境3，基本DE

環(huán)境3，混合DE

圖4 最優(yōu)路徑及收斂比較圖
Fig.4 Comparison of optimal paths and convergence

圖4為基本DE與混合DE的最優(yōu)路徑圖，針對環(huán)境1，2種算法均能找到最優(yōu)路徑。如圖4(a)，(b)所示，針對環(huán)境2和環(huán)境3這種障礙物較多的情況，混合DE能夠找到優(yōu)于基本DE的最優(yōu)路徑。這是因為在混合DE中加入了修正策略，使得算法得到改進，混合DE從第4個路徑點開始能夠找到全局最優(yōu)路徑，而基本DE從第4個路徑點開始只能找到次優(yōu)路徑，此實例分析證明d取0.5時，本文所提混合DE在不同復(fù)雜環(huán)境下均能得到優(yōu)于基本DE的最優(yōu)路徑。

3.2 數(shù)值與收斂性比較

為了測試本文所提混合算法的有效性，將其在不同路徑點間隔(d取0.2，0.5，1.0，1.5)及不同環(huán)境下與基本差分進化算法進行比較。表2給出了2種算法分別在環(huán)境1和環(huán)境2中以及在不同路徑點間隔(d取0.2，0.5，1.0，1.5)條件下的優(yōu)化結(jié)果。每種情況均運行10次，所取得最大值、最小值、平均值和標準方差見表2.

表2d取不同值時數(shù)值比較
Tab.2 Numerical comparisons whendtakes different values

環(huán)境1環(huán)境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結(jié)果顯示，在環(huán)境1中，d=0.5，d=1.0和d=1.5時，混合DE所取得的最大值、最小值、平均值和標準方差與基本DE基本相當(dāng)，而d=0.2時混合DE所得到的最大值、最小值、平均值和標準方差優(yōu)于基本DE.環(huán)境2中，針對最大值，d=0.2，d=0.5時，混合DE得到的值優(yōu)于基本DE，d=1.0，d=1.5時，混合DE所得到的值與基本DE相等。針對最小值，除了d=1.5時兩種算法取得的值相等之外，其他情況下混合DE得到的值均優(yōu)于基本DE.對于平均值和標準方差，混合DE在不同路徑點間隔下得到的值均優(yōu)于基本DE.以上結(jié)果充分說明，混合DE更適合于求解環(huán)境較為復(fù)雜情況之下的路徑規(guī)劃問題。

為了測試所提混合算法的收斂性能，將其與基本DE在不同路徑點間隔條件下對環(huán)境1和環(huán)境2進行優(yōu)化比較，將2種算法在上述情況下各自單獨運行10次，記錄每次優(yōu)化結(jié)果中的11個點，取11個點各自的平均值構(gòu)成收斂曲線。算法的收斂性能比較圖如圖5.

由圖5可知，在環(huán)境1中，對于d取0.2，0.5，1.0和 1.5，混合DE都有較好的收斂性能，且在d取1.0和1.5時混合算法在較小的計算次數(shù)就能尋求到較好的解，d取0.5時混合DE在計算次數(shù)較小時開始收斂，且收斂速度優(yōu)于基本DE.在環(huán)境2中，對于d取0.5，1.0和 1.5，混合DE不僅能搜索到最優(yōu)解，而且具有良好的收斂速度。在環(huán)境1和環(huán)境2中，d取0.2時，混合DE在到達最大計算次數(shù)5·103時，仍具有繼續(xù)尋求最優(yōu)解的能力。

圖5 不同環(huán)境及間隔點下算法收斂性比較
Fig.5 Convergence comparisons of algorithms under different environments and intervals

由上述數(shù)值比較和收斂性分析可知，針對不同環(huán)境，混合算法能取得優(yōu)于基本差分進化算法和人工勢場法的解；針對不同環(huán)境和路徑點間隔，混合算法與基本DE相比，不僅具有良好的收斂性能，而且能搜索到高質(zhì)量的解，是一種有效的路徑規(guī)劃方法。

4 結(jié)束語

本文提出了一種人工勢場-差分進化混合算法用于解決移動機器人在復(fù)雜環(huán)境下的無碰撞最短路徑規(guī)劃問題。通過在DE算法中加入人工勢場法對DE算法運行過程中產(chǎn)生的不可行路徑點進行修正。實驗結(jié)果顯示，混合差分進化算法可以獲得很好的收斂性能以及高質(zhì)量的解，有效解決移動機器人在復(fù)雜環(huán)境下的路徑尋優(yōu)問題。