水面無人艇運動規劃研究綜述

高霄鵬，劉冬雨，霍 聰

(海軍工程大學 艦船與海洋學院，湖北 武漢 430030)

0 引 言

隨著計算機技術、通信技術和人工智能技術的發展與應用，越來越多的研究所、院校以及企業等機構開始研究并投入使用無人運載器[1]。無人運載器主要包括無人車、無人機、水面無人艇以及無人潛航器等[2]。由于能夠高效率地完成危險艱巨的任務，無人運載器有著廣泛的應用領域。例如，無人車（UGV）常被用于地震救援、考古研究、智能農業以及物流配送等領域[3]；無人機（UAV）則常被用于農業、航空拍攝、災難救援、電力巡檢以及軍事打擊等領域[4]。近年來，海洋資源的進一步開發和海上作戰的需求促進了水面無人艇（USV）和無人潛航器（UUV）等海上無人裝備的研發進度，同時也開拓了海上無人裝備的應用領域，例如，海洋科考探測、海洋環境檢測、海事搜救、水下地形勘測、海上牧場、海上運輸補給、氣象 探 測 以 及 軍 事 作 戰 等 領 域[5-8]。21 世 紀，我 國 提 倡共同建設“海上絲綢之路”，并多次強調海洋強國建設在經濟發展和中國特色社會主義事業建設中的重要作用。因此，作為海上無人裝備中的一種，USV 在未來海洋建設中必將發揮重要作用。

USV 作為一個復雜系統，其中包含眾多子系統，如感知系統、載荷系統、控制系統、動力系統以及舾裝系統等[9]，如圖1 所示。各子系統相互配合，使USV 能夠在復雜的海洋環境中實現自主航行。對于無人系統而言，自主航行能力是衡量無人艇智能化水平高低的一項重要指標。“自主”意味著USV 在不依靠任何人工控制手段的情況下，能夠根據航行規則順利完成任務。在整個過程中，根據航行環境與任務目標規劃一條安全可靠的路徑是USV 必須具備的一項功能模塊，即路徑規劃模塊。

圖1 無人艇系統構成Fig.1 The composition of USV

路徑規劃起源于早期的陸地機器人[10]，給路徑規劃模塊輸入起始位置、目標位置以及障礙物信息，為機器人輸出一條可行路徑。路徑規劃是一個優化問題，最明顯的優化標準是距離[11]，即為機器人找到一條避開所有障礙物到達終點的最短路徑。傳統路徑規劃方法是將機器人視為一個質點，這對于UGV 和UAV 或許可行。對于UGV 而言，由于地理環境相對固定，且其具備緊急制動能力，所以其運動狀態可控；UAV 在航行中會受到風等環境因素的干擾，但空中不存在復雜障礙物，在遇到緊急情況時，UAV 可懸停在空中。但對于USV 而言，傳統路徑規劃方法存在一定不足。一方面，由于水域環境復雜，USV 會受到風、浪、流、水粘性力和慣性力等外界因素的干擾，即使USV 不做任何操作，也無法穩定維持在某一位置上。另一方面，大多數USV 是欠驅動的，無法在有限的空間范圍內實現大角度轉向操縱。因此，USV 的路徑規劃過程應考慮其實時的運動狀態以及操縱能力邊界。這便將路徑規劃問題由簡單的路線規劃上升為運動規劃。運動規劃過程考慮了USV 的所有動力學和運動學約束[12]，所以規劃的路徑符合USV 的航行特點，更有利于航行控制。隨著無人技術的發展，無人艇路徑規劃研究逐漸朝向精細化的運動規劃發展。

路徑規劃在某空間背景下，為USV 規劃一條連續并符合規劃要求的路徑。根據發展階段，文獻將路徑規劃問題分為路線規劃，軌跡規劃和運動規劃[13]3 類。路線規劃是路徑規劃的初級階段，該階段將USV 視為一個質點，不考慮任何運動學和動力學特性，通常適用于大尺度區域的路徑規劃[14]，例如，USV 從大連港到上海港的路徑規劃，該路徑無需考慮形狀、速度等運動細節，如圖2（a）所示。軌跡規劃是路線規劃的優化階段，對路線規劃的結果進行優化，主要優化指標包括航向角、曲率和速度等，通常適用于中等尺度區域的路徑規劃[15]，例如，USV到達港口附近時，需考慮如何進入內部端口，此時需考慮一些運動學約束，如USV 尺寸、航行速度以及回轉半徑等。運動規劃是路徑規劃的高級階段，除了考慮運動學特性外，還需考慮動力學特性，例如USV在六自由度上受到的力和力矩等，適用于小尺度區域內的精細路徑規劃[16]，例如，USV 在梳形路線巡航時，需知道如何完成直角轉彎，如圖2（b）所示。在此階段，將USV 視為剛體，充分考慮運動過程中受到的所有約束以及實時運動狀態變化，期望的規劃結果是找到一條真實可控的路徑。因此，以路徑規劃的3 個發展階段為脈絡，詳細介紹了各階段的規劃方法以及研究與應用現狀。

