周 帥 王 征 楊 洋 尹 洋

（海軍工程大學電氣工程學院 武漢 430033）

1 引言

自主水下航行器（Autonomous Underwater Vehicle，AUV）是一種依靠自身攜帶能源自主航行，可根據(jù)搭載不同的載荷執(zhí)行多種任務的無人水下航行器（UUV）［1］。AUV 在軍事、民用領域運用廣泛，能夠完成海洋探測、水下設施檢查、水雷對抗等多種任務，AUV 的研發(fā)已成為各國海洋技術(shù)研究的熱點［2］。遠離母船或岸基平臺巡航作業(yè)的AUV也會因其導航、控制系統(tǒng)的測量計算能力而制約AUV 的實際效能，其中自主導航與智能控制已成為決定未來AUV 應用的關(guān)鍵技術(shù)，本文討論的路徑規(guī)劃正是這兩個關(guān)鍵技術(shù)的重要內(nèi)容。作為體現(xiàn)AUV 與外部環(huán)境進行交互的能力的重要部分，路徑規(guī)劃水平是衡量AUV 工作效能、保證航行安全的關(guān)鍵。

2 AUV路徑規(guī)劃技術(shù)概述

路徑規(guī)劃就是使AUV 在規(guī)定的任務區(qū)域內(nèi)，以一定的衡量依據(jù)（如避障、最小轉(zhuǎn)彎半徑等）尋找一條從起點到終點的安全無碰撞路徑［2］。按照AUV 對航行環(huán)境信息的掌握程度可將路徑規(guī)劃分為全局路徑規(guī)劃和局部路徑規(guī)劃［4］。前者根據(jù)已知的航行海圖和目標點位置等信息，計算出到達目標點并滿足一定最優(yōu)準則的安全路徑；后者則根據(jù)AUV 自身攜帶的慣導、全球定位系統(tǒng)等設備獲取當前位姿信息，根據(jù)前視聲納、多普勒速度儀探測設備獲取實時的環(huán)境信息，規(guī)劃出一條避開障礙物由起點或某子目標點到下一子目標點的優(yōu)選路徑［2］。

路徑規(guī)劃一般有以下步驟：第一，建立從外部環(huán)境原始形式映射到便于規(guī)劃的內(nèi)部抽象模型，使之能夠有效地描述AUV 活動空間。第二，設計規(guī)劃算法，在建立的環(huán)境模型中搜索出一條無碰路徑。

3 AUV航行環(huán)境建模方法

常見的環(huán)境表示方法有幾何建模法（可視圖法、維諾圖法、特征地圖法）、單元分解法（柵格法、八叉樹法），其中可視圖法、維諾圖法除具有環(huán)境表達能力外，本身也是一種基于圖的搜索算法，擁有獨立的路徑搜索規(guī)則。考慮到實際的AUV 往往在復雜的水下三維環(huán)境中航行作業(yè)，對上述建模方法重點討論其在三維環(huán)境空間建模的應用。

3.1 幾何建模法

可視圖法在構(gòu)建環(huán)境模型時忽略AUV 的體積大小，視其為一個點，用不規(guī)則的多邊形抽象表示環(huán)境中的障礙物，再將多邊形各頂點與起點、目標點兩兩之間相連接，去除的連線即得出可視圖［5］。一種改進可視圖法將障礙物切線圖形化，一定程度上解決了規(guī)劃路徑冗余問題［6］。對于規(guī)劃的路徑過于靠近障礙物易導致碰撞的問題，Gal［7］提出了減少構(gòu)圖節(jié)點、添加螺旋算法的改進可視圖法，加快了計算速度且能夠有效避免碰撞，但規(guī)劃路徑會有所增長。Ji-Hong Li 等［8］根據(jù)可視圖幾何理論，利用常規(guī)幾何體實現(xiàn)了水下三維環(huán)境建模。

維諾圖是由一組由連接兩鄰點直線的垂直平分線組成的連續(xù)多邊形［9］。維諾圖法因其通用性被廣泛運用于AUV 的水下環(huán)境建模。針對維諾圖法生成路徑平滑性不佳不利于跟蹤、距離障礙物較遠導致路徑非最短等問題，Candeloro［10］在維諾圖中引入了費馬螺旋段，規(guī)劃出了由直線和螺旋段構(gòu)成的平滑路徑。

