郭銀景，孟慶良，孔 芳，呂文紅

1.山東科技大學(xué)電子信息工程學(xué)院，山東青島266590

2.青島智海牧洋科技有限公司，山東青島266590

3.山東科技大學(xué)交通學(xué)院，山東青島266590

1 引言

21世紀以來，隨著人類科學(xué)技術(shù)的不斷進步，人們對海洋資源的開發(fā)和投入也隨之增大。海洋擁有豐富的礦產(chǎn)資源、海洋生物資源、可再生能源，是人類社會可持續(xù)發(fā)展的重要資產(chǎn)。因此，海上技術(shù)的發(fā)展和相關(guān)競爭已成為許多發(fā)達國家的戰(zhàn)略要點。自主水下航行器（autonomous underwater vehicle，AUV）作為海洋作業(yè)的重要工具，非常適合海上搜索、調(diào)查、識別和打撈作業(yè)。因此，AUV路徑規(guī)劃技術(shù)的研究與發(fā)展就使得海洋開發(fā)進入了一個新時代[1]。對于AUV路徑規(guī)劃的研究始于20世紀70年代，至今仍然是各國研究的熱點問題。AUV導(dǎo)航技術(shù)中的路徑規(guī)劃問題是AUV研究的核心問題之一，而路徑規(guī)劃的核心就是算法的設(shè)計[2]。本文將AUV路徑規(guī)劃算法劃分為環(huán)境建模和路徑搜索兩類。合理的環(huán)境建模方法有利于減少路徑搜索次數(shù)，不同的路徑搜索算法基于不同的環(huán)境模型。常用環(huán)境建模方法主要有：柵格法、可視圖法、維諾圖法等。路徑搜索算法主要包括人工勢場法、快速步進法、A*算法、粒子群優(yōu)化算法等。AUV路徑規(guī)劃技術(shù)的核心就是算法的設(shè)計。目前，AUV路徑規(guī)劃算法的研究已經(jīng)引起了廣泛的關(guān)注。從傳統(tǒng)算法到后來結(jié)合仿生學(xué)發(fā)展起來的智能算法，AUV路徑規(guī)劃算法的發(fā)展已經(jīng)取得了很大的進步[3]。不同的路徑規(guī)劃算法特點不同，適用范圍和領(lǐng)域也就不同。本文從路徑規(guī)劃算法自身特點出發(fā)，對路徑規(guī)劃算法的應(yīng)用領(lǐng)域和發(fā)展狀況進行綜述，闡述各算法的優(yōu)缺點以及后人的改進算法，對路徑規(guī)劃技術(shù)的發(fā)展具有重要意義。

2 基于環(huán)境建模的路徑規(guī)劃算法

路徑規(guī)劃具體實現(xiàn)時需要分成環(huán)境建模和路徑搜索兩個步驟進行。首先需要處理環(huán)境信息，構(gòu)建相應(yīng)的數(shù)學(xué)模型，依據(jù)不同的策略處理環(huán)境信息，以便于對環(huán)境進行分析和計算，對路徑進行搜索和優(yōu)化。合理的建模方法有利于減少路徑規(guī)劃的計算量，從而加快運算速度，減少存儲空間。不同路徑搜索算法基于不同的環(huán)境建模方法。目前應(yīng)用于環(huán)境建模的主要方法有可視圖法、柵格法、維諾圖法等。

2.1 柵格法

柵格法（grid），最早是由Howden在1968年提出的，一般作為路徑規(guī)劃的環(huán)境建模技術(shù)來用，是AUV最常用的建模方法之一[4]。在進行路徑規(guī)劃時采用柵格表示地圖，如圖1所示，處理障礙物的邊界時，避免了復(fù)雜的計算。它具有表示不規(guī)則障礙物的能力，并適用于所有類型的傳統(tǒng)或智能路徑搜索算法。

Fig.1 Grid method圖1 柵格法

起初，研究者將柵格法應(yīng)用于AUV的水下三維空間進行環(huán)境建模[5-7]，但發(fā)現(xiàn)規(guī)劃的空間內(nèi)包含大量數(shù)據(jù)，占用系統(tǒng)的大部分存儲空間?；谏鲜鰡栴}，2014年，Tanakitkorn等[8]提出一種改進算法，即在實驗中不考慮水深，將三維空間簡化為基于網(wǎng)格法的二維水下環(huán)境模型。雖然環(huán)境信息存在丟失，但節(jié)省了系統(tǒng)空間，取得了令人滿意的效果。針對三維動態(tài)環(huán)境中AUV的水下目標搜索問題，2019年，Zhu等[9]構(gòu)建水下二維環(huán)境離散柵格圖，根據(jù)柵格圖構(gòu)建相應(yīng)的生物啟發(fā)式神經(jīng)動力學(xué)模型來表示動態(tài)環(huán)境信息，利用該模型自適應(yīng)地躲避障礙物，吸引目標搜索區(qū)域，提高了AUV搜索效率，減少AUV路徑規(guī)劃時間。柵格法作為常用AUV路徑規(guī)劃算法，它很難直接解決復(fù)雜的環(huán)境信息問題，一般需要與其他路徑搜索算法結(jié)合來進行路徑規(guī)劃。

2.2 可視圖法

可視圖法（visibility graph）是在1979年由Lozano和Wesley首次提出的，主要應(yīng)用于全局路徑規(guī)劃中的環(huán)境建模?？梢晥D法的優(yōu)點是可以直觀地從可視圖中求得最短路徑，方法簡單。缺點是一旦起點和目標點發(fā)生變化，就必須重構(gòu)可視圖，缺乏靈活性，如圖2所示。

Fig.2 Visibility graph method圖2 可視圖法

