日本在线www-日本在线播放一区-日本在线不卡免费视频一区-日本在线不卡视频-成人影院久久久久久影院-成人影院一区二区三区

作者：馬思遠，黃大志，徐慧麗，付曉月（江蘇海洋大學，江蘇 連云港 222005）

摘要：路徑規劃算法是無人平臺領域的重要研究方向，水面無人艇是一 種可移動的水面無人平臺。本文根據水面無人艇路徑規劃的功能進行分 類，將路徑規劃算法劃分為局部路徑規劃和全局路徑規劃，并分析和對 比各常用算法的優缺點，同時對優化算法的現狀進行了介紹。最后對目 前無人艇路徑規劃算法進行了總結。

關鍵詞：無人艇；路徑規劃算法；A*算法

Abstract: The unmanned surface vehicle is a kind of movable surface unmanned platform. This paper classifies the path planning algorithms into local path planning and global path planning according to the function of unmanned surface vehicle path planning, and analyzes and compares the advantages and disadvantages of each commonly used algorithm , and introduces the current status of optimization algorithms. Finally, we present the summary of the current unmanned surface vehicle path planning algorithms.

Key words: Unmanned surface vehicle; Path planning algorithm; A* algorithm

1　引言

水面無人艇，也可以稱為水面機器人，是一種小 型的智能水面平臺，它具有體積小、移動迅速、智能 化程度高的優點，用于執行危險或不適合人工作業的 任務[1]。最早的無人艇出現于20世紀50年代，主要用作 水面靶艇和水面排雷艇，但僅限于人工平臺的工作范 圍之內[2]。隨著當前衛星通訊技術和自主導航技術的發 展，水面無人艇作為小型任務平臺，其工作范圍已經拓 展至深海區域。在軍事領域，無人艇可以通過搭載不同 的模塊，執行情報收集、快速打擊、掃雷和海域勘測等 任務，通過港口投放和隨船投放的方式拓展海上的作戰 范圍[3]。在民用領域，水面無人艇主要用于水文勘探， 也可作為中繼站，與無人機和水下機器人通信，實現多 設備協同[4]。路徑規劃是無人艇自主航行的關鍵技術， 也是目前需要解決的重要問題[5]。

路徑規劃問題分為全局路徑規劃和局部路徑規 劃。全局路徑規劃利用電子海圖等先進信息，根據任 務需求，在較大的范圍內借助合適的搜索算法，尋求 一條可行的無障礙路線。局部路徑規劃算法在全局航 行中起輔助作用，無人艇在全局路徑航行中，對未知 的障礙物進行探測并自主避讓，避讓完成之后繼續按 照全局路徑行駛。

本文針對目前無人艇的路徑規劃算法進行了研究， 比較不同算法的優缺點，闡述了算法優化的研究現狀， 最后對無人艇路徑規劃的算法進行了總結。

2　全局路徑規劃算法

全局路徑規劃算法需要獲取整個環境的信息， 根據獲得的完全信息對環境進行建模，并對指定路 徑進行初步規劃[6]。在整個全局路徑規劃的過程中， 可以將路徑規劃問題拆分為環境信息獲取及建模和路 徑規劃算法選擇，當存在未知的障礙物或者航行途中 偶遇突發狀況則無法解決，只適用于對實時性要求不 高、環境信息獲取完全的情況。本文只闡述路徑規 劃算法，對如何獲取環境參數以及如何建模等問題 不做闡述。

2.1　Dijkstra算法

Dijkstra算法由Dijkstra[7]在1959年首次提出，是一種計算精度較高的全局路徑規劃算法，用于獲取最短 路徑。

經典的Dijkstra算法原理簡單，但是計算流程過于 復雜且占用較多的內存，獲取的結果只能按照預定的路 線航行，只適用于較小規模的路徑規劃。

王先全[8]等使用鄰接表以及二叉排序樹結構，對 傳統的Dijkstra算法進行優化，以此提高計算效率，加 快路徑規劃速度。莊佳園[9]等使用動態網格模型，將基 于距離尋優的Dijkstra算法應用于無人艇的全局路徑規 劃，通過刪減非最短路徑的節點，在降低算法自身的內 存占用的同時，加快規劃速度并優化全局路徑，使得規 劃的路徑更加平滑，適合無人艇的航行。

