AUV路徑規(guī)劃算法研究現狀與展望*

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

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

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

3.山東科技大學交通學院，山東青島266590

1 引言

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

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

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

2.1 柵格法

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

Fig.1 Grid method圖1 柵格法

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

2.2 可視圖法

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

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

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

2.3 維諾圖法

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

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

傳統(tǒng)Voronoi圖法生成的路徑相對安全且距離障礙物較遠，然而，生成的路徑不平滑。針對這一問題，2013年，Candeloro等[15]提出一種基于維諾圖和費馬螺旋段的曲率連續(xù)路徑規(guī)劃算法。采用費馬螺旋段來平滑路徑和提供曲率連續(xù)性，產生曲率連續(xù)的路徑，該算法最終得到一條僅由直線和螺旋段組成的安全、平滑的AUV可航行路徑。航行穩(wěn)定性和節(jié)能是AUV在水下環(huán)境下工作的關鍵問題。2015年，Dong等[16]提出一種基于維諾圖法的新型路徑規(guī)劃方法。在二維維諾圖中標記障礙物的位置，并通過維諾處理器生成一個近似路徑來連接初始位置和目標位置。采用極限學習機法（extreme learning machine,ELM）對路徑進行再生和平滑，以較快的速度生成光滑安全的路徑。該方法在保證安全的前提下，能夠很好地平滑規(guī)劃路徑，有效地促進AUV在水下環(huán)境中自動安全駕駛。2018年，Grefstad等[17]在前人研究的基礎上，基于Voronoi圖和Dijkstras算法規(guī)劃出一條初始路徑，采用費馬螺旋段和一種視距隨時間變化的視導系統(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)路徑的方法。路徑搜索的算法有很多，根據自身特點不同，適用領域也各不相同。本文將常用路徑搜索算法分為傳統(tǒng)路徑搜索算法、智能仿生學路徑搜索算法以及其他算法三類。

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

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

3.1.2 快速步進算法

快速步進算法（fast marching,FM）是由Sethian首先提出的一種基于水平集理論的界面演化跟蹤算法，具有良好的可靠性，但也存在計算成本大，處理時間長等問題。針對FM算法存在的問題，文獻[25]提出一種用于水下航行器避障和路徑規(guī)劃的各向異性FM算法，該算法引入AUV的運動學作為約束條件，以確保水下機器人可以到達最佳路徑，并提出一種基于自適應網格生成的多分辨率方案，提高了算法的整體速度，使得計算成本大大降低，獲得了AUV的成本最優(yōu)路徑。為了解決AUV的導航安全性、能耗等問題，2014年，Yu和Wang[26]考慮AUV的機動約束，如轉彎半徑、安全深度、油耗以及避免與障礙物碰撞的風險，將FM算法應用于大范圍海洋環(huán)境中，獲得了AUV的最優(yōu)路徑。基于先前的研究，2015年，Yu等[27]又對FM算法做出進一步研究，針對復雜動態(tài)水下環(huán)境，提出一種基于FM算法的混合搜索快速步進方法（hybrid search fast marching method，HSFM）。這種新算法使AUV在水下動態(tài)避障中更具競爭力，同時減少路徑搜索時間，并引入多個約束條件和決策標準，如海流、淺灘、珊瑚礁、動態(tài)障礙物和導航規(guī)則等，對AUV航行規(guī)劃任務的實驗表明，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)網絡中求解最短路徑的有效搜索算法。在AUV路徑規(guī)劃過程中，Li等[29]考慮海流等海洋環(huán)境因素的影響，采用傳統(tǒng)A*算法進行AUV路徑搜索。然而，傳統(tǒng)A*算法存在處理速度慢，全局優(yōu)化能力不足等問題。針對傳統(tǒng)A*算法存在的不足，2012年，陳實等[30]基于稀疏A*算法，考慮到AUV本身最大轉彎角和最大路徑長度的約束，提出一種新的用于構造搜索空間的隨機布點方法，利用隨機函數均勻地布撒足夠多的搜索節(jié)點，從而構成搜索空間，可顯著降低計算量，提高搜索效率，從而達到良好的全局路徑規(guī)劃效果并提高了計算速度，有效解決了傳統(tǒng)A*算法存在的不足，具有重要的工程應用價值。針對海流擾動下的全局路徑搜索問題，2016年，Zhang等[31]提出一種改進A*算法。根據海流的特征建立海流模型，通過分析AUV在海流導航中的速度和作用力，確定用于相鄰兩個節(jié)點向外擴展的A*算法的條件，并應用貝塞爾曲線理論來優(yōu)化路徑。2019年，吳鵬等[32]則采用雙向A*算法同時進行正反向路徑搜索，保證了最終目標節(jié)點搜索在連線中點區(qū)域內相遇，從而縮短了尋路計算時間，使得路徑搜索效率得到顯著提升，滿足路徑規(guī)劃要求，具有一定的實際意義和應用價值。

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

3.2 智能仿生學路徑搜索算法

由于傳統(tǒng)路徑搜索算法存在著路徑優(yōu)化效果差、處理速度慢等問題，因此在處理復雜動態(tài)環(huán)境信息下的路徑規(guī)劃問題時，智能仿生學路徑搜索算法逐漸成為主流算法。目前常用的智能仿生學路徑搜索算法有蟻群優(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)化，實驗表明該算法易于實現，具有較強的魯棒性和快速的收斂速度，能在有限的計算時間內保證最優(yōu)性。然而，粒子群優(yōu)化算法也存在實時避障能力不足，穩(wěn)定性差（易陷入局部最優(yōu)）等問題，因此，出現了許多改進算法，如表3所示。

