改進動態避障策略和可變步長A*的USV路徑規劃

摘 要：針對水面無人艇USV全局路徑規劃中存在的生成路徑冗余、無法滿足實時性及局部路徑規劃易陷入局部最優等問題，提出了融合改進動態避障策略和可變步長A-Star算法的路徑規劃算法DAVSA。首先，通過可變步長搜索策略對柵格地圖進行預處理，篩選出關鍵跳轉點作為A-Star算法待考慮的擴展節點，快速生成全局最優路徑。其次，提出路徑二次優化策略，縮短全局路徑長度，解決全局路徑的轉折點多、路徑冗余的問題。最后，針對傳統A-Star算法無法滿足實時路徑規劃的問題，提出改進局部路徑動態避障策略，構建全局路徑距離評價因子，達到實時最優路徑規劃的目的。仿真結果表明，相較于IDWA算法，DAVSA算法的平均全局尋路時間減少了59.46%，綜合算法運行時間減少了5.08%，綜合路徑長度縮短了9.08%，能夠滿足動態環境中實時避障的要求。

關鍵詞：跳點搜索；A-Star算法；可變步長；地圖預處理；路徑二次優化；動態避障；路徑規劃

中圖分類號：TP242 文獻標識碼：A 文章編號：2095-1302（2025）03-00-10

0 引 言

隨著海洋資源保護的重要性不斷提升以及大國競爭日趨激烈，發展水面無人艦艇變得至關重要。新一代智能水面無人艦艇（Unmanned Surface Vessel， USV）具有自主導航、智能避障和自主探測目標區域環境信息的能力[1]，在海洋資源勘探、環境監測和海洋安全等領域得到廣泛應用。高效的路徑規劃技術對提高USV的作業效率和資源利用率至關重要[2]。USV的路徑規劃算法主要分為基于已知環境信息的全局路徑規劃和未知環境的局部路徑規劃。其中，全局路徑規劃包括A-Star算法、RRT算法、遺傳算法、蟻群算法、粒子群算法、神經網絡算法、強化學習算法等。局部路徑規劃包括動態窗口算法（Dynamic Window Algorithm， DWA）、人工勢場法、時間彈性帶算法、模型預測控制算法、基于采樣的算法等[3-14]。在靜態已知地圖環境中，全局路徑規劃算法有著更好的性能，可以很快地找到一條最優路徑，但不適用于動態多變的地圖環境。局部路徑規劃算法能夠根據實時環境信息進行路徑規劃，快速響應環境變化，并及時修正路徑，但是存在容易陷入局部最優的問題。因此，找到一種既能快速生成全局最優路徑，又能根據實時信息進行動態避障的路徑規劃算法成為USV安全、高效行駛的關鍵。

A-Star算法由于具有易實現、低復雜度等優點，被廣泛應用在全局路徑規劃中，但是該算法存在生成路徑冗余和無法滿足實時性等問題。針對這些問題，許多國內外學者做了大量的研究工作。文獻[15]提出了一種基于跳點搜索的分層柵格地圖的JA*算法，將環境信息分為結構層與非結構層，并建立了搜索策略切換機制，從而有效減少了計算量，但是該算法只適用于靜態環境地圖。文獻[16]提出了改進的A-Star算法與貪婪算法相結合的多目標路徑規劃算法，改進后的算法收斂速度更快，同時剔除了A-Star算法中不必要的節點，生成的路徑更加平滑，路徑長度減少了5%，但是不能應對地圖中存在移動障礙物的情況。文獻[17]提出了一種名為FAPF的模糊決策方法，旨在消除USV在路徑上遇到障礙物無法避障的問題。但是，該算法沒有將障礙物的碰撞類型作更細致的劃分。

