基于改進蝙蝠算法和三次樣條插值的機器人路徑規劃

劉景森 吉宏遠 李煜

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

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

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

為了探索出更好地解決機器人路徑規劃問題的方法,改善基本蝙蝠算法易陷入局部極值、尋優精度不高、算法后期收斂速度較慢等缺點,提高蝙蝠算法的尋優精度和收斂速度,拓展其應用領域,本文嘗試將蝙蝠算法的優化思想和三次樣條插值方法相結合,從而求解機器人路徑規劃問題.首先,對基本蝙蝠算法進行了改進,在算法的全局搜索階段,引入動態擾動系數,擴大蝙蝠種群的多樣性.在算法的局部搜索階段,對其隨機探索方式進行改進,提高算法收斂精度.然后,采用反向學習選擇策略,進一步平衡算法的全局勘探和局部挖掘能力.最后,把改進后算法與三次樣條插值方法相結合,定義了以路徑結點為基礎的編碼方式,構造了以求解移動機器人繞避障礙和最短路徑為目標的方法和適應度函數,求解機器人路徑規劃問題.通過在簡單和復雜障礙環境、單機器人和多機器人環境下進行的路徑規劃實驗,測試對比結果表明,改進算法對于求解機器人全局路徑規劃問題具有很好的可靠性和有效性.

1 基本蝙蝠算法

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

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

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

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

其中,α和γ是常數.對任意的0<α<1,γ>0,當迭代次數t趨于正無窮時,響度趨于0,脈沖發射率趨于是初始脈沖發射率.

2 具有反向學習和正切隨機探索的蝙蝠算法PTRBA

與其他群智能算法一樣,蝙蝠算法在優化過程中,種群的多樣性和算法的深度挖掘能力之間始終存在著矛盾.對標準蝙蝠算法的改進,其目的都是希望在加強算法局部搜索能力的同時,保持種群的多樣性,防止算法在快速收斂的同時出現早熟收斂,本文改進也是基于這一思想,即利用正切隨機探索機制在加強算法局部開采能力的同時,依靠動態擾動系數和反向學習選擇機制提高蝙蝠種群的多樣性,擴大蝙蝠的搜索范圍.下面詳細介紹具體改進策略.

2.1 動態擾動系數

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

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

2.2 正切隨機探索機制

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

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

2.3 反向學習選擇策略

Tizhoosh 在文獻[23] 中給出反向學習的定義如下.

定義1.若x是定義在實數集R 上的一個區間[a,b] 的一個實數,即x ∈[a,b],則x的反向解x1定義為

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

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

3 PTRBA 基于三次樣條插值實現機器人路徑規劃

三次樣條插值是一種分段式插值方法,通過一系列基于三次多項式的插值點區間,形成一條光滑曲線.用三次樣條插值方法擬合出的機器人移動路徑曲線更加平滑,這樣可以保證機器人在急停或急轉時有較好的動力學特性,具有用直線與圓弧擬合移動機器人路徑無法比擬的優點.本文將三次樣條插值方法融入改進蝙蝠算法PTRBA (A bat algorithm with dynamic perturbation,tangent stochastic exploration and reverse learning selection mechanism) 中,用于求解機器人全局路徑規劃問題.

3.1 三次樣條插值

設在區間[a,b] 上取n+1 結點a=x0

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

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

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

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

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

1) 給出兩個端點處的一階導數值;

2) 給出兩個端點處的二階導數值;

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

3.2 編碼

由上可知,三次樣條插值是一種分段式插值方法,段與段之間的交接處,稱為路徑結點.段與段之間的樣條是不同的,而整個樣條曲線則是一階連續的,且在路徑結點處二階連續,因此,分段樣條之間的方向也可能不同,路徑結點就代表了整個路徑的最大轉向次數.即使在非常復雜的環境下,一般經歷3 ～5 次轉向就能繞開所有障礙物.依此,本文以一條路徑上的所有結點作為一個蝙蝠個體的編碼.也就是說,一個蝙蝠個體代表了對應路徑上的所有路徑結點,即一條路徑上所有m個路徑結點的橫坐標集合構成了蝙蝠個體的m維橫坐標,相應地,一條路徑上所有m個路徑結點的縱坐標集合構成了蝙蝠個體的m維縱坐標.

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

3.3 構建適應度函數

機器人路徑規劃要滿足兩個條件:1) 不能與障礙物發生碰撞;2) 路徑長度要盡可能短.本文就以滿足上述條件的無碰撞的路徑長度最短作為適應度函數的評價標準.

本文構造的適應度函數為

其中,(x i,yi)為第i個插值點的坐標.

η是一個標志變量,其初始值設置為0.η的求值過程為

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

3.4 算法流程

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

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

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

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

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

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

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