圖2 路線規劃與運動規劃Fig.2 Route planning and motion planning

1 路線規劃

在路線規劃研究中，一般將規劃對象視為一個質點，忽略運動學和動力學對規劃效果的影響，例如百度地圖為用戶規劃的行走路徑、掃地機器人的路徑規劃以及游戲中角色的移動路線等。路線規劃的相關研究相對較早，目前，已有許多經典搜索算法成熟應用于無人艇的路線規劃中。根據算法特點分為傳統路徑規劃算法、基于采樣路徑規劃算法和智能仿生算法等。

1.1 傳統路徑規劃算法

Dijkstra 算法、A*算法、人工勢場法等都屬于傳統路徑規劃算法類型。其中最為經典的是Dijkstra 算法，該算法是Edsger Wybe Dijkstra 在1956 年提出的一種用來尋找最短路徑的算法，主體思想是貪心思想[17]，即以起始點為中心向外層層擴展，每次擴展選擇移動代價最小的節點作為下一節點，直到到達終點，搜索過程如圖3（a）所示。Dijkstra 算法找到的路徑一定是最優路徑，但該方法擴展節點多，搜索效率低，導致在實際應用中存在諸多不足。1968 年，斯坦福研究院的Peter Hart 基于Dijkstra 算法提出了A*算法[18]，在路徑代價函數中增加了啟發項來使搜索方向逐步靠近目標點，A*算法的規劃效果如圖3（b）所示。A*算法不僅繼承了Dijkstra 算法的優點，還減少了擴展節點的數量，節約了搜索空間，提高了搜索效率。

圖3 Dijkstra 算法和A*算法Fig.3 Dijkstra algorithm and A* algorithm

人工勢場法是由Khatib 于1985 年提出的一種基于虛擬力場的路徑規劃算法，該算法的基本思想是當機器人在環境中運動時，將環境設置為人造勢場，目標點對機器人產生引力，障礙物對機器人產生斥力，引力和斥力的合力控制著機器人的運動方向[19]。該算法可以產生一條平滑安全的路徑，但在距離目標點較遠時，引力遠大于斥力，可能導致機器人與障礙物發生碰撞。因此，人工勢場法常被用于局部路徑規劃研究。

1.2 基于采樣路徑規劃算法

基于采樣路徑規劃算法更具靈活性，即使是同一規劃任務，規劃結果也可能不相同。基于采樣路徑規劃算法的2 種典型算法是隨機路線圖算法（PRM）和快速搜索隨機樹算法（RRT）。PRM 算法的主要思想是基于圖搜索的算法，通過在規劃空間中生成隨機的狀態點來判斷空間的可行區域位置，然后連接狀態點找到可行路徑[20]，過程如圖4 所示。該算法適用于高維空間，常被用于無人機領域，這是因為無人機的路線規劃是在三維空間進行的，PRM 算法不僅可以快速高效地搜索最優路徑，還可以解決無人機多任務分配問題。RRT 算法通過對狀態空間中的采樣點進行碰撞檢測，避免了對空間的建模，有效解決高維空間和復雜約束的路徑規劃問題[21]。該算法以初始點作為根節點，通過隨機采樣增加葉子節點的方式，生成一個隨機擴展樹，當目標點位于隨機擴展樹上時，停止增長，如圖5（a）所示。但是，RRT 算法的規劃結果往往不是最優的，針對這一問題，提出RRT*算法，縮短了路徑長度。該算法的規劃結果如圖5（b）所示。

圖4 PRM 算法Fig.4 PRM algorithm

圖5 RRT 算法和RRT*算法Fig.5 PRT algorithm and RRT* algorithm

