范柄堯，張春美

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

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

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

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

1.1 問題模型

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

(1)

S.t.

(2)

(3)

Sdk=Rk+δ

(4)

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

(5)

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

1.2 路徑編碼

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

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

2.1 差分進(jìn)化算法

2.1.1 種群初始化

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

2.1.2 變異操作

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

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

(6)

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

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

F=Fmin+(Fmax-Fmin)·r

(7)

2.1.3 交叉操作

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

(8)

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

2.1.4 選擇操作

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

(9)

式中yi,g+1為下一代的目標(biāo)向量。

2.2 混合人工勢場-差分進(jìn)化算法

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

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

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

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

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

2.3 不可行路徑點(diǎn)修正策略

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

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

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

(10)

(11)

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

此時(shí)機(jī)器人在Yi-1位置所受合力F為：

F=F0+FG

(12)

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

(13)

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

3 實(shí)驗(yàn)仿真

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

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

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

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

(14)

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

3.1 實(shí)例分析

表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

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

表1結(jié)果表明，在環(huán)境1中采用基本DE和混合DE均能得到相同的最小值和平均值，且均優(yōu)于人工勢場法，但混合DE的最大值和標(biāo)準(zhǔn)方差略優(yōu)于基本DE.而在環(huán)境2中，本文所提混合算法在最大值、最小值、平均值和標(biāo)準(zhǔn)方差方面明顯優(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)路徑。這是因?yàn)樵诨旌螪E中加入了修正策略，使得算法得到改進(jìn)，混合DE從第4個路徑點(diǎn)開始能夠找到全局最優(yōu)路徑，而基本DE從第4個路徑點(diǎn)開始只能找到次優(yōu)路徑，此實(shí)例分析證明d取0.5時(shí)，本文所提混合DE在不同復(fù)雜環(huán)境下均能得到優(yōu)于基本DE的最優(yōu)路徑。

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

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

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

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

由圖5可知，在環(huán)境1中，對于d取0.2，0.5，1.0和 1.5，混合DE都有較好的收斂性能，且在d取1.0和1.5時(shí)混合算法在較小的計(jì)算次數(shù)就能尋求到較好的解，d取0.5時(shí)混合DE在計(jì)算次數(shù)較小時(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時(shí)，混合DE在到達(dá)最大計(jì)算次數(shù)5·103時(shí)，仍具有繼續(xù)尋求最優(yōu)解的能力。

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

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

4 結(jié)束語

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