對于在海底稀疏和密集區(qū)域中具有不同規(guī)則幾何實體的障礙物，文獻[10]提出一種基于可視圖幾何理論的AUV路徑規(guī)劃算法，該算法利用常規(guī)幾何實體對三維海洋環(huán)境進行建模，在考慮能耗的前提下，規(guī)劃三維環(huán)境中AUV可航行路徑。2013年，Gal[11]在傳統(tǒng)可視圖法建模的基礎(chǔ)上，又做出進一步的研究，提出一種基于可視圖法的改進空間模型，該模型主要減少了構(gòu)建節(jié)點的數(shù)量，從而提高計算效率，又添加了螺旋算法，更好地實現(xiàn)AUV避障。為了避免與海洋復(fù)雜障礙物發(fā)生碰撞，2018年，Xidias等[12]提出一種基于動態(tài)可視圖的導(dǎo)航算法。使用動態(tài)可視圖完成AUV實時自主海上導(dǎo)航，該算法在多種情況下進行測試，以證明其魯棒性并滿足不同約束條件，在獲得最優(yōu)路徑的同時有效避碰?？梢晥D法的局部路徑規(guī)劃能力較差，常常適用于全局和連續(xù)區(qū)域內(nèi)的路徑規(guī)劃[13]。

2.3 維諾圖法

維諾圖法（Voronoi diagram）是由Dunlaing和Yap在1985年提出的，是一種通用的建模方法。在模型構(gòu)建領(lǐng)域，維諾圖法廣泛應(yīng)用于三維模型構(gòu)建中，生成一個3D全局路線維諾圖，可確保AUV在作業(yè)時遠離障礙物，如圖3所示。文獻[14]中提供了一些使用維諾圖法對AUV進行水下建模的實例。

Fig.3 Voronoi graph method圖3 維諾圖法

傳統(tǒng)Voronoi圖法生成的路徑相對安全且距離障礙物較遠，然而，生成的路徑不平滑。針對這一問題，2013年，Candeloro等[15]提出一種基于維諾圖和費馬螺旋段的曲率連續(xù)路徑規(guī)劃算法。采用費馬螺旋段來平滑路徑和提供曲率連續(xù)性，產(chǎn)生曲率連續(xù)的路徑，該算法最終得到一條僅由直線和螺旋段組成的安全、平滑的AUV可航行路徑。航行穩(wěn)定性和節(jié)能是AUV在水下環(huán)境下工作的關(guān)鍵問題。2015年，Dong等[16]提出一種基于維諾圖法的新型路徑規(guī)劃方法。在二維維諾圖中標記障礙物的位置，并通過維諾處理器生成一個近似路徑來連接初始位置和目標位置。采用極限學(xué)習(xí)機法（extreme learning machine,ELM）對路徑進行再生和平滑，以較快的速度生成光滑安全的路徑。該方法在保證安全的前提下，能夠很好地平滑規(guī)劃路徑，有效地促進AUV在水下環(huán)境中自動安全駕駛。2018年，Grefstad等[17]在前人研究的基礎(chǔ)上，基于Voronoi圖和Dijkstras算法規(guī)劃出一條初始路徑，采用費馬螺旋段和一種視距隨時間變化的視導(dǎo)系統(tǒng)進行路徑平滑處理，有效解決了AUV避碰問題。

隨著AUV計算速度的提高和對水下環(huán)境信息完整度的需求，水下三維環(huán)境建模將成為AUV路徑規(guī)劃算法研究的重點。上述三種常用環(huán)境建模方法優(yōu)缺點對比如表1所示。

Table 1 Comparison of advantages and disadvantages of common environment modeling methods表1 常用環(huán)境建模方法優(yōu)缺點對比

3 基于路徑搜索的路徑規(guī)劃算法

路徑搜索算法是基于已建立的環(huán)境模型，在搜索路徑的起點和終點之間獲得一條最優(yōu)路徑的方法。路徑搜索的算法有很多，根據(jù)自身特點不同，適用領(lǐng)域也各不相同。本文將常用路徑搜索算法分為傳統(tǒng)路徑搜索算法、智能仿生學(xué)路徑搜索算法以及其他算法三類。

3.1 傳統(tǒng)路徑搜索算法

常用的傳統(tǒng)路徑搜索算法過程簡單，易于實現(xiàn)，但也存在路徑優(yōu)化效果差（可行性差）、處理速度慢、動態(tài)避障能力不足等問題，如表2所示。AUV常用傳統(tǒng)路徑搜索算法主要有人工勢場法、快速步進法、A*算法等。

Table 2 Comparison of advantages and disadvantages of common conventional path search algorithms表2 常用傳統(tǒng)路徑搜索算法優(yōu)缺點對比

3.1.1 人工勢場法

人工勢場法（artificial potential field，APF）是Khatib于1986年提出的一種虛擬力法。靜態(tài)環(huán)境中基于人工勢場的路徑搜索是成熟的，但由于其可執(zhí)行性、收斂速度、效率等因素限制，使得動態(tài)環(huán)境中基于人工勢場的最優(yōu)路徑搜索尚不成熟。