Song 等[22]針對傳統A*算法生成的路徑折角多并存在多余節點的弊端，提出一種改進A*算法，其改進的核心思想是通過去除冗余節點使路徑趨于平滑。Li 等[23]基于柵格法建立三維環境模型，使用D i j s t k t r a和A*算法實現三維路徑搜索，該方法得到了較短的搜索路徑，更具高效性和實時性，但是該方法搜索過程計算量大。為克服這個缺陷，又設計一種多方向A*算法，通過減少搜索點來獲取更優路徑[24]。張玉奎[25]使用遺傳算法為USV 規劃全局路徑，進而使用人工勢場法進行局部路徑規劃，2 種方法的結合縮短了規劃時間，與單獨使用某一種算法相比，得到的路徑長度更短。

2 軌跡優化

軌跡規劃是對路線規劃結果的一種優化，規劃目標是生成易于跟蹤航行的路徑。由于路線規劃過程得到的路徑是曲折的，對于USV 來說，其運動過程中具有慣性，無法突然轉變航向。因此，路徑曲率連續問題是軌跡規劃過程中需要重點解決的一個方面。

2.1 曲線優化方法

常被采用的方法主要有Dubins 算法[26]、樣條曲線法[27]、Clothoid 曲線[28]和費馬螺線[29]等。Wang[30]在無人艇的路徑規劃中，使用二次B 樣條曲線對路徑點進行平滑處理，優化后的路徑更適合USV 的實際航行。劉樂柱等[31]使用Dubins 算法為USV 規劃一條曲率連續的路徑，該方法首先根據USV 運動特性計算其轉向能力，然后利用Dubins 曲線與回轉圈的切線拼接得到平滑路徑。

2.2 動力學約束方法

上述曲線擬合的方法需先獲取路徑點，再對點的連線進行優化。雖然滿足了曲率的要求，但是對于USV 來說，還有一種效果更好的改進方法：即在路徑規劃算法中加入運動學的約束。Szczerba[32]等提出稀疏A*算法，使用最大轉彎角度和最大路徑長度作為約束條件，縮短了搜索時間，同時避免了路徑中大轉彎角度的出現。Kim[33]在二維路徑規劃算法的基礎上引入曲率的約束，考慮動力學約束提出一個新的代價函數，雖然得到了更短的路徑，但是改進之后還是包含較多的折線段，也未對路徑進行平滑處理，所以得到的路徑效果有待優化。Hanguen[34]基于傳統A*算法，在搜索過程中考慮航向角和艏搖角速度的影響，實驗表明，該算法在路徑跟蹤時間上優于三維A*算法。Lee[35]考慮了航向角的影響，根據欠驅動船舶的運動特性，將搜索子節點根據無人艇的實時航向信息變為3 個子節點，增加了搜索效率，同時刪除了無人艇不能到達的節點。將船舶阻力和水深影響引入代價函數中，使無人艇航行過程的能耗降低。最后根據相鄰路徑點之間的可見性刪除不必要路徑點，同時考慮折線之間角度的大小，使算法效率提高。Wang[36]提出一種基于動態約束的全局-局部混合路徑規劃方案，通過全局路徑規劃算法生成相當稀疏的路徑點，從而得到全局最優路徑，通過控制縱向、橫向速度和加速度，實現局部避碰。航行區域的水深影響著無人艇的水動力性能，水深不足將會引起擱淺等危險狀況，Liu[37]通過分析無人艇的水動力模型，提出一種水深風險等級A*算法，在滿足最短路徑的同時考慮水深不足的危害，保證航行安全。傳統A*算法在基于距離的代價函數作用下，導致生成的路徑與障礙物距離較近，這不利于無人艇在具有復雜障礙物的水域上安全航行，Pc[38]綜合考慮碰撞風險和路徑與障礙物之間的距離，提出新的代價函數。根據船舶自身最大速度的約束計算障礙物碰撞風險，實驗表明，相比于傳統A*算法，該方法生成的路徑安全性更高，更適合限制水域的路徑規劃。

3 運動規劃

運動規劃是路徑規劃的最終階段，該過程求解的是無人艇具體要如何操作才能高效完成路徑規劃任務。因此，在運動規劃階段應綜合考慮無人艇所有的運動學約束。這些約束可總結為軌跡約束、尺度約束、首向角約束。軌跡約束是指無人艇的操縱性能對運動規劃過程產生的約束，即運動規劃過程得到的軌跡必須滿足曲率連續且符合無人艇最小回轉半徑的要求。根據無人艇的水動力性能可知，無人艇航行過程中的運動軌跡受到航速和舵角的影響：在一定航速下，轉舵角度越大，回轉圈越小；舵角不變時，航速越大，回轉圈越小。如果想要無人艇始終穩定的按照規劃的路徑航行，就須考慮無人艇的實際操縱能力。

