郭銀景, 鮑建康, 劉 琦, 屈衍璽, 呂文紅

AUV實(shí)時(shí)避障算法研究進(jìn)展

郭銀景1,2, 鮑建康3, 劉 琦1, 屈衍璽1, 呂文紅4

(1. 山東科技大學(xué) 電子信息工程學(xué)院, 山東 青島, 266590; 2. 青島智海牧洋科技有限公司, 山東 青島, 266590; 3. 山東科技大學(xué) 電氣與自動(dòng)化工程學(xué)院, 山東 青島, 266590; 4. 山東科技大學(xué) 交通學(xué)院, 山東 青島, 266590)

針對(duì)目前在研究自主水下航行器(AUV)實(shí)時(shí)避障算法過程中出現(xiàn)的重點(diǎn)難點(diǎn)及研究趨勢, 文中從動(dòng)態(tài)障礙物、多約束與多目標(biāo)以及海流干擾3方面分析了水下實(shí)時(shí)避障算法的研究難點(diǎn), 然后從人工勢場法、模糊邏輯法和智能仿生算法3個(gè)方面重點(diǎn)闡述水下實(shí)時(shí)避障算法的研究進(jìn)展。對(duì)比3種避障算法的研究現(xiàn)狀得知, 通過修正勢場函數(shù)、引入AUV運(yùn)動(dòng)約束、考慮障礙物相對(duì)速度和復(fù)雜海流影響等, 使改進(jìn)的人工勢場法克服了陷阱問題、局部極小值和目標(biāo)不可達(dá)等問題, 成為解決AUV實(shí)時(shí)避障問題的重點(diǎn)研究方向。在躲避動(dòng)態(tài)障礙物方面, 多種避障算法融合將成為一種趨勢; 在多約束與多目標(biāo)問題中, 能耗問題尤為重要卻很少被作為參數(shù)引入到避障算法中, 具有很大的研究潛力; 針對(duì)海流干擾問題, 多數(shù)避障算法僅考慮了水平方向的定常流或渦流, 因此考慮三維海流干擾也是未來水下實(shí)時(shí)避障算法的研究方向之一。

自主水下航行器; 實(shí)時(shí)避障算法; 人工勢場; 模糊邏輯; 仿生

0 引言

近年來, 隨著新材料、新能源和人工智能等技術(shù)的不斷進(jìn)步, 各海洋大國都加快了對(duì)自主水下航行器(autonomous undersea vehicle, AUV)的研究步伐并取得了重要進(jìn)展[1-2]。與載人水下航行器相比, AUV憑借著機(jī)動(dòng)性強(qiáng)、無人員傷亡風(fēng)險(xiǎn)、適應(yīng)能力與生存能力高、制造與維護(hù)成本低等優(yōu)點(diǎn)得到了各國學(xué)者的重點(diǎn)關(guān)注, 成為海洋勘察和科學(xué)研究的重要設(shè)備[3-5]。AUV需要實(shí)時(shí)應(yīng)對(duì)復(fù)雜多變的水下環(huán)境, 以便順利規(guī)劃路徑到達(dá)目的地, 因而水下避障算法已成為AUV領(lǐng)域的重點(diǎn)研究方向之一。

目前AUV水下避障算法通常分為2類: 第1類為全局路徑規(guī)劃, 在已知整體環(huán)境模型的情況下, AUV根據(jù)相應(yīng)算法規(guī)劃出起始點(diǎn)到目的地的一條安全路徑, 具體方法包括柵格法[6]、可視圖法[7]和A*算法[8]等, 該算法在動(dòng)態(tài)環(huán)境下的避障效果并不理想; 第2類為局部路徑規(guī)劃, AUV通過聲吶、激光等傳感器感知周圍的環(huán)境信息, 確定當(dāng)前環(huán)境中障礙物的分布情況, 并根據(jù)傳感器采集到的水下數(shù)據(jù)進(jìn)行小范圍避障, 具體方法包括遺傳算法[9]、人工勢場法[10-14]、神經(jīng)網(wǎng)絡(luò)法[15]、模糊邏輯法[16-18]和蟻群算法[19-20]等。

目前AUV水下實(shí)時(shí)避障的研究難點(diǎn)主要包括以下幾點(diǎn)。

1) 動(dòng)態(tài)障礙物避障

AUV在航行過程中, 除了需要規(guī)避預(yù)定路線上的巖石、珊瑚等靜態(tài)障礙物以外, 還需通過及時(shí)調(diào)整自身運(yùn)動(dòng)姿態(tài)來避開如魚群、漁網(wǎng)、浮標(biāo)等動(dòng)態(tài)障礙物[21], 并及時(shí)回歸規(guī)劃路線。

2) 多約束與多目標(biāo)

AUV的航行存在物理約束和幾何約束。物理約束指AUV的最大線速度、最大角速度和能量等, 幾何約束指AUV的形狀和尺寸。AUV規(guī)劃局部最優(yōu)路徑時(shí)存在多個(gè)目標(biāo), 如路徑最短、耗時(shí)最短、能耗最低、安全性最佳等, 這些目標(biāo)之間往往存在沖突[22]。為了進(jìn)一步提高AUV的避障性能, 在設(shè)計(jì)實(shí)時(shí)避障算法時(shí)需要引入其多種約束條件并兼顧局部路徑規(guī)劃的多個(gè)目標(biāo)。

3) 海流干擾

AUV通常在復(fù)雜多變的海流中工作, 海流會(huì)對(duì)其航行軌跡造成較大的干擾, 與其相關(guān)的路徑規(guī)劃不僅需要考慮避障問題, 還需考慮海流對(duì)AUV航行的影響。在路徑規(guī)劃時(shí), 可充分利用海流場的能量, 減少因抵消海流而造成的能量消耗, 因此需要規(guī)劃出一條能量消耗盡可能少、航行距離盡可能短的路徑[20]。

1 避障算法發(fā)展歷程

