孫海文，肖玉杰，王生玉

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

0 引言

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

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

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

柵格（grid）法[1]，即用編碼的柵格來(lái)表示地圖，把包含障礙物的柵格標(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

無(wú)人航行器節(jié)點(diǎn)的位置移動(dòng)方式如圖2 所示。

圖2 位置移動(dòng)模式Fig.2 Position movement mode

2 改進(jìn)型A*-蟻群混合算法

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

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

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

2.2 改進(jìn)型蟻群算法

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

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

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

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

2.3 改進(jìn)型A＊-蟻群混合算法

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

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

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

3 仿真實(shí)驗(yàn)

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

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

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

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

圖4 中的路線規(guī)劃路徑長(zhǎng)度和運(yùn)行時(shí)間統(tǒng)計(jì)如表1所示。

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

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

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

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

圖5 中的路線規(guī)劃路徑長(zhǎng)度和運(yùn)行時(shí)間統(tǒng)計(jì)如表2所示。

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

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

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

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

4 結(jié)語(yǔ)

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