在真實海洋環境中，USV隨時會遇到突發或未知的風險，因此需要采取局部路徑規劃的動態避障策略，以確保航行的安全。其中最經典的動態避障算法是動態窗口法，DWA算法具有良好的避障能力，能夠滿足實時路徑規劃等要求，其針對動態障礙物也有顯著的避障效果，并且生成的路徑更為平滑，缺點是容易陷入局部最優。文獻[18]提出了一種改進蟻群算法與DWA算法融合的路徑規劃算法，解決了蟻群算法的鎖死問題，但是該算法在尋找全局路徑時所消耗的時間成本較高。文獻[19]提出了改進A*算法與DWA算法相融合的路徑規劃方法，在保證全局路徑最優的前提下，增強了其動態避障的能力，但是移動障礙物運動方式過于單一，避障性能無法充分體現。文獻[20]提出了一種結合DWA算法的改進型IWSO-DWA算法，并在USV的路徑規劃中引入國際海上避碰規則公約（COLREGs），提出的方法不僅能在復雜的海洋環境中規劃出最優的全局路徑，還能實時動態地避開其他船只，確保USV的安全航行。文獻[21]提出了一種滿足COLREGs的IDWA路徑規劃方法，解決了USV無法到達目的地、路徑不合理等問題，使得USV能夠避開靜態障礙物到達目的地，但是在遇到左側存在交叉移動障礙物的情況時，采取此策略可能會發生碰撞風險。

綜上所述，針對USV在全局路徑規劃中存在的生成路徑冗余、實時性低及局部路徑規劃易陷入局部最優等問題，本文提出了融合改進動態避障策略和可變步長A-Star算法的路徑規劃算法（Dynamic Avoidance and Variable Step A-star， DAVSA）。DAVSA分為全局路徑規劃和局部路徑規劃2個部分。在全局路徑規劃階段，通過可變步長搜索策略對柵格地圖進行預處理，篩選出關鍵跳轉點作為A-Star算法待考慮的擴展節點，利用啟發式搜索快速生成全局最優路徑，減少尋路過程中節點冗余的問題。接著，提出路徑二次優化策略，進一步縮短全局路徑長度。在局部路徑規劃階段，針對傳統A-Star算法實時性低的問題，提出局部路徑動態避障策略，構建全局路徑距離評價因子，達到實時最優路徑規劃的目的。

1 環境建模

常見的水面無人艦艇路徑規劃地圖建模方法有路標導航法、SLAM技術建模、柵格地圖法等。其中柵格地圖操作簡單，易于實現，適用范圍廣，因此本文采用柵格法構建環境模型。將海域環境離散為一個個柵格，如圖1所示。每個柵格表示一個狀態，白色柵格表示自由柵格，代表可行區域；黑色柵格表示障礙物節點，不可通行和穿越。在地圖上自左向右、自下而上由0開始為柵格添加編號，依次是0， 1， 2， 3， ...， 399。

柵格編號與柵格之間的轉換計算方法如式（1）和式（2）所示：

（1）

i=（x-1）+（y-1）*n （2）

式中：（x， y）表示柵格對應的坐標位置；i表示柵格編號；n表示柵格總列數；mod（）為取余函數；floor（）為向下取整函數。

2 DAVSA算法設計

DAVSA算法分為全局路徑規劃和局部路徑規劃2部分。首先，利用可變步長搜索策略篩選出地圖中所有的跳點，再根據啟發式搜索對其進行遍歷，找到一條全局最優路徑；然后，對生成的全局路徑進行二次優化，并提取路徑上的關鍵點信息，作為下一步局部路徑規劃的引導點；最后，由DWA算法依次導航到每個局部引導點，并改進路徑評價函數，引入全局路徑評價因子，使其盡量沿著已經規劃好的全局路徑行駛。這樣，全局與局部的融合不僅可以使無人艇快速到達目的地，同時也可以避免陷入局部最優并提高算法實時性，保證了系統的時效性和安全性。通過不斷地更新和優化局部路徑，可以使無人艇始終處于最佳狀態，保證任務的順利完成。全局路徑規劃的目的是快速找到一條全局最優路徑，因此需要引入可變步長搜索策略和路徑二次優化策略。

算法流程如圖2所示。

2.1 變步長搜索策略