機(jī)器人避障算法的研究興起于 20 世紀(jì) 60年代[23]。荷蘭計(jì)算機(jī)科學(xué)家Dijkstra[24]在 1959 年提出 Dijkstra 算法, 該算法以起點(diǎn)為中心向四周拓展, 直至拓展到終點(diǎn)為止來尋找一條最短的路徑。這種算法計(jì)算量大, 容易在尋找路徑時(shí)出現(xiàn)“死區(qū)”。1968 年, Hart等[25]提出了一種A*算法, 解決了Dijkstra 算法計(jì)算量大、計(jì)算時(shí)間長的問題。然而該算法較為復(fù)雜, 需要比較當(dāng)前8個(gè)相鄰柵格點(diǎn)才能得到下一個(gè)柵格路徑。1975年, Howden等[26]提出了柵格法, 將路徑規(guī)劃問題變成尋求2個(gè)柵格節(jié)點(diǎn)間的最優(yōu)路徑問題, 但是隨著機(jī)器人的移動(dòng), 環(huán)境信息越來越多, 處理時(shí)間和存儲(chǔ)容量也越來越大, 無法滿足實(shí)時(shí)性要求。Lozano-Perez等[27]在1979年提出了可視圖法, 機(jī)器人規(guī)劃最優(yōu)路徑的過程就是尋找從起點(diǎn)到終點(diǎn)直線距離最短的過程, 但是一旦目標(biāo)移動(dòng), 可視圖將重新構(gòu)造并重新規(guī)劃最佳路徑, 因此該算法靈活性較差, 尋找路徑的時(shí)間較長。由于可視圖法僅適用于有棱角的多邊形障礙物, 無法避開圓形障礙, Gowda等[28]在1983年對(duì)可視圖法加以改進(jìn), 提出了Voronoi圖法并由Takahashi等[29]實(shí)現(xiàn)了該算法。Liu等[30]提出了切線圖法, 有效改進(jìn)了可視圖法的不足, 但該算法要求機(jī)器人必須在接近障礙物時(shí)才能避障, 避障精度較差。

1986年, Khatib[31]提出人工勢場法, 該算法操作簡單, 能夠做到實(shí)時(shí)避障, 但易使規(guī)劃路徑陷入障礙區(qū)域的“死區(qū)”, 導(dǎo)致避障失敗。Boren- stein等[32-33]將人工勢場法和網(wǎng)格法結(jié)合起來, 提出了虛力場(virtual force field, VFF)算法和矢量場柱狀圖(vector field histogram, VFH)算法。

1995年, Kennedy等[34]提出粒子群優(yōu)化(par- ticle swarm optimization, PSO)算法, 該算法具有整體性的優(yōu)點(diǎn)。但是, 該算法由于粒子之間的相互作用變得非常復(fù)雜, 實(shí)際優(yōu)化過程存在多樣性, 難以得到適用于所有優(yōu)化問題的結(jié)果。1998年, Kuffner等[35]提出了快速擴(kuò)展隨機(jī)樹(rapidly-ex- ploring random tree, RRT)搜索算法, 該算法操作簡單, 但一般很難一次找到最短路徑。

目前常見的水下實(shí)時(shí)避障算法還包括模糊邏輯法, 以及人工神經(jīng)網(wǎng)絡(luò)法、粒子群算法和蟻群算法等智能仿生算法, 各類算法的優(yōu)缺點(diǎn)如表1所示。

表1 常見水下實(shí)時(shí)避障算法優(yōu)缺點(diǎn)對(duì)比

2 水下實(shí)時(shí)避障算法

2.1 改進(jìn)人工勢場法

人工勢場法的基本思想是: 將AUV的運(yùn)動(dòng)視為一種在虛擬力場中的運(yùn)動(dòng), 障礙物對(duì)AUV施加斥力, 目標(biāo)點(diǎn)則對(duì)其施加引力, 引力和斥力的合力控制AUV的運(yùn)動(dòng)方向和位置。具體流程如圖1所示。

雖然人工勢場法對(duì)于簡單環(huán)境很有效, 但由于對(duì)其的研究均處于靜態(tài)環(huán)境中, 沒有考慮到障礙物的速度和加速度的影響, 所以在動(dòng)態(tài)避障過程中的避障效果不是很理想。在復(fù)雜多障礙的環(huán)境中, 不合理的勢場數(shù)學(xué)方程容易產(chǎn)生局部極值點(diǎn), 導(dǎo)致AUV未到達(dá)目標(biāo)點(diǎn)就停止運(yùn)動(dòng), 因此采用人工勢場法實(shí)現(xiàn)水下避障主要有以下5個(gè)缺點(diǎn): 1) 存在陷阱區(qū)域; 2) AUV在相近障礙物間不能發(fā)現(xiàn)路徑; 3) AUV在障礙物前容易產(chǎn)生震蕩; 4) AUV容易在狹窄通道中擺動(dòng); 5) 所規(guī)劃的路徑僅為可行路徑, 而非最優(yōu)路徑[36]。

為了改進(jìn)人工勢場法僅根據(jù)相對(duì)距離來控制力的大小問題, 劉學(xué)敏等[37]通過設(shè)定各個(gè)自由度上的運(yùn)動(dòng)平衡點(diǎn), 將AUV的自主避障規(guī)劃和運(yùn)動(dòng)控制結(jié)合起來, 解決了人工勢場法的陷阱問題。孫玉山等[38]在此基礎(chǔ)上進(jìn)一步改進(jìn), 將AUV的航行速度、電池電壓等參數(shù)引入到警戒距離的設(shè)定、艏向角的規(guī)劃及控制能力等參數(shù)中, 提高了AUV的動(dòng)態(tài)避障能力。針對(duì)傳統(tǒng)人工勢場法未考慮到微小型AUV的自身約束條件這一缺點(diǎn), 楊建等[11]將微小型AUV的運(yùn)動(dòng)特性嵌入到人工勢場法中。為了解決目標(biāo)不可達(dá)的問題, 李東方等[12]提出了一種基于人工勢場和RRT搜索算法的水下避障算法, 通過RRT搜索算法解決路徑被鎖死的問題。為了尋找水下避障的最優(yōu)路徑, 李東方等[39]將人工勢場法與浸入邊界法-玻爾茲曼格子法(immersed boundary method-lattice Boltzmann method, IB-LBM)相結(jié)合, 實(shí)現(xiàn)實(shí)時(shí)避障功能并能夠利用已知環(huán)境信息生成最優(yōu)路徑。