步驟8.利用式(1),(2),(8),(9) 分別對蝙蝠位置進行更新,即得出更新后具有m個路徑結點坐標的路徑.

步驟9.重復執行步驟3 ～8,直到算法達到最大迭代次數.

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

4 仿真實驗與分析

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

4.1 實驗環境及參數設置

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

4.2 單機器人系統的路徑規劃及算法尋優性能分析

對于單機器人系統,分別在簡單障礙環境和復雜障礙環境下,進行路徑規劃對比實驗.在簡單環境下,設置障礙個數為6,路徑結點個數為3.在復雜環境下,設置障礙個數為11,路徑結點數設置為4.兩種環境下的插值點個數都設置為100.其具體實驗結果分別如圖1、圖2、表1 和圖3、圖4、表2 所示.

圖1 簡單環境下4 種算法路徑規劃對比圖Fig.1 Comparison of four algorithm path planning in a simple environment

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

圖3 復雜環境下4 種算法路徑規劃對比圖Fig.3 Comparison of four algorithm path planning in a complex environment

圖4 復雜環境下4 種算法迭代曲線對比圖Fig.4 Comparison of four algorithm iteration curves in a complex environment

從圖1 和圖3 中可以直觀地看出本文改進算法PTRBA 所規劃出的機器人路徑最短,尤其是在復雜環境下,本文算法的求解效果更加明顯.這是因為在全局搜索階段,引入動態擾動系數,增強了蝙蝠飛行的靈活性,提高算法尋優能力.如圖2 和圖4 所示,算法在前期收斂速度并不是很快,但在第10 代左右時,算法可以跳出局部極值,快速向最優解靠近.這是因為在局部搜索階段,融入正切隨機探索機制,增強算法的局部開采能力和搜索策略性,使算法更容易跳出局部極值,從而提高了算法的尋優精度.如表1 和表2 所示,是每個算法獨立運行30 次所得出的路徑情況,可以看出本文算法PTRBA 求解出的路徑長度無論是最優解、最差解還是平均值都是4 種算法中最短的且求解結果非常穩定,這是因為反向學習策略進一步平衡了算法全局勘探和局部挖掘能力,是算法所求路徑與其他算法相比更加穩定.總體上,三種改進機制相互配合,提高算法收斂速度和尋優能力.

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

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

4.3 多機器人系統的路徑規劃及算法尋優性能分析

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

步驟1.利用PTRBA 和三次樣條插值方法,規劃出第1 個機器人的路徑,然后,以此路徑上的m個路徑結點為圓心,人工虛擬出m個障礙.

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

本文仿真實驗要求為3 個機器人規劃出無碰撞路徑,每條路徑上的路徑結點個數設置為3.分別在簡單環境和復雜環境下,進行對比仿真實驗.在簡單環境下,設置障礙個數為4,在復雜環境下,設置障礙個數為9.兩種環境下的插值點個數都設置為100.其具體實驗結果如下:

由圖5 ～8 和圖9 ～12 可以直觀地看出,本文改進算法PTRBA 所規劃出的移動機器人路徑很少出現不必要的曲折,這是因為全局搜索階段的動態擾動系數和局部搜索階段的正切隨機探索機制,使蝙蝠種群快速向最優解靠近,算法整體尋優能力得到提高.

圖5 簡單環境下BA 算法所規劃路徑Fig.5 Planning path of BA algorithm in a simple environment

圖6 簡單環境下PSO 算法所規劃路徑Fig.6 Planning path of PSO algorithm in a simple environment

圖7 簡單環境下UGBA 算法所規劃路徑Fig.7 Planning path of UGBA algorithm in a simple environment

圖8 簡單環境下PTRBA 算法所規劃路徑Fig.8 Planning path of PTRBA algorithm in a simple environment

圖9 復雜環境下BA 算法所規劃路徑Fig.9 Planning path of BA algorithm in a complex environment

圖10 復雜環境下PSO 算法所規劃路徑Fig.10 Planning path of PSO algorithm in a complex environment

圖11 復雜環境下UGBA 算法所規劃路徑Fig.11 Planning path of UGBA algorithm in a complex environment

圖12 復雜環境下PTRBA 算法所規劃路徑Fig.12 Planning path of PTRBA algorithm in a complex environment

表3 和表4 是每個算法獨立運行30 次得出的路徑結果,可以看出本文改進算法所規劃出的每個機器人的路徑平均解與所有機器人路徑總長度的最優解、最差解及平均解,都要優于其他三種算法,這是因為反向學習選擇策略的引入,使算法的全局探索和局部挖掘能力得到平衡,算法運行過程非常穩定,進一步驗證了本文改進算法和三次樣條插值方法相結合求解移動機器人路徑問題的可行性和可靠性.

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

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

5 結論

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