傳統的A-Star算法采用八鄰域搜索策略，如圖3所示。在擴展節點時需要將當前節點周圍所有非障礙物節點和不在開放列表中的節點都進行遍歷，圖中淺灰色節點表示需要擴展的節點。選擇一個函數啟發值最小的節點作為父節點，將該節點加入到關閉列表中。然后繼續下一輪的遍歷，直到遍歷到終點為止。最后，從終點開始向前回溯，順著每個節點的父節點一直往前走，直到回溯到起點。當回溯到起點后，就得到了一條從起點到終點的全局最優路徑。這樣雖然計算簡單，但是存在大量非必要節點的遍歷操作，以及對開放列表和關閉列表的反復讀寫操作，使得算法在應對大場景地圖時整體效率不高。

為了解決傳統A-Star算法在路徑規劃中存在的擴展節點多的問題，本文提出采用可變步長搜索策略對其進行改進。可變步長搜索策略在原有算法的基礎上修改節點擴展規則，不再對所有鄰居節點進行遍歷、計算，而是只遍歷地圖中的關鍵跳轉點，簡稱跳點。跳點就是可以在搜索時可以直接跳躍的節點，2個跳點之間的節點不會被遍歷，這樣就大大提高了搜索效率。不同于Jump-A*算法，可變步長A*算法通過動態調整搜索步長以適應地圖的不同區域，而Jump-A*算法通過跳過對稱的、無障礙的路徑段，來減少搜索空間。

關鍵跳轉點的選取規則如下：節點N是起點或終點；節點N至少有一個強迫鄰居；節點N的水平或垂直方向有滿足上述2個條件的節點。如果節點N滿足任意條件，則稱節點N為關鍵跳轉點。

強迫鄰居是指算法在遍歷過程中必須要訪問的節點。在搜索過程中，會把當前節點的強迫鄰居設定為下一步的目標點。圖4表示當前節點N周圍沒有障礙物存在的情況，此時當前節點N周圍的灰色區域代表一般鄰居，一般鄰居節點不進行遍歷操作。

假設節點N的父節點為P，如果節點P經過N到達節點Q的路徑長度比不經過N到達Q的任意路徑的長度短，則稱Q是N的強迫鄰居。如圖5所示，節點P經過節點N到達節點Q的路徑長度要比不經過節點N到達節點Q的任意路徑的長度要小，因此將節點Q定義為節點N的強迫鄰居。圖5（a）表示在水平方向搜索時，障礙物節點位于當前節點下方的情況，此時節點P經過當前節點N到達Q的距離最短，因此Q為N的強迫鄰居節點；同理，圖5（b）是在對角方向搜索時，障礙物節點位于當前節點N左側的情況，Q為N的強迫鄰居節點。

加入可變步長搜索策略可以減少傳統算法在搜索中的擴展節點個數，從而大大提高搜索效率，其算法工作原理如下：

（1）首先判斷當前節點是否為跳點；

（2）如果當前節點是跳點，則向當前節點的強迫鄰居節點擴展，如果強迫鄰居節點也是跳點，則繼續向其他強迫鄰居擴展；

（3）如果當前節點不是跳點，則搜索算法會把當前節點從待擴展節點中刪除；

（4）每個節點的評估值是根據當前節點到起點和終點的歐氏距離計算得出的。

通過對地圖中跳點的篩選，可以有效簡化啟發式搜索流程，在傳統A-Star算法基礎上增加跳點搜索策略，可以減少尋路過程中的計算次數，快速地找到一條全局最優路徑，從而提高算法搜索效率。加入可變步長搜索策略之后的搜索路徑如圖6所示。

圖6（a）中淺灰色節點表示傳統A-Star算法在搜索時需要擴展的節點，圖6（b）表示加入了可變步長搜索策略后的擴展節點。由此可見，加入可變步長搜索策略之后，擴展節點明顯減少，算法效率大大提高。

2.2 路徑二次優化策略

加入可變步長搜索策略的A-Star雖然能夠快速找到一條全局最優路徑，但是受限于八鄰域方向搜索，生成的全局路徑上仍然存在冗余節點過多、路徑的轉折點過多、路徑長度較長、直線不可達等問題，因此提出路徑二次優化策略。目的是進一步縮短全局路徑，減少路徑的轉折點，為下一步的局部探索打下良好的基礎，并最小化無人艦艇的動能損失。路徑經過二次優化后的效果如圖7（c）所示。