特征地圖則以線段、圓弧、多邊形等幾何元素抽象表示AUV 航行空間的環(huán)境特征，并以具體參數(shù)在全局坐標系下表示環(huán)境中障礙物的具體位置。以該方法建立的模型信息緊湊，位置清晰，便于識別，但另一方面，它不易量化，難以處理不規(guī)則障礙。曲鏡圓［11］建立了多波束聲納數(shù)字模型作為AUV 感知系統(tǒng)，利用特征地圖完成了水下環(huán)境建模。

3.2 單元分解法

柵格法將AUV 的三維航行空間劃分為若干個大小一致的單位立方體，并根據(jù)各立方體所處狀態(tài)（或為自由空間，或為障礙空間）分別將其標記為不同的值。其中單位立方體的大小直接影響模型的精度，單位立方體越小，環(huán)境模型精度就越高，但同時存儲的數(shù)據(jù)量將成倍增大，后續(xù)規(guī)劃算法耗時亦將增加。該方法雖簡單便于實現(xiàn)，但前提是能夠獲得原始航行空間的環(huán)境信息。通過NOAA、GMRT、JAMSTEC、IHO Data Centre for Digital Bathymetry等［12］高精度的海洋數(shù)據(jù)庫，用戶可獲得研究所需的海底地形數(shù)據(jù)。對于未知環(huán)境，趙冬梅等［13］融合聲納仿真數(shù)據(jù)得到基于占有率的柵格地圖。邢煒等［14］采用局部占用柵格法，將柵格法建立在AUV 的隨體坐標系下，將雙前視聲納實時檢測到的障礙物信息納入其中，實現(xiàn)了障礙物的精準定位。

在柵格法基礎上提出的單元樹法將AUV 的三維航行空間劃為八個部分，稱為八叉樹。將這八個部分按照“自由空間”、“障礙空間”、“混合空間（既有自由空間又有障礙空間）”三種情況分類標記。對于第三種“混合空間”，將其繼續(xù)劃為八個小部分，再將這八個小部分按照相同方式分類標記，以此類推直至劃分部分小到預定精度。八叉樹法對障礙物邊緣的分解作用，減少了模型所需的存儲空間。八叉樹法緩解了柵格法模型精度與規(guī)劃效率之間的矛盾，但也存在計算單元之間鄰接關(guān)系時損失較大的缺點。2003 年，高濤［15］通過八叉樹法建模結(jié)合距離值傳播法實現(xiàn)了AUV 水下三維路徑規(guī)劃。

表1 AUV航行環(huán)境建模方法優(yōu)缺點對比

4 AUV路徑規(guī)劃算法

選擇相應的規(guī)劃算法，在建立的環(huán)境模型中搜索出一條無碰路徑。通常包括傳統(tǒng)規(guī)劃算法、智能規(guī)劃算法以及基于機器學習的路徑規(guī)劃算法。

4.1 傳統(tǒng)規(guī)劃算法

20 世紀70 年代開始，伴隨著移動機器人的興起，針對路徑規(guī)劃算法問題的研究逐漸發(fā)展起來。常用的傳統(tǒng)規(guī)劃算法有人工勢場法、A*算法等。

人工勢場法在環(huán)境中抽象出一個虛擬力場，環(huán)境中目標、障礙對AUV 分別產(chǎn)生的一定大小的引力和斥力，以其合力引導AUV 的運動。傳統(tǒng)人工勢場法存在易陷入局部最小值以及在障礙物距離目標點較近時可能造成目標不可達等問題。Weerakoon等［16］通過在局部最小值點施加額外的斥力來幫助機器人擺脫。梁獻霞等［17］引入了虛擬障礙物，在虛擬障礙物和原有障礙物、目標點產(chǎn)生的合力綜合作用下跳出局部極小值點。此外，段建民等［18］借助遺傳算法以及填平勢場也實現(xiàn)了跳出局部極小值的目的。S.S.Ge 等［19］提出了考慮目標與AUV 距離的改進斥力函數(shù)確保AUV 到達目標點。對于更復雜的水下三維環(huán)境，郭凱紅等［20］綜合考量了障礙物形狀和目標點距離，并根據(jù)速度矢量判斷障礙物在AUV 左舷還是右舷，從而合理選擇轉(zhuǎn)向，解決了傳統(tǒng)的二維平面避障固定轉(zhuǎn)向的缺陷。馬小軒等［21］提出了考慮避障半徑的優(yōu)化斥力場函數(shù)方法，結(jié)合設置子目標點以及距離比較法分別避免陷入局部極小值和目標不可達的缺陷，實現(xiàn)了多障礙物水下三維環(huán)境的路徑規(guī)劃。