2.2　A*算法

A*算法是由Hart[10]等提出的一種啟發式算法，它 是Dijkstra算法的拓展，同時也是靜態網路中尋找最短 路徑最有效的方法。

A*算法原理簡單，比Dijkstra算法運算更快，但是 其對啟發函數非常依賴，這就導致該算法計算量巨大。 由于A*算法的效率最高，被廣泛利用，不少專家也根據 A*算法的缺陷對其加以改造。Svec等將路徑規劃算法 和局部有界最優算法結合，用于解決無人艇的動態路徑 規劃問題，通過取最小值中的極大值，將海浪等因素可 能導致的偏差考慮在內，更加適合海上環境；通過實驗 證明該算法具有實用價值，但是這對無人艇運動控制的 精度要求更高。KIMH提出了一種基于改進A*算法的路 徑規劃算法，由于KIMH將無人艇的最大轉彎半徑以及 外界環境納入考慮范圍，改進后A*算法更加靈活，通過 仿真實驗也證明了算法的有效性。

2.3　蟻群算法

蟻群算法（Ant Colony Optimization，ACO）是 Dorigo[11]等提出的一種智能優化算法，通過重復模擬 蟻群的覓食行為完成最優路徑的尋找。

蟻群算法相比于傳統算法，具有較高的魯棒性 和便于并行的優點，但是如果初期路徑規模太大或者 前期信息素缺失，可能導致路徑規劃求解時間變長或 無法得到全局最優解。針對蟻群算法的這一問題， Stutzle等提出最大最小螞蟻系統（MMAS），通過對 路徑上的信息素進行上下限的限制，在一定程度上減 少了停滯現象，但是當求解過于分散時，收斂速度也 會減慢。盡管如此，MMAS算法能夠有效平衡收斂速 度和避免局部最優解，因此MMAS算法可以較快地獲 得最優解。游曉明[12]等提出了一種新的動態搜索誘導 算子以改進蟻群算法性能，在進化過程中利用動態衰 減模型調整閾值以加快收斂速度，測試結果說明該改 進算法不僅可以加快收斂速度，同時還可以提高優化 解的質量。

2.4　遺傳算法

遺傳算法由Holland[13]提出，是一種模擬生物進 化過程的隨機搜索算法。遺傳算法具有較高的魯棒 性，適合復雜環境下的路徑求解問題，應用非常廣 泛，但是其存在收斂速度慢、控制變量多求解能力較 差的缺點。針對遺傳算法存在的缺點，Long等針對遺 傳算法求解過慢的問題，使用網格法對環境建模，提 出一種全新的初始種群，提高種群的收斂速度以及種 群的初始質量，通過設置自適應交叉概率以及變異概 率，生成路徑的速度有較為明顯的提高，實驗仿真證 明了該算法的可行性。

2.5　智能水滴算法

2009年Hamed Shah-Hossini提出智能水滴算 法，智能水滴算法根據水滴與周邊河道環境互相產生的 影響，如前進速度、自身攜帶的泥土量，通過概率實現 對路徑的選擇，水滴受重力作用進行啟發式搜索，以此 求解最優路徑。

與其他傳統算法相比，智能水滴算法具有良好的 正反饋機制和自組織特性，但是其存在計算力較低、搜 索能力差和算法早熟的缺點。

徐佳敏[14]等針對智能水滴算法的算法早熟問題，提 出了通過非均勻性的編譯避免算法早熟。EZUGWU[15] 等設計出了一種增強智能水滴算法，將退火算法作為局 部啟發式搜索元引入智能水滴算法，加快了算法的收斂 速度。

2.6　對比分析

全局路徑規劃算法的優缺點對比如表1所示，除去 文中介紹的算法之外，還有模擬退火算法、神經網絡算 法等其他全局規劃算法，但其在無人艇的路徑規劃中應 用較少，故在此不做比較。