在運動規劃研究中，要求無人艇能夠精準識別自身運動狀態，包括所處位置、速度以及首向角等。無人艇的首向角在一定程度上影響著其受到外界環境的干擾程度，同時也會影響跟蹤期望路徑的能力。由于大多數無人艇都是高度欠驅動型船舶，其運動軌跡受到自身操縱性能的約束，因此，無人艇幾乎不可能在有限的空間內完成大角度轉向。運動規劃需全面考慮USV 的動力學和運動學約束，該方法可生成更加符合無人艇操縱性的全局路徑。運動規劃的研究是從無人車開始的，傳統方法的一般步驟為：首先利用傳統的路徑規劃方法，規劃一條從起點到終點的無碰路徑；然后，基于路徑設計一個包含運動學和動力學約束的控制器，以驅動機器人安全快速地到達目標[39]。目前，流行方法是利用無人艇的操縱運動數學模型改善傳統算法，Na[40]、Mingbo[41]、Jinze[42]等將無人艇的非完整約束與快速探索隨機樹(RRT)法相結合，RRT 算法的狀態轉換可通過運動學模型改進，新節點的生成可通過動力學方程施加約束。

Lu[43]采用概率地圖法，并根據無人艇操縱性能約束進行改進，對操舵響應非線性模型進行線性化處理，考慮舵角飽和約束限制。Gu[44]根據水面無人艇的運動特性建立無人艇的運動單元庫，解決了無人艇在限制水域中的運動規劃問題。該方法同時滿足無人艇的狀態約束，機動特性約束和水深度約束。每個父節點擁有16 個子節點，搜索精度更高，但是，計算量龐大，無人艇的運動狀態不連續。Han[45]提出一種預測軌跡的搜索算法，將由操縱模型生成的軌跡分解為柵格地圖上的一系列的點，通過A*算法找到一條可行路徑，在代價函數的啟發項中引入了最大速度的影響，生成的軌跡可通過無人艇自身的操縱性能精準跟蹤。但是，算法迭代次數多，更適用于短距離規劃或離線規劃。Du[46- 47]基于柵格地圖，根據無人艇的運動數學模型來確定無人艇在不同舵角下的運動軌跡，建立軌跡單元；將由無人艇運動數學模型生成的軌跡作為路徑規劃的動態約束，在A*算法的代價函數中綜合考慮了距離和轉向的代價，可直接生成一條平滑的路徑，但是該軌跡單元的柵格大小是固定的，限制了其應用情景。Willners[48]在水面無人艇追蹤水下潛航器的應用背景下，根據無人艇的運動學模型，確定船舶的可行空間，可行空間有若干個分支組成，每個分支又離散成若干點作為分支的之間狀態進行碰撞檢測，這種搜索方式的狀態連續，但是計算量龐大，實時路徑規劃時反應遲鈍。

4 結 語

無人艇運動規劃研究起步較晚，多數運動規劃方法是基于傳統路線規劃算法，結合USV 的動力學模型或優化曲線到達最終規劃目標。近幾年國內外學者萌生了新的研究思路：將USV 的操縱性數學模型與柵格狀態相結合，即將USV 的運動狀態離散到柵格中，然后通過搜索算法選擇并連接狀態柵格，得到最終路徑，這便演化為圖搜索問題。A*算法是一種常用的圖形遍歷法，其較好的性能和準確度，對環境反映迅速，搜索效率高。在合適的代價函數的作用下，其找到的路徑為最優路徑，且A*算法與柵格模型結合的搜索效果較優，適合用于運動規劃研究。

水面無人艇的運動過程復雜，路線規劃和軌跡規劃得到的路徑并不利于航行控制模塊對軌跡進行精準跟蹤。針對這一突出問題，設計基于無人艇操縱性數學模型的運動規劃方法是一種趨勢：基于USV 操縱性數學模型，在搜索過程中考慮了USV 運動時產生的所有約束，改變搜索空間的構成；由于搜索空間的改變，導致A*算法中的避障方式無法適用于運動規劃，因此，需要設定2 種避障規則：基礎性避障和預測性避障；對代價函數進行改進，加入航向角改變代價，并將距離代價轉換為相應的時間代價，更能反映實際航行代價。為了使規劃的路徑更加符合無人艇的操縱運動特性，使用無人艇的操縱運動模型進行軌跡預測，實現對路徑點進行平滑處理，使平滑路徑的運動狀態連續，更利于無人艇控制系統的跟蹤。 另外，針對不同尺度的地圖模型和不同的任務背景，應分析柵格尺度對運動規劃效果的影響。