為了提高AUV航行的安全性和穩(wěn)定性，文獻[18]將視線法（line of sight，LOS）和APF算法相結(jié)合進行導(dǎo)航，對基本的LOS方法進行改進，并引入距離閾值作為參考航向修正，減少航向修正的計算量，還可以在航跡點改變時優(yōu)化轉(zhuǎn)彎軌跡，使得AUV在轉(zhuǎn)彎時更平穩(wěn)。2012年，Subramanian等[19]將該算法應(yīng)用于水下動態(tài)路徑搜索。然而，AUV并未達到精確的動態(tài)避障且存在局部最優(yōu)問題。因此，傳統(tǒng)的人工勢場法已不能滿足AUV實時避障與路徑最優(yōu)的要求，必須加以改進。針對三維水下環(huán)境中AUV的最優(yōu)路徑問題，2013年，Saravanakumar等[20]結(jié)合方向搜索法對上述傳統(tǒng)APF算法進行改進，提出了水下機器人多重勢場法（multiple potential field，MPPF），通過對AUV勢場的采樣，通過微調(diào)潛在函數(shù)的正比例因子以避免局部最小值，克服了三維空間中的局部最優(yōu)問題。2014年，Yan等[21]基于復(fù)雜水下環(huán)境中多AUV的動態(tài)編隊模型進一步完善了人工勢場法。該模型將APF算法與粒子群算法相結(jié)合，動態(tài)規(guī)劃最優(yōu)路徑，而變維粒子群算法的作用是通過動態(tài)調(diào)整路徑節(jié)點的數(shù)量和分布來尋找最優(yōu)路徑?？紤]到海流和復(fù)雜障礙物等海洋環(huán)境因素對AUV路徑規(guī)劃的影響，2016年，Zhu等[22]將APF算法與速度合成法相結(jié)合，提出一種新的路徑規(guī)劃算法。該方法既可以在海流擾動的環(huán)境下避開海底復(fù)雜障礙物，又可以縮短到達目標點的時間和路徑長度，提高AUV路徑規(guī)劃的效率。面對較為復(fù)雜的障礙物環(huán)繞環(huán)境難以規(guī)劃出完整路徑的問題，2019年，程志等[23]提出一種改進的人工勢場法。引入機器人前進的方向向量，對斥力的生成和計算機制進行了調(diào)整以解決其處于局部最小點情況下無法繼續(xù)規(guī)劃路徑的問題，改進的算法可以有效解決傳統(tǒng)APF算法容易出現(xiàn)的路徑規(guī)劃中斷情況，有效提高路徑規(guī)劃效率。為了提高生成路徑的可行性和平滑度，2020年，Song等[24]提出一種預(yù)測人工勢場法，基于該算法提出三種修正參數(shù)：角度限制、速度調(diào)整和預(yù)測勢。成功地限制最大轉(zhuǎn)彎角，解決凹型局部極小值問題，提高可達性，同時縮短AUV航行時間并節(jié)省能源。

3.1.2 快速步進算法

快速步進算法（fast marching,FM）是由Sethian首先提出的一種基于水平集理論的界面演化跟蹤算法，具有良好的可靠性，但也存在計算成本大，處理時間長等問題。針對FM算法存在的問題，文獻[25]提出一種用于水下航行器避障和路徑規(guī)劃的各向異性FM算法，該算法引入AUV的運動學(xué)作為約束條件，以確保水下機器人可以到達最佳路徑，并提出一種基于自適應(yīng)網(wǎng)格生成的多分辨率方案，提高了算法的整體速度，使得計算成本大大降低，獲得了AUV的成本最優(yōu)路徑。為了解決AUV的導(dǎo)航安全性、能耗等問題，2014年，Yu和Wang[26]考慮AUV的機動約束，如轉(zhuǎn)彎半徑、安全深度、油耗以及避免與障礙物碰撞的風(fēng)險，將FM算法應(yīng)用于大范圍海洋環(huán)境中，獲得了AUV的最優(yōu)路徑?；谙惹暗难芯?，2015年，Yu等[27]又對FM算法做出進一步研究，針對復(fù)雜動態(tài)水下環(huán)境，提出一種基于FM算法的混合搜索快速步進方法（hybrid search fast marching method，HSFM）。這種新算法使AUV在水下動態(tài)避障中更具競爭力，同時減少路徑搜索時間，并引入多個約束條件和決策標準，如海流、淺灘、珊瑚礁、動態(tài)障礙物和導(dǎo)航規(guī)則等，對AUV航行規(guī)劃任務(wù)的實驗表明，HSFM算法滿足在線規(guī)劃的時間約束，與其他算法相比，HSFM在時間和成本方面都具有顯著優(yōu)勢。大范圍海洋環(huán)境中，必須考慮海流等環(huán)境因素對AUV能量的影響，2017年，Song等[28]提出一種新的多層快速步進（multilayered fast marching，MFM）算法，在與障礙物保持安全距離的同時，遵循逆流區(qū)域海流規(guī)則來節(jié)約能源成本，提高了算法的實用性。

3.1.3 A*算法

A*算法是在1968年發(fā)展起來的一種啟發(fā)式搜索算法，又稱A-Star算法，是一種靜態(tài)網(wǎng)絡(luò)中求解最短路徑的有效搜索算法。在AUV路徑規(guī)劃過程中，Li等[29]考慮海流等海洋環(huán)境因素的影響，采用傳統(tǒng)A*算法進行AUV路徑搜索。然而，傳統(tǒng)A*算法存在處理速度慢，全局優(yōu)化能力不足等問題。針對傳統(tǒng)A*算法存在的不足，2012年，陳實等[30]基于稀疏A*算法，考慮到AUV本身最大轉(zhuǎn)彎角和最大路徑長度的約束，提出一種新的用于構(gòu)造搜索空間的隨機布點方法，利用隨機函數(shù)均勻地布撒足夠多的搜索節(jié)點，從而構(gòu)成搜索空間，可顯著降低計算量，提高搜索效率，從而達到良好的全局路徑規(guī)劃效果并提高了計算速度，有效解決了傳統(tǒng)A*算法存在的不足，具有重要的工程應(yīng)用價值。針對海流擾動下的全局路徑搜索問題，2016年，Zhang等[31]提出一種改進A*算法。根據(jù)海流的特征建立海流模型，通過分析AUV在海流導(dǎo)航中的速度和作用力，確定用于相鄰兩個節(jié)點向外擴展的A*算法的條件，并應(yīng)用貝塞爾曲線理論來優(yōu)化路徑。2019年，吳鵬等[32]則采用雙向A*算法同時進行正反向路徑搜索，保證了最終目標節(jié)點搜索在連線中點區(qū)域內(nèi)相遇，從而縮短了尋路計算時間，使得路徑搜索效率得到顯著提升，滿足路徑規(guī)劃要求，具有一定的實際意義和應(yīng)用價值。

