鄒春明 張云雷 徐言民 關(guān)宏旭 趙俊超

(武漢理工大學(xué)航運(yùn)學(xué)院1) 武漢 430063) (內(nèi)河航運(yùn)技術(shù)湖北省重點(diǎn)實(shí)驗(yàn)室2) 武漢 430063)(長江引航中心3) 無錫 214431)

0 引 言

自主式水下航行器(autonomous underwater vehicle，AUV)[1-3]是新的一代水下機(jī)器人，具有活動范圍大、機(jī)動性好、安全、智能等優(yōu)點(diǎn)，能夠完成各種水下任務(wù).路徑規(guī)劃研究是自主式水下航行器完成其任務(wù)的關(guān)鍵技術(shù)之一.路徑規(guī)劃可以分為兩類：全局路徑規(guī)劃和局部路徑規(guī)劃.全局路徑規(guī)劃是在已知的環(huán)境中尋找可行的路徑，通常優(yōu)化路徑是可行的，而局部路徑規(guī)劃則適用于環(huán)境未知或者部分未知的情況，在這種情況下，優(yōu)化路徑并不總是可用的.當(dāng)前，仿生智能算法在AUV局部最優(yōu)路徑規(guī)劃的應(yīng)用己經(jīng)相當(dāng)成熟，而實(shí)現(xiàn)AUV三維全局最優(yōu)路徑規(guī)劃，以保證其在海底的安全航行.

針對自主式水下航行器的路徑規(guī)劃研究，通常采用Dijkstra算法、A*算法、遺傳算法、人工勢場算法、模糊方法和粒子群優(yōu)化算法[4-7]，但是傳統(tǒng)的路徑規(guī)劃算法都存在一定的缺陷，例如，遺傳算法在解決多目標(biāo)優(yōu)化問題時存在著編碼復(fù)雜，搜索最優(yōu)解效率低、耗時長等問題.NSGA-II算法(non dominated sorting genetic algorithm-II)能夠較好地克服這種缺陷，表現(xiàn)出運(yùn)行速度快，解集收斂性好的優(yōu)點(diǎn).

本研究針對AUV全局路徑規(guī)劃問題，通過分析海底地形建立了簡單、高效的三維環(huán)境模型，根據(jù)AUV航行經(jīng)濟(jì)性和安全性原則建立了路徑長度和威脅度評價函數(shù)模型，運(yùn)用NSGA-II算法的快速Pareto排序和擁擠度距離排序方法選擇最優(yōu)路徑點(diǎn).對規(guī)劃路徑進(jìn)行平滑處理，使得改進(jìn)后的算法在復(fù)雜的三維環(huán)境中能夠快速收斂獲得路徑最優(yōu)解.

1 路徑規(guī)劃相關(guān)模型建立

1.1 三維空間環(huán)境模型

環(huán)境建模是AUV路徑規(guī)劃的首要環(huán)節(jié)，三維環(huán)境建模的方法有很多，總體上可以將建模的方法分為兩類[8]：①用規(guī)則網(wǎng)格表示模型，如用正方形、立方體、矩形和長方體組成的規(guī)則網(wǎng)格表示海底表面；②用不規(guī)則網(wǎng)格表示模型，以三角形、多邊形或不規(guī)則形狀作為模型單元的基礎(chǔ).與常規(guī)網(wǎng)格地形模型相比，不規(guī)則網(wǎng)格建模更為復(fù)雜，占用空間更大.因此，在前人研究的基礎(chǔ)上，采用空間分層[9]，平面網(wǎng)格化的基本思想建立三維空間模型，以網(wǎng)格為單位離散化表示水下航行器的工作區(qū)域.

1) 空間劃分 首先建立O-XYZ三維直角坐標(biāo)系，模擬海洋地理環(huán)境，其中Z軸正方向?qū)?yīng)海底深度值，OX軸為水下航行器橫向位移增加的方向，OY為縱向位移增加的方向.在構(gòu)建好的O-XYZ坐標(biāo)系后，沿著X軸方向進(jìn)行空間n等分，相鄰平面間距為單位長dx，見圖1a).等分后的每個平面須進(jìn)行網(wǎng)格化處理，劃分出m×m個網(wǎng)格點(diǎn)，每個網(wǎng)格點(diǎn)都有相應(yīng)的坐標(biāo)值，用來儲存路徑點(diǎn)信息，見圖1b).路徑點(diǎn)信息用0、1表示，其中0表示平面內(nèi)此路徑點(diǎn)是危險的，不可作為下一個路徑點(diǎn)的選取對象；1表示平面內(nèi)此路徑點(diǎn)是安全的，滿足安全通過的要求.按照本文模型構(gòu)建的思想，海底地形及其邊界網(wǎng)格點(diǎn)儲存的路徑點(diǎn)信息默認(rèn)為0.