A*算法通過不斷搜索靠近目標點的路徑來獲得機器人的移動路徑。該算法的評價函數(shù)包含了實際距離代價函數(shù)、估算距離代價函數(shù)，其中后者作為啟發(fā)函數(shù)直接決定了A*算法效率的高低。A*算法在柵格地圖中進行，可犧牲搜索精度來保證搜索速度，進而在較短時間內(nèi)找到最優(yōu)解。為了進一步提高搜索速度，還可以選擇跳躍點搜索、雙向搜索、帶寬搜索等手段。傳統(tǒng)的A*算法規(guī)劃出的路徑折線多，且通過障礙物邊緣時的避碰可靠性差。為了解決規(guī)劃可行性問題，于曉天等［22］結(jié)合A*算法與模糊控制算法，先通過A*算法在高層柵格地圖中進行全局規(guī)劃，再利用模糊控制算法在底層柵格地圖中進行局部規(guī)劃，最終得到一條平滑路徑。

4.2 智能規(guī)劃算法

傳統(tǒng)算法對環(huán)境空間變化適應能力較差，采用復雜優(yōu)化方法則又大大降低了算法通用性。相比較下，智能優(yōu)化算法能更有效地解決大規(guī)模復雜優(yōu)化問題。常見的智能算法有蟻群算法、粒子群算法、遺傳算法、神經(jīng)網(wǎng)絡算法等。

蟻群算法（Ant Clony Algorithm，ACA）因模擬了螞蟻覓食尋徑活動而得名，該算法根據(jù)螞蟻行進時選擇信息素濃度高的路徑并釋放的信息素的正反饋的作用找出最優(yōu)路徑［23］。傳統(tǒng)蟻群算法易陷入局部最優(yōu)、收斂慢甚至停滯。王宏健等［24］建立了蟻群可視圖模型，闡明了信息素更新規(guī)則及算法步驟，驗證了蟻群算法對解決AUV 全局路徑規(guī)劃問題的有效性。溫志文等［25］借鑒了非劣最優(yōu)解集的思想，考慮了路徑長度、平滑度、規(guī)劃時間、安全性等多個評價指標的優(yōu)化組合，同時采用了趨向位置目標的吸引策略，提高了算法全局尋優(yōu)能力。俞佳慧等［26］將蟻群算法同貝葉斯網(wǎng)絡相結(jié)合，改進了轉(zhuǎn)移概率公式及信息素濃度更新策略，提高了算法性能及其收斂性。梁凱等［27］提出了一種基于預測控制理論的方法，他在路徑規(guī)劃過程中加入了滾動窗口，仿真結(jié)果表明改進后的算法使機器人具備良好的動態(tài)避障能力。劉雨青等［28］基于Dijkstra算法改進了信息素初始化方式，構(gòu)造了新的啟發(fā)函數(shù)來消除水流導致不同路徑點能耗不同的影響，同時利用貝塞爾曲線改善路徑平滑性，提高了算法性能，適用于AUV 的路徑規(guī)劃。朱佳瑩等［29］在改進蟻群算法的基礎上引入粒子群算法路徑預搜索優(yōu)化初始信息素分布，提高了收斂速度和全局搜索能力。