利用A*算法得到的啟發(fā)式路徑成本低，求解最優(yōu)，其優(yōu)點是在規(guī)劃過程中可以及時中斷和恢復(fù)。然而，A*算法通過比較當前路徑的相鄰網(wǎng)格的啟發(fā)函數(shù)值來逐漸確定下一個路徑網(wǎng)格，當存在多個最小值時，A*算法不能保證搜索的最佳路徑。

3.2 智能仿生學(xué)路徑搜索算法

由于傳統(tǒng)路徑搜索算法存在著路徑優(yōu)化效果差、處理速度慢等問題，因此在處理復(fù)雜動態(tài)環(huán)境信息下的路徑規(guī)劃問題時，智能仿生學(xué)路徑搜索算法逐漸成為主流算法。目前常用的智能仿生學(xué)路徑搜索算法有蟻群優(yōu)化算法、粒子群優(yōu)化算法、遺傳算法、狼群算法等，但智能算法也存在收斂速度慢，計算時間過長以及易陷入局部最優(yōu)[33]等問題。

3.2.1 粒子群優(yōu)化算法

粒子群優(yōu)化算法（particle swarm optimization，PSO）最初由Kennedy和Eberhart提出，是一種基于鳥類種群捕食和返回的啟發(fā)式算法[34]。2015年，Liu等[35]采用PSO算法對AUV進行避障和路徑優(yōu)化，實驗表明該算法易于實現(xiàn)，具有較強的魯棒性和快速的收斂速度，能在有限的計算時間內(nèi)保證最優(yōu)性。然而，粒子群優(yōu)化算法也存在實時避障能力不足，穩(wěn)定性差（易陷入局部最優(yōu)）等問題，因此，出現(xiàn)了許多改進算法，如表3所示。

2016年，Zhuang等[36]提出一種混合算法，該算法將勒讓德偽譜法（Legendre pseudospectral method，LPM）與PSO算法相結(jié)合。與傳統(tǒng)PSO算法相比，新的混合算法通過重新規(guī)劃方案，可以使AUV在靜態(tài)障礙物和不同位置不確定性的動態(tài)障礙物中找到更好的運動軌跡，并成功地實現(xiàn)實時避障。針對未知海洋環(huán)境下的路徑規(guī)劃問題，2018年，Yan等[37]將粒子群優(yōu)化算法和路徑點制導(dǎo)算法相結(jié)合，提出一種新的AUV路徑規(guī)劃算法。該算法利用多波束前視聲納發(fā)現(xiàn)障礙物，采用PSO算法生成合適的航路點，通過跟蹤這些航路點可生成低功耗、無碰撞（路徑平滑）的最優(yōu)路徑。文獻[38]又從量子力學(xué)的角度出發(fā)提出一種具有量子行為的粒子群優(yōu)化改進算法（quantum behavior particle swarm optimization，QPSO），結(jié)合量子物理的思想，在更新粒子位置時重點考慮各個粒子的當前局部最優(yōu)位置信息和全局最優(yōu)位置信息。針對已知障礙物和定常海流的海洋環(huán)境中，2019年，Lim等[39]又對QPSO算法做出進一步研究，提出一種基于硬約束和軟約束的AUV路徑規(guī)劃方案。該方案使用兩種粒子群優(yōu)化算法，即選擇性差分進化混合量子粒子群算法（selectively differential evolution hybridized quantum PSO，SDEQPSO）和選擇性差分進化自適應(yīng)粒子群算法（selectively differential evolution adaptive PSO，SDEAPSO）。基于各算法求解質(zhì)量、穩(wěn)定性和計算效率等方面的考慮，SDEQPSO算法能夠生成光滑的可行路徑，計算需求相對較低和效率更高。2020年，郭興海等[40]又針對水下環(huán)境中動態(tài)障礙物和時變海流的情況，提出一種新的QPSO算法，建立以三維空間路徑最短與路徑平滑度最大為約束的多目標函數(shù)，根據(jù)水下海流變化情況，利用高斯噪聲遞歸估計海流下一時間節(jié)點的速度矢量狀態(tài)，再結(jié)合三維環(huán)境下的AUV運動學(xué)方程，用以確保AUV的速度輸出與運行的穩(wěn)定性。改進的QPSO算法能使AUV潛行時更加平穩(wěn)與安全，且具有更好的自主能力。

Table 3 Characteristic analysis of PSO and improved algorithms表3 PSO及其改進算法特性分析

3.2.2 蟻群優(yōu)化算法

蟻群優(yōu)化算法（ant colony optimization，ACO）是一種概率算法。意大利學(xué)者Dorigo受到螞蟻在食物搜索過程中獲得最佳路徑的啟發(fā)，提出了蟻群算法的概念。文獻[41]應(yīng)用蟻群優(yōu)化原理對AUV的全局路徑規(guī)劃問題進行研究，發(fā)現(xiàn)蟻群優(yōu)化算法非常適合于求解復(fù)雜環(huán)境中的全局路徑規(guī)劃問題，且規(guī)劃時間短、路徑平滑。與其他算法相比，ACO算法的優(yōu)點是可以應(yīng)用于水下3D動態(tài)路徑搜索問題，對初始路線的選擇要求較低，具有很強的魯棒性。然而，傳統(tǒng)蟻群算法也存在收斂速度慢，容易陷入局部最優(yōu)等問題，如表4所示。

Table 4 Characteristic analysis of ACO and improved algorithms表4 ACO及其改進算法特性分析

