基于改進(jìn)蝙蝠算法和三次樣條插值的機(jī)器人路徑規(guī)劃

劉景森 吉宏遠(yuǎn) 李煜

近年來隨著智能化技術(shù)的迅速發(fā)展和產(chǎn)業(yè)智慧升級(jí)的不斷推進(jìn),智能移動(dòng)機(jī)器人在越來越多的領(lǐng)域里得到了廣泛應(yīng)用,如貨物搬運(yùn)、智慧生產(chǎn)、智能生活、異常環(huán)境探測(cè)、水下作業(yè)、太空探索等等[1?2].其中,移動(dòng)機(jī)器人路徑規(guī)劃是機(jī)器人研究領(lǐng)域的一項(xiàng)關(guān)鍵技術(shù).如,在執(zhí)行搶險(xiǎn)救災(zāi)、貨物搬運(yùn)等任務(wù)時(shí),采用較好的機(jī)器人路徑規(guī)劃技術(shù)可以提高機(jī)器人作業(yè)效率、減少機(jī)器人磨損,同時(shí)也可以節(jié)約人力資源,減小資金投入[3].國內(nèi)外學(xué)者已經(jīng)就移動(dòng)機(jī)器人路徑規(guī)劃問題做了大量的工作并取得了不少成果.如可視圖法[4]、自由空間法[5]、人工勢(shì)場法[6]、A*算法[7]、深度學(xué)習(xí)方法[8]、強(qiáng)化學(xué)習(xí)方法[9]等.但可視圖法的路徑是多個(gè)直線相連接,路徑不夠平滑,不易找出最優(yōu)路徑.自由空間法的復(fù)雜度與空間中障礙的數(shù)量成正相關(guān)關(guān)系,故而此方法不適用于復(fù)雜障礙空間.人工勢(shì)場法存在容易陷入局部最優(yōu)解和終點(diǎn)不可達(dá)的缺點(diǎn),而A* 算法存在著內(nèi)存開銷大、計(jì)算時(shí)間長等不足.深度學(xué)習(xí)方法存在工作空間不完全可觀察且較不穩(wěn)定的缺點(diǎn).強(qiáng)化學(xué)習(xí)方法在面對(duì)復(fù)雜環(huán)境時(shí),其狀態(tài)空間的尺寸會(huì)變得非常龐大,無法在較小資源中實(shí)現(xiàn)實(shí)時(shí)的路徑規(guī)劃.所以隨著環(huán)境系統(tǒng)復(fù)雜性及任務(wù)難度的增加,傳統(tǒng)的路徑規(guī)劃方法難以取得理想的效果.最近幾年,通過大量的研究和實(shí)驗(yàn)發(fā)現(xiàn),仿生智能優(yōu)化算法在求解機(jī)器人路徑規(guī)劃方面具有獨(dú)特的優(yōu)勢(shì),并且多種智能優(yōu)化算法已經(jīng)成功應(yīng)用于路徑規(guī)劃的搜索策略中,如蟻群算法[10]、人工魚群算法[11]、遺傳算法[12?13]、粒子群算法[14?15]等.遺傳算法容易產(chǎn)生很多含有障礙的無效路徑,影響了算法的效率.基本的蟻群算法存在搜索時(shí)間長,易于停滯等缺點(diǎn).因此,研究速度更快、環(huán)境適應(yīng)性更強(qiáng)、路徑規(guī)劃更優(yōu)的算法成為研究者們不斷追求的目標(biāo).

2010年,劍橋大學(xué)學(xué)者Yang[16]提出了一種新型的啟發(fā)式智能優(yōu)化算法— 蝙蝠算法.蝙蝠算法是模擬蝙蝠發(fā)出和接收超聲波來捕食而提出的.目前,蝙蝠算法已經(jīng)在交互測(cè)試[17]、反應(yīng)堆堆芯布置[18]、連續(xù)優(yōu)化問題[19]、車輛路徑規(guī)劃問題[20]、線性天線陣列失效校正[21]等方面得到了實(shí)際應(yīng)用.

