無人水面艇避障路徑規(guī)劃算法綜述

劉 佳 王 杰

(南京信息工程大學(xué)自動化學(xué)院 BDAT&CICAEET 江蘇 南京 210044)

0 引 言

無人水面艇(Unmanned Surface Vehicle,USV)也可稱為水面無人艇或水面機器人，是一種無人操作的水面艦艇，主要用于執(zhí)行危險以及不適合有人船只執(zhí)行的任務(wù)[1]。在無人水面艇領(lǐng)域，美國和以色列的相關(guān)技術(shù)比較領(lǐng)先，相比較而言，目前國內(nèi)的無人水面艇技術(shù)還比較落后。美國空間和海戰(zhàn)系統(tǒng)中心研發(fā)的“SSC San Diego”號無人水面艇，結(jié)合電子海圖實現(xiàn)了路徑規(guī)劃功能，以自動雷達標(biāo)繪儀的目標(biāo)檢測信息實現(xiàn)了局部危險情況下的緊急避障[2]。以色列研發(fā)的“Protector”號無人艇已經(jīng)交付給以色列軍方，具有模塊化、反水雷戰(zhàn)、情報監(jiān)視和偵察等特點[3]。國內(nèi)的云州智能公司將無人艇推向民用領(lǐng)域，實現(xiàn)了在線水質(zhì)檢測等多項功能[4]。

避障路徑規(guī)劃一直都是無人水面艇研究的重要內(nèi)容，無人水面艇的自主能力之一是與外界未知環(huán)境進行交互，需要采集外界環(huán)境信息，從而保證無人水面艇能夠根據(jù)外界環(huán)境信息進行路徑規(guī)劃，以及進行局部危險狀況下的避障。避障路徑規(guī)劃就是根據(jù)行進要求和采集到的障礙物的狀態(tài)信息，找到一條從起始點到目標(biāo)點的最佳行進路徑，最后安全到達目標(biāo)點。

無人水面艇的避障路徑規(guī)劃可以分為基于完全信息的全局路徑規(guī)劃算法和基于傳感器信息的局部路徑規(guī)劃算法。本文對現(xiàn)有的無人水面艇避障路徑的眾多算法的優(yōu)點與不足進行了研究，對改進算法取得的最新的研究成果也進行了探討，最后對無人水面艇的避障路徑規(guī)劃的發(fā)展現(xiàn)狀進行了展望。

1 全局路徑規(guī)劃算法

全局路徑規(guī)劃一開始就要獲取整個的環(huán)境信息，然后依據(jù)環(huán)境建模構(gòu)造的環(huán)境地圖，在規(guī)定區(qū)域進行初步的路徑規(guī)劃，可以歸納為兩個子問題，即環(huán)境建模和路徑規(guī)劃算法。它依賴于全局環(huán)境信息，不能處理規(guī)劃過程中出現(xiàn)的臨時問題，若出現(xiàn)未知障礙物則無法使用，但一般情況下都可以找到最優(yōu)解，且對實時性要求也不高[5]。

環(huán)境建模是路徑規(guī)劃的第一步，其將現(xiàn)實的物理空間抽象成算法可以處理的抽象空間，實現(xiàn)相互間的映射。常見的環(huán)境建模方法有可視圖空間法、拓撲圖法、自由空間法、柵格法、Voronoi圖法和單元樹法等圖形學(xué)方法，它們往往是將無人水面艇所在的環(huán)境信息轉(zhuǎn)換成圖的問題，對整個環(huán)境空間進行描述，將實際問題轉(zhuǎn)換成數(shù)學(xué)問題，雖然提供了建模的基本方法，但也存在著搜索能力不足等問題[6]。

1.1 基于圖形法的路徑規(guī)劃算法

在上述成熟的圖形學(xué)環(huán)境建模方法之上，出現(xiàn)很多基于圖形法的全局路徑規(guī)劃算法，如Dijkstra算法、A*算法。

1.1.1 Dijkstra算法

Dijkstra算法是Dijkstra[7]在1959年提出的典型全局規(guī)劃最短路徑算法，用于計算一個節(jié)點到其他節(jié)點的最短路徑。其基本思想如下：

1) 分配起點s，并且把兩個集合記為S和U。集合S是用來儲存已求出最短路徑的頂點，集合U則是儲存還沒有求出最短路徑的頂點。

2) 一開始，集合S只包含起點s，集合U包含剩下的頂點，集合U中頂點的路徑是“起點s到該頂點的路徑”，從集合U中找出路徑最短的頂點加入集合S中。

3) 更新集合U中的頂點和頂點對應(yīng)的路徑。

4) 重復(fù)執(zhí)行步驟2)-步驟3)，直到集合U中不存在頂點。

傳統(tǒng)Dijkstra算法雖然簡單明了，但占用內(nèi)存大、計算效率較低，且只能按照預(yù)設(shè)路徑行走，所以一般只適用于小規(guī)模情況下的避障路徑規(guī)劃。