路徑二次優化是在加入可變步長策略之后進行的優化操作。具體操作流程如下：假設全局路徑由lt;1， 2， 3， ...， ngt;共n個節點依次連接組成，首先從1號節點開始，判斷lt;1， 3gt;是否可以直接連接且不穿過地圖中的障礙物節點，如果可以，則2號節點為冗余節點，應直接刪除；此時該路徑還剩余lt;1， 3， 4， ...， ngt;共n-1個節點，再判斷lt;1， 4gt;節點是否可以直接連接；若此時穿越地圖中的障礙物節點，則3號節點就不為冗余節點，應保留。接下來判斷4號節點是否為冗余節點，判斷條件是lt;3， 5gt;是否可以直接連接，依次類推直到節點n結束。此時，一條包含了n個路徑節點的無碰撞路徑二次優化完成，可形成由節點lt;1， ...， k， ...ngt;（k≥0）組成的新的全局無碰撞路徑。

如圖7所示，傳統算法規劃出的路徑上有lt;1， 2， 3， ...， 12gt;共12個節點，經過可變步長策略優化之后的路徑可以將起點至3號節點、3號節點至9號節點、11號節點至終點之間的冗余節點剔除，此時路徑上有lt;3， 9， 10， 11gt;共4個節點。根據路徑二次優化策略的思想，首先判斷起點至9號節點是否可以直接聯通，發現連接的路徑不經過障礙物節點，所以3號節點為冗余節點，應刪除；然后連接起點與10號節點，中間經過障礙物，則9號不是冗余節點，應該保留；再連接9號與11號節點，同樣經過障礙物，故保留10號節點；然后連接10號節點與終點，路徑經過障礙物，故11號節點保留，經過處理后的路徑上還有lt;9， 10， 11gt;共3個節點。

通過路徑二次優化策略，可以有效地減少路徑中的冗余節點數量，簡化路徑，從而提高全局路徑質量。

3 改進動態窗口算法

傳統的DWA算法雖然能夠滿足局部動態避障的要求，但是容易陷入局部最優，因此需要引入全局路徑信息進行引導。若采用未經過二次優化的全局路徑，可能會出現路徑長度較長的問題。因此，選擇在二次優化后的路徑上選取局部引導點，以提升局部路徑規劃的效果。對比路徑如圖8所示。其中，局部引導點取自經過二次路徑優化的全局路徑的轉折點。

為了更好地展現局部路徑規劃避障策略的效果，還需要對無人艇進行運動學建模和速度采樣建模。運動學模型反映了無人艇在運動過程中的行為特征，如線速度和角速度等。速度采樣模型則反映了在一定時間窗口內的速度變化情況，并生成若干采樣曲線預估無人艇到達的目標位置等。

3.1 運動模型

假設無人艇非全向移動，有左右2個推進裝置，可以前進和圍繞原點O左右旋轉，具有X、Y軸方向上的線速度ν和繞原點O旋轉的角速度ω。在相鄰時刻Δt內，運動距離短，可將相鄰兩點之間的運動軌跡看成直線，如圖9所示。

無人艇的行駛距離可表示為：

ΔS=v*Δt （3）

式中：ν表示無人艇的線速度；Δt是相鄰時刻的間隔；ΔS為無人艇在Δt時刻內的移動距離。轉換成無人艇的坐標表示為：

Δx=vΔtcos（θt） （4）

Δy=vΔtsin（θt） （5）

式中：θ是無人艇的朝向和水平軸的夾角；Δx是無人艇在Δt時間內水平方向上的移動距離；Δy是無人艇在Δt時間內垂直方向上的移動距離。無人艇在下一個時刻的位置表示為：

x=x0+vΔtcos（θt） （6）

y=y0+vΔtsin（θt） （7）

θt=θt0+ωΔt （8）

式中：（x0， y0）表示無人艇的初始位置；（x， y）表示經過Δt時間無人艇移動的位置。

根據以上無人艇的運動模型，用速度和時間信息推算出無人艇的下一個位置的狀態信息。

3.2 速度采樣模型