因此，提出了許多改進的蟻群算法用于AUV水下路徑搜索。文獻[42]提出一種用于AUV路徑規(guī)劃的混合自適應(yīng)ACO算法。實驗結(jié)果表明，AUV的最優(yōu)路徑長度減少14%，且算法能夠有效克服收斂速度慢問題，但易于陷入局部最優(yōu)解。為了解決局部最優(yōu)解的問題，2012年，Zhang等[43]在蟻群算法中引入了懲罰因子，以保持AUV與障礙物之間的安全距離，并結(jié)合四叉樹算法進行二維水下路徑搜索，實現(xiàn)了動態(tài)避障，且不易陷入局部最優(yōu)解。基于先前的研究，2013年，Zhang等[44]又用八叉樹算法取代四叉樹算法，從二維空間延伸到三維空間。與障礙物保持安全距離的同時，完成了AUV對水下三維空間的搜索要求，但是搜索空間從二維拓展到三維環(huán)境下易出現(xiàn)搜索效率低、時間長等問題。對于三維環(huán)境下搜索時間長的問題，文獻[45]提出一種混合算法對AUV進行全局路徑規(guī)劃，采用新的遺傳螞蟻混合策略，保留精英遺傳算法和最大最小螞蟻算法，在三維空間的復(fù)雜環(huán)境中也可以較快收斂到最優(yōu)路徑，但由于未考慮實際海流的影響，導(dǎo)致仿真環(huán)境與實際工況存在一定偏差。因此，需要考慮大范圍海洋環(huán)境中海流對AUV能耗的影響。2016年，Liu等[46]提出一種改進蟻群算法，考慮海流等環(huán)境因素對AUV能量的影響，采用路徑能耗的倒數(shù)作為路徑信息素值，用能耗值指導(dǎo)蟻群進化，相比改進前的算法，路徑不一定最短但能耗顯著降低，對降低AUV能耗、提高續(xù)航能力有一定的優(yōu)勢。2019年，袁汪凰等[47]針對蟻群算法易陷入局部最優(yōu)且收斂速度慢的問題，做出進一步研究，提出動態(tài)學(xué)習(xí)機制的雙種群蟻群算法。引入獎懲模型，獎勵算子提高算法的收斂速度，懲罰算子增加種群的多樣性。該算法能以較少的迭代次數(shù)取得最優(yōu)解或接近最優(yōu)解。2019年，針對AUV海底地形環(huán)境中的三維路徑規(guī)劃問題，張楠楠等[48]提出一種適用于全局路徑規(guī)劃的改進蟻群算法。通過對啟發(fā)函數(shù)、信息素更新方式等改進有效克服了傳統(tǒng)蟻群算法收斂速度慢、容易陷入局部最優(yōu)的缺點，并將路徑的長度和路徑的光滑度同時作為評價函數(shù)，減少AUV能量的消耗，使算法更具備實際工程意義。

3.2.3 遺傳算法

1975年，Holland在其出版的Adaption in Natural and Artificial Systems一書中首次提出了遺傳算法（genetic algorithm，GA）的概念。GA的優(yōu)勢在于它可以根據(jù)搜索過程中當前搜索的最優(yōu)值找到全局最優(yōu)值[49]。文獻[50]將傳統(tǒng)遺傳算法用于AUV的路徑搜索，發(fā)現(xiàn)GA算法可以應(yīng)用于AUV在線路徑搜索和動態(tài)避障。但其缺點是收斂速度慢，穩(wěn)定性差，處理時間過長。處理時間長是所有生物智能算法的一個共同弱點。

針對遺傳算法自身存在的不足，研究者們提出許多改進的算法。文獻[51]在基于遺傳算法的基礎(chǔ)上加入彈性網(wǎng)格概念，以減小算法搜索空間，提高路徑規(guī)劃效率，與傳統(tǒng)遺傳算法相比，收斂速度和運行效率得到改善。無人潛航器通常工作在復(fù)雜多變的海流中，由于海洋環(huán)境的特殊性，在設(shè)計路徑規(guī)劃算法時需要將海流、復(fù)雜障礙物等環(huán)境因素對AUV的影響考慮進來。文獻[52]在AUV路徑規(guī)劃中考慮到海流對AUV能量的影響，將海流因素作為遺傳算法的評價因子，將遺傳算法和粒子群優(yōu)化算法相結(jié)合應(yīng)用到AUV的全局路徑規(guī)劃中，減少AUV在大范圍海洋環(huán)境中航行時的能量消耗。為提高AUV的續(xù)航能力，必須將其在運輸過程中的能耗降至最低。2014年，Tanakitkorn等[8]在遺傳算法的代價函數(shù)中加入AUV動力學(xué)估計的能量消耗項，針對二維靜態(tài)環(huán)境下基于網(wǎng)格的遺傳算法的路徑規(guī)劃，提出一種改進的代價函數(shù)，有效減少AUV能耗。針對AUV水下導(dǎo)航控制精度下降以及穩(wěn)定性變差等問題，2017年，張磊[53]采用遺傳算法優(yōu)化模糊控制器來提高系統(tǒng)魯棒性，在時變連續(xù)海流干擾和定常非連續(xù)海流干擾下，通過路徑跟蹤誤差曲線可知，基于遺傳算法優(yōu)化的模糊控制的路徑跟蹤標準誤差為0.258 m，常規(guī)模糊控制的路徑跟蹤標準誤差為0.372 m，在海流大小改變之處的誤差對比尤為明顯，可見基于遺傳算法優(yōu)化后的模糊控制器對AUV路徑跟蹤控制具有更好的穩(wěn)定性和控制精度。為了解決大范圍海洋環(huán)境中AUV高效避障問題，2019年，Yan等[54]在改進遺傳算法的基礎(chǔ)上建立避障模型，結(jié)合實際應(yīng)用問題進行研究，結(jié)果表明，改進的遺傳算法模型不僅可以滿足轉(zhuǎn)彎角度的要求，避開障礙物，而且在滿足AUV運動特性的前提下，明顯縮短路徑規(guī)劃時間和路徑長度，節(jié)約AUV運行能耗。針對三維路徑規(guī)劃問題，2020年，何光勤等[55]基于遺傳算法對三維環(huán)境下的航跡進行路徑規(guī)劃，設(shè)計帶有懲罰的代價函數(shù)，生成短而平滑的路徑的同時，高效完成路徑規(guī)劃任務(wù)，為各種實際任務(wù)提供技術(shù)支持。