莊佳園等[8]為了減少Dijkstra算法自身內(nèi)存占用問題的影響，采用動態(tài)網(wǎng)格模型，對海面上的無人水面艇路徑規(guī)劃應(yīng)用基于電子海圖的距離尋優(yōu)Dijkstra算法，距離尋優(yōu)的目的是減少擴展非最短路徑上的節(jié)點，從而提高計算效率，加快路徑規(guī)劃速度，最后優(yōu)化路徑，增加路徑光滑度，滿足無人水面艇的控制要求。Singh等[9]在動態(tài)海洋環(huán)境下應(yīng)用Dijkstra算法進行全局路徑規(guī)劃，同時考慮到不同強度洋流對于無人水面艇最優(yōu)路徑規(guī)劃的影響，將地圖映射成二叉圖，充分考慮了最佳路徑曲率約束；將無人水面艇規(guī)定為圓形邊界包圍，為水面無人艇生成了更安全的最優(yōu)路徑。

1.1.2 A*算法及其改進算法

A*算法是Hart等[10]發(fā)明一種啟發(fā)式算法，是Dijkstra算法的一種擴展，是靜態(tài)路網(wǎng)中尋找到最短路徑的效率最高的直接搜索方法。其基本原理為：

首先設(shè)定一個代價函數(shù)：

f(n)=g(n)+h(n)

(1)

式中：f(n)是起點到某一個目標(biāo)點的估價函數(shù)；g(n)是起點到當(dāng)前節(jié)點n的實際代價值；h(n)是當(dāng)前節(jié)點n到某一個目標(biāo)節(jié)點的估計代價值，也被稱為啟發(fā)函數(shù)。A*算法找到最優(yōu)避障路徑的關(guān)鍵就是對啟發(fā)函數(shù)h(n)的選擇。

1) 當(dāng)h(n)≤d(n)時(d(n)為當(dāng)前節(jié)點到某一個目標(biāo)點的距離)，雖然能夠得到最優(yōu)解，但是搜索節(jié)點數(shù)量多，效率低下。

2) 當(dāng)h(n)>d(n)時，搜索節(jié)點變少，效率提高，但是可能會導(dǎo)致不是最優(yōu)解。

A*算法簡單，運行速度比Dijkstra算法快，但其依賴啟發(fā)函數(shù)，計算量巨大，規(guī)劃路徑的時間過長。A*算法應(yīng)用廣泛，許多學(xué)者針對其不足提出許多改進與變種，如：D*算法[11]及其變種算法Focussed D*[12]算法和D*Lite[13]算法，ARA*算法[14]，Anytime Dynamic A*算法[15]等。

D*算法是一種動態(tài)A*算法，適用于動態(tài)路網(wǎng)中；Focussed D*算法將A*算法與D*算法相結(jié)合，將啟發(fā)式函數(shù)更多地注重于成本代價的更新；D* Lite算法是基于LPA*算法的一種啟發(fā)式算法，它更加簡單易懂，便于實現(xiàn)，性能優(yōu)于Focussed D*算法，應(yīng)用更加廣泛。ARA*算法適用于有時間限制的避障路徑規(guī)劃，即犧牲最優(yōu)解的情況下進一步增強其實時性，中途被打斷也可繼續(xù)重啟生成可行路徑。Anytime Dynamic A*算法則是結(jié)合D*算法與ARA*算法，適用于動態(tài)環(huán)境下的復(fù)雜障礙物避障路徑規(guī)劃。上述改進算法已經(jīng)在機器人和無人機領(lǐng)域的路徑規(guī)劃上得到廣泛應(yīng)用，但是學(xué)者在水面無人艇的路徑規(guī)劃更多的還是基于原始A*算法的改進。

Svec等[16]提出基于A*的啟發(fā)式搜索和運動不確定性下的局部有界最優(yōu)規(guī)劃方法，用于規(guī)劃無人水面艇的動態(tài)可行路徑。該算法使用最小極大值搜索算法，允許算法考慮由于海浪導(dǎo)致無人艇偏離其原始路線的可能軌跡，更符合海上的復(fù)雜環(huán)境。實驗證明該算法具有實用價值，同時要求無人水面艇與原本規(guī)定路徑上相距距離較近，對于無人水面艇的控制要求提出了更高的要求。陳超等[17]針對A*算法依賴啟發(fā)函數(shù)的問題，提出一種基于可視圖的改進A*算法，加入判斷空間點和障礙物特征點相對關(guān)系，在起點和終點發(fā)生變化時不需要重新構(gòu)建可視圖，加強了無人水面艇適應(yīng)未知環(huán)境的能力。實驗證明運用啟發(fā)式搜索的方法可減少需要搜索節(jié)點的數(shù)目，大幅減少了規(guī)劃時間。Wang等[18]為了加快A*算法的路徑規(guī)劃速度，提出將A*算法與動態(tài)窗口法相結(jié)合的無人水面艇混合路徑規(guī)劃，將無人水面艇的運動特性考慮其中，改進成具有后平滑路徑的算法來減少航線點數(shù)量，同樣可以生成更短的路徑，在此之上借助動態(tài)窗口法選擇最佳速度來避免局部未知障礙物。實驗表明，該混合路徑規(guī)劃算法的運行速度更快，效率更高。

