孫海文，肖玉杰，王生玉

(1.中國人民解放軍91054 部隊，北京 102442；2.海軍航空大學(xué)，山東 青島 266000)

0 引言

航跡規(guī)劃[1]是USV 研究領(lǐng)域中最主要的研究方向之一。USV 航跡規(guī)劃指規(guī)劃出一條安全快速到達目標(biāo)位置的路徑。

航跡規(guī)劃主要研究避障問題。目前，傳統(tǒng)的航跡規(guī)劃算法有模擬退火算法[2]、禁忌搜索算法[3]、A*算法[4]、人工視場法[5–6]等。隨著智能仿生學(xué)算法的發(fā)展和應(yīng)用，逐漸將遺傳算法[7]、粒子群算法[8]以及蟻群算法[9]等用于航跡規(guī)劃。其中，A*算法具有較強的全局搜索能力，在低密度避障環(huán)境中能夠快速高效地規(guī)劃出到達目標(biāo)點的合理路徑，但當(dāng)避障環(huán)境密度較高時，A*算法容易陷入局部死區(qū)。蟻群算法具有較強的魯棒性，在高密度環(huán)境下亦能找到合理路徑，但其收斂速度較慢。因此本文將水面環(huán)境進行分割，在高密度環(huán)境中設(shè)置過度目標(biāo)點，在低密度環(huán)境下采用A*算法進行航路規(guī)劃，當(dāng)目標(biāo)到達過度目標(biāo)點，則采用蟻群算法進行搜索規(guī)劃航路。從而提高了USV 全局和局部航路規(guī)劃能力。

1 航行環(huán)境模型

柵格（grid）法[1]，即用編碼的柵格來表示地圖，把包含障礙物的柵格標(biāo)記為障礙柵格，反之則為自由柵格，以此為基礎(chǔ)作路徑搜索。柵格法是目前研究最為廣泛的空間規(guī)劃方法。構(gòu)建路徑規(guī)劃環(huán)境，令障礙物的柵格狀態(tài)為1，自由柵格狀態(tài)為0。環(huán)境矩陣為：

模擬空間環(huán)境如圖1 所示。

圖1 模擬的空間環(huán)境Fig.1 Simulated space environment

無人航行器節(jié)點的位置移動方式如圖2 所示。

圖2 位置移動模式Fig.2 Position movement mode

2 改進型A*-蟻群混合算法

2.1 啟發(fā)式A＊算法

A*算法[4]的估價函數(shù)為：

式中：f(n)為當(dāng)前USV 所處的節(jié)點n的總代價；g(n,s)為節(jié)點n到起始節(jié)點s的實際代價函數(shù)；h(n,e)為節(jié)點n到目標(biāo)節(jié)點e的預(yù)估代價函數(shù)。

2.2 改進型蟻群算法

在傳統(tǒng)的蟻群算法[10–11]中，當(dāng)所有螞蟻完成一次迭代后，對路徑上(i,j)上的信息量進行調(diào)整，調(diào)整公式：

式中：τij(t+n)表示t+n時刻路徑 (i,j)上的信息濃度；ρ表示信息素揮發(fā)系數(shù)；1-ρ 表示信息素殘留因子；Δτij(t)表示本次循環(huán)中所有螞蟻在路徑 (i,j)上釋放的信息素濃度之和；Q為一常數(shù)；Lk表示第k只螞蟻在本次循環(huán)中所走的總路徑長度。

為增強蟻群算法的快速性和有效性，本次改進了信息素的更新模型，增強了可行路徑中最優(yōu)路徑的信息濃度，減弱了最差路徑的信息濃度，并通過調(diào)整信息素濃度總和比例，增強算法的尋優(yōu)能力。

式中：Lmin表示第k只螞蟻在所經(jīng)歷的迭代中可行路徑的最小值；Lmax表示第k只螞蟻在所經(jīng)歷的迭代中可行路徑的最大值。

2.3 改進型A＊-蟻群混合算法

USV的航路規(guī)劃分為全局規(guī)劃和局部規(guī)劃。算法首先利用A*算法進行全局規(guī)劃，當(dāng)遇到高密度環(huán)境，則采用蟻群算法，通過蟻群信息素搜索原理，進行障礙的規(guī)避。

