顧加燁,齊 亮

(江蘇科技大學(xué) 電子信息學(xué)院, 江蘇 鎮(zhèn)江 212100)

海洋環(huán)境復(fù)雜多變,很多任務(wù)需要自主水下機(jī)器人(autonomous underwater vehicle,AUV)執(zhí)行。路徑規(guī)劃是實(shí)現(xiàn)AUV自主航行和作業(yè)的重要環(huán)節(jié),可靠的路徑規(guī)劃算法是保障機(jī)器人安全可靠工作的關(guān)鍵。海洋中存在很多不能精確測定的因素影響AUV的航行,因此如何在不確定海流和危險(xiǎn)源條件下規(guī)劃出安全、快速、節(jié)能的可行路徑成為當(dāng)下研究的重點(diǎn)。

目前常規(guī)的規(guī)劃算法已經(jīng)很成熟,常用的有A*算法[1]、群智能算法[2]和混合算法[3]等,但很多未考慮海流等因素,所以規(guī)劃的路徑在實(shí)際運(yùn)行中魯棒性并不強(qiáng)。有些算法考慮海流對AUV能耗的影響[4-5],但未考慮海流的變化和其他不確定障礙物的影響。李二超等[6]考慮不確定危險(xiǎn)源對二維移動(dòng)機(jī)器人路徑規(guī)劃的影響。嚴(yán)浙平等[7]考慮了導(dǎo)航信息的不確定性以及海流的時(shí)變性。Li等[8]提出基于區(qū)間優(yōu)化算法解決障礙物不確定問題,但未考慮海流不確定性的影響。姚緒梁等[9]提出基于區(qū)間優(yōu)化的解決不確定海流問題的路徑規(guī)劃算法,但實(shí)際是將不確定優(yōu)化問題轉(zhuǎn)化為確定性問題,在轉(zhuǎn)化過程中,并未考慮不確定危險(xiǎn)源等其他不確定約束條件,不可避免地會(huì)損失一些有價(jià)值的信息。郭興海等[10]假設(shè)不確定障礙物和海流的變化從高斯分布,提出利用高斯噪聲模型對海流進(jìn)行估計(jì),使AUV適應(yīng)海流的變化。但實(shí)際上很難確定海流是否服從該分布,且海流速度的平均值和方差在實(shí)際中難以確定。張勇[11]提出了基于區(qū)間的非支配排序與擁擠距離的多目標(biāo)優(yōu)化算法解決不確定危險(xiǎn)源下的路徑規(guī)劃問題,但未考慮其他約束。上述方法均未綜合考慮多個(gè)不同規(guī)劃目標(biāo)的不確定性帶來的影響。

本文針對海流和危險(xiǎn)源信息的不確定性,將海流和危險(xiǎn)源的不確定性表示為區(qū)間數(shù),利用基于區(qū)間可能度的非支配占優(yōu)排序和基于區(qū)間的擁擠距離,結(jié)合量子粒子群算法優(yōu)化路徑,提出一種區(qū)間多目標(biāo)量子粒子群算法(interval multi-objective quantum-behaved particle swarm optimization,IMOQPSO)。仿真驗(yàn)證表明,該算法可以在真實(shí)的海流數(shù)據(jù)下得到符合多個(gè)不確定目標(biāo)約束的Pareto解集,所規(guī)劃的路徑具有較好的分布性。

1 問題描述與環(huán)境建模

1.1 問題描述

待解決問題:在含有不確定海流和多個(gè)不確定危險(xiǎn)源的環(huán)境中,為AUV規(guī)劃從起點(diǎn)到終點(diǎn)的最優(yōu)或近似最優(yōu)路徑。不確定海流是指海流的大小和方向不是精確的值而是區(qū)間數(shù),不確定危險(xiǎn)源是指危險(xiǎn)源的威脅范圍已知但具體位置未知,危險(xiǎn)程度也是區(qū)間數(shù)。

1.2 路徑形式

