徐言民 昌 政 趙俊超 關(guān)宏旭 王 巖

(武漢理工大學(xué)航運(yùn)學(xué)院1) 武漢 430063) (內(nèi)河航運(yùn)技術(shù)湖北省重點(diǎn)實(shí)驗(yàn)室2) 武漢 430063) (長江鎮(zhèn)江航道處3) 鎮(zhèn)江 21200)

0 引 言

新世紀(jì)以來很多國家都把海洋列為國家的長遠(yuǎn)發(fā)展計(jì)劃，為了在海洋的開發(fā)中奪得先機(jī)，很多都著力于發(fā)展更為精密的海洋運(yùn)載工具.AUV是一種水下機(jī)器人，習(xí)慣上稱為自主式水下航行器(autonomous underwater vehicle,AUV)，AUV最初主要應(yīng)用于軍事和科研，如水下搜索、監(jiān)視、偵查、獵雷、作戰(zhàn)海洋學(xué)、通信、導(dǎo)航、反潛作戰(zhàn)等[1].后隨著AUV技術(shù)的逐漸成熟，AUV在商業(yè)領(lǐng)域中也嶄露頭角，用作海底石油管道的監(jiān)測、維修，以及鉆井平臺附近水域溢油監(jiān)測等任務(wù).隨著科學(xué)技術(shù)的進(jìn)一步發(fā)展，未來AUV將會朝著小型化、混合式、群體化、遠(yuǎn)程化、智能化等方向發(fā)展[2].

AUV作為無人航行器的一種，航行在水面以下不同的深度，水中的淺灘、暗礁、島嶼、洋流等都是AUV航行過程中的障礙物.為保證AUV的航行安全，必須對其進(jìn)行航路規(guī)劃[3].常用路徑規(guī)劃算法有模擬退火法、人工勢場法、禁忌搜索算法、柵格法、C空間法等[4]，但在三維空間的路徑規(guī)劃使用不多.隨著智能仿生算法的發(fā)展，如蟻群算法、粒子群算法、遺傳算法等在復(fù)雜環(huán)境的路徑規(guī)劃中適用性更強(qiáng)，在三維空間路徑規(guī)劃中使用更加廣泛.文獻(xiàn)[5]對螢火蟲算法進(jìn)行了改進(jìn)，提出了一種適用于AUV 在三維空間中的路徑規(guī)劃方法，相比傳統(tǒng)路徑搜索算法更加靈活，通過添加輔助規(guī)劃算子，實(shí)現(xiàn)了AUV路徑的快速規(guī)劃.文獻(xiàn)[6]運(yùn)用遺傳算法對水中機(jī)器魚的路徑規(guī)劃做了研究.文獻(xiàn)[7]將粒子群算法和遺傳算法與蟻群算法相融合，較使用傳統(tǒng)的蟻群算法規(guī)劃三維航跡，提高了航跡規(guī)劃的速度與效率，增加了算法的高效性.通過對蟻群算法的改進(jìn)，提高了算法在三維空間的路徑規(guī)劃效率.三維空間路徑規(guī)劃存在環(huán)境建模困難、規(guī)劃約束多等難題，使得算法搜索能力欠缺、結(jié)構(gòu)復(fù)雜計(jì)算量大等問題.引入分層思想來表達(dá)空間環(huán)境，降低了環(huán)境建模的難度，簡潔的算法結(jié)構(gòu)能高效的規(guī)劃出一條安全路徑.

1 環(huán)境模型的建立

針對三維空間下的通航環(huán)境建模，一般有采用的方法有兩種，一種是基于分層的思想，將三維空間投射到一系列的平面上，在二維空間的平面上進(jìn)行環(huán)境建模[8]；另一種方式是采用單元分解的方法，將三維空間劃分為單元格，對AUV的三維路徑規(guī)劃中，采用了八叉樹模型劃分空間[9-10]，朱大奇等[11-12]在研究AUV路徑規(guī)劃問題時(shí)，使用了均勻柵格模型，將三維空間分割為一個(gè)均勻的柵格地圖.