1.2 智能仿生學(xué)的路徑規(guī)劃算法

對于處理復(fù)雜環(huán)境下的路徑規(guī)劃問題時，科學(xué)家們學(xué)會從大自然獲取靈感，智能仿生學(xué)算法就是人們通過仿生學(xué)研究而發(fā)明的算法，常用的有蟻群算法、遺傳算法、粒子群優(yōu)化算法等。

1.2.1 蟻群算法

蟻群算法(Ant Colony Optimization，ACO)是Dorigo等[19]提出的一種智能優(yōu)化算法，仿生學(xué)家發(fā)現(xiàn)螞蟻通過一種叫作信息素的物質(zhì)在個體間傳遞信息，螞蟻可以感知這種物質(zhì)，從而指導(dǎo)方向。蟻群算法的基本原理如圖1所示，當(dāng)大量螞蟻采取集體行動時，通過螞蟻路徑越多，留下的信息素就越多，這就是正反饋過程，新螞蟻選擇較短路徑的可能性越大，最后蟻群可以找到食物來源與巢穴之間的最短路徑。有些螞蟻不會一直重復(fù)這樣的路徑，也會去尋找更好并且更短的路徑，吸引其他螞蟻過來，重復(fù)這個過程就會得到一條最優(yōu)路徑。蟻群算法就是通過迭代來模擬蟻群覓食行為來完成尋找最短路徑。

圖1 蟻群尋找食物示意圖

蟻群算法具有信息正反饋機制、較強的魯棒性和便于并行實現(xiàn)等優(yōu)點，但是在初期如果信息素缺少或者路徑問題規(guī)模太大，則會導(dǎo)致路徑規(guī)劃速度過慢。蟻群算法設(shè)置參數(shù)不準確，同樣會導(dǎo)致求解速度慢且所得解并不是全局最優(yōu)解，陷入局部最優(yōu)問題。

Wang等[20]針對蟻群算法存在的問題，首先采用網(wǎng)格法對于障礙物進行環(huán)境建模，在考慮無人水面艇的運動特性的同時，通過蟻群算法進行全局路徑規(guī)劃，仿真實驗表明該算法達到了預(yù)期目標(biāo)，能夠有效地尋找到最優(yōu)路徑。尚明棟等[21]針對傳統(tǒng)蟻群算法的早熟和停滯現(xiàn)象，在起點和目標(biāo)點之間設(shè)定一個坐標(biāo)夾角，每次移動時都選擇和初始目標(biāo)角度相同或相近的角度進行下一次移動，在參數(shù)設(shè)置中通過增加方向角權(quán)值來改進下一個節(jié)點的概率選擇，同時信息素的更新通過動態(tài)變化來進行。仿真表明，改進算法的搜索速度和全局搜索能力都有了顯著提升，最后得到的路徑更短且平滑。

1.2.2 遺傳算法

遺傳算法(Genetic Algorithms，GA)是Holland[22]根據(jù)自然界生物進化過程而提出的隨機化搜索算法，來源于進化論和遺傳學(xué)理論，已經(jīng)成為一個多學(xué)科、多領(lǐng)域的重要研究方向。基于遺傳算法的避障路徑規(guī)劃流程如圖2所示，使用適者生存原則，通過復(fù)制、交叉、突變等操作產(chǎn)生下一代的解，并逐步淘汰掉適應(yīng)度函數(shù)值低的解，增加適應(yīng)度函數(shù)值高的解，從而獲得最優(yōu)路徑。

圖2 基于遺傳算法的避障路徑規(guī)劃流程圖

遺傳算法具有較強的魯棒性，適合求解復(fù)雜路徑的優(yōu)化問題，應(yīng)用較為廣泛。但是其收斂速度慢，局部搜索能力差，控制變量較多，尋找可行解的能力較弱，易于產(chǎn)生早熟現(xiàn)象，規(guī)劃合理的避障路徑花費時間過久。

Naeem等[23]基于Wiener-Hammerstein模型，使用遺傳算法對無人水面艇進行路徑規(guī)劃，該算法已經(jīng)成功應(yīng)用在Springer號無人水面艇上，具有實用性。Praczyk等[24]設(shè)定無人水面艇一般情況下由人員遠程操作，連接不穩(wěn)定時使用遺傳算法進行緊急路徑規(guī)劃,實驗發(fā)現(xiàn)無論是簡單區(qū)域還是復(fù)雜盆地區(qū)域都能保證無人水面艇的安全。但這種方法只作為緊急后備選擇，沒有進一步考慮復(fù)雜的障礙物情況。Long等[25]針對遺傳算法收斂速度慢的問題，采用網(wǎng)格法的環(huán)境建模方法，提出一種新的初始種群方法，提高初始種群的收斂速度和初始種群質(zhì)量，設(shè)計自適應(yīng)交叉概率和變異概率，使得生成的路徑相比于傳統(tǒng)遺傳算法更短，實驗仿真證明了其安全性和可行性。曾凡明等[26]針對遺傳算法無法使用系統(tǒng)反饋信息，造成大量無效迭代，最終導(dǎo)致無法求得精確解的問題，采用遺傳算法來生成蟻群算法中的信息素分布，確保了信息素的快速生成，采用蟻群算法進行求解，確保解的準確性，實驗證明改進算法生成的路徑的魯棒性和準確性進一步提升。