常用的柵格中心點(diǎn)連線的方式構(gòu)造的路徑會(huì)導(dǎo)致路徑出現(xiàn)很多大角度轉(zhuǎn)向,不符合AUV的實(shí)際控制規(guī)律,且產(chǎn)生了更多的能量消耗,所以需要使用曲線來構(gòu)造路徑。B樣條曲線只需要一些控制點(diǎn)就可以定義擁有復(fù)雜曲率的曲線,它具有局部支撐性,曲線上單個(gè)節(jié)點(diǎn)的變化不會(huì)對曲線的整體產(chǎn)生影響,符合路徑規(guī)劃的要求。

使用準(zhǔn)均勻三次B樣條曲線構(gòu)造三維路徑[12],將路徑編碼為B樣條曲線的一系列包括起點(diǎn)和終點(diǎn)的控制點(diǎn),依據(jù)B樣條曲線的生成規(guī)則,通過公式計(jì)算即可得到實(shí)際的路徑點(diǎn)。連接這些路徑點(diǎn)可以得到平滑路徑,如圖1所示。

圖1 B樣條曲線構(gòu)造的三維路徑曲線

1.3 不確定海流模型

海流是指海水在大范圍里相對穩(wěn)定的流動(dòng),是海水運(yùn)動(dòng)的普遍形式之一。海流的大小和方向信息等可以通過雷達(dá)測量和衛(wèi)星觀測等手段獲得,小范圍觀測使用各式海流計(jì)和浮標(biāo)等。但是,由于設(shè)備精度有限和海洋環(huán)境的多變,這些海流觀測精確度不高,只能用一個(gè)矢量代表一定范圍的海流數(shù)據(jù)。因此在考察海流對AUV影響時(shí),需要將海流的速度和方向作為區(qū)間數(shù)來計(jì)算,忽略影響較小的垂直流。設(shè)海流矢量為c,水平方向的速度大小為cv,方向角度為cd,φ和θ為海流大小和方向角的不確定性水平,則海流區(qū)間的上下限表達(dá)式為:

(1)

圖2 區(qū)間海流模型示意圖

1.4 不確定危險(xiǎn)源模型

盡管已知一些固定的障礙,但仍存在許多位置信息不確定的危險(xiǎn)源(如敵方探測器等),這時(shí)針對確定障礙所規(guī)劃的路徑很可能失效[13]。在路徑與危險(xiǎn)源不確定范圍相交和不相交這2種情況下,路徑和不確定危險(xiǎn)源距離的可能最大值與可能最小值如圖3所示。左邊表示路徑不直接經(jīng)過危險(xiǎn)源的不確定范圍,右邊表示路徑穿過危險(xiǎn)源的活動(dòng)區(qū)域。

圖3 路徑與不確定危險(xiǎn)源的關(guān)系示意圖

設(shè)第i個(gè)不確定危險(xiǎn)點(diǎn)Di的位置信息不精確,其活動(dòng)范圍在一個(gè)球面Ωi內(nèi)。設(shè)球心為Oi,半徑為ri,則路徑與危險(xiǎn)源距離最近的點(diǎn)pi到危險(xiǎn)源的可能最短距離為:

(2)

2種情況下的最長可能距離均為:

(3)

1.5 海洋環(huán)境模型

建立完整的海洋環(huán)境模型如圖4所示。海流為分層結(jié)構(gòu),一個(gè)海流矢量代表一個(gè)柵格范圍內(nèi)的海流流向和速度大小。使用來自國家地球系統(tǒng)科學(xué)數(shù)據(jù)中心的南海海洋再分析產(chǎn)品數(shù)據(jù)集,包含島嶼及海流等常規(guī)海洋物理變量。選取的海圖范圍為1°N～5°N、123°E～127°E,圖中黃色為島嶼,藍(lán)色為深度較大的海底,橙色圓形部分為不確定危險(xiǎn)源范圍,每塊小區(qū)域的海流用不同長度和方向的箭頭表示。

