基于改進(jìn)煙花-蟻群算法的海流環(huán)境下水下無人潛航器的避障路徑規(guī)劃

馬 焱，肖玉杰，陳 軼，閆泓衫

（1.西北工業(yè)大學(xué)航海學(xué)院，西安710072；2.海軍研究院，北京100161）

0 引言

水下無人潛航器（UnmannedUnderwater Vehicle，UUV）是水下無人系統(tǒng)的重要組成部分，在軍用領(lǐng)域、民用領(lǐng)域均有巨大的應(yīng)用價(jià)值，是響應(yīng)國家軍民融合發(fā)展的重點(diǎn)工程之一。在智能化變革的今天，UUV智能化水平的高低決定了其核心競(jìng)爭(zhēng)力，而UUV的路徑規(guī)劃技術(shù)正是衡量其智能化水平的最基本、最核心的技術(shù)之一。

目前，路徑規(guī)劃問題在陸地和空中空間域中的研究已比較成熟，各種陸地移動(dòng)機(jī)器人、空中無人機(jī)已能很好地完成路徑規(guī)劃任務(wù)。然而，由于UUV通常在復(fù)雜多變的海流中工作，水中的阻力遠(yuǎn)遠(yuǎn)大于空中和陸地的阻力，與其相關(guān)的路徑規(guī)劃則不僅僅只需考慮避障問題，還需要考慮海流對(duì)UUV航行的作用。作為一種能量的流動(dòng)，海流對(duì)UUV航行帶來了很大的影響。在路徑規(guī)劃時(shí)，應(yīng)盡量使UUV順著海流的流向航行，充分利用海流場(chǎng)的能量，減少因抵抗海流而逆流航行帶來的能量消耗［1］。因此，需要規(guī)劃出一條能量消耗盡可能少、航行距離盡可能短的路徑。

針對(duì)UUV路徑規(guī)劃問題，很多算法應(yīng)運(yùn)而生，如快速探索隨機(jī)樹（RRT）算法［2］、螢火蟲算法［3］、人工蜂群算法［4］、人工勢(shì)場(chǎng)法［5］、基于圖搜索算法［1，6］、種群進(jìn)化算法［7］等，但各種算法均有其優(yōu)缺點(diǎn)。比如，人工勢(shì)場(chǎng)法存在當(dāng)目標(biāo)點(diǎn)附近有障礙物時(shí)無法到達(dá)目標(biāo)點(diǎn)，以及在相隔很近的障礙物之間不能發(fā)現(xiàn)路徑等缺點(diǎn)；基于圖搜索算法存在計(jì)算代價(jià)會(huì)隨著搜索空間維數(shù)的增大而出現(xiàn)指數(shù)增加的缺點(diǎn)；部分種群進(jìn)化算法存在易于早熟和陷入局部最優(yōu)解的缺點(diǎn)。文獻(xiàn)［8］提出了基于量子行為的粒子群優(yōu)化的路徑規(guī)劃方法，考慮了海流和障礙物的影響，但是其優(yōu)化目標(biāo)是航行時(shí)間代價(jià)，沒有考慮重要的能量消耗代價(jià)。文獻(xiàn)［6］利用稀疏A?算法對(duì)AUV進(jìn)行了全局路徑規(guī)劃，并建立了相應(yīng)的約束條件，但其優(yōu)化目標(biāo)是航行總距離，同樣沒有考慮能量消耗代價(jià)。文獻(xiàn)［1］考慮到了能量消耗代價(jià)，并用CD?算法進(jìn)行了路徑規(guī)劃，但是完全沒有考慮航行時(shí)間和航行距離的代價(jià)。文獻(xiàn)［9］利用GA?PSO混合算法對(duì)考慮海流環(huán)境的AUV進(jìn)行了路徑規(guī)劃，但其僅僅考慮了能量消耗，并且其建立的海流環(huán)境沒有考慮渦流等更復(fù)雜的情況。