3.2.4 螢火蟲算法

螢火蟲算法（firefly algorithm，F(xiàn)A）是一種自然啟發(fā)式算法，源于螢火蟲群體行為的簡化和模擬[56]。與其他群智能算法相比，螢火蟲算法憑借算法參數(shù)較少、操作簡單，且具有較高的尋優(yōu)精度等優(yōu)勢，已廣泛應(yīng)用到AUV的路徑規(guī)劃中[57]。針對AUV路徑規(guī)劃多目標優(yōu)化問題，2013年，董靜[58]結(jié)合螢火蟲算法獨特的優(yōu)化機制，提出一種多目標螢火蟲優(yōu)化算法。引入Pareto支配的概念以區(qū)分螢火蟲亮度，采用外部檔案保存算法產(chǎn)生Pareto最優(yōu)解，并采用自適應(yīng)神經(jīng)網(wǎng)格法維護外部檔案，最終規(guī)劃出距離較近且平滑度較好的最優(yōu)路徑。然而，F(xiàn)A算法也存在三維環(huán)境下收斂速度慢的問題。針對這一問題，2015年，Liu等[59]提出一種改進的FA來實現(xiàn)AUV的三維路徑規(guī)劃。采用排除算子提高避障效果，并采用收縮算子提高路徑的收斂速度和平滑度，該方法收斂速度快，可以在3D環(huán)境中找到有效的路徑。但由于海洋環(huán)境是動態(tài)未知的，因此，需要進一步研究如何在真實的動態(tài)海洋環(huán)境中為AUV設(shè)計一條實用的路徑。為實現(xiàn)AUV在未知動態(tài)環(huán)境中自適應(yīng)導(dǎo)航，2019年，李鳳玲等[60]提出一種基于螢火蟲算法的AUV路徑規(guī)劃方法。采用單目相機檢測機器人周圍環(huán)境信息，并設(shè)計螢火蟲算法的適應(yīng)度函數(shù)，讓AUV在避開障礙物的同時能搜索最優(yōu)路徑，驗證了螢火蟲算法在動態(tài)未知環(huán)境中路徑規(guī)劃的有效性與實時性，具有重要的實際應(yīng)用價值。

3.2.5 狼群算法

狼群算法（wolf pack algorithm，WPA）是模擬狼群的捕食行為及其獵物分布模式，開發(fā)的一種智能算法。利用“勝者為王”的頭狼生成規(guī)則以及“優(yōu)勝劣汰”的狼性更新機制，實現(xiàn)在復(fù)雜搜索空間中的路徑優(yōu)化[61]。

針對水下導(dǎo)航精度問題，2016年，Shen等[62]提出一種基于狼群算法的改進路徑規(guī)劃方法，結(jié)合地形匹配問題對AUV的導(dǎo)航和路徑規(guī)劃進行研究，利用水下地形熵的計算公式以及水下地形信息的分布，通過狼群算法設(shè)置仿真參數(shù)對規(guī)劃路線的地形匹配進行仿真，提高匹配精度，驗證了算法可行性。2017年，Zhang等[63]通過建立AUV約束條件下的水下環(huán)境威脅模型，提出基于修正WPA的Dubins路徑規(guī)劃方法。利用Dubins曲線來滿足角度控制約束，調(diào)整轉(zhuǎn)彎半徑來滿足控制約束。改進后的WPA收斂速度快，局部搜索能力強，搜索時間減少6.3%，搜索路徑減少57.3%，但改進的狼群算法中需要設(shè)置的參數(shù)比其他方法多，相對復(fù)雜，計算成本大。針對上述存在的問題，2019年，王盈祥等[64]提出一種基于差分進化的改進狼群算法（differential evolution wolf pack algorithm，DEWPA）。通過引入探狼搜索因子、猛狼最大奔襲次數(shù)、自適應(yīng)圍攻步長、差分進化策略等對傳統(tǒng)狼群算法進行改進，在降低算法計算成本的同時提高算法的全局搜索能力。考慮到大范圍海洋環(huán)境中，海流、復(fù)雜障礙物等環(huán)境因素對AUV路徑規(guī)劃的影響，為了降低執(zhí)行成本、減小能耗，AUV必須確定一個時間或能量的最優(yōu)位置。2020年，Panda等[65]提出一種新的狼群算法用于AUV的路徑規(guī)劃，通過對靜態(tài)障礙物進行三維網(wǎng)格化仿真，基于計算時長、路徑長度和路徑代價對結(jié)果進行比較分析，改進的狼群算法降低操作成本，生成了低功耗、無碰撞的最優(yōu)規(guī)劃路徑。狼群算法收斂速度快和求解精度高，同時在求解策略上能夠較好地兼顧對解空間的全局和局部開發(fā)，因而具有優(yōu)良的尋優(yōu)性能。WPA及其改進算法不同特性分析如表5所示。

Table 5 Characteristic analysis of WPA and improved algorithms表5 WPA及其改進算法特性分析

3.2.6 人工神經(jīng)網(wǎng)絡(luò)算法