圖1 空間劃分和yozi平面路徑點(diǎn)示意圖

2) 地理信息轉(zhuǎn)化 經(jīng)過對三維空間的分層、網(wǎng)格化處理，地理環(huán)境也較容易被表達(dá)出來.其中比較常用的方法是序號法和坐標(biāo)法，序號法可以減少計算時的數(shù)據(jù)量，運(yùn)行速度快，但是并沒有減少路徑點(diǎn)的存儲數(shù)量，各個路徑點(diǎn)的位置關(guān)系也不容易被直觀判斷出來.為了更好的適應(yīng)文中采用的NSGA-II算法，將環(huán)境模型坐標(biāo)化運(yùn)用到算法的優(yōu)化求解過程中.其中，轉(zhuǎn)化后地理環(huán)境模型見圖2.

圖2 海底地形環(huán)境

1.2 路徑評價函數(shù)模型

全局路徑規(guī)劃的本質(zhì)就是搜索一條從起點(diǎn)S(xs,ys,zs)到終點(diǎn)E(xe,ye,ze)的長度最短且危險度最小的路徑，而AUV在實(shí)際航行過程中要受到多種因素的影響.為便于計算，簡化處理，模型中將AUV視為質(zhì)點(diǎn)，且不考慮海洋環(huán)境下的潮流、海流等因素干擾.

AUV路徑評價函數(shù)屬于典型的多目標(biāo)決策問題，由于不同算法研究的目的有差異，評價函數(shù)考慮的因素和側(cè)重點(diǎn)也會不同.本算法重點(diǎn)考慮路徑的長度即經(jīng)濟(jì)性和路徑威脅度即安全性兩項(xiàng)評價指標(biāo)來定義評價函數(shù).

1) 路徑長度評價函數(shù)

J1=

(1)

式中：dx為相鄰平面間隔；(xi,yi,zi)為AUV運(yùn)動到y(tǒng)ozi平面上的坐標(biāo).

2) 路徑威脅度評價函數(shù) 在切面上的每個路徑點(diǎn)，在一定的步長r(r∈Z)內(nèi)，都會存在R個網(wǎng)格點(diǎn)，假設(shè)這R個網(wǎng)格點(diǎn)中有m(m<8)個點(diǎn)為危險點(diǎn)(威脅源)，則此時該路徑點(diǎn)的危險度為

(2)

R=r2-1

(3)

將各個平面上路徑點(diǎn)的威脅度相加，得到的AUV整條規(guī)劃路徑的威脅度評價函數(shù)為

(4)

3) 路徑總評價函數(shù) 為了求解多目標(biāo)優(yōu)化問題，本文運(yùn)用加權(quán)組合的方法，給路徑長度和路徑威脅度函數(shù)分配權(quán)重，并采用目前普遍使用的主觀賦權(quán)法.設(shè)路徑長度評價函數(shù)J1的權(quán)重為k，路徑威脅度評價函數(shù)J2的權(quán)重設(shè)置為1-k，得到規(guī)劃路徑總評價函數(shù)為

minJ=kJ1+(1-k)J2=

(5)

2 NSGA-II算法路徑規(guī)劃

2.1 NSGA-II算法

第二代非支配排序遺傳算法NSGA-II[10](non dominated sorting genetic algorithm-II，NSGA-II)是在第一代非支配排序遺傳算法的基礎(chǔ)上改進(jìn)而來，降低了遺傳算法的復(fù)雜性，具有運(yùn)行速度快，解集收斂性好的優(yōu)點(diǎn)，是目前最流行的多目標(biāo)遺傳算法之一.其改進(jìn)主要體現(xiàn)在兩個方面.

1) 提出了快速非支配排序算法，一方面降低了計算的復(fù)雜度，另一方面它將父代種群跟子代種群進(jìn)行合并，使得下一代的種群從雙倍的空間中進(jìn)行選取，從而保留了最為優(yōu)秀的所有個體.

2) 采用擁擠度和擁擠度比較算子，使得準(zhǔn)Pareto域中的個體能均勻地擴(kuò)展到整個Pareto域，保證了種群的多樣性.

