船舶全局路徑規(guī)劃相關(guān)算法研究綜述

李元昊，段鵬飛，郭紹義，韓 洋，秦 圻

（山東交通學(xué)院航運(yùn)學(xué)院，山東威海 264200）

0 引言

船舶的全局路徑規(guī)劃就是根據(jù)設(shè)定的評(píng)價(jià)標(biāo)準(zhǔn)，為一定航行環(huán)境中的船舶搜索出一條由起點(diǎn)至終點(diǎn)的無(wú)碰撞路徑，將靜態(tài)環(huán)境信息的全局規(guī)劃和不確定環(huán)境因素的動(dòng)態(tài)局部規(guī)劃相結(jié)合可使船舶路徑規(guī)劃達(dá)到較為理想的狀態(tài)。全局路徑規(guī)劃主要應(yīng)用于相對(duì)穩(wěn)定的環(huán)境，其普遍性相對(duì)較強(qiáng)。如圖1所示，船舶全局路徑規(guī)劃算法可分為傳統(tǒng)全局路徑規(guī)劃算法和智能優(yōu)化全局路徑規(guī)劃算法。本文對(duì)各類算法的發(fā)展背景、設(shè)計(jì)原理及具體路徑規(guī)劃場(chǎng)景下的應(yīng)用優(yōu)化進(jìn)行對(duì)比分析，并對(duì)全局路徑規(guī)劃算法的發(fā)展趨勢(shì)進(jìn)行展望。

圖1 全局路徑規(guī)劃算法分類

1 傳統(tǒng)全局路徑規(guī)劃算法

1.1 Dijkstra算法

Dijkstra算法為 Dijkstra在研究貪心算法的過(guò)程中提出的解決最短路徑問(wèn)題的方法，該算法屬于單源路徑算法，可計(jì)算質(zhì)點(diǎn)在運(yùn)動(dòng)過(guò)程中由起始點(diǎn)運(yùn)動(dòng)到其他頂點(diǎn)時(shí)的最短距離。宋勇和王文豐等將Dijkstra算法作為路徑規(guī)劃初始模型，并在此基礎(chǔ)上進(jìn)一步改進(jìn)和優(yōu)化。杜貽群等針對(duì)無(wú)人艇進(jìn)行直角和斜向轉(zhuǎn)彎的航行特點(diǎn)對(duì)Dijkstra算法的路徑搜索進(jìn)行改進(jìn)，提出了一種改進(jìn)的多方向路徑搜索算法，其轉(zhuǎn)向更為平滑，可充分適應(yīng)無(wú)人艇實(shí)際的航行要求，具有很好的適應(yīng)性。王月鵬利用Dijkstra算法對(duì)自主規(guī)劃路徑進(jìn)行優(yōu)化，實(shí)現(xiàn)無(wú)人船在水質(zhì)采樣過(guò)程中的多點(diǎn)采樣功能。

Dijkstra算法計(jì)算思路清晰，可有效尋找最優(yōu)解。然而，當(dāng)路徑規(guī)劃較為復(fù)雜時(shí)，計(jì)算所需的數(shù)據(jù)節(jié)點(diǎn)劇增，這會(huì)導(dǎo)致運(yùn)行時(shí)間大量增加，進(jìn)而降低運(yùn)行效率。

1.2 A＊算法

A算法由Peterhart等提出，該算法將最佳優(yōu)先搜索算法（Best-First-Search，BFS）和 Dijkstra算法結(jié)合在一起。對(duì)于靜態(tài)環(huán)境下全局路徑規(guī)劃的最短路徑問(wèn)題，A算法是最有效的直接搜索算法之一。

A算法的原理：通過(guò)設(shè)置代價(jià)評(píng)估函數(shù)對(duì)節(jié)點(diǎn)的綜合優(yōu)先級(jí)進(jìn)行估計(jì)，運(yùn)用廣度優(yōu)先思想從起始點(diǎn)為中心向外層層擴(kuò)展，直至遍歷到終點(diǎn)時(shí)得到最短路徑。

