基于改進蝙蝠算法機器人避障研究*

黃華東，陳 亮

(1.長沙民政職業(yè)技術(shù)學(xué)院，長沙 410004；2.長沙師范學(xué)院，長沙 410004)

0 引言

智能移動機器人廣泛地運用于農(nóng)業(yè)生產(chǎn)[1-2]、航天科技[3]、材料加工[4]、醫(yī)療救援[5]等領(lǐng)域。自由避障能力是移動機器人最為突出重要的一項能力。這要求智能機器人有對障礙物的自行規(guī)避與從起點到終點的路徑規(guī)劃的能力。路徑規(guī)劃問題的實現(xiàn)算法分為傳統(tǒng)算法與智能算法，其中傳統(tǒng)算法主要有模糊邏輯算法、可視圖法、自由空間法、人工勢場法等[6]。模糊控制算法求解多維問題難以建立模糊規(guī)則庫[7]?？梢晥D法實時性能較差，且效率較低[8]。自由空間法處理復(fù)雜障礙空間，其復(fù)雜度將超出計算能力范圍[9]。人工勢場法易得局部最優(yōu)而難以到達終點[10]。隨著人工智能的崛起，智能仿生算法被應(yīng)用于路徑規(guī)劃與優(yōu)化問題，如粒子群算法(PSO)[11]、人工魚群算法[12]、蟻群算法[13]等。傳統(tǒng)PSO中粒子易陷入不良區(qū)域，種群多樣性不足，搜索停滯，后期收斂速度較差[14]。基本魚群算法的歷史行為學(xué)習(xí)度不足，收斂精度低[15]?；鞠伻核惴ㄐ畔舛鹊?，搜索速度慢[16]。

近年來又出現(xiàn)了一種新型智能優(yōu)化算法即蝙蝠算法(BA)，是模擬蝙蝠捕食飛行過程的一種仿生智能算法，具有模型簡單、算法參數(shù)少有并行性強且分布式廣的特點[17]。但由于初期搜索范圍不夠廣，收斂過快，精度較低，后期存在較多停留邊界的個體，種群多樣性差等問題。

因此，本文將其與高斯函數(shù)與柯西函數(shù)結(jié)合，引入高斯柯西變異策略，幫助算法逃離局部極值的同時提高算法精度。另外使用線性漸變法調(diào)節(jié)響度和脈沖發(fā)射率，通過脈沖發(fā)射率的大小控制蝙蝠進行全局搜索或局部精確搜索，優(yōu)化了收斂速度慢的問題。針對存在的個體飛出解空間邊界導(dǎo)致收斂速度慢的問題，采用邊界再分配機制，減少個體在邊界聚集、提高優(yōu)化效率。

為了規(guī)避移動過程轉(zhuǎn)折點多導(dǎo)致的急轉(zhuǎn)急停問題，基于三次樣條插值對原規(guī)劃路徑進行處理，使得路徑拐點減少，保證運行平順流暢。經(jīng)過處理后的路徑規(guī)避了機器人難以實現(xiàn)的急轉(zhuǎn)急停問題，保證運行過程良好的動力學(xué)性能，保護了機器人內(nèi)部構(gòu)件不受損壞，具有原生算法路徑不可比擬的優(yōu)勢。

1 基本蝙蝠算法

BA算法是模擬蝙蝠飛行時回聲定位特點的一種仿生智能算法。通過仿照蝙蝠搜尋獵物，以一定頻率和響度的聲波，去尋找發(fā)現(xiàn)當(dāng)前最優(yōu)解。記f(x)為目標(biāo)函數(shù)，每只蝙蝠在算法中都有相應(yīng)的函數(shù)值，代表一個可行解，通過函數(shù)值比較判斷出最優(yōu)個體。算法的迭代可分解成4個過程：

(1)隨機飛行。

fi=fmin+(fmax-fmin)β

(1)

(2)

(3)

(2)局部搜索。蝙蝠接近全局最優(yōu)解時,再引入一個取值在0～1的均勻分布數(shù)R1，若R1>ri，則開始局部搜索，否則繼續(xù)全局搜索。通過下式更新位置：

(4)

式中，ε為[-1,1]上的均勻分布隨機數(shù)；At是第t代所有蝙蝠響度的平均值。

(4)更新參數(shù)。接受新解意味著蝙蝠在靠近獵物，響度減小的同時，脈沖發(fā)射速率ri不斷增加。其更新公式如下：