粒子群算法（Particle Swarm Optimization，PSO）源于對鳥群捕食行為的研究，它的基本核心是利用個體的信息共享使得整個群體的運動在問題求解空間中產(chǎn)生從無序到有序的演化過程，進而獲得問題的最優(yōu)解［30］。傳統(tǒng)的粒子群算法難以避免收斂精度較低、搜索停滯等問題。嚴浙平等［31］提出了一種競爭粒子群算法，算法中每個粒子都向著側(cè)重于全局搜索和局部搜索的兩個速度方向進化，在得到的兩個子粒子中保留較優(yōu)的子粒子，最終得到下一代粒子種群，將該算法應用于AUV 路徑規(guī)劃中得到了較優(yōu)路徑。賈慧群等［32］通過自適應地調(diào)整慣性權(quán)重因子和加速因子，同時引入雞群算法中的更新方程擾動搜索停滯的粒子，使之向全局最優(yōu)解靠近。改進后的算法在搜索精度及魯棒性上均有較大提升。

遺傳算法（Genetic Algorithm，GA）衍生于染色體選擇交叉、基因變異的生物進化機制，它將路徑編碼為染色體，再根據(jù)適應度值保留優(yōu)秀個體進行迭代，最終得到趨于全局最優(yōu)路徑［33］。傳統(tǒng)遺傳算法局部搜索能力差、運算效率低。王豪等［34］將路徑長度和拐點數(shù)量納入適應度評估，設計了自適應的交叉算子和變異算子，仿真結(jié)果表明改進后的算法迭代次數(shù)和拐點數(shù)更少。文獻［35］在遺傳算法中引入避障模型提高了AUV 動態(tài)避障能力，縮短了規(guī)劃時間和路徑長度。馮豪博等［36］提出了一種基于精英族系的遺傳算法，該算法將迭代產(chǎn)生的精英個體標記為多路徑規(guī)劃結(jié)果，實現(xiàn)了AUV 集群最優(yōu)多路徑規(guī)劃。文獻［37］將海流對AUV 航行耗能的影響考慮到適應度函數(shù)中，提出了一種遺傳算法與粒子群算法相結(jié)合的全局路徑規(guī)劃算法，降低了AUV 在大范圍海域航行能耗。潘昕等［38］提出了一種遺傳蟻群混合算法，通過遺傳算法生成初始全局可行解彌補了蟻群算法初期信息素匱乏導致求解效率低的缺陷。俞炅旻等［39］設計了利用遺傳算法優(yōu)化隸屬度函數(shù)的模糊控制器，實現(xiàn)了AUV 在未知水下環(huán)境的局部路徑規(guī)劃。

神經(jīng)網(wǎng)絡能夠并行處理、分布式儲存大量數(shù)據(jù)信息，能夠在問題內(nèi)部規(guī)律未知情況下實現(xiàn)網(wǎng)絡從輸入狀態(tài)空間到輸出狀態(tài)空間的映射。神經(jīng)網(wǎng)絡中神經(jīng)元與環(huán)境模型中位置單元一一對應，環(huán)境中障礙物信息作為輸入，通過神經(jīng)元之間連接和計算最終得出一條較優(yōu)路徑。劉成良等［40］提出了一種結(jié)合碰撞函數(shù)的神經(jīng)網(wǎng)絡算法，并通過仿真實現(xiàn)了機器人無碰撞路徑規(guī)劃。朱大奇等［41］建立了三維生物啟發(fā)神經(jīng)網(wǎng)絡模擬水下三維環(huán)境，并根據(jù)神經(jīng)元活性輸出值分布情況得出了較優(yōu)路徑，驗證了神經(jīng)網(wǎng)絡模型在AUV 三維路徑規(guī)劃的可行性。郝啟潤等［42］提出了一種結(jié)合A*算法與離散生物啟發(fā)神經(jīng)網(wǎng)絡的算法，實現(xiàn)了AUV 在未知環(huán)境的實時路徑規(guī)劃。

除上述智能規(guī)劃算法外，還有學者研究了入侵野草優(yōu)化［43］、螢火蟲算法［44］、狼群算法［45］等智能算法在AUV路徑規(guī)劃中的應用。

4.3 基于機器學習的路徑規(guī)劃算法

