久久久91-久久久91精品国产一区二区-久久久91精品国产一区二区三区-久久久999国产精品-久久久999久久久精品

作者：馬思遠(yuǎn)，黃大志，徐慧麗，付曉月（江蘇海洋大學(xué)，江蘇 連云港 222005）

摘要：路徑規(guī)劃算法是無人平臺領(lǐng)域的重要研究方向，水面無人艇是一 種可移動的水面無人平臺。本文根據(jù)水面無人艇路徑規(guī)劃的功能進(jìn)行分 類，將路徑規(guī)劃算法劃分為局部路徑規(guī)劃和全局路徑規(guī)劃，并分析和對 比各常用算法的優(yōu)缺點(diǎn)，同時對優(yōu)化算法的現(xiàn)狀進(jìn)行了介紹。最后對目 前無人艇路徑規(guī)劃算法進(jìn)行了總結(jié)。

關(guān)鍵詞：無人艇；路徑規(guī)劃算法；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　引言

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

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

本文針對目前無人艇的路徑規(guī)劃算法進(jìn)行了研究， 比較不同算法的優(yōu)缺點(diǎn)，闡述了算法優(yōu)化的研究現(xiàn)狀， 最后對無人艇路徑規(guī)劃的算法進(jìn)行了總結(jié)。

2　全局路徑規(guī)劃算法

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

2.1　Dijkstra算法

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

經(jīng)典的Dijkstra算法原理簡單，但是計(jì)算流程過于 復(fù)雜且占用較多的內(nèi)存，獲取的結(jié)果只能按照預(yù)定的路 線航行，只適用于較小規(guī)模的路徑規(guī)劃。

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

2.2　A*算法

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

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

2.3　蟻群算法

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

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

2.4　遺傳算法

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

2.5　智能水滴算法

2009年Hamed Shah-Hossini提出智能水滴算 法，智能水滴算法根據(jù)水滴與周邊河道環(huán)境互相產(chǎn)生的 影響，如前進(jìn)速度、自身攜帶的泥土量，通過概率實(shí)現(xiàn) 對路徑的選擇，水滴受重力作用進(jìn)行啟發(fā)式搜索，以此 求解最優(yōu)路徑。

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

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

2.6　對比分析

全局路徑規(guī)劃算法的優(yōu)缺點(diǎn)對比如表1所示，除去 文中介紹的算法之外，還有模擬退火算法、神經(jīng)網(wǎng)絡(luò)算 法等其他全局規(guī)劃算法，但其在無人艇的路徑規(guī)劃中應(yīng) 用較少，故在此不做比較。

表1 全局路徑規(guī)劃算法比較

3　局部路徑規(guī)劃算法

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

3.1　人工勢場法

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

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

3.2　速度障礙法

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

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

3.3　向量場直方圖法

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

3.4　對比分析

以上局部路徑規(guī)劃算法的優(yōu)缺點(diǎn)如表2所示。除此 之外還有梯度法、ASL法等經(jīng)典局部路徑規(guī)劃算法，但 是并不適用于無人艇領(lǐng)域。

表2 局部路徑規(guī)劃算法比較

4　結(jié)論

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

2021年江蘇海洋大學(xué)研究生科研創(chuàng)新計(jì)劃項(xiàng)目 （KYCX2021-087）

作者簡介：

馬思遠(yuǎn)（1998-），男，江蘇連云港人，碩士，現(xiàn)就讀 于江蘇海洋大學(xué)，研究方向?yàn)榇芭c海洋工程。

黃大志（1977-），男，河南新野人，副教授，博士， 現(xiàn)任教于江蘇海洋大學(xué)，研究方向?yàn)楹Ｑ笾悄苎b備 。 為本文通訊作者。

徐慧麗（1997-），女，江蘇鹽城人，碩士，現(xiàn)就讀于 江蘇海洋大學(xué)，研究方向?yàn)榇芭c海洋工程。

付曉月（1998-），女，河南安陽人，碩士，現(xiàn)就讀于 江蘇海洋大學(xué)，研究方向?yàn)榇芭c海洋工程。

參考文獻(xiàn)：

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

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

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

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

[5] 孫曉界. 無人水面艇實(shí)時路徑規(guī)劃系統(tǒng)研究[D]. 大連: 大連海事大學(xué), 2016.

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

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

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

[9] 莊佳園, 萬磊, 廖煜雷, 孫寒冰. 基于電子海圖的水面無人艇全局路徑規(guī)劃研究[J]. 計(jì)算機(jī)科學(xué), 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] 陳佳, 游曉明, 劉升, 李娟. 動態(tài)分級的改良螞蟻算法及其應(yīng)用研究[J]. 計(jì)算機(jī)應(yīng)用研究, 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ìn)智能水滴算法的應(yīng)急物流路徑研究[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] 劉建. 水面無人艇路徑規(guī)劃技術(shù)的研究[D]. 鎮(zhèn)江: 江蘇科技大學(xué), 2014.

[17] 陳超, 耿沛文, 張新慈. 基于改進(jìn)人工勢場法的水面無人艇路徑規(guī)劃研究[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月刊