DWA算法主要通過在無人艇周圍建立動態窗口來搜索最佳路徑，在動態窗口內對一系列線速度和角速度的候選值進行采樣，評估無人艇當前位置與目標點之間的距離、路徑上是否有障礙物等因素，計算出無人艇在未來一段時間內可能通過的窗口，推導出無人艇的最佳線速度和角速度，并選擇最優解作為無人艇下一步的運動速度。速度采樣模型如圖10所示。其中，ν表示線速度；ω表示角速度；νa表示線加速度；ωa表示角加速度；Δt表示單位時間間隔。

3.3 DWA算法改進

在速度空間（ν， ω）中采樣，根據運動學模型推測對應的軌跡，引入路徑評價函數，對軌跡進行打分，選取最優的軌跡，一般來說，評價函數如下：

G（v， ω）=σ（α*heading（v， ω）+β*dist（v， ω）+γ*velocity（v， ω））" "（9）

式中：heading（ν， ω）為方位角評價函數，用于評價無人艇在當前的設定速度下，軌跡末端朝向與目標點之間的角度差距；dist（ν， ω）為無人艇處于預測軌跡末端點位置時與地圖上最近障礙物的距離，根據該距離對于靠近障礙物的采樣點進行懲罰，確保無人艇的避障能力，降低無人艇與障礙物發生碰撞的概率；velocity（ν， ω）為當前無人艇的線速度，物理意義是使無人艇避開障礙物，朝著目標以較快的速度行駛。

上述計算并非簡單地累加，而需進行歸一化處理。通過歸一化避免不同類別得分基數相差太大，從而影響最終結果。在歸一化以后，將每個部分的權重分別定義為σ、α、β、γ，并賦予初始的權值，不同的權重系數會直接影響無人艇行駛路徑的選取。因此，引入模糊控制系統函數，通過輸入無人艇當前的方位角、與最近障礙物的距離、線速度等參數，輸出一個用于調整權重系數的集合，實現根據當前環境的特征自適應地調整權重系數。

為了減少能量流失，設計了全局節能路徑偏離評價子函數distEvalu（ν， ω），權重為λ，目的是使得融合算法規劃的路徑更接近全局最優路徑。評價子函數distEvalu（ν， ω）結合全局節能路徑信息，根據歐氏距離公式計算無人艇當前位置與全局路徑之間的最短距離，使無人艇在局部路徑規劃時更好地遵循全局路徑，修改后的綜合評價函數如下：

G（v， ω）=σ（α*heading（v， ω）+β*dist（v， ω）+γ*velocity（v， ω）+

λ*distEvalu（v， ω）） （10）

3.4 碰撞類型及避障策略

本文按照碰撞方式的不同，將碰撞類型分為4類：正面相對行駛的障礙物、左側交叉行駛的障礙物、右側交叉行駛的障礙物和同向行駛的障礙物。如圖11所示，在遇到移動障礙物在正面、左側交叉、右側交叉和追隨的情況下，無人艇會分別做出不同的避障策略。

結合國際海上避碰規則COLREGs，若無人艇與移動障礙物發生正面碰撞，且位于無人艇的左側時，無人艇應該采取右側繞行的避障策略，如圖11（a）所示；若移動障礙物出現在無人艇左側并向右行駛時，此時無人艇應該采取左側繞行的避障策略，如圖11（b）所示；同理，當移動障礙物自右向左行駛時，無人艇應該采取右側繞行的避障策略，如圖11（c）所示；當移動障礙物位于無人艇的正前方，并同向行駛時，無人艇可以分別在其左右兩側繞行，如圖11（d）所示。

4 實驗仿真

首先為了驗證DAVSA算法在水面無人艦艇路徑規劃方面的性能，對二維水面環境進行仿真建模，采用柵格地圖構建仿真環境地圖，對傳統A-Star算法、文獻[21]的IDWA算法和DAVSA算法進行了對比分析。其次為了驗證動態避障策略在真實海域的有效性，選取真實海域的電子海圖并將其作柵格化處理，分別在簡單海域和復雜海域的柵格地圖中進行4種避障策略的驗證。

仿真實驗的軟硬件配置見表1。

本文利用柵格地圖構建二維水面仿真環境，USV的起點坐標為（1，1），終點坐標為（19，19）。USV的運動學模型參數見表2。