表1 全局路徑規劃算法比較

3　局部路徑規劃算法

與全局路徑規劃算法不同，局部路徑規劃算法不需 要完整的環境信息，通過傳感器從周圍位置環境獲取信 息，包括但不限于障礙物的尺寸、形狀和相對速度，并 通過算法計算得到一條安全的路徑[16]。常見的局部路徑 規劃方法包括人工勢場法、速度障礙法、向量場直方圖 法等。

3.1　人工勢場法

人工勢場法由Khatib首次提出，目前已經成為局 部路徑規劃中應用最廣泛的方法。人工勢場法具有計算 簡單、反應迅速的優點，但是如果存在某一點合力為 0，無人艇將圍繞此點做圓周運動，最終無法到達目的 地，陷入局部最小值問題，除此之外，當無人艇的周圍 被障礙物環繞時，利用人工勢場法無法求解。

陳超[17]等通過引進新的引力場函數和斥力場函數， 對傳統的人工勢場法進行優化。除此之外，在應力場內 添加震蕩函數，當USV陷入局部最小問題時，震蕩函數 通過修改引力場方向破壞局部最小問題的平衡，通過仿 真結果得到該優化算法可以解決局部最小問題，但是求 解的路徑隨機且不是最優解。

3.2　速度障礙法

速度障礙法（Veloc ity Obstacle，VO）是 Fiorini[18]等提出的一種局部路徑規劃算法。速度障礙 法與其他智能算法相比，將障礙物的速度屬性考慮進 來，能可靠地保障無人艇的避障安全，規避的準確性非 常高；但是該算法沒有考慮障礙物速度的動態變化，并 在規劃避障路線時，速度較慢。

Kuwata等成功地將速度障礙法應用于USV的局部 避障，通過計算無人艇與障礙物之間的最近距離以及到 達最近距離的時間，只有當最近距離和到達最近距離的 時間都滿足約束條件時才會判定可能發生碰撞，同時建 立代價函數，這時候只需要從安全的速度空間內選取代 價函數值最小的速度矢量即可實現局部避障。

3.3　向量場直方圖法

向量場直方圖法是Borenstein[19]針對人工勢場法 的特殊情況提出的一種實時路徑規劃算法。向量場直方 圖法擁有較好的魯棒性，適用于多種場合的局部動態避 障，但是由于缺乏對障礙物速度屬性以及USV操控性的 考慮，計算得到的結果可能陷入局部最優問題。Loe[20] 針對局部最優問題，通過將向量場直方圖算法與A*算法 結合，得到VFH*法，該算法在復雜的局部環境中依然 可以進行局部路徑規劃。Babinec[21]等提出了一種基于 VFH的優化算法，通過柵格化建模，將無人艇航行空 間劃分為具有二值信息的單元，通過獲取單元的信任度 值計算障礙物柵格的向量值和矢量角等信息，得到復雜 環境下的最優路徑。

3.4　對比分析

以上局部路徑規劃算法的優缺點如表2所示。除此 之外還有梯度法、ASL法等經典局部路徑規劃算法，但 是并不適用于無人艇領域。

表2 局部路徑規劃算法比較

4　結論

相較于局部路徑規劃算法，全局路徑規劃算法 的研究已經比較成熟，路徑規劃的解決方案得到了實 踐并驗證了可行性。但是局部路徑規劃算法的研究目 前只適用于實驗室模型驗證，只是簡單的工程解決方 案，還無法應用于海面的復雜狀況。

2021年江蘇海洋大學研究生科研創新計劃項目 （KYCX2021-087）

作者簡介：

馬思遠（1998-），男，江蘇連云港人，碩士，現就讀 于江蘇海洋大學，研究方向為船舶與海洋工程。

黃大志（1977-），男，河南新野人，副教授，博士， 現任教于江蘇海洋大學，研究方向為海洋智能裝備 。 為本文通訊作者。

徐慧麗（1997-），女，江蘇鹽城人，碩士，現就讀于 江蘇海洋大學，研究方向為船舶與海洋工程。