圖1 人工勢場法流程圖

上述算法均是針對(duì)傳統(tǒng)人工勢場法的某一缺點(diǎn)進(jìn)行改進(jìn), 計(jì)算復(fù)雜且并未從本質(zhì)上解決人工勢場法的局部極值問題。產(chǎn)生局部極值和目標(biāo)不可達(dá)問題的本質(zhì)是勢場函數(shù)的定義存在缺陷。為了克服局部極值與目標(biāo)不可達(dá)問題, 程志等[14]對(duì)斥力的生成和計(jì)算機(jī)制進(jìn)行了調(diào)整以解決局部極值問題, 同時(shí)設(shè)立虛擬目標(biāo)點(diǎn)以擺脫陷阱區(qū)域; 李沛?zhèn)惖萚40]對(duì)引、斥力勢場函數(shù)進(jìn)行改進(jìn), 同時(shí)引入速度勢場函數(shù), 將靜態(tài)勢場轉(zhuǎn)變?yōu)閯?dòng)態(tài)勢場, 綜合考慮了水下滑翔機(jī)的運(yùn)動(dòng)約束和定常海流等因素。王奎民等[41]將海流作用力添加到勢場力中, 分別采用定常流和渦流來分析AUV所受合力。同樣是改進(jìn)勢場函數(shù), 姚鵬[42]等不僅通過定義修正矩陣來量化障礙物對(duì)初始導(dǎo)航向量場的影響, 得到障礙空間下的修正導(dǎo)航向量場, 引導(dǎo)AUV躲避靜態(tài)障礙, 而且通過引入動(dòng)態(tài)障礙物的參考運(yùn)動(dòng)速度, 構(gòu)建相對(duì)初始或相對(duì)修正導(dǎo)航向量場, 并采取有限時(shí)域推演與調(diào)整策略, 最終引導(dǎo) AUV 躲避動(dòng)態(tài)障礙。

2.2 模糊邏輯法

由于水下環(huán)境的復(fù)雜性, 建立精確的避障過程數(shù)學(xué)模型十分困難, 因此無需建立環(huán)境數(shù)學(xué)模型的模糊邏輯法逐漸得到更多的重視。其原理是基于實(shí)時(shí)傳感器信息的模糊邏輯, 參考前人的經(jīng)驗(yàn), 通過查表得到規(guī)劃信息, 實(shí)現(xiàn)局部路徑規(guī)劃(如圖2所示)。同時(shí)因?yàn)槟：壿嫹ㄒ?guī)則庫中的每條規(guī)則都具有明確的物理意義, 這一獨(dú)特優(yōu)點(diǎn)也讓利用專家知識(shí)調(diào)整模糊邏輯規(guī)則成為可能。

圖2 模糊邏輯法流程圖

傳統(tǒng)的模糊邏輯法只考慮了AUV周圍的環(huán)境信息, 但事實(shí)上AUV的實(shí)時(shí)避障過程還和其運(yùn)動(dòng)學(xué)約束、動(dòng)力學(xué)特性和操縱性有關(guān)。為此, 張禹等[17]提出了一種復(fù)合模糊實(shí)時(shí)避障算法, 當(dāng)遇到障礙時(shí), 由運(yùn)動(dòng)控制器和實(shí)時(shí)避障規(guī)劃器共同進(jìn)行運(yùn)動(dòng)控制, 提高了遠(yuǎn)程AUV實(shí)時(shí)避障過程的機(jī)動(dòng)性和實(shí)時(shí)性。針對(duì)水下非結(jié)構(gòu)化區(qū)域, Anwary等[43]采用前饋?zhàn)赃m應(yīng)共振理論(adaptive resonance theory, ART)組件分析非結(jié)構(gòu)化水下環(huán)境, 采用模糊BK(Bandler-Kohout)乘積算法對(duì)模糊規(guī)則集進(jìn)行插值, 使模糊單元的性能不斷適應(yīng)環(huán)境的變化并對(duì)最優(yōu)路徑進(jìn)行決策。模糊邏輯法的另一缺點(diǎn)是主觀性強(qiáng), 而且當(dāng)輸入量增多時(shí), 推理規(guī)則和模糊控制規(guī)則表會(huì)急劇膨脹?；诖? 林政等[16]在模糊邏輯法的基礎(chǔ)上進(jìn)行改進(jìn), 提出了一種考慮障礙物所有分布情況的模糊推理規(guī)則表并進(jìn)行了簡化處理, 根據(jù)環(huán)境情況調(diào)整航速, 增強(qiáng)了無人水面艇在復(fù)雜環(huán)境下避障的適應(yīng)能力。Sun等[44]將三維路徑規(guī)劃簡化為水平面和垂直面兩部分, 并加入速度綜合法, 得到實(shí)際的速度和角速度, 同時(shí)開發(fā)了一種具有加速/中斷(a/b)模塊的實(shí)時(shí)導(dǎo)航模糊推理系統(tǒng), 使AUV能夠自動(dòng)避開動(dòng)態(tài)障礙物。在此基礎(chǔ)上, Sun等[45]采用量子粒子群算法(quantum PSO, QPSO)生成隸屬度函數(shù)的最優(yōu)邊界值, 克服了模糊算法主觀性強(qiáng)、環(huán)境適應(yīng)性差的問題, 將優(yōu)化策略與模糊設(shè)計(jì)相結(jié)合規(guī)劃三維最優(yōu)路徑。多AUV編隊(duì)避障方面, Sahu等[46]將人工勢場法與模糊算法相結(jié)合, 將勢函數(shù)設(shè)計(jì)成AUV間距離的因變量來實(shí)現(xiàn)多AUV在期望路徑上的協(xié)同運(yùn)動(dòng)和依次避障。

2.3 智能仿生算法

人工神經(jīng)網(wǎng)絡(luò)是一種模擬生物神經(jīng)網(wǎng)絡(luò)進(jìn)行信息處理的數(shù)學(xué)模型, 它模擬大腦的某些機(jī)理與機(jī)制, 可以有效地實(shí)現(xiàn)并行處理、自學(xué)習(xí)和非線性映射等功能, 在水下實(shí)時(shí)避障領(lǐng)域具有很大的應(yīng)用價(jià)值[47-48]。

