基于改進(jìn)蝙蝠算法的水下機(jī)器人避障路徑優(yōu)化方法

龔成勇，劉 康，曾永亮

(1.蘭州理工大學(xué)能源與動(dòng)力工程學(xué)院，甘肅 蘭州 730050;2.蘭州理工大學(xué)黃河流域水生態(tài)與水工程研究院，甘肅 蘭州 730050)

0 引言

智能機(jī)器人廣泛運(yùn)用于農(nóng)業(yè)生產(chǎn)、航天科技、材料加工、醫(yī)療救援等領(lǐng)域。目前全國已建成的各類型水庫總數(shù)量為98 795座，總庫容為9 035億m3[1]，受常年使用老化以及地質(zhì)災(zāi)害影響，水下部分存在隆起、沖刷、淘空、錯(cuò)位、脫落、塌陷 、腐蝕、侵蝕、剝蝕、破損、蜂窩、麻面、露筋、滑坡、裂縫、滲漏、管涌、流土等安全隱患及險(xiǎn)情。目前常用的排查方法主要有潛水員進(jìn)行人工下水排查，或遠(yuǎn)程操縱機(jī)器下水排查。人工排查難度大、危險(xiǎn)性高，具備自主巡航、自主作業(yè)、自行返回等功能的智能型水下機(jī)器人備受青睞，其特點(diǎn)是高靈活性、長作業(yè)時(shí)間、廣作業(yè)區(qū)域，因此水下機(jī)器人成為水庫等地的隱患排查工具和手段。而自主避障能力是水下機(jī)器人在路徑規(guī)劃中最為突出重要的一項(xiàng)能力，這要求智能機(jī)器人有對(duì)障礙物的自行規(guī)避與從起點(diǎn)到終點(diǎn)的路徑規(guī)劃的能力。路徑規(guī)劃問題的實(shí)現(xiàn)算法分為傳統(tǒng)算法與智能算法，傳統(tǒng)算法有模糊算法、可視圖、自由空間法、人工勢場法等。模糊控制算法求解多維問題難以建立模糊規(guī)則庫[2]；可視圖法實(shí)時(shí)性能較差，且效率較低[3]；自由空間法處理復(fù)雜障礙空間，其復(fù)雜度將超出計(jì)算能力范圍[4]；人工勢場法易得局部最優(yōu)而難以到達(dá)終點(diǎn)[5]。隨著人工智能的崛起，智能仿生算法被應(yīng)用于路徑規(guī)劃與優(yōu)化問題，如PSO算法(particle swarm optimization，PSO)[6]、人工魚群算法[7]、蟻群算法[8]等。傳統(tǒng)PSO中粒子易陷入不良區(qū)域，種群多樣性不足，搜索停滯，后期收斂速度較差[9]；基本魚群算法的歷史行為學(xué)習(xí)度不足，收斂精度低[10]；基本蟻群算法信息濃度低，搜索速度慢[11]。

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

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

1 基本蝙蝠算法

蝙蝠算法是通過數(shù)學(xué)的方法，以蝙蝠回聲定位飛行為基礎(chǔ)，構(gòu)造出相關(guān)模型以期解決一些復(fù)雜問題的一種智能算法。模型主要通過相關(guān)變量代替蝙蝠飛行時(shí)特定的頻率和響度的聲波，去尋找發(fā)現(xiàn)當(dāng)前最優(yōu)解。記f(x)為目標(biāo)函數(shù)，每只蝙蝠在算法中都有相應(yīng)的函數(shù)值，代表一個(gè)可行解，通過函數(shù)值比較判斷出最優(yōu)個(gè)體。算法的迭代可分解成四個(gè)過程：

1) 隨機(jī)飛行

fi=fmin+(fmax-fmin)β，

(1)

(2)

(3)

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

(4)

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

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

(5)

(6)

2 蝙蝠算法的改進(jìn)與實(shí)現(xiàn)

2.1 高斯柯西變異

單一的高斯變異或柯西變異并不能完美地利用其分布特性。從函數(shù)圖來看，柯西分布兩側(cè)高，產(chǎn)生的隨機(jī)數(shù)范圍相對(duì)更廣，可擴(kuò)大飛行區(qū)域，避免個(gè)體的聚集導(dǎo)致取得局部極小。

(7)

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

高斯分布具有中心附近概率較高的特性，從圖1來看，產(chǎn)生的隨機(jī)數(shù)相對(duì)集中，適合精細(xì)搜索，更容易尋到最優(yōu)解。

(8)

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

圖1 柯西與高斯概率密度Fig.1 Probability density of Cauchy and Gaussian

2.2 線性漸變算法

(9)

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

2.3 界限隨機(jī)重置機(jī)制

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

X*=bL+λ(bU-bL)，

(10)

式(10)中，λ∈[0,1]是一個(gè)隨機(jī)變量，是位置隨機(jī)分配因子；bL代表空間邊界的下界，bU代表空間邊界的上界。

2.4 算法實(shí)現(xiàn)流程

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

1) 建立地圖環(huán)境，確定出發(fā)點(diǎn)與目的點(diǎn)，限制迭代次數(shù)，初始化蝙蝠位置、速度、頻率、脈沖發(fā)射頻率、響度、種群規(guī)模等參數(shù)。

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

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

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

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

7) 重復(fù)步驟3)步驟6)，直到達(dá)到最大迭代次數(shù)。

8) 得到最佳路徑。

3 水下機(jī)器人避障及仿真

3.1 環(huán)境建立