目前在機(jī)器人路徑規(guī)劃中一般采用圓弧[5,8]、直線[4,6?7,9?15]來分段構(gòu)造和表示機(jī)器人的移動(dòng)路徑,這樣的表示方式使得機(jī)器人在移動(dòng)過程中轉(zhuǎn)折點(diǎn)較多,欠缺連續(xù)平滑性,出現(xiàn)急停、急轉(zhuǎn)情況時(shí),機(jī)器人移動(dòng)缺乏可靠性且易造成相關(guān)部件損壞.而三次樣條插值方法則是通過一系列基于三次多項(xiàng)式的插值區(qū)間,擬合出一條光滑曲線.用這種方法產(chǎn)生的機(jī)器人路徑曲線更為平滑,可以保證機(jī)器人在急停急轉(zhuǎn)時(shí)具有更好的動(dòng)力學(xué)特性,有著直線與圓弧擬合路徑無法比擬的優(yōu)越性.基于圓弧和直線的這些特點(diǎn),本文采用三次樣條插值曲線構(gòu)造和表示機(jī)器人移動(dòng)路徑.

為了探索出更好地解決機(jī)器人路徑規(guī)劃問題的方法,改善基本蝙蝠算法易陷入局部極值、尋優(yōu)精度不高、算法后期收斂速度較慢等缺點(diǎn),提高蝙蝠算法的尋優(yōu)精度和收斂速度,拓展其應(yīng)用領(lǐng)域,本文嘗試將蝙蝠算法的優(yōu)化思想和三次樣條插值方法相結(jié)合,從而求解機(jī)器人路徑規(guī)劃問題.首先,對(duì)基本蝙蝠算法進(jìn)行了改進(jìn),在算法的全局搜索階段,引入動(dòng)態(tài)擾動(dòng)系數(shù),擴(kuò)大蝙蝠種群的多樣性.在算法的局部搜索階段,對(duì)其隨機(jī)探索方式進(jìn)行改進(jìn),提高算法收斂精度.然后,采用反向?qū)W習(xí)選擇策略,進(jìn)一步平衡算法的全局勘探和局部挖掘能力.最后,把改進(jìn)后算法與三次樣條插值方法相結(jié)合,定義了以路徑結(jié)點(diǎn)為基礎(chǔ)的編碼方式,構(gòu)造了以求解移動(dòng)機(jī)器人繞避障礙和最短路徑為目標(biāo)的方法和適應(yīng)度函數(shù),求解機(jī)器人路徑規(guī)劃問題.通過在簡單和復(fù)雜障礙環(huán)境、單機(jī)器人和多機(jī)器人環(huán)境下進(jìn)行的路徑規(guī)劃實(shí)驗(yàn),測(cè)試對(duì)比結(jié)果表明,改進(jìn)算法對(duì)于求解機(jī)器人全局路徑規(guī)劃問題具有很好的可靠性和有效性.

1 基本蝙蝠算法

在基本蝙蝠算法中,每只蝙蝠都被看作是“無質(zhì)量、無大小”的粒子,都代表著解空間中的一個(gè)可行解.對(duì)于不同的適應(yīng)度函數(shù),每只蝙蝠都有相應(yīng)的函數(shù)值.并通過比較函數(shù)值確定當(dāng)前最優(yōu)個(gè)體.然后據(jù)此更新種群中各蝙蝠的頻率、速度、脈沖發(fā)射率、響度,不斷迭代進(jìn)化,靠近和產(chǎn)生當(dāng)前最優(yōu)解,最終找到全局最優(yōu)解.算法中每只蝙蝠的頻率、速度以及位置更新式為

其中,f i表示第i只蝙蝠發(fā)出的聲波頻率,fmax和fmin表示頻率的最大值和最小值.β是在[0,1]之間均勻分布的隨機(jī)數(shù).和分別表示第t代第i只蝙蝠的速度和位置.x?表示當(dāng)前最優(yōu)位置.

一旦蝙蝠發(fā)現(xiàn)獵物,即接近全局最優(yōu)解時(shí),便在當(dāng)前最優(yōu)個(gè)體附近使用局部搜索策略.此時(shí)由生成的均勻分布隨機(jī)數(shù)P作為判斷閾值,如果P>r i(第i只蝙蝠的脈沖發(fā)射率),則使用局部搜索策略,反之,則進(jìn)行全局搜索.局部搜索的位置更新式為

其中,ε為[?1,1] 上的均勻分布隨機(jī)數(shù).At是第t代所有蝙蝠響度的平均值.xold為當(dāng)前最優(yōu)個(gè)體.xnew是局部搜索后產(chǎn)生的新個(gè)體.蝙蝠在靠近獵物的過程中,隨著迭代次數(shù)的增加,響度At逐漸降低.同時(shí),脈沖發(fā)射速率r i不斷增加.其更新式為

其中,α和γ是常數(shù).對(duì)任意的0<α<1,γ>0,當(dāng)?shù)螖?shù)t趨于正無窮時(shí),響度趨于0,脈沖發(fā)射率趨于是初始脈沖發(fā)射率.