為了在考慮海流環(huán)境的情況下，快速尋找到UUV路徑規(guī)劃問題的全局最優(yōu)解，本文借鑒文獻(xiàn)［10］提出的改進(jìn)煙花?蟻群混合算法解決了此問題。首先，建立二維海流環(huán)境，得到含有障礙物的等效柵格模型。然后，建立UUV避障路徑規(guī)劃數(shù)學(xué)模型。最后，為驗(yàn)證提出的方法在處理該問題時(shí)的優(yōu)勢(shì)，將其與ACO方法作出仿真實(shí)驗(yàn)對(duì)比。實(shí)驗(yàn)結(jié)果表明，本文提出的方法能以更快的速度找到更優(yōu)的全局最優(yōu)解。

1 搜索環(huán)境模型

1.1 二維海流環(huán)境模型

由于地球的快速自轉(zhuǎn)，海流水平面內(nèi)的運(yùn)動(dòng)規(guī)模遠(yuǎn)大于垂直面，因此可以將海流考慮為多層二維水平面內(nèi)的運(yùn)動(dòng)。這里，采用文獻(xiàn)［11］中的多個(gè)粘性Lamb渦流疊加對(duì)海流場(chǎng)模型進(jìn)行數(shù)值方程表示。其數(shù)學(xué)描述為

圖1 海流環(huán)境模型Fig.1 Model of ocean current environment

1.2 含障礙物的等效柵格模型

在該二維海流環(huán)境中，隨機(jī)布撒10個(gè)半徑為R（R∈（0，2］）的圓形障礙物，含障礙物的海流模型如圖2所示。為便于定義路徑編碼，利用文獻(xiàn)［10］中的二維柵格模型處理障礙物。對(duì)障礙物進(jìn)行適當(dāng)膨脹，最終可將UUV簡(jiǎn)化為質(zhì)點(diǎn)處理。將圓形障礙物處理為方形等效柵格時(shí)，需遵循圓形徑向跨度 “四舍五入”的原則。如圖3（a）所示，取4×4方格為例，紅色虛線為 “四舍五入”分界線，綠色實(shí)線為圓形障礙物輪廓。分界線以內(nèi)的圓形障礙物等效柵格為分界線內(nèi)的最大方形區(qū)域柵格，分界線以外的圓形障礙物等效柵格為分界線以外的最小方形區(qū)域柵格，圖3（b）、圖3（c）為兩個(gè)等效柵格實(shí)例。按照此等效原則，本文中含障礙物的海流環(huán)境等效柵格如圖4所示。

圖2 含障礙物的海流環(huán)境Fig.2 Ocean current environment with obstacles

圖3 障礙物等效柵格方法示意圖Fig.3 Schematic diagram of obstacle equivalent grid method

圖4 含障礙物的海流環(huán)境等效柵格Fig.4 Equivalent grid of ocean current environment with obstacles

2 UUV避障路徑規(guī)劃的數(shù)學(xué)模型

UUV避障路徑規(guī)劃是一個(gè)典型的多目標(biāo)多約束的非線性優(yōu)化問題，本文借鑒了文獻(xiàn)［13］中處理復(fù)雜優(yōu)化問題的方法。首先，分別設(shè)計(jì)了決策變量、目標(biāo)函數(shù)和約束條件的數(shù)學(xué)模型，然后使用外罰函數(shù)法將該模型轉(zhuǎn)化為無約束的單目標(biāo)非線性規(guī)劃問題。

2.1 決策變量設(shè)計(jì)

應(yīng)用文獻(xiàn)［10］中的柵格編碼方式，規(guī)劃的路徑最終以序列號(hào)編碼m表示，其對(duì)應(yīng)于海流環(huán)境中的坐標(biāo)為 (xm，ym)。因此，可以設(shè)計(jì)坐標(biāo)(xm，ym)為決策變量，將其變換成序列號(hào)編碼，即可得到最優(yōu)路徑。