Yan等[49]針對(duì)完全未知環(huán)境下的AUV, 提出了一種基于生物激勵(lì)神經(jīng)網(wǎng)絡(luò)的無碰撞全覆蓋路徑規(guī)劃方法, 不需要事先了解時(shí)變工作空間和顯式地優(yōu)化全局代價(jià)函數(shù)。針對(duì)河口環(huán)境, Li等[50]研究了河流狀況下的生物啟發(fā)神經(jīng)網(wǎng)絡(luò)路徑規(guī)劃, 但僅考慮了靜態(tài)障礙物, 未對(duì)AUV三維動(dòng)態(tài)避障這一核心問題進(jìn)行研究。為此, 朱大奇等[51]針對(duì)突發(fā)障礙物和水下三維環(huán)境, 在生物啟發(fā)神經(jīng)網(wǎng)絡(luò)模型的基礎(chǔ)上將相鄰神經(jīng)元的權(quán)值影響加入到模型激勵(lì)項(xiàng), 無需樣本學(xué)習(xí)與訓(xùn)練就可實(shí)現(xiàn)AUV自主避障。Huang等[52]采用該方法實(shí)現(xiàn)了多AUV協(xié)同避障, 但該方法未考慮海流對(duì)水下實(shí)時(shí)避障的影響。

針對(duì)復(fù)雜海流環(huán)境下AUV的路徑規(guī)劃問題, 朱大奇等[53]給出了一種基于離散生物啟發(fā)神經(jīng)網(wǎng)絡(luò)(glasius bio-inspired neural networks, GBNN)模型的AUV實(shí)時(shí)避障算法, 首先神經(jīng)網(wǎng)絡(luò)中的每一個(gè)神經(jīng)元與柵格地圖中的位置單元一一對(duì)應(yīng), 然后根據(jù)神經(jīng)元的活性輸出值分布情況并結(jié)合方向信度算法實(shí)現(xiàn)AUV自主路徑規(guī)劃, 最后考慮障礙物環(huán)境與動(dòng)態(tài)時(shí)變海流對(duì)AUV實(shí)時(shí)避障的影響, 自適應(yīng)地規(guī)劃出一條無碰撞且節(jié)能的安全路徑, 可實(shí)現(xiàn)在線路徑重規(guī)劃, 具有較好的實(shí)時(shí)性。

除了人工神經(jīng)網(wǎng)絡(luò)法以外, 遺傳算法、PSO算法、蜂群算法[54]、快速搜索隨機(jī)樹算法[55]以及螢火蟲算法[56]等智能仿生算法也被應(yīng)用到水下實(shí)時(shí)避障領(lǐng)域中。Yao等[57]為了獲得最優(yōu)的避障路徑, 對(duì)遺傳算法中的變異因子進(jìn)行改進(jìn), 并將海流的影響也考慮其中。孫兵等[58]采用粒子群算法對(duì)模糊控制器的隸屬度函數(shù)參數(shù)進(jìn)行優(yōu)化, 將具有最大適應(yīng)度值的粒子選作最優(yōu)解, 最大程度地優(yōu)化模糊控制器進(jìn)而指導(dǎo)AUV規(guī)劃出最優(yōu)路徑。考慮到水下機(jī)器人和障礙物的實(shí)際尺寸不可忽略, 羅頎棟[59]將警戒柵格的概念引入蟻群算法中, 提出了一種基于保守原則的蟻群算法, 提高了水下避障的安全性, 但延長了避障路徑。馬焱等[20]將蟻群算法與煙花算法相融合, 先利用煙花算法收斂快的特點(diǎn)尋找參考路徑, 然后將其轉(zhuǎn)化為蟻群算法的初始化信息素分布, 在復(fù)雜環(huán)境下, 該算法在效率和精度上均優(yōu)于煙花算法和蟻群算法。

3 總結(jié)與展望

通過修正勢場函數(shù)、引入AUV運(yùn)動(dòng)約束、考慮障礙物相對(duì)速度和復(fù)雜海流影響等, 使改進(jìn)后的人工勢場法克服了陷阱問題、局部極小值和目標(biāo)不可達(dá)等缺陷, 成為解決AUV水下實(shí)時(shí)避障問題的熱點(diǎn)研究方向。近年來水下實(shí)時(shí)避障技術(shù)取得了很多研究成果, 但也存在如動(dòng)態(tài)避障效果差、難以兼顧多目標(biāo)與多約束以及海流對(duì)避障干擾嚴(yán)重等亟待解決的技術(shù)難點(diǎn), 結(jié)合對(duì)各類水下實(shí)時(shí)避障算法的總結(jié)與分析, 針對(duì)上述技術(shù)難點(diǎn)的研究有望在以下幾方面取得突破。

1) 多種水下實(shí)時(shí)避障算法融合

針對(duì)水下復(fù)雜未知的動(dòng)態(tài)障礙物, 單一避障算法難以幫助AUV順利避障。因此學(xué)者們趨向于將多種水下實(shí)時(shí)避障算法進(jìn)行融合以改善避障效果, 實(shí)現(xiàn)多種水下實(shí)時(shí)避障算法的優(yōu)勢互補(bǔ), 充分發(fā)揮各自算法的優(yōu)點(diǎn)。例如, 田廣等[60]將行為運(yùn)動(dòng)學(xué)模型和模糊邏輯法相融合, 提高了AUV對(duì)未知環(huán)境的適應(yīng)能力; 孫兵等[58]通過PSO迭代優(yōu)化模糊控制器的設(shè)計(jì), 尋找水下局部路徑規(guī)劃的最優(yōu)解; 馬焱等[20]將煙花算法與蟻群算法相融合, 在復(fù)雜環(huán)境下仍能快速、高精度地尋找到最優(yōu)路徑。因此, 研究如何將多種水下實(shí)時(shí)避障算法進(jìn)行有效融合來實(shí)現(xiàn)各避障算法的優(yōu)勢互補(bǔ)是一個(gè)很有價(jià)值的研究方向。

2) 考慮能耗約束的避障算法研究