2 具有反向?qū)W習(xí)和正切隨機(jī)探索的蝙蝠算法PTRBA

與其他群智能算法一樣,蝙蝠算法在優(yōu)化過程中,種群的多樣性和算法的深度挖掘能力之間始終存在著矛盾.對(duì)標(biāo)準(zhǔn)蝙蝠算法的改進(jìn),其目的都是希望在加強(qiáng)算法局部搜索能力的同時(shí),保持種群的多樣性,防止算法在快速收斂的同時(shí)出現(xiàn)早熟收斂,本文改進(jìn)也是基于這一思想,即利用正切隨機(jī)探索機(jī)制在加強(qiáng)算法局部開采能力的同時(shí),依靠動(dòng)態(tài)擾動(dòng)系數(shù)和反向?qū)W習(xí)選擇機(jī)制提高蝙蝠種群的多樣性,擴(kuò)大蝙蝠的搜索范圍.下面詳細(xì)介紹具體改進(jìn)策略.

2.1 動(dòng)態(tài)擾動(dòng)系數(shù)

基本蝙蝠算法在全局搜索階段利用式(3) 進(jìn)行位置更新,其中的求解過程利用?x?是上一代蝙蝠位置到當(dāng)前最優(yōu)位置的距離,蝙蝠在每次進(jìn)行全局搜索時(shí),都要受到這個(gè)距離的直接牽引和約束,這樣的方式容易使蝙蝠種群進(jìn)行全局搜索時(shí)跳不出局部最優(yōu),算法極易陷入局部極值.針對(duì)這個(gè)問題,提出了一種動(dòng)態(tài)擾動(dòng)系數(shù)方法,在式(3) 中對(duì)上一代蝙蝠位置進(jìn)行擾動(dòng),改變其位置,擴(kuò)大蝙蝠種群捕食的靈活性,使得蝙蝠的全局搜索能力得到提高.動(dòng)態(tài)擾動(dòng)系數(shù)σ的計(jì)算如式(7) 所示,式(3) 的改進(jìn)如式(8) 所示.

其中,t是當(dāng)前迭代次數(shù),Tmax是最大迭代次數(shù).σ隨著迭代次數(shù)的增加而自適應(yīng)減小,在算法前期對(duì)上一代的蝙蝠位置擾動(dòng)力度較大,以此減輕x?對(duì)蝙蝠向更廣闊范圍探索的約束,擴(kuò)大蝙蝠種群的搜索范圍,在算法后期對(duì)上一代的蝙蝠位置擾動(dòng)力度較小,有利于提高算法的深度挖掘能力.κ為擾動(dòng)偏離因子,κ ∈[0.1,0.9] 經(jīng)多次實(shí)驗(yàn)反復(fù)測(cè)試當(dāng)時(shí)尋優(yōu)效果最佳,本文取值為0.5.betarnd() 為服從貝塔分布的隨機(jī)數(shù),其作用是對(duì)遞減的σ值進(jìn)行擾動(dòng),進(jìn)一步增強(qiáng)蝙蝠捕食的靈活性,增強(qiáng)算法全局搜索的開拓能力.

2.2 正切隨機(jī)探索機(jī)制

蝙蝠種群利用式(4) 進(jìn)行局部搜索,是以當(dāng)前最優(yōu)蝙蝠作為參考,向外進(jìn)行隨機(jī)搜索,式(4) 中的ε ∈[?1,1],是一個(gè)均勻隨機(jī)數(shù),這樣的均勻探索方式使算法在局部搜索階段易陷入盲目狀態(tài),不能較好地體現(xiàn)局部搜索的挖掘能力.針對(duì)這個(gè)問題受柯西分布函數(shù)[22]的啟發(fā),利用式(9)對(duì)算法在局部搜索階段的隨機(jī)方式進(jìn)行改進(jìn)

其中,r是[0,1]上的均勻分布隨機(jī)數(shù),的值有兩個(gè)分布特征:1) 主要分布在0 左右;2)會(huì)有極少一部分?jǐn)?shù)值較大的數(shù).特性1 使蝙蝠種群在當(dāng)前最優(yōu)值附近搜索,增強(qiáng)算法局部開采能力,特性2 使算法更容易跳出局部極值,從而使蝙蝠算法的局部尋優(yōu)機(jī)制更具策略性,而不只是盲目地隨機(jī)探索.

2.3 反向?qū)W習(xí)選擇策略