付曉月（1998-），女，河南安陽人，碩士，現就讀于 江蘇海洋大學，研究方向為船舶與海洋工程。

參考文獻：

[1] 曲毅, 潘民子. 無人艇路徑自主規劃方法及策略研究綜述[J]. 信息通信, 2019, (08) : 278 - 280.

[2] 段寶生. 無人水面自主工程勘察船技術[J]. 中國科技信息, 2014, (15) : 106 - 107.

[3] 薛春祥, 黃孝鵬, 朱咸軍, 蔣瑩瑩. 外軍無人系統現狀與發展趨勢[J]. 雷達與對抗, 2016, 36 (01) : 1 – 5, 10.

[4] 李家良. 水面無人艇發展與應用[J]. 火力與指揮控制, 2012, 37 (06) : 203 - 207.

[5] 孫曉界. 無人水面艇實時路徑規劃系統研究[D]. 大連: 大連海事大學, 2016.

[6] 劉琨. 基于人工勢場和蟻群算法的無人船路徑規劃研究[D]. 海南: 海南大學, 2016.

[7] E. W. Dijkstra. A note on two problems in connexion with graphs[J]. Numerische Mathematik, 1959, 1 (1).

[8] 王先全, 周錫祥, 余浩源, 李浩, 王向雨. 基于改進Dijkstra的應急指揮車及時救援的最短路徑算法的研究[J]. 電腦知識與技術, 2021, 17 (14) : 1 – 3, 10.

[9] 莊佳園, 萬磊, 廖煜雷, 孫寒冰. 基于電子海圖的水面無人艇全局路徑規劃研究[J]. 計算機科學, 2011, 38 (09) : 211 – 214, 219.

[10] Peter E. Hart, Nils J. Nilsson, Bertram Raphael. Correction to "A Formal Basis for the Heuristic Determination of Minimum Cost Paths"[J]. ACM SIGART Bulletin, 1972, (37).

[11] Marco Dorigo, Gianni Di Caro, Luca M. Gambardella. Ant Algorithms for Discrete Optimization[J]. Artificial Life, 1999, 5 (2).

[12] 陳佳, 游曉明, 劉升, 李娟. 動態分級的改良螞蟻算法及其應用研究[J]. 計算機應用研究, 2019, 36 (02) : 380 - 384.

[13] Holland John H.. Adaptation in Natural and Artificial Systems: An Introductory Analysis with Applications to Biology, Control, and Artificial Intelligence[M]. The MIT Press: 2018-08-31.

[14] 徐佳敏, 葉春明. 基于改進智能水滴算法的應急物流路徑研究[J]. 物流科技, 2015, 38 (08) : 28 - 31.

[15] Ezugwu Absalom E, Akutsah Francis, Olusanya Micheal O, Adewumi Aderemi O. Enhanced intelligent water drops algorithm for multi-depot vehicle routing problem.[J]. PloS one, 2018, 13 (3).

[16] 劉建. 水面無人艇路徑規劃技術的研究[D]. 鎮江: 江蘇科技大學, 2014.

[17] 陳超, 耿沛文, 張新慈. 基于改進人工勢場法的水面無人艇路徑規劃研究[J]. 船舶工程, 2015, 37 (09) : 72 - 75.

[18] Paolo Fiorini. Motion Planning in Dynamic Environments Using Velocity Obstacles[J]. The International Journal of Robotics Research, 1998, 17 (7).

[19] Johann Borenstein, Yoram Koren. The vector field histogram-fast obstacle avoidance for mobile robots.[J]. IEEE Trans. Robotics and Automation, 1991, 7 (3).

[20] Loe ?. Collision avoidance concepts for marine surface craft[J]. Rapp. tecn. Norvegian University of Science e Technology, 2007.

[21] Babinec A, Duchoň F, Dekan M, et al. VFH* TDT (VFH* with Time Dependent Tree): A new laser rangefinder based obstacle avoidance method designed for environment with non-static obstacles[J]. Robotics and autonomous syste ms, 2014, 62 (8) : 1098 - 1115.

摘自《自動化博覽》2021年11月刊