根據(jù)環(huán)境柵格圖的特點在高密度局部圖中設(shè)置過渡節(jié)點，過渡節(jié)點的總代價函數(shù)要小于USV 所處節(jié)點的代價。目標(biāo)先采用A*算法朝向目標(biāo)節(jié)點進行全局規(guī)劃，到達過渡節(jié)點時采用蟻群搜索算法進行局部規(guī)劃。在USV的全局航行過程中，不斷采用蟻群算法進行局部高密度避障在，可有效地提高航行器在復(fù)雜環(huán)境中的航路規(guī)劃能力，避免陷入局部死鎖。算法流程如圖3 所示。

圖3 改進的A*-螞蟻混合算法流程圖Fig.3 Flow chart of improved A * -ant hybrid algorithm

3 仿真實驗

為了驗證本文所提改進型A*-蟻群混合算法的有效性和優(yōu)勢性，進行仿真實驗比較。

3.1 低密度簡單環(huán)境下的仿真比較分析

本仿真試驗選取22 km×22 km的正方形水域，采用柵格法劃分該區(qū)域為22×22的網(wǎng)格，各網(wǎng)格表示1 km×1 km 區(qū)域。黑色表示障礙物區(qū)或禁航區(qū)，白色表示自由航行區(qū)。分別采用傳統(tǒng)A*算法、蟻群算法、改進型蟻群算法、改進型A*-蟻群混合算法進行航路規(guī)劃。蟻群規(guī)模為M=50，最大迭代次數(shù)為N=100；信息素重要程度因子α=1；啟發(fā)函數(shù)重要程度因子β=5；常系數(shù)Q=2 000；信息素揮發(fā)因子為ρ=0.7；單位柵格邊長為1 km。仿真結(jié)果如圖4 所示。

圖4 四種算法的仿真結(jié)果Fig.4 Simulation results of four algorithms

圖4 中的路線規(guī)劃路徑長度和運行時間統(tǒng)計如表1所示。

表1 四種算法的數(shù)據(jù)統(tǒng)計Tab.1 Data statistics of four algorithms

根據(jù)圖4 和表1 比較分析，4 種方法的路徑長度比較為改進型蟻群算法<本文算法

3.2 高密度復(fù)雜環(huán)境下仿真比較分析

為了進一步證明該算法的優(yōu)越性和有效性。選取面積為45 km×45 km的正方形水域，采用柵格法將面積劃分為45×45 個網(wǎng)格，每個網(wǎng)格代表1 km×1 km的面積。分別采用傳統(tǒng)A*算法、蟻群算法、改進型蟻群算法、改進型A*-蟻群混合算法進行航路規(guī)劃。仿真參數(shù)不變，增加了障礙的復(fù)雜性。仿真結(jié)果如圖5 所示。

圖5 中的路線規(guī)劃路徑長度和運行時間統(tǒng)計如表2所示。

根據(jù)圖5 和表2的比較分析，4 種方法的路徑長度比較為：本文算法<改進型蟻群算法<傳統(tǒng)蟻群算法

圖5 四種算法的仿真結(jié)果Fig.5 Simulation results of four algorithms

表2 四種算法的數(shù)據(jù)統(tǒng)計Tab.2 Data statistics of four algorithms

仿真結(jié)果表明，A*算法在低密度、小規(guī)模環(huán)境下具有較強的路徑規(guī)劃能力和較短的運行時間。然而，在高密度、復(fù)雜的環(huán)境中，A*算法容易陷入死區(qū)。與傳統(tǒng)蟻群算法和A*算法相比，本文提出的算法大大提高了路徑規(guī)劃的質(zhì)量和效率，能夠快速有效地完成OSV的路徑規(guī)劃。

4 結(jié)語

針對高密度復(fù)雜環(huán)境下的無人水面航行器（USV）航跡規(guī)劃問題，本算法有效地增強USV 航跡規(guī)劃能力，解決了傳統(tǒng)蟻群算法和A*算法各自使用不能兼顧全局和局部規(guī)劃的問題。通過仿真比較分析，本算法能夠有效地平衡全局和局部規(guī)劃，提高在復(fù)雜環(huán)境下的USV 航跡規(guī)劃能力。本文方法將為USV 大規(guī)模復(fù)雜的環(huán)境任務(wù)提供研究依據(jù)。