4.1 全局路徑規劃實驗驗證

在全局路徑規劃過程中開展算法對比實驗。對比算法分別為傳統A-Star算法、IDWA算法、引入可變步長的A-Star算法與DAVSA算法，對比指標有尋路時間、擴展節點個數和路徑長度等，實驗結果如圖12～圖15所示。

圖13中淺灰節點代表IDWA算法在尋路過程中的擴展節點，對比圖12的傳統A-Star算法，二者都能找到一條全局最優路徑。但是在時間方面，IDWA算法相對于傳統A-Star算法有所縮短，擴展節點個數也相對減少。圖14所示為引入可變步長之后的A-Star算法實驗結果，其中淺灰色節點為路徑上的關鍵跳點，深灰色為備選跳點。相比于IDWA算法，該算法的尋路時間明顯縮短，擴展節點個數也相對減少。圖15表示DAVSA算法的最終路徑，相對于引入可變步長的A-Star算法和IDWA算法，路徑長度進一步縮短，擴展節點個數也明顯減少，具體見表3。

通過表3可以看出，擴展節點的減少使得算法尋路時間縮短，雖然相較于可變步長的A-Star，DAVSA的節點進一步減少，但由于路徑二次優化消耗了一定的時間，因此總體尋路時間略有增加。

4.2 簡單海域地圖下的動態避障對比實驗

加入動態障礙物后，要求其實時規劃的路徑應避開移動的障礙物，因此需要采用DWA算法的思想來避免移動障礙物對無人艇的影響。在規劃路徑時，首先考慮到無人艇當前的狀態以及運動能力，選擇合適的線速度和角速度。接著，考慮移動障礙物的位置和速度，并反向應用到無人艇的速度和方向上。這樣就可以避免無人艇撞到障礙物，同時規劃出一條安全通暢的路徑。在實際應用中，可以根據實時的障礙物信息進行動態調整，保證路徑的正確性和完整性。

在進行局部路徑規劃時，選取全局路徑的關鍵點作為局部路徑規劃的局部引導點，以這些點為基礎，結合無人艇的當前狀態信息，改進局部路徑規劃算法，使其沿著全局最優路徑向目標點前進。無人艇可以根據在當前的局部環境中探測到的障礙物運動情況進行實時避障；同時，依據全局最優路徑的評價因子和全局路徑信息來實時規劃路徑，避免與障礙物發生碰撞。

為了驗證無人艇動態避障策略的有效性，本文將選取真實海域的電子海圖進行柵格化處理，選取簡單海域環境并將其柵格化為20×20的柵格地圖，圖16所示為簡單海域的柵格地圖。

為了驗證動態避障策略的有效性，在簡單海域柵格地圖中，針對航行中經常遇到的情況，增加4種不同移動方向的動態障礙物，分別是正面相對行駛的障礙物、同向行駛的移動障礙物、左側交叉行駛的障礙物和右側交叉行駛的障礙物。在20×20簡單柵格環境下，將DAVSA算法與IDWA算法[21]進行對比實驗，測試4種USV的動態避障策略針對不同移動方向障礙物的效果，結果如圖17～圖20所示。

由圖17～圖20可明顯看出，DAVSA算法下的路徑均優于IDWA算法下的路徑，尤其是在遇到自左向右和自右向左移動的障礙物的情況下。這是因為通過引入動態避障策略，可以減少無人艇與移動障礙物的會遇時間，在縮短全局尋路綜合時間的同時也能縮短路徑長度。

當無人艇遇到正面相對行駛的移動障礙物時，無人艇應該向右舷改變路線，以免發生碰撞。圖17（a）為采用IDWA算法的無人艇避障路線，圖17（b）為采用DAVSA算法的無人艇避障路線。當無人艇遇到同向行駛的移動障礙物，且位于無人艇的右側方向時，無人艇應向左舷改變航向。圖18（a）為采用IDWA算法的無人艇避障路線，圖18（b）