Tizhoosh 在文獻(xiàn)[23] 中給出反向?qū)W習(xí)的定義如下.

定義1.若x是定義在實(shí)數(shù)集R 上的一個(gè)區(qū)間[a,b] 的一個(gè)實(shí)數(shù),即x ∈[a,b],則x的反向解x1定義為

定義2.若P(x1,x2,···,xn) 是n維空間上的一個(gè)點(diǎn),x1,x2,···,xn為實(shí)數(shù),且xi ∈[ai,bi],則其反向解定義為

結(jié)合上述兩個(gè)定義,把反向?qū)W習(xí)策略運(yùn)用到蝙蝠算法的進(jìn)化機(jī)制中,把P(x1,x2,···,xn)看作是蝙蝠位置,依據(jù)定義2 得到其反向解,比較原蝙蝠位置和其反向解的適應(yīng)度函數(shù)值,若反向解的適應(yīng)度函數(shù)值優(yōu)于原蝙蝠位置的適應(yīng)度函數(shù)值,則用反向解代替原蝙蝠位置.反向?qū)W習(xí)選擇策略的引入,增強(qiáng)了蝙蝠種群的多樣性,進(jìn)一步解決了基本蝙蝠算法易陷入局部最優(yōu)的不足,更好地平衡了算法的全局搜索和深度挖掘能力.

3 PTRBA 基于三次樣條插值實(shí)現(xiàn)機(jī)器人路徑規(guī)劃

三次樣條插值是一種分段式插值方法,通過一系列基于三次多項(xiàng)式的插值點(diǎn)區(qū)間,形成一條光滑曲線.用三次樣條插值方法擬合出的機(jī)器人移動(dòng)路徑曲線更加平滑,這樣可以保證機(jī)器人在急?；蚣鞭D(zhuǎn)時(shí)有較好的動(dòng)力學(xué)特性,具有用直線與圓弧擬合移動(dòng)機(jī)器人路徑無法比擬的優(yōu)點(diǎn).本文將三次樣條插值方法融入改進(jìn)蝙蝠算法PTRBA (A bat algorithm with dynamic perturbation,tangent stochastic exploration and reverse learning selection mechanism) 中,用于求解機(jī)器人全局路徑規(guī)劃問題.

3.1 三次樣條插值

設(shè)在區(qū)間[a,b] 上取n+1 結(jié)點(diǎn)a=x0

1)s(x)∈C2[a,b];

2)s(xi)=fi,i=0,1,2,···,n;

3)在每個(gè)小區(qū)間[xi,xi+1] 上,s(x) 是三次多項(xiàng)式.則稱s(x) 為三次樣條插值函數(shù).

三次樣條插值函數(shù)是分段三次多項(xiàng)式,在每個(gè)小區(qū)間[xi,xi+1] 上可以寫成:s(x)=aix3+bix2+cix+di,i=0,1,2,···,n ?1.其中,ai,bi,ci,di為待定系數(shù),所以,s(x)共有4n個(gè)待定系數(shù).為了確定s(x),必須有對(duì)應(yīng)的4n個(gè)條件.由s(xi)=fi,i=0,1,2,···,n可知n+1個(gè)插值條件,由s(x)∈C2[a,b]可知,s(x)在區(qū)間[a,b]上二階連續(xù)可導(dǎo),可導(dǎo)必連續(xù),所以,s(x)的導(dǎo)數(shù)在區(qū)間[a,b] 上必然連續(xù),那么在n?1 個(gè)插值點(diǎn)處也必然連續(xù),即=i=1,2,···,n?1,共n ?1個(gè)條件.既然s(x)二階可導(dǎo),則s(x)必然一階可導(dǎo)且s(x)連續(xù),可導(dǎo)必連續(xù),可知:

可得2(n ?1) 個(gè)條件.到此為止,共有4n ?2 個(gè)條件.再補(bǔ)充兩個(gè)邊界條件就可以確定s(x),常用的邊界條件有以下3 種:

1) 給出兩個(gè)端點(diǎn)處的一階導(dǎo)數(shù)值;

2) 給出兩個(gè)端點(diǎn)處的二階導(dǎo)數(shù)值;

3)s(x) 是以b ?a為周期的函數(shù).

3.2 編碼