圖4 海洋環(huán)境模型示意圖

2 航行時(shí)間與危險(xiǎn)度計(jì)算

2.1 航行時(shí)間計(jì)算

每個(gè)粒子編碼為一組包括起點(diǎn)和終點(diǎn)的B樣條曲線的控制點(diǎn),再利用B樣條曲線生成算法,生成一系列路徑點(diǎn)集合x1,x2,…,xn。其中x1和xn分別為路徑的起點(diǎn)和終點(diǎn),用直線連接起來得到路徑X為:

(4)

AUV沿路徑航行所消耗的時(shí)間為在各子路徑xixi+1上消耗的時(shí)間之和:

(5)

(6)

2.2 路徑危險(xiǎn)度計(jì)算

由式(2)(3)可以得到2種情況下路徑點(diǎn)與危險(xiǎn)源的可能最大距離和可能最小距離。從規(guī)避可能的危險(xiǎn)角度來說,路徑點(diǎn)距離危險(xiǎn)源的距離越遠(yuǎn)越好,但有時(shí)完全繞開意味著更長的路程或者逆海流行駛,所以在計(jì)算時(shí),給危險(xiǎn)源設(shè)定一個(gè)絕對危險(xiǎn)距離lmin和安全距離lmax。小于絕對危險(xiǎn)距離則意味著絕對危險(xiǎn),大于最大威脅距離則代表此危險(xiǎn)源對該路徑?jīng)]有威脅,介于兩者之間時(shí),危險(xiǎn)程度與距離成反比。路徑上單個(gè)點(diǎn)p相對第i個(gè)危險(xiǎn)源Di的危險(xiǎn)度可以用式(7)計(jì)算[11]:

(7)

3 基于區(qū)間的多目標(biāo)路徑規(guī)劃算法

3.1 基于區(qū)間可能度模型的占優(yōu)關(guān)系

區(qū)間可能度模型的構(gòu)造方法分為2類:一類為區(qū)間序關(guān)系,只能定性地判斷區(qū)間之間的優(yōu)劣;另一類為區(qū)間可能度,可以定量地比較區(qū)間的優(yōu)劣程度。其中,區(qū)間序關(guān)系的比較方法包括基于區(qū)間上下界的偏好和基于區(qū)間中點(diǎn)和半徑的偏好,它們都無法量化區(qū)間的優(yōu)劣程度,不便于后期排序比較并且存在某些重疊區(qū)間無法比較的情況。

現(xiàn)有的區(qū)間可能度構(gòu)造方式本質(zhì)是等價(jià)的,可表述為:

(8)

其中AI和BI分別為兩個(gè)需要比較的區(qū)間。

(9)

(10)

則說明X2的航行時(shí)間區(qū)間和危險(xiǎn)度區(qū)間都小于X1,所以路徑X2占優(yōu)X1,記為X2?X1。

3.2 基于區(qū)間的擁擠距離

為了獲得分布均勻的Pareto前沿,需要計(jì)算進(jìn)化個(gè)體之間的擁擠距離以進(jìn)一步區(qū)分經(jīng)過非支配排序后具有相同序值的進(jìn)化個(gè)體。由于本文適應(yīng)度都是區(qū)間,原有的確定性多目標(biāo)優(yōu)化中的計(jì)算擁擠度的方式不再適用,所以采用基于區(qū)間的擁擠距離計(jì)算方法。圖5展示了幾條路徑的目標(biāo)函數(shù)超體之間的距離情況。橫軸表示航行時(shí)間,縱軸表示危險(xiǎn)程度,φ(X1,X2)為兩條路徑的重疊度。

圖5 路徑在目標(biāo)空間的距離關(guān)系

(11)

路徑個(gè)體X1的目標(biāo)函數(shù)超體的體積V(X1)為2個(gè)適應(yīng)度區(qū)間的寬度的乘積:

(12)

