周治國，邸順帆

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

0 引 言

路徑規(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ā)展趨勢、展望未來研究方向。

1 無人艇感知模塊

環(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]。

2 路徑規(guī)劃與避障

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

2.1 全局路徑規(guī)劃

全局路徑規(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

2.2 局部避障算法

局部避障即局部路徑規(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

2.3 強(qiáng)化學(xué)習(xí)算法

強(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

3 結(jié) 語

無人艇實(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)性。