1.2.3 粒子群優(yōu)化算法

粒子群優(yōu)化算法(Particle Swarm Optimization，PSO)是Eberhart等[27]根據(jù)飛鳥集群覓食行為發(fā)明的一種進化計算算法。該算法是基于群體的，將鳥看成一個個粒子，這些粒子同時擁有速度和位置屬性，單個粒子根據(jù)找到食物最近路徑分享給群體，同時比較群體中的最近路徑從而改變路徑，多次迭代后整個群體就找到最優(yōu)路徑。粒子群算法的數(shù)學(xué)模型描述如下：

假設(shè)D維搜索空間里存在n個粒子，第i個粒子表示為Xi={xi1,xi2,…,xiD},它有最好適應(yīng)值的位置表示為pbesti={pi1,pi2,…,piD}，所有粒子有最好適應(yīng)值的位置表示為gbest={g1,g2,…,gD},粒子i的速度記作Vi={vi1,vi2,…,viD}。同時根據(jù)下列公式更新每個粒子的速度和位置：

Vid(t+1)=wvid(t)+c1rand()·[pid(t)-xid(t)]+

c2rand()[gd(t)-xid(t)] 1≤i≤n,1≤d≤D

(2)

x(t+1)=x(t)+v(t+1)

(3)

式中：w為慣性權(quán)重；rand()為[0,1]范圍內(nèi)的隨機值；c1和c2為加速常數(shù)。

粒子群優(yōu)化算法和遺傳算法相類似，但是沒有遺傳算法的交叉變異等過程，它的特點是追蹤單個粒子和群體信息共享去尋找最優(yōu)解。粒子群優(yōu)化算法具有搜索速度快、計算較為簡單和具有記憶性等優(yōu)點，但是會產(chǎn)生早熟收斂和陷入局部最優(yōu)等問題。

杜開君等[28]為了避免粒子群算法陷入局部最優(yōu)問題，提出一種基于國際海上碰撞規(guī)則的無人水面艇的動態(tài)避障方法。采用極坐標(biāo)進行建模，對于障礙物采用圓形或者有向包圍盒進行簡化，考慮了無人水面艇運動特性，算法將海事規(guī)則作為約束條件之一，將粒子群算法引入無人水面艇的避障規(guī)劃之中，實驗證明算法滿足要求。Zhang等[29]針對粒子群算法存在的問題，提出基于極坐標(biāo)建模的改進粒子群優(yōu)化算法，在種群初始化方法中引入β分布、改進慣性因子更新方法，在粒子速度更新方面加入差分進化的思想，仿真實驗驗證了算法的有效性。鄭佳春等[30]為了應(yīng)對粒子群優(yōu)化算法的粒子飛行速度問題，引入模擬退火機制來更新粒子群優(yōu)化算法中粒子的速度和位置，使得PSO算法可以跳出局部極值區(qū)域，收斂到全局最優(yōu)粒子群解，仿真實驗證明該改進算法可以在復(fù)雜海域條件下安全快速進行路徑規(guī)劃。

1.3 對比分析

全局路徑算法之間的比較及其改進方法如表1所示。除此之外，還有模擬退火算法、模糊邏輯算法、禁忌搜索算法、神經(jīng)網(wǎng)絡(luò)算法[31-32]等全局路徑規(guī)劃算法在機器人領(lǐng)域應(yīng)用廣泛，但是在無人水面艇的路徑規(guī)劃中應(yīng)用較少。

表1 全局路徑規(guī)劃算法特點與改進方法

續(xù)表1

基于圖形法的路徑規(guī)劃算法一般要與環(huán)境建模中的地圖構(gòu)建集成使用，但是無人水面艇處于水上環(huán)境，接收到的傳感器信息有限且易受干擾，在地圖網(wǎng)格數(shù)量較大時，很難處理動態(tài)障礙物信息，不能保證路徑規(guī)劃的實時性。因此圖形學(xué)的路徑規(guī)劃算法要在地圖網(wǎng)格數(shù)量和路徑規(guī)劃實時性上尋求一定平衡。

智能仿生學(xué)的路徑規(guī)劃算法克服了傳統(tǒng)路徑規(guī)劃算法的部分缺點，具有很好的魯棒性，路徑規(guī)劃速度也得到進一步提升。但對于輸入激勵與抑制的設(shè)定存在一定人為的不確定因素，在尋找路徑的過程中易陷入局部最優(yōu)的問題，如蟻群算法和粒子群優(yōu)化算法；存在參數(shù)設(shè)置過于繁多的問題，比如遺傳算法。