建立空間直角坐標(biāo)系O-XYZ表示整個(gè)空間環(huán)境，將XOY劃分為n×n的網(wǎng)格，將海底地形的深度值與Z軸對應(yīng)，因Z軸方向從原點(diǎn)向上，將相應(yīng)地形的水深數(shù)據(jù)轉(zhuǎn)為高度值，用高度值表示XOY平面上每一點(diǎn)地形情況，最后生成相應(yīng)的環(huán)境模型，為簡化計(jì)算，對所涉及的長度和距離等除以選取的艇長進(jìn)行量綱—的量化.圖1為25×25的三維環(huán)境模型示意圖.

圖1 三維環(huán)境示意圖

2 路徑規(guī)劃算法設(shè)計(jì)

2.1 規(guī)劃路徑的表示

根據(jù)生成的環(huán)境模型，采用分層思想，將空間沿著坐標(biāo)系O-XYZ中的X軸，以dx等分成若干個(gè)YOZ平面，見圖2.

圖2 空間分層示意圖

由圖2可知，X軸被等分為n份，一共可生成n個(gè)YOZ平面，((YOZ)1,(YOZ)2,…,(YOZ)k,…,(YOZ)n).從空間中一點(diǎn)(xS,yS,zS)到另一點(diǎn)(xE,yE,zE)的路徑就可以表示為一系列在YOZ平面上的點(diǎn)的連線.

2.2 環(huán)境信息的轉(zhuǎn)化

通過將空間沿X軸等分成n個(gè)平面，將空間中的環(huán)境信息也分散到每一個(gè)YOZ平面中，即整個(gè)空間環(huán)境將被n個(gè)YOZ平面分割，每一個(gè)YOZ平面都是空間環(huán)境的一個(gè)切面.根據(jù)每一個(gè)斷面上點(diǎn)的高度值，可以確定規(guī)劃路徑在每個(gè)YOZ面上的可行區(qū)域，見圖3.圖中虛線為環(huán)境空間中某一切面YOZ.

圖3 環(huán)境切面示意圖

將每個(gè)切面再進(jìn)行網(wǎng)格化處理，分成n×n的網(wǎng)格點(diǎn)，與之對應(yīng)的建立一個(gè)n×n的矩陣用來存儲每一個(gè)網(wǎng)格點(diǎn)的環(huán)境信息.因?yàn)楦叨戎挡⒉欢际钦麛?shù)，為了便于矩陣存儲信息，同時(shí)保證路徑可行區(qū)域的安全性，將高度值進(jìn)行了取整加一的膨化處理，圖3實(shí)線表示處理后的空間切面.

圖3將切面YOZ分為25×25的網(wǎng)格，同時(shí)建立一個(gè)25×25的0矩陣，將高度值不為0的路徑不可行區(qū)域所對應(yīng)的矩陣元素全部表示為1，見圖4.0對應(yīng)圖4中“*”，1對應(yīng)圖4中“g”.

圖4 切面YOZ對應(yīng)矩陣示意圖

2.3 路徑評價(jià)函數(shù)的確定

在路徑規(guī)劃中，總是希望所規(guī)劃的路徑距離障礙物越遠(yuǎn)越好，路徑的長度越短越好，為了找出空間中兩點(diǎn)間的最優(yōu)的路徑，就必須要對路徑進(jìn)行評價(jià).考慮到AUV的續(xù)航能力以及規(guī)劃航線的安全性，評價(jià)函數(shù)分別從路徑的總長度和路徑的危險(xiǎn)程度兩個(gè)方面對規(guī)劃的路徑進(jìn)行評價(jià).

路徑長度的評價(jià)函數(shù) 規(guī)劃的路徑在切面(YOZ)i-1上的點(diǎn)為pi-1其坐標(biāo)為(xi-1,yi-1,zi-1)，在切面(YOZ)i路徑點(diǎn)在上的點(diǎn)為pi其坐標(biāo)為(xi,yi,zi)，則這兩個(gè)相鄰面之間的路徑長度可以用式(1)進(jìn)行表示.