為采用DAVSA算法的無人艇避障路線。當無人艇檢測到移動障礙物來自無人艇的左舷，遇到左舷交叉的情況，無人艇應向右舷改變路線，以免發生碰撞。圖19（a）為采用IDWA算法的無人艇避障路線，圖19（b）為采用DAVSA算法的無人艇避障路線。當無人艇檢測到移動障礙物來自無人艇的右舷，遇到右舷交叉的情況，無人艇應向左舷改變路線，以免發生碰撞。圖20（a）表示采用IDWA算法的無人艇避障路線，圖20（b）為采用DAVSA算法的無人艇避障路線。

通過算法仿真得到表4的數據。仿真結果表明，對障礙物在4種不同移動方向上的算法性能提升值取平均，DAVSA算法相較于IDWA算法，平均全局尋路時間降低了59.46%，綜合算法運行時間降低了5.08%，綜合路徑長度縮短了9.08%，能夠滿足動態環境中實時避障的要求。具體計算公式如式（11）～式（13）所示：

（11）

式中：Tglobal表示全局尋路時間提升率；TglobalIDWAi表示第i個IDWA算法的全局尋路時間；TglobalDAVSAi表示第i個DAVSA算法的全局尋路時間。

（12）

式中：Tcomplete表示綜合尋路時間提升率；TcompleteIDWAi表示第i個IDWA算法的綜合尋路時間；TcompleteDAVSAi表示第i個DAVSA算法的綜合尋路時間。

（13）

式中：Lpath表示路徑長度縮短率；LpathIDWAi表示第i個IDWA算法的路徑長度；LpathDAVSAi表示第i個DAVSA算法的路徑長度。

DAVSA算法之所以優于IDWA算法，是因為DAVSA針對不同來向的移動障礙物分別對應不同的避障策略，綜合考慮無人艇與移動障礙物之間的相對位置、速度和障礙物距離等因素，從而保證無人艇的安全導航，并最大程度上接近在全局最優路徑上行駛。由表4可知，在遇到不同來向的移動障礙物時，DAVSA算法在全局尋路時間、綜合尋路時間以及路徑長度這3個性能指標上均優于IDWA算法。

4.3 復雜環境下的動態避障策略驗證

為了進一步驗證無人艇在復雜海域的避障能力，本文選取復雜海域環境進行仿真實驗。同樣地，對復雜海域電子地圖進行柵格化處理。圖21所示為復雜海域的柵格地圖。

在復雜海域柵格地圖中，同樣增加4種不同移動方向的動態障礙物，分別是正面相對行駛、同向行駛、左側交叉行駛和右側交叉行駛的移動障礙物。在20×20的復雜柵格環境下，測試USV的動態避障策略對于4種不同移動方向障礙物的效果，結果如圖22～圖25所示。

由圖22～圖25可知，DAVSA算法能夠在遵守COLREGs的前提下，針對不同來向的移動障礙物采取對應的避障策略，自動計算出最佳的避障路徑，避免與障礙物發生碰撞，從而有效地確保無人艇在簡單和復雜的海域環境中安全航行。

對比表4、表5可知，在復雜環境下DAVSA算法的綜合尋路時間和路徑長度都有所增加。這是由執行動態避障策略所導致的，無人艇需要更多的時間來調整路徑，路徑長度也可能因為避障而變得更長。

5 結 語

針對USV在全局路徑規劃中存在的生成路徑冗余且無法滿足實時性的要求，以及局部路徑規劃過程中容易陷入局部最優等問題，提出了DAVSA的路徑規劃算法。改進后的算法能夠快速生成一條全局最優路徑，經過二次優化后擁有更短的路徑，同時具有較好的動態避障能力，能夠有效地響應各種場景下的移動障礙物，并產生相應的狀態變化。文中通過實驗驗證了算法的有效性。雖然該算法已經取得了一定的成果，但還存在一些不足之處。當前的實驗都是在已知全局地圖信息的前提下進行的，未來的研究方向將會聚焦于未知環境下的路徑規劃和實時預測，并研究適用于復雜海洋環境下的水面無人艦艇路徑規劃算法。

注：本文通訊作者為劉琦。

參考文獻

[1] LIU C， XIANG X， HUANG J， et al. Development of USV autonomy： architecture， implementation and sea trials [J]. Brodogradnja， 2022， 73（1）： 89-107.