目前在水下實(shí)時(shí)避障算法的各種最優(yōu)目標(biāo)和約束條件中, 兼顧AUV能耗問題的研究成果較少[20], 羅頎棟[59]甚至通過延長避障路徑, 犧牲能耗的方式來提高水下避障的安全性。然而事實(shí)上, AUV的能耗問題是影響其續(xù)航能力的重要因素, 也是設(shè)計(jì)和優(yōu)化水下實(shí)時(shí)避障算法時(shí)必須考慮到的物理約束之一。在設(shè)計(jì)或改進(jìn)各種水下實(shí)時(shí)避障算法時(shí)都應(yīng)該將AUV的能耗問題考慮進(jìn)來。例如, 在利用模糊邏輯法實(shí)現(xiàn)水下實(shí)時(shí)避障時(shí), 可以設(shè)計(jì)關(guān)于AUV剩余能量的隸屬度函數(shù)并結(jié)合專家經(jīng)驗(yàn)給出規(guī)則表, 通過查表利用剩余能量來決定避障時(shí)AUV的線速度和角速度。為了減少避障過程中AUV所消耗的能量, 將其能耗作為參數(shù)引入水下實(shí)時(shí)避障算法會(huì)成為一個(gè)重要的研究方向。

3)考慮三維海流干擾的避障算法研究

AUV通常工作在復(fù)雜多變的海流中, 而海流會(huì)對(duì)其實(shí)時(shí)避障造成很大的影響, 因此在設(shè)計(jì)水下實(shí)時(shí)避障算法時(shí)需要將復(fù)雜海流對(duì)AUV的影響考慮進(jìn)來。李沛?zhèn)怺40]在利用人工勢場法解決水下避障問題時(shí)僅考慮了定常海流, 該算法無法適應(yīng)復(fù)雜多變的海流環(huán)境。王奎民等[41]將海流作用力添加到勢場力中, 分別采用定常流和渦流來分析AUV所受合力, 但只考慮了水平方向上流速恒定的海流, 即僅在二維平面內(nèi)對(duì)海流環(huán)境建模。Yao等[57]對(duì)障礙物附近的定常海流流場進(jìn)行了三維建模, 通過調(diào)整流場權(quán)重系數(shù)使AUV在某些情況下順著水流航行, 借此減少能耗或提高導(dǎo)航速度。朱大奇等[53]考慮三維空間下動(dòng)態(tài)時(shí)變海流對(duì)AUV實(shí)時(shí)避障的影響, 但該算法存在空間爆炸問題, 即由于空間柵格數(shù)量急劇上升所帶來的計(jì)算量增加, 影響了算法的實(shí)時(shí)性。隨著對(duì)水下實(shí)時(shí)避障算法的進(jìn)一步研究, 如何解決三維空間下復(fù)雜海流對(duì)AUV實(shí)時(shí)避障的干擾將成為水下實(shí)時(shí)避障研究的熱點(diǎn)方向之一。

[1] 李碩, 劉健, 徐會(huì)希, 等. 我國深海自主水下機(jī)器人的研究現(xiàn)狀[J]. 中國科學(xué): 信息科學(xué), 2018, 48(9): 1152-1164.Li Shuo, Liu Jian, Xu Hui-xi, et al. Research Status of Deep-Sea Autonomous Underwater Robot in China[J]. Chinese Science: Information Science, 2018, 48(9): 1152-1164.

[2] 鐘宏偉, 李國良, 宋林樺, 等. 國外大型無人水下航行器發(fā)展綜述[J]. 水下無人系統(tǒng)學(xué)報(bào), 2018, 26(4): 273- 282.Zhong Hong-wei, Li Guo-liang, Song Lin-hua, et al. A Review of the Development of Large-Scale Unmanned Underwater Vehicles Abroad[J]. Journal of Unmanned Undersea Systems, 2018, 26(4): 273-282.

[3] Han G, Long X, Zhu C, et al. A High-Availability Data Collection Scheme based on Multi-AUVs for Underwater Sensor Networks[J]. IEEE Transactions on Mobile Com- puting, 2020, 19(5): 1010-1022.

[4] LI D L, Wang P, Du L. Path Planning Technologies for Autonomous Underwater Vehicles-A Review[J]. IEEE Access, 2019, 7: 9745-9768.

[5] 潘光, 宋保維, 黃橋高, 等. 水下無人系統(tǒng)發(fā)展現(xiàn)狀及其關(guān)鍵技術(shù)[J]. 水下無人系統(tǒng)學(xué)報(bào), 2017, 25(2): 44-51. Pan Guang, Song Bao-wei, Huang Qiao-gao, et al. Development Status and Key Technologies of Underwater Unmanned System[J]. Journal of Unmanned Undersea System, 2017, 25(2): 44-51.

[6] Li J, Lee M, Lee W, et al. Real Time Obstacle Detection in a Water Tank Environment and its Experimental Study[C]//2014 IEEE/OES Autonomous Underwater Vehicles(AUV). Oxford, MS, USA: IEEE, 2014: 1-5.

[7] Xidias E, Zissis D. Real Time Autonomous Maritime Navigation Using Dynamic Visibility Graphs[C]//2018 IEEE/OES Autonomous Underwater Vehicle Workshop (AUV). Porto, Portugal: IEEE, 2018: 1-6.

[8] Huang C, Huang B, Zhang Y. An Improved A* Algorithm Applied to Three-Dimensional Space[C]//2019 IEEE 8th Jo- int International Information Technology and Artificial Intelligence Conference(ITAIC). Chongqing, China: IEEE, 2019.

[9] Lee J, Kim D W. An Effective Initialization Method for Genetic Algorithm-Based Robot Path Planning Using a Directed Acyclic Graph[J]. Information Sciences, 2016, 332: 1-18.

[10] Montiel O, Sepulveda R, Orozco-Rosas U. Optimal Path Planning Generation for Mobile Robots Using Parallel Evolutionary Artificial Potential Field[J]. Journal of Intelligent & Robotic Systems, 2015, 79(2): 237-257.

[11] 楊健, 孟凡塵. 基于人工勢場法的微小型AUV避障運(yùn)動(dòng)方法研究[J]. 水雷戰(zhàn)與艦船防護(hù), 2017, 25(4): 67-71.Yang Jian, Meng Fan-chen. Research on Obstacle Avoidance Method of Micro AUV Based on Artificial Potential Field Method[J]. Mine Warfare and Ship Protection, 2017, 25(4): 67-71.