(1)

在式(1)中由于dx=xi-xi-1是一個(gè)定值，連接每個(gè)切面中的路徑點(diǎn)就可以組成一條路徑，當(dāng)AUV沿著選取的路徑航行時(shí)，AUV的路徑長度評價(jià)值F1計(jì)算模型見式(2).

(2)

危險(xiǎn)程度的評價(jià)函數(shù) 在切面上的每個(gè)路徑點(diǎn)，在一定步長r(r∈Z)內(nèi)，都會存在R個(gè)網(wǎng)格點(diǎn)，假設(shè)這R個(gè)網(wǎng)格點(diǎn)中有m(m<8)個(gè)點(diǎn)為不可行點(diǎn)，即代表切面矩陣中為1的元素，則此時(shí)該路徑點(diǎn)的危險(xiǎn)就可以記為式(3)，當(dāng)選取的路徑點(diǎn)周圍全部為不可行點(diǎn)，即Di=1時(shí)，此時(shí)表示選取的路徑點(diǎn)不可行，需要重新選取路徑點(diǎn).

R=r2-1

(3)

把規(guī)劃路徑中所有路徑點(diǎn)的危險(xiǎn)度進(jìn)行相加就可以得到整條路徑的危險(xiǎn)程度評價(jià)值F2計(jì)算模型見式(4).

(4)

路徑的總評價(jià)函數(shù) 路徑規(guī)劃的目的是使路徑長度與危險(xiǎn)程度都達(dá)到最優(yōu)值，對于建立的評價(jià)函數(shù)，就相當(dāng)于對兩個(gè)目標(biāo)進(jìn)行優(yōu)化求解.最直觀簡潔的方法就是采用加權(quán)的方法，通過對兩個(gè)不同的目標(biāo)設(shè)置不同的權(quán)重，然后再相加，從而把兩個(gè)不同目標(biāo)的優(yōu)化求解轉(zhuǎn)化成一個(gè)目標(biāo)的優(yōu)化求解，最后得到路徑規(guī)劃總評價(jià)函數(shù)模型，見式(5).

minF=KF1+(1-K)F2=

(5)

F為路徑總評價(jià)值，權(quán)重系數(shù)K取值范圍[0,1]，根據(jù)不同的環(huán)境情況，危險(xiǎn)度和路徑長度評價(jià)函數(shù)權(quán)重不同.

2.4 算法的實(shí)現(xiàn)

((xi,y1,z1),(xi,y1,z2),…,

(xi,yi,zi),…，(xi,ya,zb))

(6)

式中：a，b為(YOZ)i平面中橫縱坐標(biāo)的編號，且(a≤n,b≤n)；n為(YOZ)i平面中被分割的最大網(wǎng)格數(shù)量.

(7)

(8)

Li取最小時(shí)，Lj和Lk的取值都最小.Lj取最小值表示所選取的路徑點(diǎn)與上一路徑點(diǎn)之間的距離最短，符合路徑規(guī)劃中整體路徑最短的要求，Lk取最小值表示平面(YOZ)i-1與平面(YOZ)i之間的路徑向量pi-1pi在總體方向上與向量SE比較接近，這也符合路徑規(guī)劃中路程最短的要求，具體方法見圖5.此時(shí)平面(YOZ)i-1與平面(YOZ)i之間的路徑長度就為向量pi-1pi的絕對值|pi-1pi|，即

|pi-1pi|=

(9)

圖5 路徑點(diǎn)選取方法