2.2 目標(biāo)函數(shù)設(shè)計(jì)

分別定義UUV路徑規(guī)劃時(shí)的能量消耗代價(jià)f1、航行距離代價(jià)f2、航行時(shí)間代價(jià)f3，建立優(yōu)化目標(biāo)函數(shù)。

（1）能量消耗代價(jià)f1

UUV的航行路徑由從起點(diǎn)至當(dāng)前點(diǎn)的一系列離散點(diǎn)依次表示，它是1個(gè)動(dòng)態(tài)變化的集合，Path={p1，p2，…，pi，…，pn}。 其中，pi=(xi，yi)為第i步經(jīng)過的坐標(biāo)點(diǎn)，n為途徑點(diǎn)總個(gè)數(shù)。設(shè)相鄰2個(gè)路徑點(diǎn)構(gòu)成1個(gè)路徑段li，i+1，每個(gè)路徑段li，i+1的

圖5 路徑段速度合成示意圖Fig.5 Schema of velocity composition in path section

由圖5可知

由三角函數(shù)關(guān)系可得

式中，θri、θsi、θci分別為第i段路徑的合速度、靜水速度、海流速度與水平方向的夾角，取逆時(shí)針方向?yàn)檎?/p>

式中，ρ為由UUV尺寸和水流特性決定的常數(shù)。對(duì)于一條給定的路徑Path，其能量消耗代價(jià)f1為

（2）航行距離代價(jià)f2

航行距離代價(jià)的定義類似于文獻(xiàn)［10］中的適應(yīng)度函數(shù)，航行距離為歷史途徑距離與未來預(yù)測(cè)距離之和。Path路徑對(duì)應(yīng)的航行距離代價(jià)f2為

式中，f2為給定的路徑Path對(duì)應(yīng)的航行距離代價(jià)值，dH為歷史途徑距離，dF為未來預(yù)測(cè)距離，（xHi，yHi）為Path路徑中歷史途徑柵格集中于第i個(gè)柵格所對(duì)應(yīng)的坐標(biāo)，（xP，yP）、（xN，xN）、（xE，yE）分別為途徑點(diǎn)j的當(dāng)前柵格、將訪柵格、終點(diǎn)柵格所對(duì)應(yīng)的坐標(biāo)。

（3）航行時(shí)間代價(jià)f3

由此建立的目標(biāo)函數(shù)為

式中，w1、w2、w3分別為3個(gè)子目標(biāo)所占的權(quán)重。

2.3 約束條件設(shè)計(jì)

（1）最大轉(zhuǎn)彎角約束

由于UUV視角范圍和機(jī)動(dòng)性能的限制，UUV在某一時(shí)刻的轉(zhuǎn)彎角存在一定的范圍。因此，要求在每一途徑點(diǎn)i處的轉(zhuǎn)彎角φi不超過最大轉(zhuǎn)彎角φmax，即有

（2）最小轉(zhuǎn)彎半徑約束

由于UUV尺寸和最大轉(zhuǎn)彎角的限制，UUV在某一時(shí)刻的最小轉(zhuǎn)彎半徑存在一定的范圍。因此，要求在每一途徑點(diǎn)i處的轉(zhuǎn)彎半徑ri不小于最小轉(zhuǎn)彎半徑Rmin，即有

圖6 轉(zhuǎn)彎角定義示意圖Fig.6 Sketch of turn angle definition

2.4 約束問題無約束化等效

利用文獻(xiàn)［10］中的外罰函數(shù)法將該問題轉(zhuǎn)化為無約束單目標(biāo)非線性規(guī)劃問題，取一個(gè)充分大的數(shù)M（M＞0），構(gòu)造增廣目標(biāo)函數(shù)

因此，可將該復(fù)雜的數(shù)學(xué)模型轉(zhuǎn)化為無約束的極值問題，即有

3 改進(jìn)煙花-蟻群算法的UUV避障路徑規(guī)劃