(5)

(6)

2 改進方向

2.1 高斯柯西變異

單一的高斯變異或柯西變異并不能完美地利用其分布特性。柯西分布兩端概率較高，產(chǎn)生廣范圍隨機數(shù)，擴大搜索范圍，避免個體的聚集導(dǎo)致取得局部極小。

(7)

式中，r∈(0,1)是個隨機數(shù)，服從均勻分布；t為迭代次數(shù)；Tmax是最大迭代次數(shù)；C(1,0)是服從標(biāo)準(zhǔn)柯西分布的隨機變量。

高斯分布具有中心附近概率較高的特性，適合在最優(yōu)解附近小步長精細搜索，精確尋找全局最優(yōu)解。

(8)

式中，R3∈(0,1)是個均勻分布隨機數(shù)；N(0,1)是服從標(biāo)準(zhǔn)高斯分布的隨機變量。

圖1 柯西與高斯概率密度

式(7)、式(8)中1-t/Tmax在[0,1]內(nèi)單調(diào)遞減，搜索前期階段t值較小時，1-t/Tmax較大，按式(7)進行柯西擾動，擴大搜索范圍。搜索后期階段，t值增大，1-t/Tmax變小，當(dāng)其小于隨機數(shù)R3時，按式(8)進行高斯變異，小步長能對最優(yōu)解附近實行深度搜尋。兩種變異策略交替使用，根據(jù)搜索進程自適應(yīng)調(diào)整策略，使得全局搜索與局部搜索得到合理平衡，提高了最優(yōu)解的搜索精度，同時加快了后期的收斂速度。

2.2 線性漸變算法

(9)

由于兩個參數(shù)單調(diào)遞減，故響度最大值A(chǔ)max即初始響度，一直遞減至最小值A(chǔ)min，脈沖發(fā)射率rmax即初始脈沖發(fā)射率一直遞減至最小值rmin，直到達到最大迭代次數(shù)Tmax。

2.3 邊界再分配機制

由于蝙蝠算法隨機搜索的內(nèi)生性，個體搜索至邊界后聚集不可避免，這將進一步降低多樣性。為此本文融合邊界再分配機制，將越界個體通過式(10)進行位置隨機再分配，而保證個體的速度大小和方向不改變，以此提高個體利用，加快算法后期收斂。位置更新如式(10)所示。

X*=Lb+λ(Ub-Lb)

(10)

式中，λ∈[0,1]是一個隨機變量，是位置隨機分配因子；Lb代表空間邊界的下界；Ub代表空間邊界的上界。

2.4 三次樣條插值法的路徑平滑

本文路徑規(guī)劃地圖采用柵格地圖表示，因此會在轉(zhuǎn)彎處產(chǎn)生明顯拐點。為了讓移動機器人減少實際輪子的軸磨損和能耗，應(yīng)保證規(guī)劃出的路徑具有平滑性。

三次樣條插值具有一階和二階導(dǎo)數(shù)的收斂性，三次函數(shù)的最高項系數(shù)為0時三次樣條插值曲線仍為曲線，插值效果更好。另外三次樣條插值與高階插值相比具有計算簡單穩(wěn)定性好的優(yōu)點。因此本文使用三次樣條插值形成平滑路徑。

取區(qū)間[a,b]分成n個區(qū)間[(x0,x1),(x1,x2),…,(xn-1,xn)]，三次樣條方程滿足以下條件：

在任意的[(xi-1,xi)]上，S(x)=Si(x)都是一個三次方程：

Si(x)=ai+bi(x-xi)+ci(x-xi)2+di(x-xi)3

(11)

S(x)在區(qū)間[a,b]中是連續(xù)的：

S(x0)=y0,…,S(xn+1)=yn+1

(12)

S-=S+(xi),i=1,2,…,n

(13)

S′(x)在區(qū)間[a,b]中是連續(xù)的：

(14)

S′′(x)在區(qū)間[a,b]中是連續(xù)的：

(15)

在本文中三次樣條函數(shù)用于在起點控制點和目標(biāo)點的路徑上進行插值可以將移動機器人的路徑分割為一系列連接路徑點的線段從而獲得了通過連接所有插值點而形成的完整路徑。

2.5 算法實現(xiàn)流程

本文算法的實現(xiàn)具體流程如下：