平面(YOZ)i中的路徑點(diǎn)搜索出來后，連接點(diǎn)與終點(diǎn)E，得到一條新的向量piE，此時(shí)向量piE與平面(YOZ)i到平面(YOZ)n會重新產(chǎn)生一系列的點(diǎn)，把向量piE作為選取下一個(gè)路徑點(diǎn)時(shí)的參考向量，重復(fù)上述選取路徑點(diǎn)的方法，依次進(jìn)行就可以得到(YOZ)i平面與(YOZ)i+1平面之間最短的安全路徑，見圖6.把每一段最短的安全路徑依次連接起來就可以構(gòu)建一條從起點(diǎn)到終點(diǎn)的安全路徑.

圖6 路徑選取示意圖

3 路徑規(guī)劃

本文將路徑規(guī)劃的起終點(diǎn)設(shè)定在了環(huán)境障礙物兩側(cè)，起點(diǎn)坐標(biāo)設(shè)置為[1,8,6]，終點(diǎn)坐標(biāo)設(shè)置為[25,23,10],權(quán)值K=0.5.使用MATLAB軟件對模型進(jìn)行求解，為了驗(yàn)證所設(shè)計(jì)算法的效果，使用仿生算法中蟻群算法與本設(shè)計(jì)算法進(jìn)行比較，見圖7.

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

由圖7可知，本算法與蟻群算法均能完成路徑的規(guī)劃.從規(guī)劃路徑的長度進(jìn)行比較，本算法的規(guī)劃路徑長度較蟻群算法的短；從規(guī)劃路徑中航向變化的改變幅度來看，本算法的規(guī)劃路徑中航向變化幅度較蟻群算法小；整體看來，本文所設(shè)計(jì)算法規(guī)劃結(jié)果較蟻群算法要好，但對于規(guī)劃路徑中航向改變的頻繁程度，兩種算法都需要有所提高.

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

對應(yīng)本文所建立的規(guī)劃模型，規(guī)劃航路為D維向量加起始點(diǎn)的一組向量.為了保證規(guī)劃路徑的精度，在規(guī)劃路徑時(shí)設(shè)置的維數(shù)較多，規(guī)劃結(jié)果呈現(xiàn)出曲線或者較多段線段的形態(tài)，這也導(dǎo)致了規(guī)劃的路徑中航向變化頻繁的問題，實(shí)際中并不適用.為了更貼近實(shí)際，仍需要對規(guī)劃路徑進(jìn)行優(yōu)化.

所求路徑可表示為P=(p1,p2,…,pn),包括起終點(diǎn)，路徑一共要穿過n個(gè)YOZ平面.以終點(diǎn)為基點(diǎn)，跳過相鄰路徑點(diǎn)，按反向順序選取路徑點(diǎn)進(jìn)行檢驗(yàn)，判斷與構(gòu)成線段所穿過路徑點(diǎn)與間的所有YOZ平面是否均為可行區(qū)域，即線段與平面交點(diǎn)均位于相應(yīng)平面的可行區(qū)域內(nèi)，則從路徑P中剔除與相鄰的上一個(gè)路徑點(diǎn)，選取下一個(gè)路徑點(diǎn)pn-3進(jìn)行檢驗(yàn);否則保留上一個(gè)路徑點(diǎn)，再重新以為基點(diǎn)，重復(fù)上述操作.直至檢驗(yàn)判斷遍歷至起點(diǎn)為止，就可得到一條優(yōu)化后的路徑P′,見圖8.

圖8 優(yōu)化后路徑示意圖

5 結(jié) 束 語

引入分層的思想重新對環(huán)境進(jìn)行表達(dá)，提出了一種適用于復(fù)雜水下三維環(huán)境的AUV路徑規(guī)劃方法.通過仿真實(shí)驗(yàn)，驗(yàn)證了所提出的路徑規(guī)劃方法的可行性，且較于常規(guī)的蟻群算法，此算法結(jié)構(gòu)更簡單高效，仿真結(jié)果更好，提出的路徑優(yōu)化方法有效減少了規(guī)劃路徑中的轉(zhuǎn)向點(diǎn)，解決了頻繁轉(zhuǎn)向的問題，使規(guī)劃結(jié)果更具實(shí)用性.