在求解UUV避障路徑規(guī)劃數(shù)學(xué)模型時(shí)，針對(duì)該轉(zhuǎn)化后的無約束非線性極值問題，本文使用了文獻(xiàn)［10］提出的改進(jìn)煙花?蟻群算法進(jìn)行求解。

煙花算法［10］是一種新穎的優(yōu)化算法，其具有局部搜索能力和全局搜索能力的自調(diào)節(jié)機(jī)制，同時(shí)其種群具有多樣性，針對(duì)大規(guī)模的復(fù)雜優(yōu)化問題，具備良好的搜索效率。但是，對(duì)于基本煙花算法，煙花產(chǎn)生機(jī)制沒有利用火花群中其他優(yōu)秀火花的位置信息和整個(gè)群體信息，火花之間交流較少。另外，當(dāng)將煙花算法應(yīng)用到終點(diǎn)柵格不位于搜索區(qū)域中心或區(qū)域中心附近位置時(shí)，搜索過程中會(huì)出現(xiàn)大量 “迷失”的火花，產(chǎn)生很多非完整路徑。為解決基本煙花算法中存在的種群信息交流不足和映射規(guī)則不盡合理的缺陷，提出了“先鋒火花”的概念。先鋒火花增強(qiáng)了群體間的信息交互，增加了火花粒子的多樣性，提高了算法的搜索精度和收斂速度。

3.1 先鋒火花生成規(guī)則

先鋒火花生成規(guī)則與基本煙花生成火花的區(qū)別在于煙花爆炸算子和映射規(guī)則的不同。

（1）先鋒火花爆炸算子

①爆炸強(qiáng)度

由先鋒煙花產(chǎn)生的先鋒火花個(gè)數(shù)為

其中，Sp為產(chǎn)生的先鋒火花的個(gè)數(shù)；coefp為先鋒火花數(shù)系數(shù)，用來限制生成的先鋒火花的個(gè)數(shù)；Dmax、Dmin分別為當(dāng)前種群中火花所在柵格到終點(diǎn)柵格距離的最大值和最小值；Dp為先鋒煙花所在柵格到終點(diǎn)柵格的距離。

②爆炸幅度

先鋒煙花爆炸幅度的范圍公式為

其中，Ap為先鋒煙花爆炸的幅度范圍，Maxp、Minp分別為先鋒煙花爆炸幅度的最大值和最小值。

（2）先鋒火花鏡面映射規(guī)則

先鋒火花使用 “鏡面映射”規(guī)則對(duì)超出搜索區(qū)域邊界的先鋒火花做映射操作，鏡面映射規(guī)則的計(jì)算公式為

3.2 改進(jìn)煙花-蟻群算法

改進(jìn)煙花算法能以很快的速度實(shí)現(xiàn)收斂，但得到的最優(yōu)路徑并不是有效路徑。該路徑存在跨越障礙物的現(xiàn)象，這是因?yàn)楸ɑ鸹ǖ乃阉鞣绞綖椴贿B續(xù)的跳躍式搜索，故而所尋路徑不可避免地越過了障礙物，形成無效路徑。

鑒于改進(jìn)的煙花算法能以很少的迭代次數(shù)和初始煙花數(shù)快速尋找到一條從起點(diǎn)柵格到終點(diǎn)柵格的最優(yōu)路徑，因而可以將此路徑作為參考路徑，再與其他群的智能優(yōu)化算法結(jié)合，快速找到最短的全局有效路徑。

可以結(jié)合改進(jìn)煙花算法和蟻群算法的優(yōu)點(diǎn)，克服各自缺陷，找到一條有效的全局最優(yōu)路徑。改進(jìn)煙花?蟻群混合算法首先利用改進(jìn)煙花算法產(chǎn)生1條初始參考路徑，然后將其轉(zhuǎn)化為蟻群算法的初始信息素分布。該混合算法在時(shí)間效率和精度上均分別優(yōu)于改進(jìn)煙花算法和蟻群算法，是求解優(yōu)化問題的一種新方法。