[12] 李東方, 王超, 鄧宏彬, 等. 基于人工勢場和RRT算法的機(jī)器蛇水下三維避障算法[J]. 兵工學(xué)報(bào), 2017, 38(S1): 205-214.Li Dong-fang, Wang Chao, Deng Hong-bin, et al. Three Dimensional Obstacle Avoidance Algorithm Based on Artificial Potential Field and RRT Algorithm[J]. Journal of Military Engineering, 2017, 38(S1): 205-214.

[13] 吳正平, 唐念, 陳永亮, 等. 基于改進(jìn)人工勢場法的AUV路徑規(guī)劃[J]. 化工自動(dòng)化及儀表, 2014, 41(12): 1421-1423.Wu Zheng-ping, Tang Nian, Chen Yong-liang, et al. AUV Path Planning Based on Improved Artificial Potential Field Method[J]. Chemical automation and instrumentation, 2014, 41(12): 1421-1423.

[14] 程志, 張志安, 李金芝, 等. 改進(jìn)人工勢場法的移動(dòng)機(jī)器人路徑規(guī)劃[J]. 計(jì)算機(jī)工程與應(yīng)用, 2019, 55(23): 1-6.Cheng Zhi, Zhang Zhi-an, Li Jin-zhi, et al. Path Planning of Mobile Robot Based on Improved Artificial Potential Field Method[J]. Computer Engineering and Application, 2019, 55(23): 1-6.

[15] Duan H B, Huang L Z. Imperialist Competitive Algorithm Optimized Artificial Neural Networks for UCAV Global Path Planning[J]. Neurocomputing, 2014, 125: 166-171.

[16] 林政, 呂霞付. 基于改進(jìn)模糊算法的水面無人艇自主避障[J]. 計(jì)算機(jī)應(yīng)用, 2019, 39(9): 1-7.Lin Zheng, Lü Xia-fu. Autonomous Obstacle Avoidance of Surface Unmanned Vehicle Based on Improved Fuzzy Algorithm[J]. Computer application, 2019, 39(9): 1-7.

[17] 張禹, 邢志偉, 黃俊峰, 等. 遠(yuǎn)程自治水下機(jī)器人三維實(shí)時(shí)避障方法研究[J]. 機(jī)器人, 2003, 25(6): 481-485.Zhang Yu, Xing Zhi-wei, Huang Jun-feng, et al. Research on 3D Real-Time Obstacle Avoidance Method of Autonomous Underwater Vehicle[J]. Robot, 2003, 25(6): 481-485.

[18] 韓偉, 孫凱彪. 基于模糊人工勢場法的智能全向車路徑規(guī)劃[J]. 計(jì)算機(jī)工程與應(yīng)用, 2018, 54(6): 105-109, 167.Han Wei, Sun Kai-biao. Intelligent Omnidirectional Vehicle Path Planning Based on Fuzzy Artificial Potential Field Method[J]. Computer Engineering and Application, 2018, 54(6): 105-109, 167.

[19] 張汝波, 李建軍, 楊玉. 基于改進(jìn)蟻群算法的AUV航路避障任務(wù)規(guī)劃[J]. 華中科技大學(xué)學(xué)報(bào)(自然科學(xué)版), 2015, 43(S1): 428-430.Zhang Ru-bo, Li Jian-jun, Yang Yu. AUV Route Obstacle Avoidance Task Planning Based on Improved Ant Colony Algorithm[J]. Journal of Huazhong University of Science and Technology(Natural Science Edition), 2015, 43(S1): 428-430.

[20] 馬焱, 肖玉杰, 陳軼, 等. 基于改進(jìn)煙花-蟻群算法的海流環(huán)境下水下無人潛航器的避障路徑規(guī)劃[J]. 導(dǎo)航與控制, 2019, 18(1): 51-59.Ma Yi, Xiao Yu-jie, Chen Yi, et al. Obstacle Avoidance Path Planning of Underwater Vehicle Based on Improved Fireworks Ant Colony Algorithm[J]. Navigation and Control, 2019, 18(1): 51-59.

[21] 陳文淵, 沈斌堅(jiān). 基于三維成像聲納技術(shù)的AUV前視避障方法[J]. 傳感器與微系統(tǒng), 2015, 34(4): 12-15.Chen Wen-yuan, Shen Bin-jian. Obstacle Avoidance Me- thod of AUV Based on 3D Imaging Sonar Technology[J]. Sensors and Microsystems, 2015, 34(4): 12-15.

[22] 段群杰. 水下機(jī)器人實(shí)時(shí)路徑規(guī)劃方法研究[D]. 哈爾濱: 哈爾濱工程大學(xué), 2007.

[23] Endo G, Togawa K, Hirose S. Study on Self-Contained and Terrain Adaptive Active Cord Mechanism[C]//Pro- ceedings of the 1999 IEEE/RSJ International Conference on Intelligent Robots and Systems(Cat. No.99CH36289). Kyongju, South Korea: IEEE, 1999: 1399-1405.

[24] Dijkstra E W. A Note on Two Problems in Connection with Graphs[J]. Numerische Mathematics, 1959, 1(1): 269-271.

[25] Hart P E, Nilsson N J, Raphael B. A Formal Basis for the Heuristic Determination of Minimum Cost Paths[J]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2): 100-107.

[26] Howden W E. Solution Plans and Interactive Problem Solving[J]. Computers & Graphics, 1975, 1(1): 21-26.

[27] Lozano-Pérez T, Wesley M A. An Algorithm for Planning Collision-Free Paths among Polyhedral Obstacles[J]. Communications of the Acm, 1979, 22(10): 560-570.

[28] Gowda I, Kirkpatrick D, Lee D, et al. Dynamic Voronoi diagrams[J]. IEEE Transactions on Information Theory, 1983, 29(5): 724-731.

[29] Takahashi O, Schilling R J. Motion Planning in a Plane Using Generalized Voronoi Diagrams[J]. IEEE Transactions on Robotics and Automation, 1989, 5(2): 143-150.