2 局部路徑規(guī)劃算法

局部路徑規(guī)劃是指在未知或部分未知的環(huán)境下通過傳感器獲取周圍環(huán)境的信息，包括障礙物的尺寸、形狀和位置等信息，并使無人水面艇自主獲得一條安全可行的最優(yōu)路徑。局部路徑規(guī)劃算法主要有人工勢場法、動態(tài)窗口法、速度障礙法、快速擴展隨機樹算法等。

2.1 人工勢場法

Khatib[33]提出的人工勢場理論(Artificial Potential Fields,APF)是避障規(guī)劃中使用最廣泛的算法之一。人工勢場法的主要思想如圖3所示，首先用一個抽象的人造勢場進行環(huán)境搭建，該勢場由引力場和斥力場構(gòu)成。引力場由目標(biāo)點位置產(chǎn)生并作用于無人水面艇，勢場向量方向由無人水面艇指向目標(biāo)點；斥力場由環(huán)境中障礙物產(chǎn)生，勢場向量方向由障礙物指向無人水面艇。無人水面艇環(huán)境空間的總勢場為引力場和斥力場共同疊加作用，最終通過二者的合力控制無人水面艇來完成避障操作，到達目標(biāo)點。

圖3 人工勢場法示意圖

人工勢場法具有實時性高、反應(yīng)迅速和計算簡單等優(yōu)點，但是運動過程中如果某個點的合力為零，無人水面艇則不可以繞過該點，這就存在局部最小值問題。且當(dāng)目標(biāo)被障礙物包圍時，路徑不能收斂，無人水面艇同樣無法到達目標(biāo)點。

Xie等[34]為減少人工勢場法局部最小問題的影響，對吸引力函數(shù)和斥力函數(shù)都進行改進，增加了一個調(diào)節(jié)因子，當(dāng)無人水面艇接近目標(biāo)時，該調(diào)節(jié)因子控制下降的吸引力函數(shù)是線性函數(shù)，同時規(guī)定斥力是一個降低的高階函數(shù)，實驗證明改進的人工勢場法能使無人水面艇到達目標(biāo)點。Wang等[35]針對人工勢場法局部最小問題，在排斥力場函數(shù)中增加無人水面艇與目標(biāo)點之間的距離，并定時檢測無人水面艇是否進入了局部最小點，通過增加這兩個因素去改進人工勢場法，可以讓無人水面艇安全地避免局部最小點問題，仿真結(jié)果證明該改進算法可以有效幫助無人水面艇成功避免動態(tài)障礙物。Wu等[36]針對人工勢場法存在的問題，提出在人工勢場里面將斥力分解成兩個分力，并使一個分力處于引力的反方向，稱之為角度勢場，進一步與全局蟻群算法相結(jié)合，在不同環(huán)境下應(yīng)用此改進算法進行實驗，進一步提高安全性。

2.2 向量場直方圖法

向量場直方圖法(Vector Field Histogram，VFH)是Borenstein等[37]針對人工勢場法的目標(biāo)點附近有障礙物時很難到達目標(biāo)點這一問題提出的一種實時的路徑規(guī)劃算法。它的主要思想是將無人水面艇所處環(huán)境建立局部柵格地圖，同時計算每個方向USV的前行代價，這個方向的障礙物越多，相應(yīng)的前行代價也就越大，根據(jù)代價值的不同建立直方圖，選擇最低代價的方向前進，同時引入一個平衡函數(shù)來平衡最低代價與目標(biāo)方向，最終確定最優(yōu)避障路徑。

向量場直方圖法計算高效，具有較好的魯棒性，適用于多障礙物避障，但是沒有考慮USV自身的動力學(xué)與運動學(xué)。有學(xué)者在其基礎(chǔ)上提出VFH+和VFH*算法。Loe[38]將VFH算法應(yīng)用于無人水面艇的局部路徑規(guī)劃中，并設(shè)定了多種障礙情景，發(fā)現(xiàn)VFH算法在簡單的多障礙物情景下表現(xiàn)良好，但是在更加復(fù)雜的環(huán)境中也有可能陷入局部最優(yōu)問題，故將VFH算法與A*算法相結(jié)合，即引入VFH*算法應(yīng)對復(fù)雜環(huán)境的局部路徑規(guī)劃。同時將VFH算法與快速擴展隨機樹算法相結(jié)合，能夠快速尋找到最優(yōu)安全路徑。魏新勇等[39]針對USV自身是一種橢圓形，直接使用VFH*算法會造成USV尾端碰撞的問題，提出一種結(jié)合激光雷達進行前后數(shù)據(jù)融合的USV的環(huán)境建模，使得USV能夠準確避讓檢測到的障礙物，再通過建立直方圖和代價函數(shù)選出最終的避障路徑方向。仿真實驗證明，該方法能夠有效避免尾部相撞和陷入局部最小化等問題，完成局部避障。