熊壬浩等對(duì) A算法的運(yùn)算過(guò)程及改進(jìn)方法進(jìn)行了詳細(xì)的描述。武善平等和陳新等主要對(duì)A算法的啟發(fā)函數(shù)提出改進(jìn)，前者利用自適應(yīng)的改進(jìn)啟發(fā)函數(shù)，并著重考慮目標(biāo)點(diǎn)的方位信息和障礙物的安全距離；后者對(duì)啟發(fā)函數(shù)、分區(qū)距離信息和角度變量進(jìn)行加權(quán)處理以提高搜索效率。

由于規(guī)劃路徑的轉(zhuǎn)折點(diǎn)較多、搜索范圍相對(duì)較小，A算法容易形成局部最優(yōu)的情況。張丹紅等和高峰等分別對(duì) A算法的搜索方式和節(jié)點(diǎn)搜索領(lǐng)域進(jìn)行改進(jìn)和擴(kuò)展，將八角度、八鄰域節(jié)點(diǎn)搜索擴(kuò)充到多角度、多鄰域的搜索，從而提高空間搜索能力和收斂速度。

相比傳統(tǒng)的Dijkstra算法，A算法在計(jì)算目標(biāo)點(diǎn)與下一個(gè)頂點(diǎn)之間的距離的同時(shí)會(huì)預(yù)估目標(biāo)點(diǎn)與終點(diǎn)之間的距離，進(jìn)而減少無(wú)用的計(jì)算量。目前，Dijkstra算法和A算法常與其他算法結(jié)合使用，或根據(jù)具體的應(yīng)用場(chǎng)景適當(dāng)優(yōu)化以減少計(jì)算量。

1.3 模擬退火算法（Simulated Annealing 1.3 Algorithm，SA）

METROPOLIS等最早提出模擬退火算法，KIRKPATRICK等將模擬退火算法應(yīng)用到組合優(yōu)化領(lǐng)域。在船舶的路徑規(guī)劃中，模擬退火算法更適合用于局部搜索，但其目前在全局路徑搜索的過(guò)程中仍起到不可或缺的作用。模擬退火算法通常與其他路徑規(guī)劃算法結(jié)合使用，以避免出現(xiàn)路徑規(guī)劃局部最優(yōu)的情況。

針對(duì)模擬退火算法在水面無(wú)人艇在路徑規(guī)劃中全局搜索能力不足的問(wèn)題，鄭佳春等將模擬退火算法與粒子群算法相結(jié)合，提出Simulated Annealing Particle Swarm Optimization（SAPSO）混合算法，該算法收斂性好，且能規(guī)避局部最優(yōu)解。SAPSO混合算法適用于不確定因素影響下的動(dòng)態(tài)環(huán)境規(guī)劃問(wèn)題。

2 智能優(yōu)化全局路徑規(guī)劃算法

智能優(yōu)化算法是一種啟發(fā)式優(yōu)化算法，包括遺傳算法、蟻群算法、禁忌搜索算法、模擬退火算法、粒子群算法等。智能優(yōu)化算法一般是針對(duì)具體問(wèn)題設(shè)計(jì)相關(guān)的算法，理論要求弱，技術(shù)性強(qiáng)。智能算法與最優(yōu)化算法進(jìn)行比較，相比之下，智能算法速度快，應(yīng)用性強(qiáng)。對(duì)于未知海況環(huán)境下控制參數(shù)的約束優(yōu)化問(wèn)題，可采用智能算法予以有效解決。

2.1 神經(jīng)網(wǎng)絡(luò)算法

神經(jīng)網(wǎng)絡(luò)算法采用并列連接的方式，在路徑規(guī)劃時(shí)盡量遠(yuǎn)離障礙物以使獲得的路徑最短。根據(jù)神經(jīng)網(wǎng)絡(luò)算法中各神經(jīng)元是否存在反饋、是否能接受外加輸入與其他各節(jié)點(diǎn)的反饋以及自身的反饋情況，可將神經(jīng)網(wǎng)絡(luò)算法分為前饋神經(jīng)網(wǎng)絡(luò)算法和反饋神經(jīng)網(wǎng)絡(luò)算法。