[30] Liu Y H, Arimoto S. Finding the Shortest Path of a Disc Among Polygonal Obstacles Using a Radius-Independent Graph[J]. IEEE Transactions on Robotics and Automation, 1995, 11(5): 682-691.

[31] Khatib O. Real-time Obstacle Avoidance for Manipulators and Mobile Robots[J]. The International Journal of Robotics Research, 1986, 5(1): 90-98.

[32] Borenstein J, Koren Y. The Vector Field Histogram-Fast Obstacle Avoidance for Mobile Robots[J]. IEEE Tran- sactions on Robotics & Automation, 2002, 7(3): 278-288.

[33] Ulrich I, Borenstein J. VFH+: Reliable Obstacle Avoidance for Fast Mobile Robots[C]//Proceedings of the 1998 IEEE International Conference on Robotics and Automation. Leuven, Belgium: IEEE, 1998: 1572-1577.

[34] Kennedy J, Eberhart R. Particle Swarm Optimization[C]// Proceedings of ICNN’95-International Conference on Neural Networks. Perth, WA, Australia: IEEE, 1995: 1942-1948.

[35] Kuffner J J, Lavalle S M. RRT-connect: An Efficient Approach to Single-Query Path Planning[J]. IEEE International Conference on Robotics & Automation, 2000, 2(1): 995-1001.

[36] 高云峰, 黃海. 復(fù)雜環(huán)境下基于勢場原理的路徑規(guī)劃方法[J]. 機(jī)器人, 2004, 26(2): 114-118.Gao Yun-feng, Huang Hai. Path Planning Method Based on Potential Field Principle in Complex Environment[J]. Robot, 2004, 26(2): 114-118.

[37] 劉學(xué)敏, 李英輝, 徐玉如. 基于運(yùn)動(dòng)平衡點(diǎn)的水下機(jī)器人自主避障方式[J]. 機(jī)器人, 2001, 23(3): 270-274.Liu Xue-min, Li Ying-hui, Xu Yu-ru. Autonomous Obstacle Avoidance of Underwater Robot Based on Motion Balance Point[J]. Robot, 2001, 23(3): 270-274.

[38] 孫玉山, 張英浩, 常文田, 等. 基于改進(jìn)運(yùn)動(dòng)平衡點(diǎn)的水下機(jī)器人自主避障方法研究[J]. 中國造船, 2013, 54 (2): 17-25.Sun Yu-shan, Zhang Ying-hao, Chang Wen-tian, et al. Research on Autonomous Obstacle Avoidance Method of Underwater Robot Based on Improved Motion Balance Point[J]. China Shipbuilding, 2013, 54(2): 17-25.

[39] 李東方, 李科偉, 鄧宏彬, 等. 基于人工勢場與IB- LBM的機(jī)器蛇水中2D避障控制算法[J]. 機(jī)器人, 2018, 40(3): 346-359.Li Dong-fang, Li Ke-wei, Deng Hong-bin, et al. 2D Obstacle Avoidance Control Algorithm in Snake Water Based on Artificial Potential Field and IB-LBM[J]. Robot, 2018, 40(3): 346-359.

[40] 李沛?zhèn)? 楊啟. 基于改進(jìn)人工勢場法的水下滑翔機(jī)路徑規(guī)劃[J]. 艦船科學(xué)技術(shù), 2019, 41(7): 89-93.Li Pei-lun, Yang Qi. Underwater Glider Path Planning Based on Improved Artificial Potential Field Method[J]. Ship Science and Technology, 2019, 41(7): 89-93.

[41] 王奎民, 趙玉飛, 侯恕萍, 等. 一種改進(jìn)人工勢場的UUV動(dòng)礙航物規(guī)避方法[J]. 智能系統(tǒng)學(xué)報(bào), 2014, 9(1): 47-52.Wang Kui-min, Zhao Yu-fei, Hou Shu-ping, et al. A Method to Improve UUV Obstacle Avoidance of Artificial Potential Field[J]. Journal of Intelligent Systems, 2014, 9(1): 47-52.

[42] 姚鵬, 解則曉. 基于修正導(dǎo)航向量場的AUV自主避障方法[J/OL]. 自動(dòng)化學(xué)報(bào). https://kns.cnki.net/KCMS/ detail/11.2109.TP.20190219.1551.005.html, 2019-02-19.Yao Peng, Jie Ze-xiao. AUV Autonomous Obstacle Avoi- dance Method Based on Modified Navigation Vector Field[J]. Acta Automatica Sinica. https://kns.cnki.net/KC MS/detail/11. 2109.TP.20190219.1551.005.html, 2019-02-19.

[43] Anwary A R, Lee Y, Jung H, et al. Unsupervised Real-time Obstacle Avoidance Technique Based on a Hybrid Fuzzy Method for AUVs[J]. International Journal of Fuzzy Logic and Intelligent Systems, 2008, 8(1): 82-86.

[44] Sun B, Zhu D Q, Jiang L S, et al. A Novel Fuzzy Control Algorithm for Three-Dimensional AUV Path Planning Based on Sonar Model[J]. Journal of Intelligent & Fuzzy Systems, 2014, 26(6): 2913-2926.

[45] Sun B, Zhu D Q, Yang S X. An Optimized Fuzzy Control Algorithm for Three-Dimensional AUV Path Planning[J]. In- ternational Journal of Fuzzy Systems, 2018, 20(2): 597-610.

[46] Sahu B K, Subudhi B. Flocking Control of Multiple AUVs Based on Fuzzy Potential Functions[J]. IEEE Transactions on Fuzzy Systems, 2018, 26(5): 2539-2551.

[47] Ghatee M, Mohades A. Motion Planning in Order to Optimize the Length and Clearance Applying a Hopfield Neural Network[J]. Expert Systems with Applications, 2009, 36: 4688-4695.

[48] Tavares J. Bio-inspired Algorithms for the Vehicle Routing Problem(Studies in Computational Intelligence)[M]. Berlin: Springer, 2009.

[49] Yan M Z, Zhu D Q. An Algorithm of Complete Coverage Path Planning for Autonomous Underwater Vehicles[J]. Key Engineering Materials, 2011, 467-469: 1377-1385.

[50] Li S, Guo Y. Neural-network based AUV Path Planning in Estuary Environments[C]//Proceedings of the 10th World Congress on Intelligent Control and Automation. Beijing, China: 10th World Congress on Intelligent Control and Automation, 2012: 3724-3730.

