基于改進人工勢場算法的無人船路徑規劃

葉軍林 何建林 陳孟祥

摘要：針對無人船路徑規劃中傳統勢場算法存在的問題，如容易進入局部極小點、航行路徑不平滑、在復雜航行環境中目標不可達等，提出了一種改進的人工勢場方法。通過增加距離影響因子和改進斥力場函數，解決了上述問題；在無人船行進過程中，通過動態調整斥力參數，并增加逃逸力，使目標點成為全局勢場中的最小點；通過在Matlab平臺上進行仿真實驗，驗證了改進后的人工勢場方法的有效性。實驗結果表明，改進的方法能夠克服目標不可達問題和局部極小值問題，同時在計算量和路徑規劃步數方面具有一定的優勢。

關鍵詞：路徑規劃；人工勢場；局部極小值；斥力函數

中圖分類號： TP391. 9? ? ? ? ?文獻標識碼：A

文章編號：1009-3044（2023）35-0010-06

開放科學（資源服務）標識碼（OSID）

0 引言

無人式水面航行器也稱水面無人船/艇（Unmanned Surface Vehicle，USV） ，問世已有 70余年的歷史，但相比于無人機/車系統，無人船/艇是一種較為陌生的無人化、智能化作業平臺。無人船一般用于代替人員執行各種水域復雜任務，其中路徑規劃技術在無人船舶自主導航中具有極其重要的應用價值。作為核心技術，路徑規劃旨在解決無人船在存在固定或移動障礙物的環境中如何安全航行的問題。其主要任務是搜索出一條從起點到目標點的路徑，該路徑既要保證安全無碰撞，又要達到最優或接近最優的效果。

當前，路徑規劃技術已經相當成熟，并且廣泛應用。其中，一些常見的規劃方法包括Dijkstra算法、A*算法、人工勢場法、模糊算法、粒子群算法、遺傳算法、非線性模型預測算法，以及這些算法的改進和融合。Dijkstra算法的優點在于較高的最短路徑搜索成功率，然而，該算法的缺點也顯而易見。由于需要遍歷所有頂點，算法效率較低。A*算法的優點是算法較為簡單，易于實現，并且擴展節點數量較少。它能夠保證全局最優解的收斂性，然而該算法的缺點是啟發函數h（n）的選擇不容易。如果啟發函數h（n）涉及的信息越多，計算量就會增加，從而導致算法效率降低；相反，如果啟發函數提供的信息較少，則算法的準確性可能較差。模糊控制法是一種利用人類已有的駕駛經驗結合模糊的環境信息的方法，通過查詢表格來確定實時的路徑規劃策略。然而，這種方法在避障方面的準確度較低。粒子群算法具有隨機搜索算法的特點，然而對于高維度的復雜問題，粒子群算法可能會出現早熟收斂現象，導致收斂性能較差，并且無法保證達到最優解。

相較于其他算法，人工勢場法在實際無人船路徑規劃問題中具有較快的反應速度、較高的實時性和較少的計算量，因此在實踐中得到廣泛應用。然而，在復雜的航行環境中，無人船可能會出現目標不可達和局部最小點問題，導致行進路線規劃失效[1]。

針對人工勢場法的缺點，國內外學者提出了多種解決方案。其中包括在使用原勢場模型的同時消除或逃離局部極小點，構建新的勢場函數，以及與智能優化算法相結合[2]。在本文中，采用指數函數構建了一個新的勢場函數模型，并根據無人船與障礙物距離的實時調整勢場函數的參數，判定無人船陷入局部極小點時增加逃逸力。通過這種方法，解決了傳統人工勢場法中目標不可達和局部最小點問題，實現了對無人船路徑的實時規劃。

1 傳統人工勢場算法在海域環境中的應用

1.1 目標任務

圖1為南方某港口，港口內有工作繁忙的船只以及障礙物?，F有一艘無人船需要穿過眾多障礙物行進到出?？贒點完成采集信息任務，采用傳統人工勢場算法實現該艘無人船從起始點A到目標終點D的路徑規劃，航跡如圖中黑色虛線所示。

1.2 傳統人工勢場算法做路徑規劃