人工神經(jīng)網(wǎng)絡(luò)（artificial neural networks，ANN）是一種受生物神經(jīng)網(wǎng)絡(luò)功能的運作啟發(fā)而產(chǎn)生的算法數(shù)學(xué)模型，具有強大的自學(xué)習(xí)和自適應(yīng)能力。因此，在AUV路徑搜索中存在許多應(yīng)用[66-67]。然而，ANN算法也存在處理時間長、計算效率低等問題。針對上述問題，2016年，Ni等[68]基于生物啟發(fā)式神經(jīng)網(wǎng)絡(luò)（biologically inspired neural network，BINN）提出一種改進的AUV路徑規(guī)劃算法，該算法對神經(jīng)網(wǎng)絡(luò)模型的分流方程進行了改進，以解決3D水下環(huán)境中AUV的實時路徑規(guī)劃問題，有效避障的同時提高了算法的計算效率。此外，人工神經(jīng)網(wǎng)絡(luò)算法易與其他算法相結(jié)合。因此，其改進算法以及與其他算法的結(jié)合就成為路徑搜索領(lǐng)域的熱門話題。為了解決AUV“太靠近”障礙物和路徑優(yōu)化的問題，2018年，Cao等[69]提出一種勢場生物啟發(fā)式神經(jīng)網(wǎng)絡(luò)（potential field bio-inspired neural network，PBNN）算法，通過生物啟發(fā)神經(jīng)網(wǎng)絡(luò)算法用來規(guī)劃實時無碰撞路徑，引入勢場防止AUV“太靠近”障礙物，在點對點路徑規(guī)劃中引入引力勢場來優(yōu)化路徑，從而實時規(guī)劃出安全平滑的路徑?？紤]到突發(fā)障礙物的影響，文獻[70]提出一種三維生物啟發(fā)式神經(jīng)網(wǎng)絡(luò)模型進行動態(tài)規(guī)劃與避障，有效地促使AUV自主避障，自適應(yīng)地規(guī)劃出一條無碰撞的行駛路徑，實時性較好，但并未考慮實際海流的影響，導(dǎo)致仿真環(huán)境與實際工況存在一定偏差。因此，在實際水下路徑搜索中需要考慮海流對AUV能耗的影響，2019年，Zhu等[71]提出一種改進的多AUV自組織神經(jīng)網(wǎng)絡(luò)算法（self-organizing map neural network，SOMNN），用于3D水下環(huán)境中AUV的實時避障和路徑規(guī)劃，選擇不同方位下海流的最短路徑，在保證總能耗最小的前提下進行路徑規(guī)劃，獲得最優(yōu)規(guī)劃路徑。ANN及其改進算法不同特性分析如表6所示。

Table 6 Characteristic analysis of ANN and improved algorithms表6 ANN及其改進算法特性分析

3.3 其他算法

近年來，隨著對AUV的不斷探索與發(fā)展，一些新的算法因其優(yōu)秀特點而被廣泛應(yīng)用到AUV的路徑規(guī)劃問題中來，且取得了不錯的效果，這些算法一般都具有較強的路徑搜索能力。比如水平集方法（level set method，LSM）、行為策略方法、快速探索隨機樹算法（rapidly-exploring random tree，RRT）、Dijkstra算法等。

水平集方法應(yīng)用于路徑搜索最大優(yōu)勢在于它可以有效地模擬動態(tài)過程，該方法可用于解決水下動力因素引起的問題。文獻[72]采用水平集方法來預(yù)測AUV在不確定、強、動態(tài)海流中的時間最優(yōu)路徑，同時應(yīng)用偏微分方程控制隨機時間的最佳可達性來確定時間最優(yōu)路徑。快速探索的隨機樹算法具有強大的空間搜索能力，廣泛應(yīng)用于AUV的路徑搜索。RRT算法可以收斂到最優(yōu)解，可以在二維環(huán)境中實現(xiàn)AUV的路徑搜索，并且可以解決多維環(huán)境中的路徑搜索問題。Carreras等[73]采用RRT算法有效解決AUV路徑規(guī)劃問題，在受到微分約束的無碰撞運動的情況下，通過運動學(xué)方程獲得新的狀態(tài)從而生成更可行的求解路徑，在真實復(fù)雜的水下環(huán)境中具有很好的適應(yīng)性。針對AUV全覆蓋路徑規(guī)劃問題，甘文洋等[74]提出一種基于行為策略的規(guī)劃算法，構(gòu)建柵格信度函數(shù)區(qū)分環(huán)境信息，引入行為策略確保AUV自動避開障礙物，該算法在二維和三維環(huán)境下能夠完成AUV的全覆蓋任務(wù)。

4 總結(jié)與展望

AUV路徑規(guī)劃算法在水下自主導(dǎo)航中占據(jù)重要地位。本文將常用AUV路徑規(guī)劃算法分為環(huán)境建模方法和路徑搜索算法兩類，詳細介紹了AUV路徑規(guī)劃算法的研究現(xiàn)狀并分析了各算法的優(yōu)缺點，闡述了這些算法的基本工作原理和應(yīng)用范圍，比較了它們的實時性、算法的復(fù)雜性、環(huán)境適應(yīng)性和規(guī)劃路徑的平穩(wěn)性。分析發(fā)現(xiàn)，在面對復(fù)雜的三維海底動態(tài)環(huán)境時，如何提高算法在海流、復(fù)雜障礙物等三維海洋環(huán)境中的實用性，從而實現(xiàn)高效避障和節(jié)約能耗是AUV路徑規(guī)劃的重中之重。

隨著科學(xué)技術(shù)的不斷發(fā)展，人們對AUV路徑規(guī)劃的研究已取得巨大的成果，但由于面臨的海洋環(huán)境日益復(fù)雜，對AUV路徑規(guī)劃技術(shù)的要求也越來越高。因此，尋求最優(yōu)規(guī)劃路徑，響應(yīng)復(fù)雜環(huán)境的變化將成為未來AUV路徑規(guī)劃算法發(fā)展的重點。從已有的研究成果看，AUV路徑規(guī)劃算法將會朝以下研究趨勢進行發(fā)展。