由上可知,三次樣條插值是一種分段式插值方法,段與段之間的交接處,稱為路徑結(jié)點(diǎn).段與段之間的樣條是不同的,而整個(gè)樣條曲線則是一階連續(xù)的,且在路徑結(jié)點(diǎn)處二階連續(xù),因此,分段樣條之間的方向也可能不同,路徑結(jié)點(diǎn)就代表了整個(gè)路徑的最大轉(zhuǎn)向次數(shù).即使在非常復(fù)雜的環(huán)境下,一般經(jīng)歷3 ～5 次轉(zhuǎn)向就能繞開所有障礙物.依此,本文以一條路徑上的所有結(jié)點(diǎn)作為一個(gè)蝙蝠個(gè)體的編碼.也就是說,一個(gè)蝙蝠個(gè)體代表了對(duì)應(yīng)路徑上的所有路徑結(jié)點(diǎn),即一條路徑上所有m個(gè)路徑結(jié)點(diǎn)的橫坐標(biāo)集合構(gòu)成了蝙蝠個(gè)體的m維橫坐標(biāo),相應(yīng)地,一條路徑上所有m個(gè)路徑結(jié)點(diǎn)的縱坐標(biāo)集合構(gòu)成了蝙蝠個(gè)體的m維縱坐標(biāo).

假設(shè)已知m個(gè)路徑結(jié)點(diǎn)的坐標(biāo)(xm1,ym1),(xm2,ym2),···,(xmm,ymm)以及起點(diǎn)和終點(diǎn)的坐標(biāo)(xs,ys),(xt,yt).在區(qū)間(xs,xm1,xm2,···,xmm,xt)和(ys,ym1,ym2,···,ymm,yt)上,通過三次樣條插值得到n個(gè)插值點(diǎn)的橫坐標(biāo)(x1,x2,···,x n) 和縱坐標(biāo)(y1,y2,···,yn).此時(shí),得到了n個(gè)插值點(diǎn).由路徑結(jié)點(diǎn)和插值點(diǎn)以及起點(diǎn)和終點(diǎn)組成的連線就是我們要求得機(jī)器人的路徑.

3.3 構(gòu)建適應(yīng)度函數(shù)

機(jī)器人路徑規(guī)劃要滿足兩個(gè)條件:1) 不能與障礙物發(fā)生碰撞;2) 路徑長度要盡可能短.本文就以滿足上述條件的無碰撞的路徑長度最短作為適應(yīng)度函數(shù)的評(píng)價(jià)標(biāo)準(zhǔn).

本文構(gòu)造的適應(yīng)度函數(shù)為

其中,(x i,yi)為第i個(gè)插值點(diǎn)的坐標(biāo).

η是一個(gè)標(biāo)志變量,其初始值設(shè)置為0.η的求值過程為

為了計(jì)算方便,可將障礙物設(shè)置為圓形表示,nobs是障礙的總個(gè)數(shù),xx為一條路徑上所有插值點(diǎn)橫坐標(biāo)的集合,yy是所有插值點(diǎn)縱坐標(biāo)的集合.(xobsk,yobsk) 為第k個(gè)障礙的圓心坐標(biāo),robsk為第k個(gè)障礙的半徑.式(14)是為了求出一條路徑上所有插值點(diǎn)到第k個(gè)障礙圓心的距離,這個(gè)距離稱為dk.式(15)是為了判斷路徑是否經(jīng)過第k個(gè)障礙,若路徑經(jīng)過第k個(gè)障礙,則集合θk中必存在有大于0 的數(shù).若路徑?jīng)]有通過任何一個(gè)障礙,則集合θk中的數(shù)都是0.式(16) 中mean(θk) 是集合θk中所有數(shù)的平均數(shù),η是一個(gè)累加值,即nobs個(gè)mean(θk) 的值相加之和,若所求得路徑?jīng)]有通過障礙物區(qū)域,則η=0.反之,η是一個(gè)大于0的數(shù).

3.4 算法流程

步驟1.根據(jù)具體環(huán)境確定路徑結(jié)點(diǎn)的個(gè)數(shù)m,確定插值點(diǎn)的個(gè)數(shù)n,確定機(jī)器人的起點(diǎn)(x s,ys)和終點(diǎn)(xt,yt),確定算法的最大迭代次數(shù)Tmax,蝙蝠的種群規(guī)模npop,速度vi,聲波響度Ai,脈沖發(fā)射速率r i,聲波頻率的最大值fmax和最小值fmin.

步驟2.初始化蝙蝠位置,每只蝙蝠位置坐標(biāo)形如[(xm1,xm2,···,xnmn),(ym1,ym2,···,ynmn)],(x m1,ym1),(xm2,ym2),···,(xmmn,ynmn)分別為m個(gè)路徑結(jié)點(diǎn)的坐標(biāo).并利用式(11),求出其反向解.