神經(jīng)網(wǎng)絡(luò)算法通過(guò)參數(shù)設(shè)置實(shí)現(xiàn)自我學(xué)習(xí)的功能，規(guī)劃速度快、結(jié)構(gòu)簡(jiǎn)單、魯棒性強(qiáng)。神經(jīng)網(wǎng)絡(luò)算法存在以下不足之處：1）泛化能力和記憶能力較差；2）學(xué)習(xí)速率通常不變；3）學(xué)習(xí)參數(shù)不具備存儲(chǔ)功能。針對(duì)神經(jīng)網(wǎng)絡(luò)算法的不足之處，很多學(xué)者對(duì)其進(jìn)行相應(yīng)的優(yōu)化和改進(jìn)，或?qū)⑵渑c其他算法組合使用。

耿曉龍等和呂揚(yáng)民等通過(guò)將人工神經(jīng)網(wǎng)絡(luò)與強(qiáng)化學(xué)習(xí)算法中的Q學(xué)習(xí)算法相結(jié)合，以有效解決路徑規(guī)劃在不同領(lǐng)域的相關(guān)問(wèn)題。其中，耿曉龍通過(guò)在強(qiáng)化學(xué)習(xí)中設(shè)立獎(jiǎng)罰規(guī)則，將神經(jīng)網(wǎng)絡(luò)與Q學(xué)習(xí)算法有效結(jié)合，得到路徑規(guī)劃最優(yōu)解，并通過(guò)實(shí)驗(yàn)仿真對(duì)算法進(jìn)行驗(yàn)證。

2.2 遺傳算法

遺傳算法是JOHN在生物進(jìn)化論的自然選擇和遺傳變異觀點(diǎn)的基礎(chǔ)上提出的。該算法通過(guò)加入選擇、交叉和變異算子對(duì)初始長(zhǎng)度編碼下的種群進(jìn)行運(yùn)算，并將適應(yīng)度作為路徑解的評(píng)價(jià)標(biāo)準(zhǔn)。遺傳算法的邏輯流程見表2。

圖2 遺傳算法的邏輯流程

遺傳算法具有選擇、交叉、變異的特征，故其搜索過(guò)程具有靈活多變的特點(diǎn)，可有效提高全局路徑的搜索能力。然而，遺傳算法的計(jì)算速度較慢、路徑拐點(diǎn)較多、算法的實(shí)時(shí)性和適應(yīng)性較差。

欒志玲與馬建敏等對(duì)交叉變異的概率進(jìn)行自適應(yīng)調(diào)整以提高算法的全局搜索效率，使用自適應(yīng)交叉變異概率替代現(xiàn)有交叉變異概率以避免早熟現(xiàn)象的出現(xiàn)。欒志玲提出一種改進(jìn)遺傳算法，在原來(lái)基礎(chǔ)之上增加種群熵對(duì)種群多樣性進(jìn)行評(píng)估，并通過(guò)Matlab仿真驗(yàn)證了算法的可行性。

馬丹提出使用精英保留策略方法來(lái)解決遺傳算法收斂性慢的問(wèn)題，提出增加免疫算子來(lái)解決遺傳算法多樣性減少的問(wèn)題。文獻(xiàn)[23]提出一種改進(jìn)策略，通過(guò)增加插入、刪除算子對(duì)路徑編碼進(jìn)行優(yōu)化，可有效提高解空間內(nèi)的尋優(yōu)效率。

2.3 蟻群算法

蟻群算法屬于生物啟發(fā)式類的算法，其最鮮明的特點(diǎn)在于螞蟻群體的多樣性和路徑搜索的正反饋特性。在選擇路徑的過(guò)程中，路徑選擇概率和信息素?fù)]發(fā)系數(shù)是決定全局尋優(yōu)能力的重要因素，由初始信息素和啟發(fā)信息的大小決定。

路徑選擇概率和啟發(fā)信息的計(jì)算公式分別為

式（1）和式（2）中：下標(biāo)和為節(jié)點(diǎn)；為節(jié)點(diǎn)數(shù)量；為時(shí)刻；和分別為信息素因子和啟發(fā)函數(shù)因子，反映信息素和啟發(fā)函數(shù)對(duì)螞蟻下一步轉(zhuǎn)移作用的強(qiáng)度；為兩節(jié)點(diǎn)間的直線距離。

由式（1）可知，信息素和啟發(fā)信息與路徑選擇的概率之間存在正相關(guān)關(guān)系。該算法的正反饋特性可使算法在搜索過(guò)程中不斷收斂，最終逼近最優(yōu)解。