人工勢場法是通過模擬粒子在勢場中的運動，將無人船的路徑規劃問題轉化為在勢場中的運動問題。在人工勢場法中，通常將目標點視為吸引子（attraction） ，將障礙物視為斥力（repulsion） 。無人船會受到目標點的吸引力和障礙物的斥力影響，從而生成一條避開障礙物、朝向目標點的路徑。人工勢場法包括吸引子勢場和斥力勢場兩個基本組成部分。吸引子勢場（Attraction Field） ：吸引子勢場用來引導無人船朝向目標點，通常采用逆距離的方式定義吸引子勢場，即目標點越近，吸引力越強；這樣，無人船會受到目標點的吸引力，朝著目標點移動。斥力勢場（Repulsion Field） ：斥力勢場用來避開障礙物，障礙物被視為斥力源，斥力的大小和距離成反比；當機器人接近障礙物時，斥力增大，使無人船受到斥力的作用而避開障礙物。通過在空間中疊加吸引子勢場和斥力勢場，無人船會受到吸引力和斥力的綜合影響，從而產生一個合適的移動方向。無人船根據當前位置和勢場的梯度信息，選擇一個最優的方向進行移動，實現路徑規劃，如圖2所示。

1.3 傳統人工勢場算法模型

無人船能從港口起始點A航行到目標終點D，是因為無人船航行過程中受到吸引子勢場的作用，吸引子勢場為矢量，大小取決于無人船當前位置與目標終點的距離，方向由無人船指向目標終點。吸引子勢場的表達式如式（1） 所描述。

[Uatt=12kx-xg2+y-yg2] （1）

式中為k為吸引子勢場參數，（x，y） 和（[xg，yg]）分別是為無人船運動當前時刻在坐標軸位置和目標終點位置。

吸引力定義為吸引子勢場的負梯度[3]，如式（2） 所示。

[Fatt=-?Uatt= -kx-xg，-ky-yg] （2）

吸引力的大小為：

[|Fatt|=k x-xg2+y-yg2] （3）

由式（3） 知無人船離目標點距離愈遠，引力越大，反之亦然。

無人船在起始位置A點受到的斥力勢場由表達式（4） 所描述。

[Urep=12m1ρ-1ρo? ，ρ<ρo0? ? ? ? ? ? ? ? ? ? ? ? ?，ρ≥ρo ] （4）

式中，m為斥力勢場系數，[ρ]為無人船當前位置與障礙物之間的距離，[ρo]為障礙物對無人船的斥力勢場影響距離。求取排斥力勢場函數[Urep]的負梯度即可得到排斥力表達式（5） 。

[Frep=-?Urep= mρ2 1ρ-1ρo[?Urep?x，?Urep?y]] （5）

障礙物對無人船的斥力大小函數為：

[|Frep|=mρ2 1ρ-1ρo? ，ρ<ρo0? ? ? ? ? ? ? ? ? ? ? ?，ρ≥ρo] （6）

根據公式（6） 的觀察，當無人船靠近障礙物時，它受到的斥力與無人船與障礙物之間的距離成反比。為了更清晰地表示無人船受到的排斥力，將其分解到xy坐標系上。排斥力與坐標軸的夾角可以通過式（7） 計算。

[θ=cos-1（x-xdx-xo2+y-yo2）] （7）

排斥力在xy坐標軸的分量為：

[|Frep-x|=|Frep|cosθ? ，ρ<ρo0? ? ? ? ? ? ? ? ? ? ? ? ?，ρ≥ρo]

[|Frep-y|=|Frep|sinθ? ，ρ<ρo0? ? ? ? ? ? ? ? ? ? ? ? ?，ρ≥ρo] （8）

無人船在航行過程中收到的總勢場為U=[Urep]+[Uatt]，總合力為F=[Fatt]+[Frep]。

1.4 經典人工勢場法路徑規劃問題

