基于NSGA-II算法的AUV三維全局路徑規(guī)劃*

鄒春明 張?jiān)评?徐言民 關(guān)宏旭 趙俊超

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

0 引 言

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

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

本研究針對(duì)AUV全局路徑規(guī)劃問(wèn)題，通過(guò)分析海底地形建立了簡(jiǎn)單、高效的三維環(huán)境模型，根據(jù)AUV航行經(jīng)濟(jì)性和安全性原則建立了路徑長(zhǎng)度和威脅度評(píng)價(jià)函數(shù)模型，運(yùn)用NSGA-II算法的快速Pareto排序和擁擠度距離排序方法選擇最優(yōu)路徑點(diǎn).對(duì)規(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)境建模的方法有很多，總體上可以將建模的方法分為兩類(lèi)[8]：①用規(guī)則網(wǎng)格表示模型，如用正方形、立方體、矩形和長(zhǎ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等分，相鄰平面間距為單位長(zhǎng)dx，見(jiàn)圖1a).等分后的每個(gè)平面須進(jìn)行網(wǎng)格化處理，劃分出m×m個(gè)網(wǎng)格點(diǎn)，每個(gè)網(wǎng)格點(diǎn)都有相應(yīng)的坐標(biāo)值，用來(lái)儲(chǔ)存路徑點(diǎn)信息，見(jiàn)圖1b).路徑點(diǎn)信息用0、1表示，其中0表示平面內(nèi)此路徑點(diǎn)是危險(xiǎn)的，不可作為下一個(gè)路徑點(diǎn)的選取對(duì)象；1表示平面內(nèi)此路徑點(diǎn)是安全的，滿(mǎn)足安全通過(guò)的要求.按照本文模型構(gòu)建的思想，海底地形及其邊界網(wǎng)格點(diǎn)儲(chǔ)存的路徑點(diǎn)信息默認(rèn)為0.

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

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

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

1.2 路徑評(píng)價(jià)函數(shù)模型

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

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

1) 路徑長(zhǎng)度評(píng)價(jià)函數(shù)

J1=

(1)

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

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

(2)

R=r2-1

(3)

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

(4)

3) 路徑總評(píng)價(jià)函數(shù) 為了求解多目標(biāo)優(yōu)化問(wèn)題，本文運(yùn)用加權(quán)組合的方法，給路徑長(zhǎng)度和路徑威脅度函數(shù)分配權(quán)重，并采用目前普遍使用的主觀(guān)賦權(quán)法.設(shè)路徑長(zhǎng)度評(píng)價(jià)函數(shù)J1的權(quán)重為k，路徑威脅度評(píng)價(jià)函數(shù)J2的權(quán)重設(shè)置為1-k，得到規(guī)劃路徑總評(píng)價(jià)函數(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)而來(lái)，降低了遺傳算法的復(fù)雜性，具有運(yùn)行速度快，解集收斂性好的優(yōu)點(diǎn)，是目前最流行的多目標(biāo)遺傳算法之一.其改進(jìn)主要體現(xiàn)在兩個(gè)方面.

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

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

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

2.2 算法流程

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

表1 符號(hào)含義

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

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

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

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

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

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

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

步驟7再次執(zhí)行非支配排序和擁擠度距離排序.對(duì)備選種群MergePop中每個(gè)路徑點(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ī)劃總評(píng)價(jià)函數(shù)中的權(quán)值k=0.4，運(yùn)用NSGA-II算法求解全局最優(yōu)路徑，進(jìn)行20次仿真實(shí)驗(yàn)，選取規(guī)劃效果最優(yōu)的一次路徑.仿真參數(shù)設(shè)置見(jiàn)表2.

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

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

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

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

設(shè)AUV路線(xiàn)規(guī)劃的結(jié)果為點(diǎn)序列為[x1,x2,…,xn]，平滑后路線(xiàn)規(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)滿(mǎn)足 ‖y(i)-y(i+1)‖取值最小.(‖y(i)-y(i+1)‖為平滑后y(i)點(diǎn)之間的距離).

步驟3初始化y(i)=x(i)，迭代循環(huán)式(6)，直到滿(mǎn)足最小化目標(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ǔ)上，基于梯度下降法對(duì)規(guī)劃的路徑進(jìn)行優(yōu)化處理，為了凸顯優(yōu)化前后路徑的效果，設(shè)置起點(diǎn)縱坐標(biāo)y=60，平滑處理后的路徑見(jiàn)圖3.

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

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

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

圖4 路徑長(zhǎng)度和長(zhǎng)度收斂情況比較

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

4 結(jié) 束 語(yǔ)

針對(duì)自主水下航行器(AUV)在三維環(huán)境中的路徑規(guī)劃問(wèn)題，建立了簡(jiǎn)單有效的三維地理環(huán)境模型，基于改進(jìn)NSGA-II算法的快速Pareto排序及擁擠度距離計(jì)算選擇最優(yōu)路徑點(diǎn)，并對(duì)規(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)域、操縱控制等約束條件.