4.1 AUV路徑規(guī)劃算法的智能化發(fā)展

海洋環(huán)境復(fù)雜多變，充斥著湍流、渦流等強瞬態(tài)自然現(xiàn)象，傳統(tǒng)的路徑規(guī)劃方法很難實時抵抗這些強時變、強非線性現(xiàn)象所帶來的干擾，并且AUV自身的動力學(xué)模型和環(huán)境信息難以進行公式化的精確描述。以上問題使得基于環(huán)境模型的路徑搜索算法在復(fù)雜海洋環(huán)境下很難精準規(guī)劃，而以深度強化學(xué)習(xí)（deep reinforcement learning，DRL）等為代表的新一代人工智能算法，不依賴環(huán)境模型且具有較強的自學(xué)習(xí)能力，可以更好地解決水下機器人在未知環(huán)境下的實時路徑規(guī)劃問題。例如通過借助DRL算法的感知決策能力，實現(xiàn)AUV對復(fù)雜海洋環(huán)境的理解并做出智能決策，從而實現(xiàn)由海洋環(huán)境到AUV運行行為的端到端控制。同時，可以利用啟發(fā)式回報函數(shù)的設(shè)計來提高算法的搜索效率，解決路徑規(guī)劃算法收斂速度慢的問題。伴隨著深度強化學(xué)習(xí)網(wǎng)絡(luò)的發(fā)展，未來有望徹底解決水下機器人無先驗環(huán)境知識下的局部路徑規(guī)劃問題。因此，將新興的人工智能算法應(yīng)用于AUV的路徑規(guī)劃中，進一步提高AUV的智能化水平將成為未來發(fā)展的重點。

4.2 AUV路徑規(guī)劃算法的融合

目前，AUV路徑規(guī)劃算法的研究已經(jīng)取得了重大進展，但在每個具體規(guī)劃算法中還存在一些不足，因此路徑規(guī)劃領(lǐng)域的重點依然是新的高效的路徑規(guī)劃算法和融合算法的研究。近年來，隨著一些新的算法（技術(shù)）逐漸應(yīng)用到路徑規(guī)劃中來，這種互補式的算法融合也促使了各算法的發(fā)展，通過取長補短，從而產(chǎn)生出一系列更為優(yōu)秀的算法。例如將機器學(xué)習(xí)與群智能算法結(jié)合應(yīng)用于AUV路徑規(guī)劃中，可以有效地克服群智能算法易陷入局部最優(yōu)解的問題，同時解決了AUV路徑規(guī)劃過程中的死區(qū)問題。這種機器學(xué)習(xí)優(yōu)化技術(shù)也可以應(yīng)用于其他智能路徑規(guī)劃算法，使得AUV路徑規(guī)劃算法體系更加完善，從根本上解決AUV路徑規(guī)劃算法的局部最優(yōu)問題，使得AUV水下探索的應(yīng)用前景更加廣闊。

4.3 向廣域探測的AUV遠程化方向發(fā)展

來自于科學(xué)需求的牽引使得長航程AUV成為很多科研機構(gòu)研究的熱點，但在現(xiàn)階段，長航程AUV的發(fā)展主要受能源、多變復(fù)雜海洋環(huán)境等因素的約束。能源是影響AUV航行距離的一個重要因素。通過智能算法根據(jù)外部環(huán)境與AUV自身能源水平來評估任務(wù)完成的可能性，無疑將是AUV長時間作業(yè)的關(guān)鍵。例如利用模糊邏輯法來實現(xiàn)水下實時路徑規(guī)劃時，可以設(shè)計關(guān)于潛航器剩余能量的隸屬度函數(shù)并結(jié)合專家經(jīng)驗給出規(guī)則表，通過查表根據(jù)剩余能量來決定規(guī)劃時潛航器的線速度和角速度，這必然有助于AUV開展遠距離、大尺度的海洋環(huán)境觀測以及海底資源探測等作業(yè)。此外，海洋中所蘊藏的潮汐能、波浪能、海流能、溫差能、鹽能等可再生能源的智能采集和利用也將是未來AUV遠程化發(fā)展所要探索的一個新方向。

4.4 多AUV協(xié)作路徑規(guī)劃算法的研究

多AUV協(xié)作并不是多個單元的機械式組合，而是以作業(yè)任務(wù)為牽引，設(shè)計集群系統(tǒng)算法策略。隨著AUV作業(yè)范疇的不斷擴展以及作業(yè)任務(wù)日益復(fù)雜化，單個AUV往往很難高效完成人們制定的任務(wù)，多AUV并行協(xié)作就成為解決此類問題的重要方式。然而，由于海洋環(huán)境的復(fù)雜性以及水下通信的困難度，極大地提高了多AUV協(xié)作路徑規(guī)劃的難度，而以深度學(xué)習(xí)、強化學(xué)習(xí)等為代表的新一代人工智能方法在圖像處理、機器人控制等領(lǐng)域的性能優(yōu)勢就為多AUV協(xié)作路徑規(guī)劃提供了一個新方向，但也應(yīng)該清楚地認識到人工智能方法的脆弱性。為了使新一代人工智能方法更好地融入到多AUV路徑規(guī)劃中，需要以作業(yè)任務(wù)為中心設(shè)計路徑規(guī)劃算法，將復(fù)雜任務(wù)進行分解，在核心處理步驟中構(gòu)建適合的智能算法，對提高集群整體路徑規(guī)劃的可行性和系統(tǒng)的穩(wěn)定性具有重要的研究價值。