結合1.1節的目標任務可知：在理想情況下，無人船受到目標點的吸引子勢場和障礙物的斥力勢場的聯合作用，會自動識別路徑中的障礙物并避開，不斷接近目標點，實現整個航行。然而，有時在特定情況下，出現了局部極小點的情況，導致無人船在某個位置停止而無法繼續沿規劃路徑前進。在圖3路徑規劃仿真中，當無人船經過航跡點B時，起始位置A、障礙物位置B和目標終點位置D位于同一直線上，此時，目標終點D對無人船的吸引力和障礙物B對無人船的斥力疊加后為零，這將導致無人船的運動陷入局部極小值。這種情況是人工勢場法的一個局限性，稱為局部最小點問題。圖4是在傳統人工勢場路徑規劃下遇見的無人船在目標處震蕩的問題。

2 改進人工勢場算法

針對無人船路徑規劃中的目標不可達和限于目標極小點問題，可以考慮以下解決方法。動態調整勢場參數：通過動態調整勢場函數的參數，可以改變吸引力和斥力的權重，從而優化路徑規劃結果；可以根據實際情況，根據障礙物的距離、目標點的位置等因素，自適應地調整參數，以提高路徑可達性。引入逃逸力機制：在勢場法中引入逃逸力，可以幫助無人船從局部最小點中脫離出來；逃逸力可以根據當前位置和勢場梯度的信息，提供一個額外的推力，使無人船能夠跳出局部最小點并重新搜索更優路徑。逃逸力的大小和方向可以根據具體需要進行調整。

2.1 解決目標點不可達問題

大多數學者對人工勢場的改進主要集中在斥力勢場函數上，其中使用的函數通常是基于無人船與障礙物相對位置的倒數的二次函數。然而，這種函數在實際應用中存在一些問題，因為即使無人船做出輕微的移動，勢場的強度會發生劇烈變化，這對路徑判斷造成了困擾。鑒于此，本文選擇使用指數函數來改進斥力勢場函數，以減緩斥力場強度的變化速度。

同時，為了解決目標不可達的問題，引入了目標點與無人船相對位置的考慮。通過將改進的斥力勢場函數乘以一個因子，使得目標點位置的斥力為零，可以確保無人船朝著目標點的方向移動而不受斥力的干擾。改進后的斥力勢場函數如式（9） 所示[4，9]。

[Urep=12m1ρ-1ρo2 [1-exp（-x-xg2+y-yg2r2）] ，ρ<ρo0，ρ≥ρo] （9）

對式（9）的斥力勢場函數求負梯度即可分解為兩個方向的排斥力[Frep-x]和[Frep-y]，[Frep-x]的方向由障礙物指向無人船，[Frep-y]的方向由無人船指向目標，大小如式（10） 所示。

[[Frep-x=-?xUrep= -m 1ρ-1ρo2x-xgexp（-x-xg2+y-yg2r2]? ]

[+m [1-exp（-x-xg2+y-yg2r2）1ρ-1ρox-xoρ3]]

[Frep-y=-?yUrep= -m 1ρ-1ρo2y-ygexp（-x-xg2+y-yg2r2]]

[+m [1-exp（-x-xg2+y-yg2r2）1ρ-1ρoy-yoρ3]]] （10）

由式（10） 可知：當無人船接近目標點，[x-xg2+y-yg2→0]，可推導出斥力的合力大小[|Frep|→0]。

在這個改進的斥力勢場函數中，當無人船靠近目標點附近的障礙物時，無人船受到的排斥力為零。這意味著無人船不再受到障礙物的排斥力的影響，并且只受到目標點的引力作用，使得無人船能夠在目標點附近自由移動，解決了傳統人工勢場算法中的目標點不可達問題。

2.2 解決局部極小點問題

為了使得無人船能順利到達目標點或者使陷入局部極小值的無人船能逃脫局部極小值點到達目標點，根據無人船與障礙物距離的遠近動態調整斥力函數參數、增加逃逸力。結合無人船與障礙物距離調整勢場力參數，增加逃逸力，使陷入局部極小值點的無人船擺脫陷阱，抵達目標點。

首先判斷無人船是否進入極小值點，無人船移動的連續5個步長可以用作判斷無人船是否陷入局部最小點的依據[5]。如果在這5個連續步長小于[α] *iterStep，[α∈][ 2，4] 時，通過調節[α]值，可較快地檢測無人船是否陷入局部最小。根據無人船與障礙物的距離，調整斥力函數的參數[ρo]和r；當判斷出無人船已經陷入局部最小時，按式（11） 設計逃逸力。