步驟3.利用三次樣條插值方法和(xs,xm1,xm2,···,xmm,xt),求出n個(gè)插值點(diǎn)的橫坐標(biāo)(x1,x2,···,xn).同理,可求出n個(gè)插值點(diǎn)的縱坐標(biāo)(y1,y2,···,yn).此時(shí),得出n個(gè)插值點(diǎn)的坐標(biāo)(x1,y1),(x2,y2),···,(xn,yn).

步驟4.利用式(13)計(jì)算出路徑長度,即n個(gè)插值點(diǎn)之間的距離.

步驟5.利用式(14)～(16) 判斷此路徑是否經(jīng)過障礙區(qū),并得出標(biāo)志變量η的值.

步驟6.利用式(12),計(jì)算適應(yīng)度函數(shù)的值.同理,求出其反向解的適應(yīng)度值.

步驟7.比較蝙蝠位置和其反向解的適應(yīng)度值.若后者小于前者,則用反向解代替原蝙蝠位置.

步驟8.利用式(1),(2),(8),(9) 分別對(duì)蝙蝠位置進(jìn)行更新,即得出更新后具有m個(gè)路徑結(jié)點(diǎn)坐標(biāo)的路徑.

步驟9.重復(fù)執(zhí)行步驟3 ～8,直到算法達(dá)到最大迭代次數(shù).

步驟10.得到并輸出最短路徑.

4 仿真實(shí)驗(yàn)與分析

為了驗(yàn)證本文算法在求解機(jī)器人路徑規(guī)劃問題上的有效性與可行性,在保證客觀、公正的前提下,將改進(jìn)算法PTRBA 與標(biāo)準(zhǔn)粒子群算法(Particle swarm optimization,PSO)、基本蝙蝠算法(Bat algorithm) 以及文獻(xiàn)[24] 中提出的改進(jìn)蝙蝠算法— 融合均勻變異與高斯變異的蝙蝠優(yōu)化算法(Uniform-Gaussian mutation bat algorithm,UGBA) 進(jìn)行實(shí)驗(yàn)對(duì)比分析,從而全面檢驗(yàn)PTRBA算法的尋優(yōu)性能.

4.1 實(shí)驗(yàn)環(huán)境及參數(shù)設(shè)置

為了保證算法比較的客觀和公平,PSO,BA,UGBA,PTRBA 算法均采用相同軟、硬件平臺(tái),運(yùn)行環(huán)境為Windows7、編程環(huán)境為MATLAB R2014a.仿真實(shí)驗(yàn)中,4 種算法的種群規(guī)模、最大迭代次數(shù)保持一致,即npop=150;Tmax=100.BA,UGBA,PTRBA 算法中的聲波響度、脈沖發(fā)射速率主要控制著算法的局部搜索能力,基于公正性,本文對(duì)以上兩個(gè)參數(shù)的設(shè)置與基本蝙蝠算法保持一致,即A0=0.25;r0=0.5.PSO算法中的學(xué)習(xí)因子c1,c2分別決定粒子個(gè)體經(jīng)驗(yàn)和群體經(jīng)驗(yàn)對(duì)粒子運(yùn)行軌跡的影響,在PSO 算法中,個(gè)體經(jīng)驗(yàn)和群體經(jīng)驗(yàn)有著同等重要的影響力,一般設(shè)置為c1=c2=1.5,本文采用同樣的取值.

4.2 單機(jī)器人系統(tǒng)的路徑規(guī)劃及算法尋優(yōu)性能分析

對(duì)于單機(jī)器人系統(tǒng),分別在簡單障礙環(huán)境和復(fù)雜障礙環(huán)境下,進(jìn)行路徑規(guī)劃對(duì)比實(shí)驗(yàn).在簡單環(huán)境下,設(shè)置障礙個(gè)數(shù)為6,路徑結(jié)點(diǎn)個(gè)數(shù)為3.在復(fù)雜環(huán)境下,設(shè)置障礙個(gè)數(shù)為11,路徑結(jié)點(diǎn)數(shù)設(shè)置為4.兩種環(huán)境下的插值點(diǎn)個(gè)數(shù)都設(shè)置為100.其具體實(shí)驗(yàn)結(jié)果分別如圖1、圖2、表1 和圖3、圖4、表2 所示.

圖1 簡單環(huán)境下4 種算法路徑規(guī)劃對(duì)比圖Fig.1 Comparison of four algorithm path planning in a simple environment