2.3 動態(tài)窗口法

動態(tài)窗口法(Dynamic Window Approach,DWA)是Fox等[40]提出的一種在線避障算法，主要依靠實時探測的局部信息，以滾動的方式進行在線規(guī)劃，用啟發(fā)式方法生成優(yōu)化子目標(biāo)，隨著窗口不斷滾動不停地獲得新的局部信息，然后在滾動中實現(xiàn)優(yōu)化與反饋的結(jié)合，最終實現(xiàn)局部路徑規(guī)劃的規(guī)劃。

唐平鵬等[41]針對動態(tài)窗口法的問題提出無人水面艇分層策略將動態(tài)窗口分解為艏向窗口和線速度窗口,使用切線法和弧線法分別從艏向窗口和線速度窗口中求出規(guī)避角速度和線速度，并引入角速度緩沖模型以提升規(guī)劃過程中艇體的穩(wěn)定性。湖面實驗表明該改進算法有著很好的適應(yīng)能力，增強了無人水面艇行駛能力的安全性。Lin等[42]提出未知環(huán)境下基于動態(tài)窗口的避障方法，由于無人水面艇不能像陸地機器人那樣快速轉(zhuǎn)向或改變速度，需要一定的響應(yīng)時間，并且還需要滿足無人水面艇的最小旋轉(zhuǎn)直徑的要求，所以加入控制周期(T0)以確保無人水面艇能夠快速安全地避開障礙物，以滿足避障要求。使用擴展障礙物的方法，就是用圓形或矩形體根據(jù)其縱橫比來表示不同的障礙物，合理地簡化了障礙物的形狀，減少了消耗量的計算，縮短了計算時間。該改進方法考慮到復(fù)雜的多種動、靜態(tài)障礙物，實驗中設(shè)計三種不同的應(yīng)用場景，不管是單個障礙物還是多個障礙物都可以實時完成避障要求，具有適應(yīng)真實復(fù)雜環(huán)境的能力。

2.4 速度障礙法

速度障礙法(Velocity Obstacle，VO)是Fiorini等[43]提出的一種局部避障算法，在無人水面艇與障礙物之間在速度空間構(gòu)建一個三角區(qū)域，只要速度向量落入到此三角區(qū)域內(nèi)則判定二者會發(fā)生碰撞，若要進行避障必須從非三角區(qū)域中找一個最優(yōu)的速度矢量，從而找到最優(yōu)路徑。

速度障礙法的基本原理[44]如圖4所示，設(shè)定無人水面艇的位置向量為PA,障礙物B“膨化”之后的位置向量為PB,為了將USV簡化成一個質(zhì)點，將USV橢圓的長半軸分別疊加到障礙物的半長軸和半短軸上。圖中VA為USV的速度向量，VB為動態(tài)障礙物的速度向量，VBA為USV相對于動態(tài)障礙物的速度向量。

VBA=VA-VB

(4)

圖4 速度障礙法示意圖

將障礙物看作是靜止的，λL和λR分別是USV與障礙物的2條切線，當(dāng)USV發(fā)出沿著VBA方向的射線λBA與障礙物相交時，則判定USV將來會與障礙物發(fā)生碰撞危險。定義USV與障礙物發(fā)生碰撞的相對速度VBA的集合是速度空間中的相對碰撞區(qū)：

RCCAB={VBA|λBA∩B≠?}

(5)

式中：RCCAB是λL和λR之間的區(qū)域范圍。定義在USV的絕對速度空間里，會讓USV與障礙物發(fā)生碰撞的速度VA的集合為速度障礙VOAB：

VOAB=RCCAB⊕VB

(6)

式中：⊕是閔可夫斯基向量和運算。VOAB相當(dāng)于RCCAB沿著VB方向移動，當(dāng)USV的速度向量VA落在該區(qū)域，USV與障礙物會發(fā)生碰撞。

吳博等[45]考慮外界風(fēng)浪的影響和無人水面艇的運動特性，將速度障礙法應(yīng)用到無人艇避障規(guī)劃中，計算無人水面艇和障礙物的相對距離，分析二者的相對速度和相對位置關(guān)系，得出符合無人水面艇控制要求的可行路徑，提高行駛安全性。Kuwata等[46]針對速度障礙法沒有考慮動態(tài)障礙物的動態(tài)變化的問題，提出速度障礙法服從國際海上避碰規(guī)則，通過識別障礙物，判斷無人水面艇應(yīng)該通過障礙物的哪一側(cè)方向，保證了在動態(tài)海洋環(huán)境下的安全避障。通過相對速度計算無人水面艇到障礙物最接近目標(biāo)點的距離和時間，滿足約束條件時則判定無人水面艇與障礙物發(fā)生碰撞。構(gòu)建一個代價函數(shù)，為使代價函數(shù)最小，在可行速度空間找一個速度向量作為避障的速度向量，最后生成可行路徑。該改進算法已實際應(yīng)用于無人水面艇的目標(biāo)跟蹤任務(wù)中。

