高霄鵬，劉冬雨，霍 聰

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

0 引 言

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

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

圖1 無人艇系統(tǒng)構成Fig.1 The composition of USV

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

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

圖2 路線規(guī)劃與運動規(guī)劃Fig.2 Route planning and motion planning

1 路線規(guī)劃

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

1.1 傳統(tǒng)路徑規(guī)劃算法

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

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

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

1.2 基于采樣路徑規(guī)劃算法

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

圖4 PRM 算法Fig.4 PRM algorithm

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

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

2 軌跡優(yōu)化

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

2.1 曲線優(yōu)化方法

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

2.2 動力學約束方法

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

3 運動規(guī)劃

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

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

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

4 結 語

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

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