從圖5中可以看出,2個(gè)路徑的重疊度φ越大,則它們的距離越近;在2個(gè)路徑?jīng)]有重疊時(shí),它們的距離仍然與2個(gè)超體的V成反比,與中心點(diǎn)之間的距離成正比。因此路徑X1和X2之間的距離可以表示為:

d(X1,X2)=

(13)

其中,m(TI)和m(HI)分別為區(qū)間TI和HI的中點(diǎn),分子為2個(gè)路徑目標(biāo)函數(shù)超體中心點(diǎn)的歐拉距離。假設(shè)根據(jù)計(jì)算,與路徑X1距離最近的2條路徑分別為X2和X3,則X1的擁擠距離為:

(14)

3.3 區(qū)間多目標(biāo)路徑規(guī)劃算法

結(jié)合上述區(qū)間占優(yōu)排序與區(qū)間擁擠度定義與QPSO算法,可以得到基于區(qū)間的多目標(biāo)量子粒子群算法,將其應(yīng)用于AUV路徑規(guī)劃的步驟如下:

步驟1建立海洋環(huán)境模型并初始化模型參數(shù)。初始化模型參數(shù),包括航行范圍、AUV航行速度、不確定危險(xiǎn)源的不確定范圍、不確定海流的范圍、路徑粒子的數(shù)目、迭代次數(shù)、擴(kuò)張收縮因子α。

步驟2 編碼粒子。將粒子編碼為B樣條曲線控制點(diǎn)坐標(biāo)組成的序列,設(shè)定每個(gè)控制點(diǎn)的搜索范圍。在搜索范圍內(nèi)隨機(jī)初始化每條路徑。根據(jù)B樣條曲線生成規(guī)則,由控制點(diǎn)生成具體的路徑點(diǎn)。

步驟4 根據(jù)QPSO算法[16]的粒子位置更新公式更新所有路徑粒子位置:

(15)

步驟5計(jì)算更新后的每條路徑的航行時(shí)間區(qū)間和危險(xiǎn)度區(qū)間?；趨^(qū)間占優(yōu)關(guān)系更新個(gè)體歷史最優(yōu)位置yi(t)。

步驟6對更新后的所有路徑粒子進(jìn)行占優(yōu)排序,選擇占優(yōu)等級最高的粒子存入外部儲(chǔ)備集。

步驟7對外部儲(chǔ)備集中的粒子進(jìn)行占優(yōu)排序,刪除被支配的粒子。

步驟8對占優(yōu)等級較低的粒子進(jìn)行單點(diǎn)變異操作,隨機(jī)選擇除兩端點(diǎn)外的其他控制點(diǎn),在一定區(qū)域內(nèi)對該點(diǎn)坐標(biāo)進(jìn)行隨機(jī)變化。

步驟9若外部儲(chǔ)備集中粒子數(shù)目大于規(guī)定數(shù)目,則利用區(qū)間擁擠距離公式計(jì)算外部儲(chǔ)備集中的粒子擁擠度,選取一定數(shù)目的粒子存入外部儲(chǔ)備集,否則直接執(zhí)行步驟10。

步驟11判斷迭代次數(shù)是否達(dá)到設(shè)定次數(shù),若未達(dá)到迭代次數(shù)則轉(zhuǎn)至步驟4;若達(dá)到設(shè)定次數(shù)則將外部儲(chǔ)備集中的各路徑作為最終結(jié)果。

4 仿真分析

為驗(yàn)證方案可行性,使用Matlab 2016b對算法進(jìn)行仿真,仿真平臺(tái)的配置為:Intel i5-10210U處理器,1.6 GHz主頻,內(nèi)存16 GB。

4.1 仿真參數(shù)設(shè)置