圖2 簡單環(huán)境下4 種算法迭代曲線對(duì)比圖Fig.2 Comparison of four algorithm iteration curves in a simple environment

圖3 復(fù)雜環(huán)境下4 種算法路徑規(guī)劃對(duì)比圖Fig.3 Comparison of four algorithm path planning in a complex environment

圖4 復(fù)雜環(huán)境下4 種算法迭代曲線對(duì)比圖Fig.4 Comparison of four algorithm iteration curves in a complex environment

從圖1 和圖3 中可以直觀地看出本文改進(jìn)算法PTRBA 所規(guī)劃出的機(jī)器人路徑最短,尤其是在復(fù)雜環(huán)境下,本文算法的求解效果更加明顯.這是因?yàn)樵谌炙阉麟A段,引入動(dòng)態(tài)擾動(dòng)系數(shù),增強(qiáng)了蝙蝠飛行的靈活性,提高算法尋優(yōu)能力.如圖2 和圖4 所示,算法在前期收斂速度并不是很快,但在第10 代左右時(shí),算法可以跳出局部極值,快速向最優(yōu)解靠近.這是因?yàn)樵诰植克阉麟A段,融入正切隨機(jī)探索機(jī)制,增強(qiáng)算法的局部開采能力和搜索策略性,使算法更容易跳出局部極值,從而提高了算法的尋優(yōu)精度.如表1 和表2 所示,是每個(gè)算法獨(dú)立運(yùn)行30 次所得出的路徑情況,可以看出本文算法PTRBA 求解出的路徑長度無論是最優(yōu)解、最差解還是平均值都是4 種算法中最短的且求解結(jié)果非常穩(wěn)定,這是因?yàn)榉聪驅(qū)W習(xí)策略進(jìn)一步平衡了算法全局勘探和局部挖掘能力,是算法所求路徑與其他算法相比更加穩(wěn)定.總體上,三種改進(jìn)機(jī)制相互配合,提高算法收斂速度和尋優(yōu)能力.

表1 簡單環(huán)境下4 種算法所求路徑長度比較Table 1 Comparison of path lengths obtained by four algorithms in a simple environment

表2 復(fù)雜環(huán)境下4 種算法所求路徑長度比較Table 2 Comparison of path length obtained by four algorithms in a complex environment

4.3 多機(jī)器人系統(tǒng)的路徑規(guī)劃及算法尋優(yōu)性能分析

與單機(jī)器人系統(tǒng)相比,多機(jī)器人路徑規(guī)劃問題更為復(fù)雜,它要求各個(gè)機(jī)器人之間不能發(fā)生碰撞.為滿足此要求,本文使用了一種基于人工障礙的多機(jī)器人路徑規(guī)劃方法[25?26],該方法可防止各條機(jī)器人路徑之間出現(xiàn)交叉現(xiàn)象,從而避免了各個(gè)機(jī)器人之間可能發(fā)生的碰撞.其具體過程如下:

步驟1.利用PTRBA 和三次樣條插值方法,規(guī)劃出第1 個(gè)機(jī)器人的路徑,然后,以此路徑上的m個(gè)路徑結(jié)點(diǎn)為圓心,人工虛擬出m個(gè)障礙.

步驟2.此時(shí),除了原來環(huán)境中障礙外,又人工虛擬出了m個(gè)障礙,形成了一個(gè)新的障礙環(huán)境.在此新環(huán)境下,規(guī)劃出第2 個(gè)機(jī)器人的路徑.由于第1個(gè)機(jī)器人的路徑上已經(jīng)人工設(shè)置了m個(gè)障礙,所以,第2 個(gè)機(jī)器人的路徑不會(huì)與第1 個(gè)機(jī)器人的路徑相交.以此類推,規(guī)劃出所有機(jī)器人的路徑.

本文仿真實(shí)驗(yàn)要求為3 個(gè)機(jī)器人規(guī)劃出無碰撞路徑,每條路徑上的路徑結(jié)點(diǎn)個(gè)數(shù)設(shè)置為3.分別在簡單環(huán)境和復(fù)雜環(huán)境下,進(jìn)行對(duì)比仿真實(shí)驗(yàn).在簡單環(huán)境下,設(shè)置障礙個(gè)數(shù)為4,在復(fù)雜環(huán)境下,設(shè)置障礙個(gè)數(shù)為9.兩種環(huán)境下的插值點(diǎn)個(gè)數(shù)都設(shè)置為100.其具體實(shí)驗(yàn)結(jié)果如下:

由圖5 ～8 和圖9 ～12 可以直觀地看出,本文改進(jìn)算法PTRBA 所規(guī)劃出的移動(dòng)機(jī)器人路徑很少出現(xiàn)不必要的曲折,這是因?yàn)槿炙阉麟A段的動(dòng)態(tài)擾動(dòng)系數(shù)和局部搜索階段的正切隨機(jī)探索機(jī)制,使蝙蝠種群快速向最優(yōu)解靠近,算法整體尋優(yōu)能力得到提高.

圖5 簡單環(huán)境下BA 算法所規(guī)劃路徑Fig.5 Planning path of BA algorithm in a simple environment

圖6 簡單環(huán)境下PSO 算法所規(guī)劃路徑Fig.6 Planning path of PSO algorithm in a simple environment

圖7 簡單環(huán)境下UGBA 算法所規(guī)劃路徑Fig.7 Planning path of UGBA algorithm in a simple environment

圖8 簡單環(huán)境下PTRBA 算法所規(guī)劃路徑Fig.8 Planning path of PTRBA algorithm in a simple environment

圖9 復(fù)雜環(huán)境下BA 算法所規(guī)劃路徑Fig.9 Planning path of BA algorithm in a complex environment

圖10 復(fù)雜環(huán)境下PSO 算法所規(guī)劃路徑Fig.10 Planning path of PSO algorithm in a complex environment

圖11 復(fù)雜環(huán)境下UGBA 算法所規(guī)劃路徑Fig.11 Planning path of UGBA algorithm in a complex environment

圖12 復(fù)雜環(huán)境下PTRBA 算法所規(guī)劃路徑Fig.12 Planning path of PTRBA algorithm in a complex environment

表3 和表4 是每個(gè)算法獨(dú)立運(yùn)行30 次得出的路徑結(jié)果,可以看出本文改進(jìn)算法所規(guī)劃出的每個(gè)機(jī)器人的路徑平均解與所有機(jī)器人路徑總長度的最優(yōu)解、最差解及平均解,都要優(yōu)于其他三種算法,這是因?yàn)榉聪驅(qū)W習(xí)選擇策略的引入,使算法的全局探索和局部挖掘能力得到平衡,算法運(yùn)行過程非常穩(wěn)定,進(jìn)一步驗(yàn)證了本文改進(jìn)算法和三次樣條插值方法相結(jié)合求解移動(dòng)機(jī)器人路徑問題的可行性和可靠性.

表3 簡單環(huán)境下4 種算法所求路徑比較Table 3 Comparison of path lengths obtained by four algorithms in a simple environment

表4 復(fù)雜環(huán)境下4 種算法所求路徑比較Table 4 Comparison of path lengths obtained by four algorithms in a complex environment

5 結(jié)論

本文將蝙蝠算法與三次樣條插值方法相結(jié)合求解機(jī)器人路徑規(guī)劃問題.首先對(duì)蝙蝠算法進(jìn)行改進(jìn),在全局搜索階段,引入動(dòng)態(tài)擾動(dòng)系數(shù),增強(qiáng)了蝙蝠飛行的靈活性,提高算法全局尋優(yōu)能力.在局部搜索階段,融入正切隨機(jī)探索機(jī)制,增強(qiáng)算法的局部開采能力和搜索策略性,使算法更容易跳出局部極值.反向?qū)W習(xí)選擇策略進(jìn)一步平衡了算法全局勘探和局部挖掘能力,使算法所求路徑與其他算法相比更加穩(wěn)定.然后,以三次樣條插值中的路徑結(jié)點(diǎn)作為蝙蝠個(gè)體的編碼,從而把蝙蝠算法和三次樣條插值方法與機(jī)器人路徑規(guī)劃結(jié)合起來,并據(jù)此構(gòu)建了無碰撞最短路徑的方法和目標(biāo)函數(shù).最后,分別在簡單環(huán)境和復(fù)雜環(huán)境下對(duì)單機(jī)器人和多機(jī)器人系統(tǒng)進(jìn)行了路徑規(guī)劃對(duì)比實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明,基于PTRBA 算法和三次樣條插值得的機(jī)器人路徑規(guī)劃方法的求解性能優(yōu)于其他對(duì)比算法,驗(yàn)證了改進(jìn)后算法在規(guī)劃移動(dòng)機(jī)器人路徑方面的有效性和優(yōu)越性.下一步將繼續(xù)改進(jìn)蝙蝠算法的優(yōu)化性能,探索更有效的路徑擬合方法,研究新的啟發(fā)式智能算法并應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃問題.