強化學習是智能體通過與環(huán)境的交互學習策略并迭代使累計獎勵值達到最大的方法，該方法無需先驗知識，適合解決AUV 在水下環(huán)境的路徑規(guī)劃問題［46］。劉和祥等［47］基于前視聲納信息采用Q-learning 算法在半實物仿真中實現(xiàn)了AUV 的局部路徑規(guī)劃。針對動作空間、樣本空間維數(shù)增大導致算法收斂性變差等問題，冉祥瑞［48］提出了半馬爾可夫決策過程，通過任務分層緩解了強化學習的“維度災難”，提高了AUV 在水下環(huán)境的自適應能力。

深度強化學習利用神經(jīng)網(wǎng)絡擬合了Q 值表解決了狀態(tài)-動作空間過大的問題，兼具了深度學習的感知能力與強化學習決策能力，更加適用于AUV 大范圍水下三維環(huán)境的路徑規(guī)劃［49］。Yukiyasu 等［50］利用深度強化學習方法實現(xiàn)了AUV 在各種海底環(huán)境在線學習的路徑規(guī)劃。Prashant等［51］通過神經(jīng)網(wǎng)絡處理空間連續(xù)問題，提高了算法學習速度。卜祥津等［52］采用Asynchronous Advantage Actor-Critic算法訓練機器人路徑規(guī)劃，根據(jù)機器人避障需求切換狀態(tài)，優(yōu)化了狀態(tài)空間，提高了學習效率。張士偉等［53］提出了Actor-Multi-Critic 算法，多個評論家根據(jù)不同標準對AUV 動作進行評分，克服單一評論家評價耦合的問題，仿真結(jié)果表明該算法可滿足AUV 動態(tài)路徑規(guī)劃實時性和可靠性的要求。

表2 各類規(guī)劃算法的特性分析

5 結(jié)語

本文立足于無人水下航行器路徑規(guī)劃技術(shù)發(fā)展現(xiàn)狀，以環(huán)境模型建立和規(guī)劃算法為重點，概述了各類建模方法、規(guī)劃算法原理及應用，對比分析了它們各自的適用范圍及優(yōu)缺點并針對其弱點提出了改進方向。研究發(fā)現(xiàn)，柵格法因其建模過程簡單、便于執(zhí)行計算而應用最廣，但目前仍難以平衡柵格分辨率與計算效率?；谌褐悄艿囊?guī)劃算法在大規(guī)模優(yōu)化問題以及復雜環(huán)境適應問題上優(yōu)于傳統(tǒng)規(guī)劃算法，能夠較好地實現(xiàn)全局或局部路徑規(guī)劃，但也存在動態(tài)規(guī)劃能力不足、求解精度與收斂速度難以兼顧等問題。深度強化學習不依賴環(huán)境模型和具體的求解規(guī)則，具備在線學習、自主學習的能力。近年來提出的近端策略優(yōu)化算法［54］（Proximal Policy Optimization，PPO）可處理高維狀態(tài)空間和實現(xiàn)連續(xù)動作控制，在解決復雜水下三維環(huán)境的局部路徑規(guī)劃問題上具有較大的潛力。還有學者提出將深度強化學習與群智能算法相結(jié)合，在保證較強動態(tài)規(guī)劃能力的基礎上提升全局規(guī)劃能力，也成為新的研究方向。

當前，AUV 在軍民領域執(zhí)行的任務呈現(xiàn)多樣化、復雜化的特點。根據(jù)不同任務場景需求，例如在廣闊海域覆蓋搜索、圍捕目標，在近海底空間考慮地形海流、躲避水下監(jiān)聽威脅等，有針對性地建立充分表達環(huán)境的模型，設計適合解決該問題的路徑規(guī)劃算法逐漸成為研究的重點。為了彌補單一AUV 無法勝任復雜任務的缺陷，實際任務通常由異構(gòu)的AUV 集群協(xié)同執(zhí)行，利用深度強化學習協(xié)同規(guī)劃AUV 集群的無沖突作業(yè)路徑也成為當下研究的熱點。隨著深度強化學習網(wǎng)絡的發(fā)展以及合成孔徑聲納等設備的開發(fā)應用，AUV 在復雜任務場景下的路徑規(guī)劃問題有望得到徹底解決。