選取AUV的推進(jìn)速度為0.9 m/s。海流的方向不確定性θ為20°,海流大小不確定性φ為0.2倍的海流大小。不確定危險(xiǎn)源的不確定半徑為 5 km,安全距離lmax為20 km,絕對危險(xiǎn)距離lmin為1 km。航行的起點(diǎn)和終點(diǎn)分別為(1.25°N,123.25°E)和(3.91°N,126.11°E)。根據(jù)多次仿真實(shí)驗(yàn)比較,最終選取粒子數(shù)目為30,收縮擴(kuò)張因子α隨著迭代次數(shù)減小。實(shí)驗(yàn)顯示,迭代600次后路徑變化趨于穩(wěn)定。

4.2 規(guī)劃結(jié)果分析

算法規(guī)劃出的Pareto前沿如圖6所示。彩色矩形代表各條路徑在2個(gè)目標(biāo)空間上的適應(yīng)度,縱軸為危險(xiǎn)度,橫軸為航行消耗的時(shí)間。從圖6中可以看出,最終前沿路徑的適應(yīng)度區(qū)間較為分散,表明基于區(qū)間的擁擠距離策略達(dá)到了預(yù)期的效果,每條路徑都在航行時(shí)間與危險(xiǎn)度之間互不占優(yōu)。路徑危險(xiǎn)度最小達(dá)到0,最大為0.94,因此沒有產(chǎn)生絕對危險(xiǎn)的路徑。決策時(shí)可以根據(jù)實(shí)際需要選擇合適的路徑。

圖6 Pareto前沿示意圖

圖7是路徑規(guī)劃結(jié)果圖。左下方圓標(biāo)為路徑的起點(diǎn),右上方星標(biāo)為路徑終點(diǎn),橙色球體代表不確定危險(xiǎn)源的活動(dòng)范圍,紅色曲線為規(guī)劃得到的路徑。表層海流在北緯3°以南大致是從西向東,以北是從東向西流;底層海流在東經(jīng)125°以東為從南向北流動(dòng)。

圖7 路徑規(guī)劃結(jié)果

從圖7中可以看出,算法規(guī)劃的路徑具有多樣性,其中既有穿過危險(xiǎn)源的快速路徑,也有繞開危險(xiǎn)源的安全路徑,各路徑之間較為分散,表明得到的Pareto前沿的分布性較好。為了進(jìn)一步說明規(guī)劃的效果,外部儲(chǔ)備集中所有路徑的航行時(shí)間和危險(xiǎn)程度如表1所示。

表1 本文算法規(guī)劃結(jié)果數(shù)據(jù)

從表1中可以看到,路徑3的航行時(shí)間最長達(dá)到524.594 2 km,但航行時(shí)間小于路徑長度只有493.677 3 km的路徑1,這是因?yàn)楹叫袝r(shí)間與路線長短并不完全對應(yīng),而與是否借助海流有關(guān)。航行時(shí)間區(qū)間的寬度也與海流有關(guān),經(jīng)過海流影響大的區(qū)域會(huì)導(dǎo)致不確定性增加,如航行時(shí)間下限最小的路徑2,其區(qū)間寬度達(dá)到了126.450 9,這是因?yàn)槁窂?順海流航行,節(jié)約了時(shí)間,同時(shí)由于直接穿過了危險(xiǎn)區(qū)域,其危險(xiǎn)度也最高。路徑1為無危險(xiǎn)路徑,由于路徑1繞開了所有危險(xiǎn)源,也繞開了有利海流,所以其航行時(shí)間最長,達(dá)到了558.128 8×103s。危險(xiǎn)度很低的路徑2,其最大航行時(shí)間也是最長的。其他路徑在危險(xiǎn)度和航行時(shí)間之間做了折中。

4.3 規(guī)劃器性能對比驗(yàn)證