[Frepx（i）=σ*Frep-x（i）*cos（angle_re（i））Frepy（i）=γ*Frep-x（i）*sin（angle_re（i））] （11）

式中：[σ]，[γ]為逃逸力系數，[Frep-x（i）]為當前障礙物指向無人船的斥力函數分量，[angle_re（i）]為障礙物指向無人船向量與X軸之間的夾角，[Frepx（i）]和[Frepy（i）]為逃逸力在坐標軸上的分量。無人船跳出局部極小值之后，撤回逃逸力，無人船在原勢場作用下繼續路徑規劃算法[6，10]。

2.3 算法流程

無人船路徑規劃的算法流程如圖5所示。首先，在無人船路徑規劃的開始階段，需要對無人船的起始點、目標點和障礙物的位置進行初始化，確定它們在坐標系中的位置。其次，在無人船航行的過程中，需要持續計算障礙物對無人船的斥力和目標點對無人船的吸引力。再次，對合力進行計算，由引力、斥力和合力值計算當前無人船的角度，根據步長和當前位置計算下一迭代位置；再次，判斷無人船是否陷入局部最小值狀態。如果無人船無法繼續航行或無法顯著改變其位置，那么可以推斷它可能陷入了局部最小值點，通過調整斥力參數和引入逃逸力，幫助無人船擺脫局部最小值點。如果不是陷入局部最小值，調整參數，駛離復雜障礙物環境；最后繪制無人船從起點到目標點的完整規劃路徑[7]。

3 仿真實驗

實驗假設無人船的航行范圍是一個大小為35m×35m的區域，人們在該區域內隨機布置了多個障礙物，并測得它們的位置坐標。下面是每個障礙物的位置坐標：障礙物1（5，5） ，障礙物2（16，18） ，障礙物3（17，19） ，障礙物4（19，20） ，障礙物5（20，20） ，障礙物6（20，19） ，障礙物7（21，18） ，設無人船的初始位置X 為（0，0） ，目標點的位置Xg為（25，25） 。仿真系統基本參數設計，見表1，用Matlab R2016a進行仿真。

在簡單的障礙物環境中，如圖6所示，當障礙物位置與目標終點臨近時，采用傳統人工勢場算法進行無人船航跡仿真，發現無人船無法到達目標；在Matlab仿真中截取了無人船的部分航跡數據，如圖7所示，發現無人船抵達（ 18.6，17.6） 坐標位置后，即使再行進551次，依然停留在原地，從而判斷無人船已經陷入了局部最小值。

利用引用為[8]的文獻中所提出的算法[8]，在一個簡單的障礙物環境中進行了仿真實驗。根據仿真結果，無人船的航行軌跡如圖8所示，在這個路徑中，無人船沿著障礙物的邊緣移動，并成功跳出了局部最小值點。圖9展示了仿真實驗的Mablab工作窗口數據，從中可以看出該算法經過了644次迭代才到達目標點。

進一步提升無人船的航行環境復雜度，增加了障礙物的數量，并更改了它們的坐標位置。下面是新的障礙物位置坐標：（8，13） ，（9，12） ，（10，14） ，（11，13） ，（11，8） ，（13，9） ，（16，18） ，（17，19） （19，20） ，（20，20） ，（20，19） ，（21，19） ，（21，18） 。根據引用為[8]的文獻中所提出的算法，在仿真實驗中得到了無人船的運動軌跡曲線，如圖10所示。從該圖所示的航行軌跡曲線可以看出，無人船到達凹形區域時，陷入了局部最小值點的困境[11-13]]。

根據本文所提出的改進人工勢場算法，進行了仿真實驗。在無人船向目標點航行的過程中，可以通過判斷無人船與障礙物之間的距離來實現障礙物的避障。當無人船進入障礙物的影響距離時，可以根據與障礙物的實時距離選擇不同的斥力系數，調整無人船受到的斥力大小，避免無人船陷入局部極值點；無人船在復雜航行環境中時，如在凹型障礙物中陷入局部極值點，通過調整斥力勢場系數和增加逃逸力，使無人船逃離凹型障礙物脫離局部極值點[14]。