本文以數(shù)學(xué)模型模擬真實(shí)的水下三維環(huán)境，主要研究復(fù)雜水下地形的水下機(jī)器人全局路徑規(guī)劃問題。以山峰的形式模擬機(jī)器人水下工作面臨的地形狀況，由于水下機(jī)器人需要貼近水底對(duì)相關(guān)設(shè)施進(jìn)行排查作業(yè)，故仿真時(shí)使得機(jī)器人盡可能貼近水底作業(yè)而不至于觸碰障礙物。將機(jī)器人實(shí)際工作環(huán)境用三維的水下地形和俯視角度的等高線圖形表示，如圖2、圖3所示。整個(gè)模型空間為200 m×200 m×200 m，x范圍是(0，200) m，y為(-100，100) m，z為(-450，-250) m。

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

為驗(yàn)證改進(jìn)后算法在水下機(jī)器人全局路徑規(guī)劃問題中是否具備優(yōu)越性，以Matlab R2016a軟件為基礎(chǔ)，將算法思路進(jìn)行一系列仿真實(shí)驗(yàn)。為模擬復(fù)雜環(huán)境的規(guī)劃問題，解空間并未設(shè)置標(biāo)準(zhǔn)正方體，水下機(jī)器人的起點(diǎn)坐標(biāo)設(shè)為(0，-100，-350) m，目標(biāo)點(diǎn)設(shè)為(200，100，-360) m，水下機(jī)器人體積忽略不計(jì)，視為空間中的質(zhì)點(diǎn)。算法的基本參數(shù)設(shè)置如表1所示。

表1 模擬基本參數(shù)Tab.1 Basic parameters for simulation on planned path

3.3 實(shí)例數(shù)值模擬

基于相同環(huán)境且根據(jù)上節(jié)設(shè)置的參數(shù)值，分別利用本文算法和基本蝙蝠算法進(jìn)行路徑規(guī)劃，并分別與文獻(xiàn)[12]中的GHBA和VWBA算法進(jìn)行對(duì)比，模擬結(jié)果圖3為改進(jìn)前的三維規(guī)劃路徑，圖4為改進(jìn)前的規(guī)劃路徑俯視柵格圖，圖5為改進(jìn)后的三維規(guī)劃路徑，圖6為改進(jìn)后的規(guī)劃路徑俯視柵格圖。

圖3 算法改進(jìn)前規(guī)劃路徑Fig.3 Planned path based on bat algorithm before improved

從圖3、圖5與圖4、圖6對(duì)比可以看出，相比于基本蝙蝠算法，本文算法規(guī)劃出的路徑長度短，節(jié)點(diǎn)數(shù)少，且沒有急劇的銳角轉(zhuǎn)彎，路徑的平滑性更好，符合機(jī)器人實(shí)際運(yùn)行要求。因此在對(duì)機(jī)器人進(jìn)行路徑規(guī)劃時(shí)，本文算法能夠更好地適應(yīng)機(jī)器人實(shí)際運(yùn)行環(huán)境，高效完成相應(yīng)任務(wù)，對(duì)機(jī)器人的工作更加有利。而基本蝙蝠算法容易出現(xiàn)往復(fù)的無用規(guī)劃，且存在較多易損傷機(jī)器人物理結(jié)構(gòu)的銳角機(jī)動(dòng)。另外，本文算法到達(dá)目標(biāo)點(diǎn)所需的算法收斂時(shí)間明顯少于基本蝙蝠算法，表明本文算法的收斂效果優(yōu)于基本蝙蝠算法，規(guī)劃效率更加高效。具體的指標(biāo)對(duì)比如表2所示。

圖4 改進(jìn)前規(guī)劃路徑俯視柵格圖Fig.4 The top-view grid map of planned path based on bat algorithm before improved

圖5 算法改進(jìn)后規(guī)劃路徑Fig.5 Planned path based on improved bat algorithm

圖6 改進(jìn)后規(guī)劃路徑俯視柵格圖Fig.6 The top-view grid map of planned path based on improved bat algorithm

表2 指標(biāo)對(duì)比Tab.2 Comparison to indicators of simulation on path planning based on different algorithms

4 結(jié)論

針對(duì)水庫中水下機(jī)器人避障研究過程中出現(xiàn)的問題，通過研究改進(jìn)蝙蝠算法，主要可以得到以下結(jié)論：1) 使用線性漸變法調(diào)節(jié)響度和脈沖發(fā)射率，通過脈沖發(fā)射率的大小調(diào)節(jié)全局與局部搜索的關(guān)系，進(jìn)一步優(yōu)化收斂速度，從而提高機(jī)器人的路徑定位速度。2) 在局部尋優(yōu)階段融合高斯柯西變異策略，前期利用柯西函數(shù)兩翼高概率特性產(chǎn)生廣泛圍隨機(jī)數(shù)，擴(kuò)大算法搜索范圍，后期利用高斯函數(shù)中間概率高、兩端概率低的特性進(jìn)行精準(zhǔn)定位。保證機(jī)器人全局最優(yōu)路徑規(guī)劃同時(shí)，提高了局部精度。3) 采用界限隨機(jī)重置機(jī)制，優(yōu)化了蝙蝠在邊界聚集，帶來的種群多樣性不足問題，提高收斂效率。滿足了機(jī)器人實(shí)際定位有效性。

數(shù)值模擬表明，改進(jìn)后的算法規(guī)劃路徑更短，拐點(diǎn)數(shù)更少，運(yùn)行時(shí)間短，迭代次數(shù)少，對(duì)水下機(jī)器人工作運(yùn)行過程中的避障能力更強(qiáng)，路徑規(guī)劃平順且長度短，為現(xiàn)實(shí)機(jī)器人智能避障提供了一種優(yōu)化方法。