2.5 碰撞錐方法

碰撞錐方法(Collision Cone Approach,CCA)是Chakravarthy等[47]提出的一種用來分析兩個運動物體之間的碰撞關(guān)系的理論，根據(jù)USV與障礙物之間的地理位置，實時計算出兩者可能發(fā)生碰撞的危險區(qū)域并在避障路徑進行規(guī)避，如果不會發(fā)生碰撞則按原來路徑前進。該算法具有模型簡單、實時性高、應(yīng)用廣泛等優(yōu)點，對于靜態(tài)障礙物和動態(tài)障礙物都能快速給出高安全的避障路徑。

碰撞錐方法和速度障礙法都是基于碰撞錐理論，防止無人水面艇進入到與障礙物碰撞的范圍內(nèi)。但是速度障礙法考慮到了無人水面艇禁止使用的不同速度向量，同時也可能包括不同的方向。碰撞錐方法考慮禁止無人水面艇的航行方向，無人水面艇和障礙物都是恒定速度航行，其還可對非圓形障礙物進行避障。

Pu等[48]針對一般路徑規(guī)劃算法將障礙物進行圓形建模的問題，同時考慮到大多數(shù)動態(tài)船只會成為障礙物，提出一種基于橢圓碰撞錐方法的無人水面艇路徑規(guī)劃算法，進一步提出點與橢圓的碰撞錐計算方法，可以計算出無人水面艇與動態(tài)船只之間的碰撞角度范圍，同時結(jié)合國際海上避碰規(guī)則從而獲取到避障角度，完成避障后還可回歸到原始路徑繼續(xù)前進。實驗證明該算法能夠精準有效地完成無人水面艇的避障要求。吉大海等[49]針對速度障礙法適用于低速航行的不足，提出一種無人水面艇在高速情況下的基于行為的危險規(guī)避路徑規(guī)劃算法。首先使用碰撞錐理論判斷無人水面艇與障礙物的位置關(guān)系，然后將形成的碰撞約束和國際海上避碰規(guī)則約束相結(jié)合，轉(zhuǎn)換成對無人水面艇避障行為的約束，最終以USV航行角度和線速度優(yōu)化問題來獲得避障路徑。仿真實驗證明，改進后的混合算法能讓高速航行的USV完成動態(tài)障礙物的避障。

2.6 快速擴展隨機樹算法

快速擴展隨機樹算法(Rapidly-exploring Random Tree,RRT)由Lavalle[50]提出，采用樹結(jié)構(gòu)代替有向圖結(jié)構(gòu)，在規(guī)定控制率時，通過對狀態(tài)空間的采樣點進行碰撞檢測，避免空間建模，應(yīng)用于高維多自由度機器人在復(fù)雜環(huán)境下的路徑規(guī)劃問題。

快速擴展隨機樹算法主要思想是迅速減小一個隨機選擇的節(jié)點到樹的距離，直到滿足預(yù)期要求，最終目的就是找到一條從根節(jié)點到目標(biāo)點的可行路徑。基本快速擴展隨機樹算法構(gòu)建過程如圖5所示，RRT算法在高維環(huán)境下的路徑規(guī)劃中應(yīng)用廣泛，但在全局空間下均勻搜索，導(dǎo)致時間花費過久，造成資源浪費，實時性較差，而且隨機采樣點缺乏可重復(fù)性，最終可能導(dǎo)致生成的路徑不是最優(yōu)路徑。

圖5 基本快速擴展隨機樹算法構(gòu)建過程

莊佳園等[51]針對RRT算法耗時長、無法滿足實時性要求的問題，提出一種基于RRT的局部路徑規(guī)劃算法。針對無人水面艇的航行特點，對傳統(tǒng)RRT算法進行了改進，以海上和湖上實際雷達圖像進行環(huán)境建模，改進生長點選擇使樹朝著最有利方向生長，改進探索點的選擇使得規(guī)劃軌跡接近最優(yōu)軌跡。最后對航線進行優(yōu)化，去除多余航線點。實驗表明優(yōu)化后的路徑更適合無人水面艇的控制要求，進一步提高了USV局部路徑規(guī)劃的速度。Chen等[52]針對RRT算法只可設(shè)定一個目標(biāo)點問題，提出一種用于無人水面艇多點路徑規(guī)劃的RRT算法，對于單個目標(biāo)航行點的時候可以快速產(chǎn)生航行路線。但是對于多個預(yù)設(shè)的目標(biāo)點時，將目標(biāo)點動態(tài)調(diào)整為沿路的航線點，并且在RRT樹的生長過程中動態(tài)刷新樹的節(jié)點信息，使得航行路線可以通過所有航行點。同時在每個路徑段都加入路徑平滑算法，與A*算法相比，可以較短時間完成避障路徑規(guī)劃。

2.7 對比分析