通過快速Pareto排序及擁擠度距離計算進(jìn)行路徑點(diǎn)選擇后，在種群中的每個個體都將獲得兩項(xiàng)屬性，即非支配排序?qū)蛹壧柡蛽頂D度距離.

2.2 算法流程

記種群規(guī)模為PopSize，最大迭代代數(shù)為Gen，非支配層級數(shù)為L，非支配解集合為Fi(i=1，2,…，L)，擁擠度距離為Nd.符號含義見表1.

表1 符號含義

使用NSGA-II算法求解AUV三維全局最優(yōu)路徑的執(zhí)行過程如下.

步驟1初始化算法參數(shù)，生成初始種群Pop，即初始化隨機(jī)生成一條由起始點(diǎn)到目標(biāo)終點(diǎn)的AUV參考路徑，Pop中由起始點(diǎn)到目標(biāo)終點(diǎn)順序存儲每個路徑點(diǎn)的坐標(biāo)值(xi,yi,zi).

步驟2評價當(dāng)前路徑的適應(yīng)值.將Pop中每個路徑點(diǎn)坐標(biāo)值(xi,yi,zi)分別代入評價函數(shù)計算AUV當(dāng)前路徑點(diǎn)的長度、威脅度適應(yīng)值.

步驟3執(zhí)行非支配排序和擁擠度距離排序.對Pop中每個路徑點(diǎn)坐標(biāo)值與其他所有路徑點(diǎn)坐標(biāo)值，根據(jù)步驟2中適應(yīng)值的計算結(jié)果分別兩兩比較，執(zhí)行擁擠度距離計算及排序，擁擠度距離大者勝出.

步驟4執(zhí)行交叉操作.對由Pop中路徑點(diǎn)形成的兩個不可行路徑段進(jìn)行單點(diǎn)交叉操作，按隨機(jī)方式選擇交叉點(diǎn)從而得到兩個新的路徑段.

步驟5執(zhí)行變異操作.在Pop*存儲的新路徑中，隨機(jī)選擇除起始點(diǎn)和目標(biāo)終點(diǎn)以外的任意路徑點(diǎn)，根據(jù)選中的隨機(jī)數(shù)，對應(yīng)找到這個路徑點(diǎn)位置執(zhí)行變異操作.變異操作的新路徑中由起始點(diǎn)到目標(biāo)終點(diǎn)的每個路徑點(diǎn)坐標(biāo)值(xi,yi,zi)順序存儲至Pop**中.

步驟6執(zhí)行合并操作，對Pop*和Pop**執(zhí)行合并操作，生成備選種群MergePop.

步驟7再次執(zhí)行非支配排序和擁擠度距離排序.對備選種群MergePop中每個路徑點(diǎn)坐標(biāo)值，執(zhí)行與步驟3中描述相同的操作，得出關(guān)于MergePop的Fi(i=1，2,…,L)和Nd.

步驟8判斷算法運(yùn)行終止條件.若未達(dá)到最大迭代代數(shù)Gen，則轉(zhuǎn)去執(zhí)行步驟2，否則終止算法并輸出最優(yōu)解.

2.3 仿真實(shí)驗(yàn)

仿真采用matlab軟件編程，設(shè)置AUV起始點(diǎn)坐標(biāo)為SO1(1,60,100)，終點(diǎn)坐標(biāo)為EO1(101,101,100).為了保證路徑點(diǎn)的安全，設(shè)置路徑規(guī)劃總評價函數(shù)中的權(quán)值k=0.4，運(yùn)用NSGA-II算法求解全局最優(yōu)路徑，進(jìn)行20次仿真實(shí)驗(yàn)，選取規(guī)劃效果最優(yōu)的一次路徑.仿真參數(shù)設(shè)置見表2.

表2 仿真參數(shù)設(shè)置

NSGA-II算法能夠成功地避開海底地形障礙，規(guī)劃出AUV有效可行的全局路徑.但是在躲避海底地形威脅時，路徑曲線不夠平滑，部分轉(zhuǎn)向點(diǎn)角度過大，導(dǎo)致AUV頻繁轉(zhuǎn)向、總航程變長.因此，為了保證規(guī)劃路徑的經(jīng)濟(jì)性，更好的適應(yīng)AUV的操縱性要求，規(guī)劃的路徑還需進(jìn)一步的優(yōu)化處理.

3 規(guī)劃路徑的優(yōu)化

