基于區(qū)間多目標(biāo)量子粒子群算法的AUV路徑規(guī)劃研究

顧加燁,齊 亮

(江蘇科技大學(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的航行,因此如何在不確定海流和危險源條件下規(guī)劃出安全、快速、節(jié)能的可行路徑成為當(dāng)下研究的重點(diǎn)。

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

本文針對海流和危險源信息的不確定性,將海流和危險源的不確定性表示為區(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ù)下得到符合多個不確定目標(biāo)約束的Pareto解集,所規(guī)劃的路徑具有較好的分布性。

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

1.1 問題描述

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

1.2 路徑形式

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

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

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

1.3 不確定海流模型

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

(1)

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

1.4 不確定危險源模型

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

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

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

(2)

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

(3)

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

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

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

2 航行時間與危險度計算

2.1 航行時間計算

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

(4)

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

(5)

(6)

2.2 路徑危險度計算

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

(8)

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

(9)

(10)

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

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

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

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

(11)

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

(12)

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

d(X1,X2)=

(13)

其中,m(TI)和m(HI)分別為區(qū)間TI和HI的中點(diǎn),分子為2個路徑目標(biāo)函數(shù)超體中心點(diǎn)的歐拉距離。假設(shè)根據(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航行速度、不確定危險源的不確定范圍、不確定海流的范圍、路徑粒子的數(shù)目、迭代次數(shù)、擴(kuò)張收縮因子α。

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

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

(15)

步驟5計算更新后的每條路徑的航行時間區(qū)間和危險度區(qū)間。基于區(qū)間占優(yōu)關(guān)系更新個體歷史最優(yōu)位置yi(t)。

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

步驟7對外部儲備集中的粒子進(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若外部儲備集中粒子數(shù)目大于規(guī)定數(shù)目,則利用區(qū)間擁擠距離公式計算外部儲備集中的粒子擁擠度,選取一定數(shù)目的粒子存入外部儲備集,否則直接執(zhí)行步驟10。

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

4 仿真分析

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

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

選取AUV的推進(jìn)速度為0.9 m/s。海流的方向不確定性θ為20°,海流大小不確定性φ為0.2倍的海流大小。不確定危險源的不確定半徑為 5 km,安全距離lmax為20 km,絕對危險距離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個目標(biāo)空間上的適應(yīng)度,縱軸為危險度,橫軸為航行消耗的時間。從圖6中可以看出,最終前沿路徑的適應(yīng)度區(qū)間較為分散,表明基于區(qū)間的擁擠距離策略達(dá)到了預(yù)期的效果,每條路徑都在航行時間與危險度之間互不占優(yōu)。路徑危險度最小達(dá)到0,最大為0.94,因此沒有產(chǎn)生絕對危險的路徑。決策時可以根據(jù)實(shí)際需要選擇合適的路徑。

圖6 Pareto前沿示意圖

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

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

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

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

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

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

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

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

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

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

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

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

5 結(jié)論

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