局部路徑規(guī)劃算法的優(yōu)缺點與其改進方法如表2所示。此外還有Bug算法、曲率速度法、接近圖法、ASL法、梯度法等經(jīng)典局部路徑規(guī)劃算法已經(jīng)在自主機器人領(lǐng)域得到廣泛應(yīng)用，但在無人水面艇領(lǐng)域的應(yīng)用較少。

表2 局部路徑規(guī)劃算法特點與改進方法

續(xù)表2

人工勢場法根據(jù)傳感器信息獲得局部障礙物信息，多用于局部靜態(tài)障礙物的路徑規(guī)劃，在目標(biāo)點附近沒有障礙物時，其規(guī)劃速度和規(guī)劃準確度最佳。向量場直方圖法針對局部最優(yōu)問題提出改進，更適合多障礙物情形下的避障。動態(tài)窗口法和速度障礙法更適用于局部動態(tài)障礙物的路徑規(guī)劃處理，考慮無人水面艇方向空間和速度空間的危險規(guī)避，但是對于無人水面艇的控制也提出更高的要求。碰撞錐方法實時性高，適用于非圓形障礙物避障。快速擴展隨機樹算法大多應(yīng)用于高維環(huán)境下的路徑規(guī)劃，更符合海洋環(huán)境下的無人水面艇避障路徑規(guī)劃。

上述全局路徑規(guī)劃算法和局部路徑規(guī)劃算法都符合無人水面艇的避障路徑規(guī)劃要求，大部分文獻提出的改進算法忽略了洋流、風(fēng)浪等外界環(huán)境的影響，其環(huán)境建模還需要進一步完善。由于無人水面艇處于海洋環(huán)境，和陸地機器人行動不同，這些算法也忽略了無人水面艇的運動特性即在海洋中實際轉(zhuǎn)向能力。

3 結(jié) 語

隨著控制技術(shù)的進一步發(fā)展，無人水面艇的應(yīng)用場景越來越豐富，為了進一步發(fā)展無人水面艇，必須對現(xiàn)階段的無人水面艇的不足進行改進，但是沒有一種單一算法可以在任意的環(huán)境下準確有效避障，故未來還需對以下幾方面展開研究：

(1) 進一步完善現(xiàn)有路徑規(guī)劃算法的實用性。對于無人水面艇的環(huán)境建模，必須通過具體測量或者使用準確的電子海圖去獲得比較可靠的數(shù)據(jù)，考慮水流、風(fēng)浪等外界環(huán)境的影響，利用獲得的數(shù)據(jù)對模型進行驗證。在規(guī)劃海洋環(huán)境避障路徑時，無人水面艇必須考慮國際海上避碰規(guī)則，因為可能與真實船舶進行實時避障，只有共同遵循規(guī)則才能確保雙方船只航行安全，完成安全避障。在無人水面艇進行避障行動的時候必須考慮無人水面艇自身的運動特性，與陸地機器人的運動不同，由于水流的特性，無人水面艇的運動路徑可能存在一定的偏移和誤差，必須考慮其旋轉(zhuǎn)半徑，根據(jù)無人水面艇的實際轉(zhuǎn)向能力，適當(dāng)“膨脹”無人水面艇與障礙物之間的距離，引入安全距離的概念，才能產(chǎn)生實際可行的避障路徑。

(2) 新的路徑規(guī)劃算法。近年來，智能算法得到了極大的發(fā)展，出現(xiàn)許多新的人工智能方法和新的數(shù)理方法，這些算法在其他無人機器設(shè)備上得到很好應(yīng)用，但在無人水面艇路徑規(guī)劃上還沒有發(fā)揮應(yīng)有的優(yōu)勢，可以研究將傳統(tǒng)路徑規(guī)劃算法與智能算法相融合，尋求可以克服現(xiàn)有方法缺點的新的路徑規(guī)劃算法，以期得到未知環(huán)境下的適應(yīng)性更好的動態(tài)避障組合算法。

(3) 多無人水面艇協(xié)同工作。多無人水面艇協(xié)同工作也是目前新的研究方向，多機器人協(xié)同工作在很多領(lǐng)域中已經(jīng)十分常見，比如物流公司多個無人機器小車協(xié)同搬運快遞、無人機的飛行編隊和水下機器人的合作搜救與觀察等，其中涉及運動控制算法、編隊算法問題和多機器人之間的通信問題，將路徑規(guī)劃算法與運動控制算法相結(jié)合，在實踐中進一步完成更多未知環(huán)境下的避障路徑規(guī)劃。

(4) 路徑規(guī)劃算法和底層控制。對于無人水面艇的導(dǎo)航避障問題，路徑規(guī)劃問題只是其中重要一環(huán)，傳感器及控制器的工作也是其中重要問題之一。路徑規(guī)劃算法為無人水面艇提供可行航線，但是具體操作需要傳感器與控制器來完成。大部分路徑規(guī)劃算法在模擬實驗中的仿真驗證表明了算法的可行性，但是理論研究最終還是要應(yīng)用于實際，在真實環(huán)境中使用這些算法還需要進一步的研究與改進。