基于Citespace 的水面無人艇路徑規劃與避障算法研究

周治國，邸順帆

(北京理工大學 集成電路與電子學院, 北京 100081)

0 引 言

路徑規劃與避障一直都是水面無人艇研究的重要內容，水面無人艇需具備的自主能力之一是通過感知模塊與外界未知環境進行交互獲得信息，從而保證水面無人艇能據此進行路徑規劃和局部避障[1]?；趪鴥韧獍l展現狀以及路徑規劃與避障技術的重要性，本文針對水面無人艇路徑規劃與避障領域，運用科學知識圖譜的方式對數據進行挖掘，總結技術發展趨勢、展望未來研究方向。

1 無人艇感知模塊

環境感知是無人艇實現路徑規劃與自主避障的前提。無人艇通過傳感器感知環境信息，為后續識別和決策提供支撐[3]。無人艇的傳感器大體上可以分為：1）用于外部環境感知，包括激光雷達（Lidar）、單目或雙目相機、深度相機、毫米波雷達、紅外等，多用于目標識別和跟蹤，表1 為3 種Velodyne 激光雷達的性能參數對比，表2 為單目相機、雙目相機和深度相機三者的優缺點對比；2）用于自身狀態感知，包括慣性測量單元（IMU）、GPS 等，用于無人艇自身的定位及姿態矯正。

表1 Velodyne 激光雷達性能參數對比Tab.1 Performance parameter comparison of Velodyne Lidar

表2 單目、雙目及深度相機對比Tab.2 Comparison of monocular, binocular and depth cameras

國內外研究者對于感知技術的研究通常集中在外部環境感知方面，如基于可見光成像的目標檢測，基于雙目或單目視覺的目標跟蹤，以及使用激光雷達等測距傳感器的水面障礙物定位。通常單一傳感器不能全面地反映復雜海況，容易受到天氣、距離、自身工作條件等因素的影響[6]，出于提高水面目標跟蹤與定位的精確度、改善實時檢測及跟蹤效果差等目的，現階段環境感知信息的獲取不再局限于單個傳感器的輸入，傳感器融合的技術為無人艇感知技術開辟了新道路。David 等[7]在2017 年提出了一種基于激光雷達和視覺系統融合的海面目標檢測跟蹤定位方法, Mou 等[8]將雙目相機同GPS 和電子羅盤等進行信息融合，得到了海面障礙物的準確位置。在傳感器融合過程中如何克服各個傳感器的缺點，提供實時、準確的環境感知信息仍是研究難點，但毫無疑問，多傳感器信息融合是未來無人艇環境感知的關鍵技術[9]。

2 路徑規劃與避障

無人艇的避碰路徑規劃算法可以分為全局路徑規劃和局部路徑規劃兩類[10]。

2.1 全局路徑規劃

全局路徑規劃是依據整個環境構造環境地圖后在規定區域內進行的，不能處理規劃過程中的突發狀況，規定區域內進行的，不能處理規劃過程中的突發狀況，對實時性要求不高且一般可找到最優解。經典算法有Dijkstra 算法、A*算法、蟻群算法、遺傳算法等。

Dijkstra 算法[11]是Dijkstra 是提出的全局規劃最短路徑算法，該算法雖簡單但占用內存大、計算效率低，僅適用于小范圍內的路徑規劃。A*算法[12]是經典的啟發式路徑規劃算法，通過設置代價函數，尋找兩點之間的最小代價。由于依賴于啟發函數，A*算法計算量巨大，導致規劃路徑的時間較長。蟻群算法[13]和遺傳算法[14]都屬于智能仿生學算法，用于處理復雜環境下的路徑規劃問題。蟻群算法通過迭代模仿蟻群覓食行為尋找最短路徑，具有便于并行和魯棒性強的優點，但設置參數不準確或初期信息素缺少時會出現路徑規劃速度過慢的問題。張丹紅等[15]針對無人艇海上巡邏路徑規劃問題，提出了A*算法與蟻群算法相結合進行最短巡邏路徑優化的方法，效果如圖1 所示。遺傳算法是一種隨機化搜索算法，其實質是一種在解空間中搜索與環境最匹配的自適應方法，通過逐步淘汰掉適應性函數低的解，增加適應性函數高的解，從而獲得最優路徑。遺傳算法具有較高的魯棒性，但其收斂速度較低且控制變量較多，所花費時間要更久。

