周治國,邸順帆
(北京理工大學(xué) 集成電路與電子學(xué)院, 北京 100081)
路徑規(guī)劃與避障一直都是水面無人艇研究的重要內(nèi)容,水面無人艇需具備的自主能力之一是通過感知模塊與外界未知環(huán)境進(jìn)行交互獲得信息,從而保證水面無人艇能據(jù)此進(jìn)行路徑規(guī)劃和局部避障[1]。基于國內(nèi)外發(fā)展現(xiàn)狀以及路徑規(guī)劃與避障技術(shù)的重要性,本文針對水面無人艇路徑規(guī)劃與避障領(lǐng)域,運(yùn)用科學(xué)知識圖譜的方式對數(shù)據(jù)進(jìn)行挖掘,總結(jié)技術(shù)發(fā)展趨勢、展望未來研究方向。
環(huán)境感知是無人艇實(shí)現(xiàn)路徑規(guī)劃與自主避障的前提。無人艇通過傳感器感知環(huán)境信息,為后續(xù)識別和決策提供支撐[3]。無人艇的傳感器大體上可以分為:1)用于外部環(huán)境感知,包括激光雷達(dá)(Lidar)、單目或雙目相機(jī)、深度相機(jī)、毫米波雷達(dá)、紅外等,多用于目標(biāo)識別和跟蹤,表1 為3 種Velodyne 激光雷達(dá)的性能參數(shù)對比,表2 為單目相機(jī)、雙目相機(jī)和深度相機(jī)三者的優(yōu)缺點(diǎn)對比;2)用于自身狀態(tài)感知,包括慣性測量單元(IMU)、GPS 等,用于無人艇自身的定位及姿態(tài)矯正。
表1 Velodyne 激光雷達(dá)性能參數(shù)對比Tab.1 Performance parameter comparison of Velodyne Lidar
表2 單目、雙目及深度相機(jī)對比Tab.2 Comparison of monocular, binocular and depth cameras
國內(nèi)外研究者對于感知技術(shù)的研究通常集中在外部環(huán)境感知方面,如基于可見光成像的目標(biāo)檢測,基于雙目或單目視覺的目標(biāo)跟蹤,以及使用激光雷達(dá)等測距傳感器的水面障礙物定位。通常單一傳感器不能全面地反映復(fù)雜海況,容易受到天氣、距離、自身工作條件等因素的影響[6],出于提高水面目標(biāo)跟蹤與定位的精確度、改善實(shí)時(shí)檢測及跟蹤效果差等目的,現(xiàn)階段環(huán)境感知信息的獲取不再局限于單個(gè)傳感器的輸入,傳感器融合的技術(shù)為無人艇感知技術(shù)開辟了新道路。David 等[7]在2017 年提出了一種基于激光雷達(dá)和視覺系統(tǒng)融合的海面目標(biāo)檢測跟蹤定位方法, Mou 等[8]將雙目相機(jī)同GPS 和電子羅盤等進(jìn)行信息融合,得到了海面障礙物的準(zhǔn)確位置。在傳感器融合過程中如何克服各個(gè)傳感器的缺點(diǎn),提供實(shí)時(shí)、準(zhǔn)確的環(huán)境感知信息仍是研究難點(diǎn),但毫無疑問,多傳感器信息融合是未來無人艇環(huán)境感知的關(guān)鍵技術(shù)[9]。
無人艇的避碰路徑規(guī)劃算法可以分為全局路徑規(guī)劃和局部路徑規(guī)劃兩類[10]。
全局路徑規(guī)劃是依據(jù)整個(gè)環(huán)境構(gòu)造環(huán)境地圖后在規(guī)定區(qū)域內(nèi)進(jìn)行的,不能處理規(guī)劃過程中的突發(fā)狀況,規(guī)定區(qū)域內(nèi)進(jìn)行的,不能處理規(guī)劃過程中的突發(fā)狀況,對實(shí)時(shí)性要求不高且一般可找到最優(yōu)解。經(jīng)典算法有Dijkstra 算法、A*算法、蟻群算法、遺傳算法等。
Dijkstra 算法[11]是Dijkstra 是提出的全局規(guī)劃最短路徑算法,該算法雖簡單但占用內(nèi)存大、計(jì)算效率低,僅適用于小范圍內(nèi)的路徑規(guī)劃。A*算法[12]是經(jīng)典的啟發(fā)式路徑規(guī)劃算法,通過設(shè)置代價(jià)函數(shù),尋找兩點(diǎn)之間的最小代價(jià)。由于依賴于啟發(fā)函數(shù),A*算法計(jì)算量巨大,導(dǎo)致規(guī)劃路徑的時(shí)間較長。蟻群算法[13]和遺傳算法[14]都屬于智能仿生學(xué)算法,用于處理復(fù)雜環(huán)境下的路徑規(guī)劃問題。蟻群算法通過迭代模仿蟻群覓食行為尋找最短路徑,具有便于并行和魯棒性強(qiáng)的優(yōu)點(diǎn),但設(shè)置參數(shù)不準(zhǔn)確或初期信息素缺少時(shí)會出現(xiàn)路徑規(guī)劃速度過慢的問題。張丹紅等[15]針對無人艇海上巡邏路徑規(guī)劃問題,提出了A*算法與蟻群算法相結(jié)合進(jìn)行最短巡邏路徑優(yōu)化的方法,效果如圖1 所示。遺傳算法是一種隨機(jī)化搜索算法,其實(shí)質(zhì)是一種在解空間中搜索與環(huán)境最匹配的自適應(yīng)方法,通過逐步淘汰掉適應(yīng)性函數(shù)低的解,增加適應(yīng)性函數(shù)高的解,從而獲得最優(yōu)路徑。遺傳算法具有較高的魯棒性,但其收斂速度較低且控制變量較多,所花費(fèi)時(shí)間要更久。
圖1 A*算法與蟻群算法相結(jié)合的路徑優(yōu)化效果Fig.1 Path optimization effect of A* algorithm combined with ant colony algorithm
局部避障即局部路徑規(guī)劃是在未知環(huán)境下通過傳感器獲取周圍障礙物信息,包括其位置、形狀、尺寸等,使無人艇自主生成安全可行的最優(yōu)路徑,其經(jīng)典算法如人工勢場法、動(dòng)態(tài)窗口法、速度障礙法等。
人工勢場法最初由Khatib[16]提出,通過建立勢場解決實(shí)時(shí)避障問題,原理簡單實(shí)時(shí)性高,但可能會產(chǎn)生局部最小值的問題。動(dòng)態(tài)窗口法[17]是一種在線避障算法,在窗口不斷滾動(dòng)中實(shí)現(xiàn)優(yōu)化與反饋,準(zhǔn)確度較高且計(jì)算量小,但算法對航行器的控制要求較高,穩(wěn)定性較差。汪流江等[18]提出一種基于A*與動(dòng)態(tài)窗口法的混合路徑規(guī)劃算法,在A*算法得到全局路徑生成局部目標(biāo)點(diǎn)后,隨著局部目標(biāo)點(diǎn)的不斷更新USV 使用動(dòng)態(tài)窗口法航行至全局目標(biāo)點(diǎn),圖2 為該混合路徑規(guī)劃算法與單獨(dú)采用A*算法的路徑搜索結(jié)果對比,可以看到混合路徑規(guī)劃對應(yīng)的路線拐點(diǎn)更少且角度更小。速度障礙法[19]由Fiorini 等提出,通過在無人艇與障礙物間的速度空間內(nèi)構(gòu)建一個(gè)三角區(qū)域,當(dāng)速度向量落入此三角區(qū)內(nèi)判定二者發(fā)生碰撞,之后從非三角區(qū)域中找到一個(gè)最優(yōu)的速度矢量,實(shí)現(xiàn)最優(yōu)路徑避障。速度障礙法考慮動(dòng)態(tài)障礙物的運(yùn)動(dòng)信息,算法穩(wěn)定性高且規(guī)劃路徑準(zhǔn)確度高,但速度較慢。
圖2 混合路徑規(guī)劃算法仿真結(jié)果Fig.2 Simulation results of hybrid path planning algorithm
強(qiáng)化學(xué)習(xí)(Reinforcement Learning, RL)是機(jī)器學(xué)習(xí)的范式和方法論之一。強(qiáng)化學(xué)習(xí)的學(xué)習(xí)機(jī)制是智能體通過與環(huán)境交互獲得對動(dòng)作的反饋,以“試錯(cuò)”的方式進(jìn)行學(xué)習(xí),目標(biāo)是使智能體獲得最大的獎(jiǎng)賞。按照算法的優(yōu)化機(jī)制,強(qiáng)化學(xué)習(xí)分為基于值函數(shù)的方法(Value-based)和基于策略的方法(Policy-based)。前者的代表性算法為深度Q 網(wǎng)絡(luò)(Deep Q Network,DQN)及其改進(jìn)算法,后者的代表算法有策略梯度算法及其各種形式。
2.3.1 Q 學(xué)習(xí)及其改進(jìn)算法
最初由WATKINS[20]提出的Q 學(xué)習(xí)是一種典型的Value-based 方法,該算法引入Q 值表保存每個(gè)狀態(tài)下對應(yīng)的動(dòng)作值,然后通過增量的方式不斷更新,Q 值越大則證明該狀態(tài)下采取的策略越好。王程博等[21]建立了一種基于Q 學(xué)習(xí)的無人駕駛船舶路徑規(guī)劃模型,在仿真環(huán)境中驗(yàn)證了該方法可實(shí)現(xiàn)在未知環(huán)境中的自適應(yīng)航行。Q 學(xué)習(xí)算法對環(huán)境模型的要求較低且收斂性較好,但在復(fù)雜水域環(huán)境中會因Q 值表無法存儲大量狀態(tài)行為信息而導(dǎo)致維數(shù)災(zāi)難的問題。封佳祥等[22]針對Q 學(xué)習(xí)算法在多任務(wù)約束條件下收斂慢的問題,提出一種基于任務(wù)分解獎(jiǎng)賞函數(shù)的Q 學(xué)習(xí)算法,通過仿真實(shí)驗(yàn)驗(yàn)證了采用該算法進(jìn)行無人艇路徑規(guī)劃的可行性,圖3 為多任務(wù)約束條件下基于該算法的路徑規(guī)劃仿真結(jié)果。Sarsa 算法[23]與Q 學(xué)習(xí)算法類似,決策部分相同,區(qū)別在于該算法生成樣本的值函數(shù)與網(wǎng)絡(luò)更新參數(shù)使用的值函數(shù)相同,其優(yōu)點(diǎn)是收斂速度快,缺點(diǎn)是可能無法找到最優(yōu)策略。Zhang 等[24]提出一種基于Sarsa 強(qiáng)化學(xué)習(xí)的USV 自適應(yīng)避障算法,在價(jià)值函數(shù)設(shè)計(jì)中將路線偏離角及其趨勢引入到動(dòng)作獎(jiǎng)懲中,最后通過對比實(shí)驗(yàn)驗(yàn)證了所提算法的有效性。
圖3 多任務(wù)約束條件下基于Q 學(xué)習(xí)算法的無人艇路徑規(guī)劃仿真結(jié)果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 方法,針對最大化回報(bào)值的目標(biāo)建立目標(biāo)函數(shù),通過不斷調(diào)整參數(shù)使目標(biāo)函數(shù)梯度上升,從而實(shí)現(xiàn)梯度最大化。該類算法要求的參數(shù)少且能夠處理連續(xù)空間,但在每次梯度更新時(shí)并未參考之前的估計(jì)值,導(dǎo)致收斂緩慢并存在陷入局部最優(yōu)的問題。將Value-based 和Policy-based 進(jìn)行結(jié)合,Barto 等[26]研究者提出了執(zhí)行-評估(Actor-Critic, AC)方法,該方法中Actor 負(fù)責(zé)通過策略梯度學(xué)習(xí)策略,Critic 負(fù)責(zé)值函數(shù)估計(jì),二者相互影響,在訓(xùn)練過程中不斷地多元迭代優(yōu)化。然而該方法依賴于Critic 的價(jià)值判斷,故存在難以收斂的問題。傳統(tǒng)的強(qiáng)化學(xué)習(xí)算法應(yīng)用于路徑規(guī)劃時(shí)對地圖模型的要求較為簡單,但面對大規(guī)模的復(fù)雜環(huán)境時(shí),一方面受更新速度的限制,在處理較大數(shù)據(jù)量時(shí)容易引起維數(shù)災(zāi)難;另一方面泛化能力較差,在面對全新狀態(tài)時(shí)需要消耗大量時(shí)間進(jìn)行規(guī)劃,從而難以達(dá)到實(shí)時(shí)避障的要求。
2.3.3 深度強(qiáng)化學(xué)習(xí)
深度強(qiáng)化學(xué)習(xí)(Deep Reinforcement Learning,DRL)已成為新的研究熱點(diǎn),并被嘗試應(yīng)用在無人駕駛領(lǐng)域[27]。
DRL 興起之后,研究者們提出了許多對傳統(tǒng)強(qiáng)化學(xué)習(xí)模型的改進(jìn)算法:將卷積神經(jīng)網(wǎng)絡(luò)與Q 學(xué)習(xí)算法相結(jié)合的深度Q 網(wǎng)絡(luò)(Deep Q-Network, DQN)模型[28]、采用2 套參數(shù)將動(dòng)作選擇和策略評估分離開的深度雙Q 學(xué)習(xí)(Deep Double Q-Network, DDQN)[29]、基于競爭網(wǎng)絡(luò)結(jié)構(gòu)的DQN(ueling DQN)[30]、以及基于AC 架構(gòu)的深度確定性策略梯度(Deep Deterministic Policy Gradient, DDPG)算法[31]、近端策略優(yōu)化(Proximal Policy Optimization,PPO)算法[32]等。
隨博文等[33]提出一種基于深度Q 網(wǎng)絡(luò)的USV 避障路徑規(guī)劃算法,利用深度神經(jīng)網(wǎng)絡(luò)估計(jì)Q 函數(shù),有效解決了傳統(tǒng)Q 學(xué)習(xí)算法在復(fù)雜水域環(huán)境中易產(chǎn)生維數(shù)災(zāi)難的問題,該算法與A*算法的路徑規(guī)劃效果如圖4所示。Xu 等[34]在經(jīng)典DQN 算法的基礎(chǔ)上進(jìn)行改進(jìn),提出了一種基于深度強(qiáng)化學(xué)習(xí)的COLREGs 智能避障算法(COLREGs Intelligent Collision Avoidance, CICA),使得無人艇可在國際海上避碰規(guī)則下(COLREGs)成功躲避動(dòng)態(tài)障礙物—移動(dòng)船舶,實(shí)驗(yàn)驗(yàn)證該算法同傳統(tǒng)局部避障算法相比表現(xiàn)更佳。Meyer 等[35]利用PPO 算法實(shí)現(xiàn)USV 在國際海上避碰規(guī)則(COLREGs)下遵循期望路徑行駛并避免與沿途船只發(fā)生碰撞。
圖4 深度Q 網(wǎng)絡(luò)與A*算法在相同仿真環(huán)境下的路徑規(guī)劃效果對比Fig.4 Comparison of path planning effect between deep Q network and A* algorithm in the same simulation environment
無人艇實(shí)現(xiàn)自主航行的關(guān)鍵在于能夠通過傳感器采集到的信息進(jìn)行路徑規(guī)劃,同時(shí)在沿途遇到危險(xiǎn)能夠進(jìn)行局部避障,最終安全到達(dá)目標(biāo)點(diǎn)。近年來該領(lǐng)域得到了越來越廣泛地關(guān)注,應(yīng)用場景更加豐富,但目前國內(nèi)外在實(shí)現(xiàn)真正無人化作業(yè)方面仍有待提升。
感知技術(shù)方面,由于無人艇工作在水域環(huán)境中,存在光照反射、天氣變化等的影響,其檢測結(jié)果會受到較大干擾。傳統(tǒng)的感知算法雖具有理論性強(qiáng)、可靠性高、應(yīng)用廣泛的特點(diǎn),但在目標(biāo)檢測準(zhǔn)確率上存在局限性,而深度學(xué)習(xí)感知算法有著魯棒性強(qiáng)、準(zhǔn)確度高的優(yōu)點(diǎn),隨著機(jī)器學(xué)習(xí)的不斷發(fā)展,將其合理運(yùn)用將使得無人艇的感知能力得到進(jìn)一步提升。
路徑規(guī)劃與避障方面,大多算法僅限于在二維仿真環(huán)境中進(jìn)行訓(xùn)練和測試,實(shí)用性有待提高。一方面,仿真環(huán)境的建模要考慮水流、風(fēng)浪、光照等環(huán)境因素;另一方面,無人艇不應(yīng)該是簡單的質(zhì)點(diǎn),其物理模型在構(gòu)建時(shí)要考慮自身運(yùn)動(dòng)的實(shí)際情況,如橫向縱向速度、轉(zhuǎn)動(dòng)角速度以及來自水流和螺旋槳的外力等;另外,在規(guī)劃避障路徑時(shí),由于真實(shí)環(huán)境中遇到其他船舶時(shí)只有雙方均安全航行才能保證避障成功,故雙方應(yīng)遵循相同的規(guī)則,比如海洋環(huán)境中考慮國際海上碰避規(guī)則,國內(nèi)河流環(huán)境考慮中國內(nèi)河避碰規(guī)則等。只有考慮到這些實(shí)際環(huán)境因素,才能產(chǎn)生實(shí)際可行的避障路徑,提高避障于路徑規(guī)劃算法的適應(yīng)性。