參照表1中仿真系統的基本參數，當限于局部極值點且無人船與障礙物的距離小于[ρ0]/2時，逃逸力系數σ=1.1，γ=-0.9，調整斥力函數系數r=1.8，[ ρ0]=1.8。根據本文提出改進算法，分別繪制無人船在簡單航行環境中和復雜航行環境中的運行軌跡如圖11和12所示。圖13是復雜航行環境中無人船的移動步數，經過398 步無人船到達目標點。

仿真圖6至圖13，是在相同環境下，采用3種不同算法模擬無人船的路徑規劃。傳統人工勢場算法在本文提供的簡單障礙物環境中陷入局部最小值；文獻[8]改進算法引入距離因子，在簡單障礙物環境中經過644步無人船可以抵達目標，但在復雜障礙物環境中陷入局部最小值；采用本文提出的算法，無人船在兩種障礙物環境中均能抵達目標，且移動的步數相比文獻[8]改進算法的步數大大降低。

4 結束語

針對傳統人工勢場算法在路徑規劃應用中常見的問題，本文提出了一種改進算法，采用指數函數改進斥力函數，并引入無人船與障礙物之間的距離因子改善目標不可達的問題；同時，當無人船陷入局部最小值時，根據無人船與障礙物之間的距離動態調整勢場模型系數，并增加逃逸力以幫助無人船快速跳出局部最小值點，是一種有效的改進方法。通過這種方法，可以使無人船在面對簡單或復雜的障礙物環境時，具備躲避障礙物、逃離局部最小值點并平滑到達目標點的能力。航行步數比參考文獻[8]更加優化，滿足了無人船實時路徑規劃的要求[15]。

參考文獻：

[1] 薛飛.基于無人船的路徑規劃與避障問題研究[D].哈爾濱：哈爾濱工程大學，2017.

[2] 劉傳領.基于勢場法和遺傳算法的機器人路徑規劃技術研究[D].南京：南京理工大學，2012.

[3] 劉琨.基于人工勢場和蟻群算法的無人船路徑規劃研究[D].?？冢汉Ｄ洗髮W，2016.

[4] 欒天宇.無人船自動駕駛系統的設計與實現[D].北京：北京理工大學，2018.

[5] 劉瀛.基于改進勢場與蟻群算法的機器人路徑規劃法[J].計算機仿真，2021，38（11）：355-360.

[6] 張佳尚，陳志華.基于預添加虛擬力的改進人工勢場算法[J].兵器裝備工程學報，2023，44（3）：219-225.

[7] 羅強，王海寶，崔小勁，等.改進人工勢場法自主移動機器人路徑規劃[J].控制工程，2019，26（6）：1091-1098.

[8] CHEN Y Q，LI T X.Collision avoidance of unmanned ships based on artificial potential field[C]//2017 Chinese Automation Congress （CAC）.Jinan，China.IEEE，2017：4437-4440.

[9] YU J B，DENG W，ZHAO Z Y，et al.A hybrid path planning method for an unmanned cruise ship in water quality sampling[J].IEEE Access，2019，7：87127-87140.

[10] LYU H G，YIN Y.Ship’s trajectory planning for collision avoidance at sea based on modified artificial potential field[C]//2017 2nd International Conference on Robotics and Automation Engineering （ICRAE）.Shanghai，China.IEEE，2017：351-357.

[11] 許萬，程兆，朱力，等.一種基于改進人工勢場法的局部路徑規劃算法[J].電子測量技術，2022，45（19）：83-88.

[12] 江明，王飛，葛愿，等.基于改進蟻群算法的移動機器人路徑規劃研究[J].儀器儀表學報，2019，40（2）：113-121.

[13] 陳繼清，譚成志，莫榮現，等.基于人工勢場的A*算法的移動機器人路徑規劃[J].計算機科學，2021，48（11）：327-333.

[14] 劉濤，賈立校，曹翔.動態人工勢場法的無人船避障路徑規劃[J].艦船科學技術，2023，45（5）：89-92.

[15] 余必秀，初秀民，柳晨光，等.基于改進A*算法的無人航道測量船路徑規劃方法[J].武漢大學學報（信息科學版），2019，44（8）：1258-1264.

【通聯編輯：梁書】