圖1 A*算法與蟻群算法相結合的路徑優化效果Fig.1 Path optimization effect of A* algorithm combined with ant colony algorithm

2.2 局部避障算法

局部避障即局部路徑規劃是在未知環境下通過傳感器獲取周圍障礙物信息，包括其位置、形狀、尺寸等，使無人艇自主生成安全可行的最優路徑，其經典算法如人工勢場法、動態窗口法、速度障礙法等。

人工勢場法最初由Khatib[16]提出，通過建立勢場解決實時避障問題，原理簡單實時性高，但可能會產生局部最小值的問題。動態窗口法[17]是一種在線避障算法，在窗口不斷滾動中實現優化與反饋，準確度較高且計算量小，但算法對航行器的控制要求較高，穩定性較差。汪流江等[18]提出一種基于A*與動態窗口法的混合路徑規劃算法，在A*算法得到全局路徑生成局部目標點后，隨著局部目標點的不斷更新USV 使用動態窗口法航行至全局目標點，圖2 為該混合路徑規劃算法與單獨采用A*算法的路徑搜索結果對比，可以看到混合路徑規劃對應的路線拐點更少且角度更小。速度障礙法[19]由Fiorini 等提出，通過在無人艇與障礙物間的速度空間內構建一個三角區域，當速度向量落入此三角區內判定二者發生碰撞，之后從非三角區域中找到一個最優的速度矢量，實現最優路徑避障。速度障礙法考慮動態障礙物的運動信息，算法穩定性高且規劃路徑準確度高，但速度較慢。

圖2 混合路徑規劃算法仿真結果Fig.2 Simulation results of hybrid path planning algorithm

2.3 強化學習算法

強化學習（Reinforcement Learning, RL）是機器學習的范式和方法論之一。強化學習的學習機制是智能體通過與環境交互獲得對動作的反饋，以“試錯”的方式進行學習，目標是使智能體獲得最大的獎賞。按照算法的優化機制，強化學習分為基于值函數的方法（Value-based）和基于策略的方法（Policy-based）。前者的代表性算法為深度Q 網絡（Deep Q Network,DQN）及其改進算法，后者的代表算法有策略梯度算法及其各種形式。

2.3.1 Q 學習及其改進算法

最初由WATKINS[20]提出的Q 學習是一種典型的Value-based 方法，該算法引入Q 值表保存每個狀態下對應的動作值，然后通過增量的方式不斷更新，Q 值越大則證明該狀態下采取的策略越好。王程博等[21]建立了一種基于Q 學習的無人駕駛船舶路徑規劃模型，在仿真環境中驗證了該方法可實現在未知環境中的自適應航行。Q 學習算法對環境模型的要求較低且收斂性較好，但在復雜水域環境中會因Q 值表無法存儲大量狀態行為信息而導致維數災難的問題。封佳祥等[22]針對Q 學習算法在多任務約束條件下收斂慢的問題，提出一種基于任務分解獎賞函數的Q 學習算法，通過仿真實驗驗證了采用該算法進行無人艇路徑規劃的可行性，圖3 為多任務約束條件下基于該算法的路徑規劃仿真結果。Sarsa 算法[23]與Q 學習算法類似，決策部分相同，區別在于該算法生成樣本的值函數與網絡更新參數使用的值函數相同，其優點是收斂速度快，缺點是可能無法找到最優策略。Zhang 等[24]提出一種基于Sarsa 強化學習的USV 自適應避障算法，在價值函數設計中將路線偏離角及其趨勢引入到動作獎懲中，最后通過對比實驗驗證了所提算法的有效性。

圖3 多任務約束條件下基于Q 學習算法的無人艇路徑規劃仿真結果Fig.3 Simulation result of USV path planning based on Q-learning algorithm under multi-task constraints

2.3.2 策略梯度算法