2016年，Zhuang等[36]提出一種混合算法，該算法將勒讓德偽譜法（Legendre pseudospectral method，LPM）與PSO算法相結合。與傳統(tǒng)PSO算法相比，新的混合算法通過重新規(guī)劃方案，可以使AUV在靜態(tài)障礙物和不同位置不確定性的動態(tài)障礙物中找到更好的運動軌跡，并成功地實現實時避障。針對未知海洋環(huán)境下的路徑規(guī)劃問題，2018年，Yan等[37]將粒子群優(yōu)化算法和路徑點制導算法相結合，提出一種新的AUV路徑規(guī)劃算法。該算法利用多波束前視聲納發(fā)現障礙物，采用PSO算法生成合適的航路點，通過跟蹤這些航路點可生成低功耗、無碰撞（路徑平滑）的最優(yōu)路徑。文獻[38]又從量子力學的角度出發(fā)提出一種具有量子行為的粒子群優(yōu)化改進算法（quantum behavior particle swarm optimization，QPSO），結合量子物理的思想，在更新粒子位置時重點考慮各個粒子的當前局部最優(yōu)位置信息和全局最優(yōu)位置信息。針對已知障礙物和定常海流的海洋環(huán)境中，2019年，Lim等[39]又對QPSO算法做出進一步研究，提出一種基于硬約束和軟約束的AUV路徑規(guī)劃方案。該方案使用兩種粒子群優(yōu)化算法，即選擇性差分進化混合量子粒子群算法（selectively differential evolution hybridized quantum PSO，SDEQPSO）和選擇性差分進化自適應粒子群算法（selectively differential evolution adaptive PSO，SDEAPSO）。基于各算法求解質量、穩(wěn)定性和計算效率等方面的考慮，SDEQPSO算法能夠生成光滑的可行路徑，計算需求相對較低和效率更高。2020年，郭興海等[40]又針對水下環(huán)境中動態(tài)障礙物和時變海流的情況，提出一種新的QPSO算法，建立以三維空間路徑最短與路徑平滑度最大為約束的多目標函數，根據水下海流變化情況，利用高斯噪聲遞歸估計海流下一時間節(jié)點的速度矢量狀態(tài)，再結合三維環(huán)境下的AUV運動學方程，用以確保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）是一種概率算法。意大利學者Dorigo受到螞蟻在食物搜索過程中獲得最佳路徑的啟發(fā)，提出了蟻群算法的概念。文獻[41]應用蟻群優(yōu)化原理對AUV的全局路徑規(guī)劃問題進行研究，發(fā)現蟻群優(yōu)化算法非常適合于求解復雜環(huán)境中的全局路徑規(guī)劃問題，且規(guī)劃時間短、路徑平滑。與其他算法相比，ACO算法的優(yōu)點是可以應用于水下3D動態(tài)路徑搜索問題，對初始路線的選擇要求較低，具有很強的魯棒性。然而，傳統(tǒng)蟻群算法也存在收斂速度慢，容易陷入局部最優(yōu)等問題，如表4所示。

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

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

3.2.3 遺傳算法

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

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

3.2.4 螢火蟲算法

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

3.2.5 狼群算法

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

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

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

3.2.6 人工神經網絡算法

人工神經網絡（artificial neural networks，ANN）是一種受生物神經網絡功能的運作啟發(fā)而產生的算法數學模型，具有強大的自學習和自適應能力。因此，在AUV路徑搜索中存在許多應用[66-67]。然而，ANN算法也存在處理時間長、計算效率低等問題。針對上述問題，2016年，Ni等[68]基于生物啟發(fā)式神經網絡（biologically inspired neural network，BINN）提出一種改進的AUV路徑規(guī)劃算法，該算法對神經網絡模型的分流方程進行了改進，以解決3D水下環(huán)境中AUV的實時路徑規(guī)劃問題，有效避障的同時提高了算法的計算效率。此外，人工神經網絡算法易與其他算法相結合。因此，其改進算法以及與其他算法的結合就成為路徑搜索領域的熱門話題。為了解決AUV“太靠近”障礙物和路徑優(yōu)化的問題，2018年，Cao等[69]提出一種勢場生物啟發(fā)式神經網絡（potential field bio-inspired neural network，PBNN）算法，通過生物啟發(fā)神經網絡算法用來規(guī)劃實時無碰撞路徑，引入勢場防止AUV“太靠近”障礙物，在點對點路徑規(guī)劃中引入引力勢場來優(yōu)化路徑，從而實時規(guī)劃出安全平滑的路徑。考慮到突發(fā)障礙物的影響，文獻[70]提出一種三維生物啟發(fā)式神經網絡模型進行動態(tài)規(guī)劃與避障，有效地促使AUV自主避障，自適應地規(guī)劃出一條無碰撞的行駛路徑，實時性較好，但并未考慮實際海流的影響，導致仿真環(huán)境與實際工況存在一定偏差。因此，在實際水下路徑搜索中需要考慮海流對AUV能耗的影響，2019年，Zhu等[71]提出一種改進的多AUV自組織神經網絡算法（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)秀特點而被廣泛應用到AUV的路徑規(guī)劃問題中來，且取得了不錯的效果，這些算法一般都具有較強的路徑搜索能力。比如水平集方法（level set method，LSM）、行為策略方法、快速探索隨機樹算法（rapidly-exploring random tree，RRT）、Dijkstra算法等。

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

4 總結與展望

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

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

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

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

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

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

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

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

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

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