（1）改進(jìn)煙花算法與蟻群算法的銜接

（2）混合算法的路徑點(diǎn)選擇

其中，allowedk={C-tabuk}為螞蟻k下一步允許選擇的柵格，C為所有柵格的集合，α為信息啟發(fā)式因子，β為期望啟發(fā)式因子，ηmn（l）為啟發(fā)函數(shù)，ηmn（l）=1/dmn，dmn為相鄰兩柵格m、n的中心點(diǎn)距離。

（3）混合算法的信息素更新

該混合算法的信息素更新公式為

其中，ρ（0≤ρ＜1）為信息素殘留因子，1-ρ為信息素的揮發(fā)系數(shù)；Lc為螞蟻周游最優(yōu)路徑長度；Lw為改進(jìn)煙花算法尋找到的最優(yōu)參考路徑長度；ak、bk為整型變量，分別代表周游螞蟻尋找到的路徑和改進(jìn)煙花算法尋找到的路徑更新信息素的權(quán)重，其和為常數(shù)K；Q0為信息素強(qiáng)度，為一常數(shù)。

初始時(shí)刻的Δτmn（0）將信息素強(qiáng)度Q0均分到改進(jìn)煙花算法尋找到的全局最優(yōu)參考路徑Lw上，其計(jì)算公式為

4 仿真實(shí)驗(yàn)驗(yàn)證

4.1 實(shí)驗(yàn)參數(shù)設(shè)置

為驗(yàn)證改進(jìn)煙花?蟻群混合算法在UUV避障路徑規(guī)劃中的優(yōu)越性，對(duì)提出的算法進(jìn)行了仿真實(shí)驗(yàn)，并將其與基本蟻群算法的路徑規(guī)劃效果做出了對(duì)比。

基本蟻群算法的參數(shù)設(shè)置為：螞蟻數(shù)目Na=30，最大迭代次數(shù)Ma=50，信息啟發(fā)式因子α=1，期望啟發(fā)式因子β=7，信息素殘留因子ρ=0.3，信息素強(qiáng)度Q0=200。

目標(biāo)函數(shù)權(quán)重w1、w2、w3分別為0.5、0.2、0.2，與UUV尺寸和水流特性相關(guān)的常數(shù)ρ=10。

4.2 實(shí)驗(yàn)結(jié)果及分析

為了比較改進(jìn)煙花?蟻群混合算法和基本蟻群算法在UUV避障路徑規(guī)劃中的優(yōu)劣，主要比較了2種算法尋找到的避障最優(yōu)路徑的平均適應(yīng)度值收斂速度、最優(yōu)路徑適應(yīng)度值和計(jì)算時(shí)間。這里得到了在40km×40km的平面海域內(nèi)，在含有10個(gè)隨機(jī)障礙物、8個(gè)隨機(jī)渦流的海流環(huán)境下，2種算法的避障最優(yōu)路徑的仿真實(shí)驗(yàn)結(jié)果，如圖7～圖11所示。

圖7是改進(jìn)煙花算法尋找到的最優(yōu)路徑。由圖7可知，改進(jìn)煙花算法可以有效利用海流能量，較好地順著海流流向，避開逆流海流，同時(shí)兼顧航行距離最短的目標(biāo)。但是，由于煙花算法跳躍式搜索的特點(diǎn)，尋找到的路徑會(huì)跨越部分障礙物，致使尋找到的路徑為無效路徑。獲得該路徑計(jì)算用時(shí)為4.23s，且收斂速度較快。

以圖7得到的路徑為參考路徑，利用改進(jìn)煙花?蟻群混合算法尋找到的避障最優(yōu)路徑的平均適應(yīng)度值收斂曲線和最優(yōu)路徑分別如圖8、圖9所示。由圖8可知，該混合算法能夠快速得到全局最優(yōu)解，大約迭代15次后便趨于收斂。由圖9可知，改進(jìn)煙花?蟻群混合算法所得路徑不僅能盡量靠攏參考路徑，還可以有效避障，充分發(fā)揮了煙花算法和蟻群算法各自的優(yōu)勢(shì)。