策略梯度算法（Policy Gradient）[25]是一種典型的Policy-based 方法，針對最大化回報值的目標建立目標函數，通過不斷調整參數使目標函數梯度上升，從而實現梯度最大化。該類算法要求的參數少且能夠處理連續空間，但在每次梯度更新時并未參考之前的估計值，導致收斂緩慢并存在陷入局部最優的問題。將Value-based 和Policy-based 進行結合，Barto 等[26]研究者提出了執行-評估（Actor-Critic, AC）方法，該方法中Actor 負責通過策略梯度學習策略，Critic 負責值函數估計，二者相互影響，在訓練過程中不斷地多元迭代優化。然而該方法依賴于Critic 的價值判斷，故存在難以收斂的問題。傳統的強化學習算法應用于路徑規劃時對地圖模型的要求較為簡單，但面對大規模的復雜環境時，一方面受更新速度的限制，在處理較大數據量時容易引起維數災難；另一方面泛化能力較差，在面對全新狀態時需要消耗大量時間進行規劃，從而難以達到實時避障的要求。

2.3.3 深度強化學習

深度強化學習（Deep Reinforcement Learning,DRL）已成為新的研究熱點，并被嘗試應用在無人駕駛領域[27]。

DRL 興起之后，研究者們提出了許多對傳統強化學習模型的改進算法：將卷積神經網絡與Q 學習算法相結合的深度Q 網絡（Deep Q-Network, DQN）模型[28]、采用2 套參數將動作選擇和策略評估分離開的深度雙Q 學習(Deep Double Q-Network, DDQN)[29]、基于競爭網絡結構的DQN（ueling DQN）[30]、以及基于AC 架構的深度確定性策略梯度（Deep Deterministic Policy Gradient, DDPG）算法[31]、近端策略優化（Proximal Policy Optimization，PPO）算法[32]等。

隨博文等[33]提出一種基于深度Q 網絡的USV 避障路徑規劃算法，利用深度神經網絡估計Q 函數，有效解決了傳統Q 學習算法在復雜水域環境中易產生維數災難的問題，該算法與A*算法的路徑規劃效果如圖4所示。Xu 等[34]在經典DQN 算法的基礎上進行改進，提出了一種基于深度強化學習的COLREGs 智能避障算法（COLREGs Intelligent Collision Avoidance, CICA），使得無人艇可在國際海上避碰規則下（COLREGs）成功躲避動態障礙物—移動船舶，實驗驗證該算法同傳統局部避障算法相比表現更佳。Meyer 等[35]利用PPO 算法實現USV 在國際海上避碰規則（COLREGs）下遵循期望路徑行駛并避免與沿途船只發生碰撞。

圖4 深度Q 網絡與A*算法在相同仿真環境下的路徑規劃效果對比Fig.4 Comparison of path planning effect between deep Q network and A* algorithm in the same simulation environment

3 結 語

無人艇實現自主航行的關鍵在于能夠通過傳感器采集到的信息進行路徑規劃，同時在沿途遇到危險能夠進行局部避障，最終安全到達目標點。近年來該領域得到了越來越廣泛地關注，應用場景更加豐富，但目前國內外在實現真正無人化作業方面仍有待提升。

感知技術方面，由于無人艇工作在水域環境中，存在光照反射、天氣變化等的影響，其檢測結果會受到較大干擾。傳統的感知算法雖具有理論性強、可靠性高、應用廣泛的特點，但在目標檢測準確率上存在局限性，而深度學習感知算法有著魯棒性強、準確度高的優點，隨著機器學習的不斷發展，將其合理運用將使得無人艇的感知能力得到進一步提升。

路徑規劃與避障方面，大多算法僅限于在二維仿真環境中進行訓練和測試，實用性有待提高。一方面，仿真環境的建模要考慮水流、風浪、光照等環境因素；另一方面，無人艇不應該是簡單的質點，其物理模型在構建時要考慮自身運動的實際情況，如橫向縱向速度、轉動角速度以及來自水流和螺旋槳的外力等；另外，在規劃避障路徑時，由于真實環境中遇到其他船舶時只有雙方均安全航行才能保證避障成功，故雙方應遵循相同的規則，比如海洋環境中考慮國際海上碰避規則，國內河流環境考慮中國內河避碰規則等。只有考慮到這些實際環境因素，才能產生實際可行的避障路徑，提高避障于路徑規劃算法的適應性。