啟發(fā)式的概率搜索具有著跳出局部最優(yōu)解的特點(diǎn)，多個(gè)體同時(shí)搜索的效率相比單個(gè)體搜索得到明顯提高。然而，算法中個(gè)體分布情況會(huì)導(dǎo)致算法的收斂速度與種群多樣性之間存在矛盾。隨機(jī)選擇探索全局空間最優(yōu)解大概率可找到最短路徑，但需要很長(zhǎng)時(shí)間才能發(fā)揮正反饋的作用。

針對(duì)傳統(tǒng)蟻群算法初期搜索效率低、收斂較慢的問(wèn)題，王成等采用不均勻分布初始信息素、引入權(quán)重因子等方式對(duì)蟻群信息更新規(guī)則進(jìn)行改進(jìn)。賀嘉等將雙向搜索算法融入傳統(tǒng)蟻群算法，可顯著提高搜索效率，模擬仿真及實(shí)船試驗(yàn)驗(yàn)證了算法的可行性。

童幫裕等針對(duì)冰區(qū)航行路徑規(guī)劃的特殊性，考慮航線距離、航行操作復(fù)雜度和流冰規(guī)避等影響因素，結(jié)合人工勢(shì)場(chǎng)法對(duì)蟻群算法進(jìn)行改進(jìn)，利用新的啟發(fā)信息函數(shù)進(jìn)行路徑選擇。研究結(jié)果表明：該算法在在動(dòng)態(tài)避讓、航速控制方面仍有待改進(jìn)和優(yōu)化。

馬小銘等提出一種改進(jìn)蟻群算法，主要通過(guò)引入環(huán)境因子以調(diào)整啟發(fā)函數(shù)，進(jìn)而降低死鎖情況的發(fā)生，該算法對(duì)于船舶路徑規(guī)劃問(wèn)題具有重要借鑒意義。王成等通過(guò)引入懲戒因子對(duì)陷入死鎖的信息素進(jìn)行懲罰，進(jìn)而降低死鎖率。然而，該方法沒有考慮發(fā)生死鎖的環(huán)境細(xì)節(jié)。EBERHARTR等通過(guò)引入環(huán)境因子以增強(qiáng)對(duì)環(huán)境的閱讀能力，進(jìn)而有效避免死鎖，提高有效螞蟻的數(shù)量。

2.4 粒子群算法

粒子群算法由EBERHART等提出，屬于概率型全局路徑規(guī)劃算法。該算法不斷對(duì)個(gè)體和群體的最優(yōu)位置進(jìn)行搜索，直到找到全局最優(yōu)解。其中，個(gè)體優(yōu)劣程度的適應(yīng)值評(píng)價(jià)函數(shù)直接影響到算法的執(zhí)行效率，下面通過(guò)流程圖的方式對(duì)算法原理進(jìn)行說(shuō)明。粒子群算法的邏輯流程見圖3。

圖3 遺傳算法的邏輯流程

粒子群算法從隨機(jī)解出發(fā)通過(guò)迭代尋找最優(yōu)解，且可調(diào)參數(shù)較少，故其具有應(yīng)用簡(jiǎn)單、收斂速度快、計(jì)算復(fù)雜程度較低等特點(diǎn)，但同樣存在尋優(yōu)過(guò)程中種群多樣性和算法收斂速度上的矛盾。

王文豐等利用線性遞減慣性權(quán)重粒子群算法進(jìn)行路徑規(guī)劃，引入混沌理論對(duì)種群進(jìn)行初始化，以平衡種群的全局搜索能力和局部搜索能力。宋勇對(duì)線性遞減慣性權(quán)重粒子群算法以及引入混沌理論的改進(jìn)算法進(jìn)行了更加詳細(xì)的描述，并在此基礎(chǔ)上進(jìn)行動(dòng)態(tài)避障研究。通過(guò)結(jié)合局部動(dòng)態(tài)的路徑規(guī)劃中改進(jìn)的滾動(dòng)窗口算法對(duì)動(dòng)態(tài)威脅區(qū)域進(jìn)行有效的規(guī)避，進(jìn)而得到最優(yōu)路徑解。