為進(jìn)一步驗(yàn)證區(qū)間算法的有效性,將本文算法與不考慮不確定性的常規(guī)多目標(biāo)優(yōu)化算法進(jìn)行比較。首先,直接使用海流的測量值作為準(zhǔn)確值,危險(xiǎn)源的不確定半徑設(shè)為0,使用多目標(biāo)量子粒子群算法進(jìn)行路徑規(guī)劃,規(guī)劃結(jié)果如表2所示。從表2可知,確定海流和確定危險(xiǎn)源情況下規(guī)劃的路徑,最小航行時(shí)間為323.918 7×103s,大于表1中的最小航行時(shí)間,但最大航行時(shí)間359.974 1×103s要遠(yuǎn)小于不確定條件下的最大航行時(shí)間558.128 8×103s,同時(shí)危險(xiǎn)程度的最大值0.841 9也小于表1中的最大值,出現(xiàn)這種情況的原因是不確定條件下規(guī)劃的不確定程度同步增大。

表2 多目標(biāo)量子粒子群規(guī)劃結(jié)果數(shù)據(jù)

在海流區(qū)間范圍和危險(xiǎn)源不確定范圍內(nèi)按正態(tài)分布隨機(jī)生成1 000個(gè)規(guī)劃環(huán)境,均值取測量值,方差按3σ原則分別取海流和危險(xiǎn)源不確定范圍的1/3。分別記錄本文算法規(guī)劃出的路徑、常規(guī)的多目標(biāo)量子粒子群算法規(guī)劃出的路徑在隨機(jī)環(huán)境下的航行時(shí)間和危險(xiǎn)度結(jié)果,如表3、4所示。

綜合比較表3和表4可以看出,雖然常規(guī)的多目標(biāo)優(yōu)化算法規(guī)劃得路徑在最小航行時(shí)間上平均比本文算法所規(guī)劃的路徑減少了16%,但由于未考慮海流的不確定性,最大航行時(shí)間出現(xiàn)了無窮大情況,即在變化后的海流沖擊下,AUV無法繼續(xù)沿原航路前進(jìn)。此外,常規(guī)算法所規(guī)劃的路徑在危險(xiǎn)度的最大和最小值上相比本文算法規(guī)劃的路徑平均分別高了8.4%和6%,且出現(xiàn)了危險(xiǎn)度為1的不可行路徑,這同樣是由于規(guī)劃時(shí)沒有考慮危險(xiǎn)源位置的不確定性,沒有做好提前規(guī)劃。在不可行次數(shù)方面,常規(guī)算法規(guī)劃的路徑中有4條路徑都產(chǎn)生了大量不可行路徑,而使用區(qū)間優(yōu)化算法規(guī)劃的路徑在規(guī)劃時(shí)已經(jīng)規(guī)避了最壞情況,所以沒有產(chǎn)生不可行路徑。上述測試結(jié)果表明,相較于不考慮不確定性的規(guī)劃算法,本文所提出的算法具有較好的魯棒性,在海流和危險(xiǎn)源發(fā)生變化后,仍具有較好的可行性。

表3 本文算法所得路徑的隨機(jī)測試結(jié)果

表4 多目標(biāo)量子粒子群算法路徑的隨機(jī)測試結(jié)果

5 結(jié)論

針對AUV的航行環(huán)境中存在多種不確定約束的情況,利用區(qū)間可能度模型等區(qū)間優(yōu)化方法將量子粒子群算法中粒子的適應(yīng)度值的計(jì)算和比較改進(jìn)為適應(yīng)度區(qū)間的計(jì)算和比較,并結(jié)合非支配占優(yōu)排序算法,使得到的區(qū)間多目標(biāo)量子粒子群算法可以用于約束不確定的規(guī)劃環(huán)境。仿真結(jié)果表明,算法可以在含有不確定海流和不確定危險(xiǎn)源的環(huán)境中規(guī)劃出多條分布性較好的可行路徑。另外,通過隨機(jī)生成海流和危險(xiǎn)源的方式測試了本文算法和常見未考慮不確定性的多目標(biāo)優(yōu)化算法。結(jié)果表明,相較于目前常見算法規(guī)劃出的路徑,所提算法在不確定環(huán)境下的可靠性更高,適用于含有多種不確定約束的海洋環(huán)境。