[51] 朱大奇, 孫兵, 李利. 基于生物啟發(fā)模型的AUV三維自主路徑規(guī)劃與安全避障算法[J]. 控制與決策, 2015, 30(5): 798-806.Zhu Da-qi, Sun Bing, Li Li. AUV 3D Autonomous Path Planning and Obstacle Avoidance Algorithm Based on Bioheuristic Model[J]. Control and decision, 2015, 30(5): 798-806.

[52] Huang Z R, Zhu D Q, Sun B. A Multi-AUV Cooperative Hunting Method in 3-D Underwater Environment with Obstacle[J]. Engineering Applications of Artificial Intel- ligence, 2016, 50: 192-200.

[53] 朱大奇, 劉雨, 孫兵, 等. 自治水下機(jī)器人的自主啟發(fā)式生物啟發(fā)神經(jīng)網(wǎng)絡(luò)路徑規(guī)劃算法[J]. 控制理論與應(yīng)用, 2019, 36(2): 183-191.Zhu Da-qi, Liu Yu, Sun Bing, et al. Autonomous Heuristic Bioheuristic Neural Network Path Planning Algorithm for Autonomous Underwater Vehicles[J]. Control Theory and Application, 2019, 36(2): 183-191.

[54] Liu H, Xu B, Lu D J, et al. A Path Planning Approach for Crowd Evacuation in Buildings Based on Improved Artificial Bee Colony Algorithm[J]. Applied Sofit Computing, 2018, 68: 360-376.

[55] Wei K, Ren B Y. A Method on Dynamic Path Planning for Robotic Manipulator Autonomous Obstacle Avoidance Based on an Improved RRT Algorithm[J]. Sensors, 2018, 18(2): 571.

[56] Patle B K, Pandey A, Jagadeesh A, et al. Path Planning in Uncertain Environment by Using Firefly Algorithm[J]. Defence Technology, 2018(14): 691-701.

[57] Yao P, Zhao S. Three-Dimensional Path Planning for AUV Based on Interfered Fluid Dynamical System Under Ocean Current[J]. IEEE Access, 2018, 6: 42904-42916.

[58] 孫兵, 朱大奇, 楊元元. 基于粒子群優(yōu)化的自治水下機(jī)器人模糊路徑規(guī)劃[J]. 高技術(shù)通訊, 2013, 23(12): 1284-1291.Sun Bing, Zhu Da-qi, Yang Yuan-yuan. Fuzzy Path Planning of Autonomous Underwater Vehicle Based on Particle Swarm Optimization[J]. High Tech Communication, 2013, 23(12): 1284-1291.

[59] 羅頎棟. 水下球形機(jī)器人的運(yùn)動(dòng)控制方法研究[D]. 北京: 北京郵電大學(xué), 2017.

[60] 田廣, 劉和祥, 趙海鷹, 等. 自治式水下機(jī)器人避障行為機(jī)制研究[J]. 傳感器與微系統(tǒng), 2009, 28(12): 59-63.Tian Guang, Liu He-xiang, Zhao Hai-ying, et al. Research on Obstacle Avoidance Mechanism of Autonomous Underwater Vehicle[J]. Sensors and Microsystems, 2009, 28 (12): 59-63.

Research Progress of Real-Time Obstacle Avoidance Algorithms for Unmanned Undersea Vehicle: A Review

GUO Yin-jing1,2, BAO Jian-kang3, LIU Qi1, QU Yan-xi1, Lü Wen-hong4

(1. College of Electronic Information Engineering, Shandong University of Science and Technology, Qingdao 266590, China; 2. Qingdao Intelligent Ocean Technology Co., Qingdao 266590, China; 3. College of Electrical Engineering and Automation, Shandong University of Science and Technology, Qingdao 266590, China; 4. College of Transportation, Shandong University of Science and Technology, Qingdao 266590, China)

Aiming at the difficulties and trends in the research of autonomous undersea vehicle(AUV) real-time obstacle avoidance algorithms, the difficulties in the research of underwater real-time obstacle avoidance algorithm are analyzed from three aspects of dynamic obstacles, multiple constraints and multiple objectives, and ocean current disturbance. Then, the research progress of underwater real-time obstacle avoidance algorithm is focused on the three aspects, i.e. artificial potential field method, fuzzy logic method, and intelligent bionic algorithm.By comparing the current researches on three kinds of obstacle avoidance algorithms, it is known that the improved artificial potential field method overcomes the problems of trap, local minimum, and goal unreachability, and becomes the key research direction to solve the real-time obstacle avoidance problem of unmanned undersea vehicle by modifying the potential field function, introducing the AUV motion constraint, considering the relative speed of obstacles and the influence of complex ocean current, etc.In the aspect of avoiding dynamic obstacles, the fusion of multiple obstacle avoidance algorithms will become a trend. As for the multi-constraint and multi-objective problem, energy consumption is particularly important but is rarely introduced into obstacle avoidance algorithm as a parameter, which has great research potential. For the ocean current disturbance, the majority of real-time obstacle avoidance algorithms only consider steady flow or eddy current in the horizontal direction, thus, consideration of the three-dimensional ocean current disturbance will also become one of the research directions of underwater real-time obstacle avoidance algorithm in the future.

autonomous undersea vehicle(AUV); real-time obstacle avoidance algorithm; artificial potential field; fuzzy logic; bionic

U674.941; TJ630.33

A

2096-3920(2020)04-0351-08

10.11993/j.issn.2096-3920.2020.04.001

2019-10-24;

2019-12-15.

山東省重點(diǎn)研發(fā)計(jì)劃(公益類專項(xiàng))項(xiàng)目(2018GHY115022); 國家自然科學(xué)基金(61471224).

郭銀景(1966-), 男, 博士, 教授, 主要研究方向?yàn)闊o線通信、AUV導(dǎo)航與控制.

郭銀景, 鮑建康, 劉琦, 等. AUV實(shí)時(shí)避障算法研究進(jìn)展[J]. 水下無人系統(tǒng)學(xué)報(bào), 2020, 28(4): 351-358.

(責(zé)任編輯: 陳 曦)