圖8 改進(jìn)煙花-蟻群混合算法避障最優(yōu)路徑平均適應(yīng)度值收斂曲線Fig.8 Convergence curve of average fitness value of optimal path avoiding obstacles for improved fireworksant colony hybrid algorithm

圖9 改進(jìn)煙花-蟻群混合算法尋找到的最優(yōu)路徑Fig.9 Optimal path found by improved fireworks-ant colony hybrid algorithm

圖10、圖11分別為兩種算法得到的避障最優(yōu)路徑的平均適應(yīng)度值收斂曲線和最優(yōu)路徑對(duì)比結(jié)果。由兩種算法在海流環(huán)境下的平均適應(yīng)度值收斂曲線可知，改進(jìn)煙花?蟻群算法能在5～15次迭代左右快速尋找到全局有效最優(yōu)路徑，而基本蟻群算法在迭代50次時(shí)才勉強(qiáng)尋找到次優(yōu)路徑。由兩種算法在海流環(huán)境下的最優(yōu)路徑對(duì)比可知，改進(jìn)煙花?蟻群算法能夠充分利用參考路徑信息，兼顧路徑距離代價(jià)和避障，而基本蟻群算法會(huì)出現(xiàn)逆海流航行路徑，尋找到的路徑距離也不是全局最優(yōu)的。環(huán)境越復(fù)雜，基本蟻群算法的劣勢(shì)表現(xiàn)得越明顯，而改進(jìn)煙花?蟻群算法仍能快速、高精度地在參考路徑附近尋找到全局有效最優(yōu)路徑。

圖10 基于改進(jìn)煙花-蟻群混合算法、蟻群算法的平均路徑長度收斂曲線對(duì)比Fig.10 Comparison of convergence curves of average path length based on improved fireworks-ant colony hybrid algorithms and ant colony algorithm

圖11 基于改進(jìn)煙花-蟻群混合算法、蟻群算法尋找到的最優(yōu)路徑對(duì)比Fig.11 Optimal path comparison based on improved fireworksant colony hybrid algorithm and ant colony algorithm

由表1可知，改進(jìn)煙花算法能在非常短的時(shí)間內(nèi)尋找到參考路徑。在同樣的環(huán)境和參數(shù)下，改進(jìn)煙花?蟻群混合算法的計(jì)算時(shí)間約為基本蟻群算法的一半。就尋找到的最優(yōu)路徑的精度而言，改進(jìn)煙花?蟻群混合算法基本找到了客觀上的最優(yōu)路徑，而基本蟻群算法的最優(yōu)路徑精度則較低。實(shí)際上，該混合算法在很少的迭代次數(shù)下就尋找到了全局有效最優(yōu)路徑，因而該算法實(shí)際尋找到的最優(yōu)路徑的時(shí)間比表1中還要短很多。

表1 算法結(jié)果比較Table 1 Comparison of algorithm results

5 結(jié)論

本文針對(duì)考慮海流和障礙物影響的二維海流環(huán)境下UUV避障路徑的規(guī)劃問題，建立了含有隨機(jī)分布障礙物的二維海流環(huán)境模型和綜合考慮能量消耗代價(jià)、航行時(shí)間代價(jià)、航行距離代價(jià)的路徑規(guī)劃數(shù)學(xué)模型，應(yīng)用改進(jìn)煙花?蟻群混合算法對(duì)該非線性優(yōu)化問題進(jìn)行了求解。實(shí)驗(yàn)結(jié)果表明，該算法能夠快速尋找到全局最優(yōu)解，為水下無人潛航器避障路徑的規(guī)劃提供了一個(gè)新途徑。