劉 佳 王 杰

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

0 引 言

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

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

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

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

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

環(huán)境建模是路徑規(guī)劃的第一步，其將現(xiàn)實(shí)的物理空間抽象成算法可以處理的抽象空間，實(shí)現(xiàn)相互間的映射。常見的環(huán)境建模方法有可視圖空間法、拓?fù)鋱D法、自由空間法、柵格法、Voronoi圖法和單元樹法等圖形學(xué)方法，它們往往是將無人水面艇所在的環(huán)境信息轉(zhuǎn)換成圖的問題，對(duì)整個(gè)環(huán)境空間進(jìn)行描述，將實(shí)際問題轉(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ī)劃最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他節(jié)點(diǎn)的最短路徑。其基本思想如下：

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

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

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

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

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

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

1.1.2 A*算法及其改進(jìn)算法

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

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

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

(1)

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

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

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

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

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

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

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

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

1.2.1 蟻群算法

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

圖1 蟻群尋找食物示意圖

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

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

1.2.2 遺傳算法

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

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

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

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

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

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

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

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)的隨機(jī)值；c1和c2為加速常數(shù)。

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

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

1.3 對(duì)比分析

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

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

續(xù)表1

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

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

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

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

2.1 人工勢(shì)場(chǎng)法

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

圖3 人工勢(shì)場(chǎng)法示意圖

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

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

2.2 向量場(chǎng)直方圖法

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

向量場(chǎng)直方圖法計(jì)算高效，具有較好的魯棒性，適用于多障礙物避障，但是沒有考慮USV自身的動(dòng)力學(xué)與運(yùn)動(dòng)學(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)對(duì)復(fù)雜環(huán)境的局部路徑規(guī)劃。同時(shí)將VFH算法與快速擴(kuò)展隨機(jī)樹算法相結(jié)合，能夠快速尋找到最優(yōu)安全路徑。魏新勇等[39]針對(duì)USV自身是一種橢圓形，直接使用VFH*算法會(huì)造成USV尾端碰撞的問題，提出一種結(jié)合激光雷達(dá)進(jìn)行前后數(shù)據(jù)融合的USV的環(huán)境建模，使得USV能夠準(zhǔn)確避讓檢測(cè)到的障礙物，再通過建立直方圖和代價(jià)函數(shù)選出最終的避障路徑方向。仿真實(shí)驗(yàn)證明，該方法能夠有效避免尾部相撞和陷入局部最小化等問題，完成局部避障。

2.3 動(dòng)態(tài)窗口法

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

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

2.4 速度障礙法

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

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

VBA=VA-VB

(4)

圖4 速度障礙法示意圖

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

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

(5)

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

VOAB=RCCAB⊕VB

(6)

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

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

2.5 碰撞錐方法

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

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

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

2.6 快速擴(kuò)展隨機(jī)樹算法

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

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

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

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

2.7 對(duì)比分析

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

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

續(xù)表2

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

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

3 結(jié) 語

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

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

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

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

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