高霄鵬,劉冬雨,霍 聰
(海軍工程大學 艦船與海洋學院,湖北 武漢 430030)
隨著計算機技術、通信技術和人工智能技術的發(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
在路線規(guī)劃研究中,一般將規(guī)劃對象視為一個質點,忽略運動學和動力學對規(guī)劃效果的影響,例如百度地圖為用戶規(guī)劃的行走路徑、掃地機器人的路徑規(guī)劃以及游戲中角色的移動路線等。路線規(guī)劃的相關研究相對較早,目前,已有許多經典搜索算法成熟應用于無人艇的路線規(guī)劃中。根據算法特點分為傳統(tǒng)路徑規(guī)劃算法、基于采樣路徑規(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ī)劃研究。
基于采樣路徑規(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ī)劃時間,與單獨使用某一種算法相比,得到的路徑長度更短。
軌跡規(guī)劃是對路線規(guī)劃結果的一種優(yōu)化,規(guī)劃目標是生成易于跟蹤航行的路徑。由于路線規(guī)劃過程得到的路徑是曲折的,對于USV 來說,其運動過程中具有慣性,無法突然轉變航向。因此,路徑曲率連續(xù)問題是軌跡規(guī)劃過程中需要重點解決的一個方面。
常被采用的方法主要有Dubins 算法[26]、樣條曲線法[27]、Clothoid 曲線[28]和費馬螺線[29]等。Wang[30]在無人艇的路徑規(guī)劃中,使用二次B 樣條曲線對路徑點進行平滑處理,優(yōu)化后的路徑更適合USV 的實際航行。劉樂柱等[31]使用Dubins 算法為USV 規(guī)劃一條曲率連續(xù)的路徑,該方法首先根據USV 運動特性計算其轉向能力,然后利用Dubins 曲線與回轉圈的切線拼接得到平滑路徑。
上述曲線擬合的方法需先獲取路徑點,再對點的連線進行優(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ī)劃。
運動規(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ī)劃時反應遲鈍。
無人艇運動規(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ī)劃效果的影響。