針對(duì)多路徑規(guī)劃問(wèn)題，劉利強(qiáng)等在粒子群算法的基礎(chǔ)上引入小生境識(shí)別、粒子群隔離算法、交叉算子等，將種群粒子分為主群粒子和子群粒子，在此基礎(chǔ)上完成區(qū)域內(nèi)局部尋優(yōu)，從而有效規(guī)劃出多條最優(yōu)及次優(yōu)路徑。

鄭佳春等將粒子群算法與模擬退火算法相結(jié)合，對(duì)無(wú)人船艇的路徑規(guī)劃進(jìn)行研究。舒宗玉采用混合粒子群算法對(duì)初始路徑進(jìn)行優(yōu)化，并在路徑最短基礎(chǔ)上提出路徑平滑和路徑安全的多目標(biāo)優(yōu)化問(wèn)題，但仍需進(jìn)一步精確測(cè)量才能符合實(shí)際要求。

3 發(fā)展趨勢(shì)分析

1）結(jié)合具體應(yīng)用環(huán)境與算法特點(diǎn)優(yōu)化常規(guī)算法性能

為獲得路徑規(guī)劃的最優(yōu)解并使得所規(guī)劃的路徑符合各種航行環(huán)境和應(yīng)用場(chǎng)景，對(duì)各種規(guī)劃算法的運(yùn)用大致可分為以下3種：（1）對(duì)常規(guī)算法中的不足進(jìn)行改進(jìn)；（2）利用多種算法的優(yōu)勢(shì)進(jìn)行適當(dāng)?shù)乃惴ňC合；（3）將改進(jìn)優(yōu)化算法與常規(guī)的某類算法進(jìn)行結(jié)合產(chǎn)生新的混合算法。在保證路徑規(guī)劃有效性的同時(shí)，主要通過(guò)控制算法的收斂速度、提高全局搜索的效率、防止局部收斂的出現(xiàn)等方式來(lái)提高算法性能。

2）仿真與實(shí)船試驗(yàn)對(duì)路徑規(guī)劃理論計(jì)算結(jié)果驗(yàn)證有待進(jìn)一步的完善

針對(duì)路徑規(guī)劃算法的研究目前大都還處于理論描述以及模擬仿真驗(yàn)證階段，僅有少數(shù)的研究通過(guò)仿真和實(shí)船進(jìn)行驗(yàn)證。通過(guò)實(shí)船對(duì)算法過(guò)程的驗(yàn)證往往與理論計(jì)算有一定的差距，雖然對(duì)實(shí)驗(yàn)設(shè)計(jì)的要求較高，但更能直觀反映方法在真實(shí)海洋環(huán)境中的應(yīng)用效果，可以對(duì)存在的隱患問(wèn)題和突發(fā)狀況進(jìn)行排查，并選擇更適合的解決方案以適應(yīng)海洋航行的需要，降低航行突發(fā)風(fēng)險(xiǎn)的發(fā)生概率，也能使算法的實(shí)用性和推廣性得到保障。

3）借鑒其他領(lǐng)域研究成果使全局路徑規(guī)劃與局部路徑規(guī)劃相結(jié)合

當(dāng)前對(duì)路徑規(guī)劃的研究往往在全局路徑規(guī)劃的基礎(chǔ)上對(duì)局部不確定因素下的動(dòng)態(tài)規(guī)劃進(jìn)行綜合考慮，或?qū)Χ嗄繕?biāo)條件或多路徑條件下的路徑規(guī)劃問(wèn)題進(jìn)行研究。對(duì)環(huán)境感知的動(dòng)態(tài)路徑規(guī)劃算法在機(jī)器人路徑規(guī)劃中應(yīng)用廣泛，對(duì)無(wú)人船在復(fù)雜環(huán)境下的路徑規(guī)劃幫助很大。

4 結(jié)論

船舶路徑規(guī)劃算法對(duì)于無(wú)人艦艇在各種環(huán)境下的自主航行至關(guān)重要，本文對(duì)各類算法的發(fā)展背景、設(shè)計(jì)原理及具體路徑規(guī)劃場(chǎng)景下的應(yīng)用優(yōu)化進(jìn)行對(duì)比分析，并對(duì)全局路徑規(guī)劃算法的發(fā)展趨勢(shì)進(jìn)行展望，希望為無(wú)人艇全局路徑規(guī)劃算法的優(yōu)化提供一定指導(dǎo)。