由于NSGA-II算法在建立的網(wǎng)格環(huán)境模型下對路徑進(jìn)行規(guī)劃，規(guī)劃出路徑的長度與平滑程度存在一定缺陷，并不利于水下航行器的航行，所以需要對路徑進(jìn)行優(yōu)化處理.本文應(yīng)用梯度下降法(gradient descent)，即通過多次迭代，使得目標(biāo)函數(shù)取得最小值.梯度下降法是迭代法的一種，可以用于求解最小二乘問題.在求解評價函數(shù)的最小值時，可以通過梯度下降法來逐步迭代求解，得到最小化的評價函數(shù)和模型參數(shù)值.

設(shè)AUV路線規(guī)劃的結(jié)果為點(diǎn)序列為[x1,x2,…,xn]，平滑后路線規(guī)劃的點(diǎn)序列為[y1,y2,…,yn]，路徑平滑最小化目標(biāo)為alpha×‖x(i)-y(i)‖2+beta×‖y(i)-y(i+1)‖

設(shè)置參數(shù)alpha=beta=0.6，路徑平滑算法流程如下：

步驟1求解y(i)使得‖x(i)-y(i)‖的平方最小.(‖x(i)-y(i)‖為平滑后的點(diǎn)y(i)與原始點(diǎn)x(i)的偏離程度).

步驟2使得y(i)滿足 ‖y(i)-y(i+1)‖取值最小.(‖y(i)-y(i+1)‖為平滑后y(i)點(diǎn)之間的距離).

步驟3初始化y(i)=x(i)，迭代循環(huán)式(6)，直到滿足最小化目標(biāo).

y(i)=y(i)+alpha×[x(i)-y(i)]+

beta×[y(i-1)-2×y(i)+y(i+1)]

(6)

在第2節(jié)仿真實(shí)驗(yàn)的基礎(chǔ)上，基于梯度下降法對規(guī)劃的路徑進(jìn)行優(yōu)化處理，為了凸顯優(yōu)化前后路徑的效果，設(shè)置起點(diǎn)縱坐標(biāo)y=60，平滑處理后的路徑見圖3.

圖3 優(yōu)化前后路徑立體圖和俯視圖

圖3中淺色曲線為NSGA-II算法規(guī)劃的路徑，深色曲線為應(yīng)用梯度下降法平滑處理后所產(chǎn)生的路徑.由圖3可知，改進(jìn)后的路徑曲線趨于平滑，路徑轉(zhuǎn)向點(diǎn)減少且部分特殊轉(zhuǎn)向角變小，能夠更好的符合水下航行器的航行實(shí)際.

圖4為路徑優(yōu)化前后威脅度、長度迭代收斂曲線.總體可以看出NSGA-II算法在路徑規(guī)劃時得到的目標(biāo)代價值較小，且能夠快速響應(yīng)，收斂速度較快.

圖4 路徑長度和長度收斂情況比較

對比分析優(yōu)化前后威脅度收斂情況，平滑算法處理后，程序經(jīng)過37次迭代達(dá)到了最優(yōu)解，而原算法雖然中期收斂速度較快，但收斂曲線不穩(wěn)定，最終在46次迭代后收斂，并且最終代價值高于平滑算法處理的結(jié)果.同樣對比分析路徑長度收斂情況，優(yōu)化后算法收斂速度加快，經(jīng)過第32次迭代達(dá)到最優(yōu)解，且路徑長度最優(yōu)解更小.而原算法經(jīng)過44次迭代達(dá)到收斂狀態(tài).

4 結(jié) 束 語

針對自主水下航行器(AUV)在三維環(huán)境中的路徑規(guī)劃問題，建立了簡單有效的三維地理環(huán)境模型，基于改進(jìn)NSGA-II算法的快速Pareto排序及擁擠度距離計算選擇最優(yōu)路徑點(diǎn)，并對規(guī)劃的路徑進(jìn)行平滑優(yōu)化處理.仿真結(jié)果表明，本文采用的算法能夠?yàn)锳UV快速規(guī)劃出三維空間下的最優(yōu)路徑.但由于本文將AUV視為質(zhì)點(diǎn)，未考慮AUV的六自由度及操縱性的影響，導(dǎo)致仿真實(shí)驗(yàn)與實(shí)際的工作情況存在一定偏差，后期的路徑規(guī)劃研究將充分考慮AUV安全領(lǐng)域、操縱控制等約束條件.