[2] ZHAO L， BAI Y， WANG F， et al. Path planning for autonomous surface vessels based on improved artificial fish swarm algorithm： a further study [J]. Ships and offshore structures， 2023， 18（9）： 1325-1337.

[3] TANG X， ZHU Y， JIANG X. Improved A-star algorithm for robot path planning in static environment [J]. Journal of physics： conference series， 2021， 1792（1）： 012067.

[4] MAO S， YANG P， GAO D， et al. A motion planning method for unmanned surface vehicle based on improved RRT algorithm [J]. Journal of marine science and engineering， 2023， 11（4）： 687.

[5] LIU C， LIU A， WANG R， et al. Path planning algorithm for multi-locomotion robot based on multi-objective genetic algorithm with elitist strategy[J]. Micromachines， 2022， 13（4）： 616.

[6]郝琨，張慧杰，李志圣，等.基于改進避障策略和雙優化蟻群算法的機器人路徑規劃[J].農業機械學報，2022，53（8）：303-312.

[7] PHUNG M， HA Q. Safety-enhanced UAV path planning with spherical vector-based particle swarm optimization [J]. Applied soft computing， 2021， 107： 107376.

[8] SUNG I， CHOI B， NIELSEN P. On the training of a neural network for online path planning with offline path planning algorithms [J]. International journal of information management， 2021， 57： 102142.

[9] CHEN L， WANG Y， MIAO Z， et al. Transformer-based imitative reinforcement learning for multi-robot path planning [J]. IEEE transactions on industrial informatics， 2023， 19（10）： 10233-10243.

[10] YAO M， DENG H， FENG X， et al. Improved dynamic windows approach based on energy consumption management and fuzzy logic control for local path planning of mobile robots [J]. Computers amp; industrial engineering， 2024， 187： 109767.

[11] HE Z， CHU X， LIU C， et al. A novel model predictive artificial potential field based ship motion planning method considering COLREGs for complex encounter scenarios [J]. ISA transactions， 2023， 134： 58-73.

[12] DAI W， MA X. Improvement of collision detection using time elastic band algorithm [C]//2021 The 9th International Conference on Information Technology： IoT and Smart City. [S.l.]： [s.n.]， 2021： 93-97.

[13] HANG P， HUANG S， CHEN X， et al. Path planning of collision avoidance for unmanned ground vehicles： a nonlinear model predictive control approach [J]. Proceedings of the institution of mechanical engineers， Part I： journal of systems and control engineering， 2021， 235（2）： 222-236.

[14] ZHOU C， HUANG B， FRANTI P. A review of motion planning algorithms for intelligent robots [J]. Journal of intelligent manufacturing， 2022， 33（2）： 387-424.

[15]周熙棟，張輝，陳波.非結構化場景下基于改進JPS算法的移動機器人路徑規劃[J].控制與決策，2024，39（2）：474-482.

[16] XIANG D， LIN H， OUYANG J， et al. Combined improved A* and greedy algorithm for path planning of multi-objective mobile robot [J]. Scientific reports， 2022， 12（1）： 1-12.

[17] WANG N， XU H， LI C， et al. Hierarchical path planning of unmanned surface vehicles： a fuzzy artificial potential field approach [J]. International journal of fuzzy systems， 2021， 23（6）： 1797-1808.

[18]魏立新，張鈺錕，孫浩，等. 基于改進蟻群和 DWA 算法的機器人動態路徑規劃[J]. 控制與決策，2022，37（9）：2211-2216.

[19]劉鈺銘，黃海松，范青松，等.基于改進A*-DWA算法的移動機器人路徑規劃[J].計算機集成制造系統，2024，30（1）：158-171.

[20] LIANG J， LIU L. Optimal path planning method for unmanned surface vehicles based on improved shark-inspired algorithm[J]. Journal of marine science and engineering， 2023， 11（7）： 1386.

[21] GUAN W， WANG K. Autonomous collision avoidance of unmanned surface vehicles based on improved a-star and dynamic window approach algorithms[J]. IEEE intelligent transportation systems magazine， 2023， 15（3）： 36-50.