(1)建立地圖環(huán)境，確定起終點和最大迭代次數(shù)初始化蝙蝠位置、速度、頻率、脈沖發(fā)射頻率、響度，種群規(guī)模等參數(shù)；

(2)計算蝙蝠種群的適應(yīng)度，記錄最優(yōu)個體x*；

(3)按照式(2)、式(3)更新蝙蝠位置和速度，越界個體按式(10)進行處理，產(chǎn)生新個體xnew；

(4)生成隨機數(shù)R1，若R1>ri，則根據(jù)式(7)、式(8)選擇變異機制，并將變異個體賦值給xnew；

(6)比較所有蝙蝠的適應(yīng)度，找到當(dāng)前最優(yōu)解x*；

(7)重復(fù)(3)和(6)，直到達到最大迭代次數(shù)；

(8)得到平滑前的最佳路徑；

(9)通過三次樣條插值法得到平滑路徑。

3 仿真及分析

3.1 地圖環(huán)境生成

本文將柵格圖作為機器人建模環(huán)境。柵格地圖形如棋盤，將障礙物通過膨脹法或腐蝕法進行柵格化，暗色部分表示個體不可通過，白色部分表示可自由通過。機器人在傳統(tǒng)柵格圖移動有8個方向可供選擇，如圖2所示。

圖2 移動方向

機器人柵格環(huán)境模型如圖3所示。以左下角第一個柵格的中心點坐標(biāo)(0.5,0.5)為原點，根據(jù)柵格圖中每個柵格的行列次序，依據(jù)從下至上，從左到右原則依次遞增。如柵格地圖規(guī)格為j行k列，柵格號為G，柵格粒徑為1，則柵格中心坐標(biāo)可表示為：

圖3 柵格圖

(16)

式中，x、y分別為中心點的橫、縱坐標(biāo)；mod為取余操作；int表示求整。

3.2 參數(shù)設(shè)置

基于MATLAB2016a平臺搭建20×20柵格地圖環(huán)境，設(shè)置起點為(0.5,0.5)，終點為(19.5,19.5)。其余主要參數(shù)設(shè)置如表1所示。

表1 本文用到的基本參數(shù)

3.3 實例仿真分析

基于相同環(huán)境且根據(jù)上節(jié)設(shè)置的參數(shù)值，分別利用本文算法和基本蝙蝠算法進行路徑規(guī)劃，基本蝙蝠算法仿真圖如圖4所示，改進蝙蝠算法未平滑仿真圖如圖5所示，改進蝙蝠算法平滑化仿真圖如圖6所示，各項指標(biāo)對比如表2所示。

圖4 基本蝙蝠算法仿真圖

圖5 改進蝙蝠算法未平滑仿真圖 圖6 改進蝙蝠算法平滑化仿真圖

表2 指標(biāo)對比

從圖4、圖5可以看出，相比于基本蝙蝠算法，本文算法規(guī)劃出的路徑長度更短，拐點數(shù)更少，并且路徑的平滑性更好。圖6相比于使用三次樣條插值法前的圖5則幾乎沒有拐點，路徑非常平滑對機器人的性能損耗較小。另外，本文算法收斂效果優(yōu)于基本蝙蝠算法。因此在對機器人進行路徑規(guī)劃時，本文算法能夠更好的適應(yīng)機器人實際運行環(huán)境，高效完成相應(yīng)任務(wù)，對機器人的工作更加有利。

4 結(jié)論

本文以線性漸變方式調(diào)節(jié)響度和脈沖發(fā)射率，通過脈沖發(fā)射率的大小控制蝙蝠進行全局搜索或局部精確搜索，優(yōu)化了收斂速度慢的問題。在局部尋優(yōu)階段融合高斯柯西變異策略，前期利用柯西函數(shù)兩翼高概率特性產(chǎn)生廣泛圍隨機數(shù)，擴大算法搜索范圍，后期利用高斯函數(shù)中間概率高，兩端概率低的特性進行精準(zhǔn)定位。同時采用邊界再分配機制，優(yōu)化了蝙蝠在邊界聚集，帶來的種群多樣性不足問題，提高收斂效率。最后，利用三次樣條插值法將拐點平滑，形成一條光滑曲線。仿真表明，改進后的蝙蝠算法相較于基本蝙蝠算法，規(guī)劃路徑更短，拐點數(shù)更少，運行時間短，迭代次數(shù)少，對機器人工作運行更為有利。