基于分層思想的AUV路徑規劃算法研究

徐言民 昌 政 趙俊超 關宏旭 王 巖

(武漢理工大學航運學院1) 武漢 430063) (內河航運技術湖北省重點實驗室2) 武漢 430063) (長江鎮江航道處3) 鎮江 21200)

0 引 言

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

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

1 環境模型的建立

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

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

圖1 三維環境示意圖

2 路徑規劃算法設計

2.1 規劃路徑的表示

根據生成的環境模型，采用分層思想，將空間沿著坐標系O-XYZ中的X軸，以dx等分成若干個YOZ平面，見圖2.

圖2 空間分層示意圖

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

2.2 環境信息的轉化

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

圖3 環境切面示意圖

將每個切面再進行網格化處理，分成n×n的網格點，與之對應的建立一個n×n的矩陣用來存儲每一個網格點的環境信息.因為高度值并不都是整數，為了便于矩陣存儲信息，同時保證路徑可行區域的安全性，將高度值進行了取整加一的膨化處理，圖3實線表示處理后的空間切面.

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

圖4 切面YOZ對應矩陣示意圖

2.3 路徑評價函數的確定

在路徑規劃中，總是希望所規劃的路徑距離障礙物越遠越好，路徑的長度越短越好，為了找出空間中兩點間的最優的路徑，就必須要對路徑進行評價.考慮到AUV的續航能力以及規劃航線的安全性，評價函數分別從路徑的總長度和路徑的危險程度兩個方面對規劃的路徑進行評價.

路徑長度的評價函數 規劃的路徑在切面(YOZ)i-1上的點為pi-1其坐標為(xi-1,yi-1,zi-1)，在切面(YOZ)i路徑點在上的點為pi其坐標為(xi,yi,zi)，則這兩個相鄰面之間的路徑長度可以用式(1)進行表示.

(1)

在式(1)中由于dx=xi-xi-1是一個定值，連接每個切面中的路徑點就可以組成一條路徑，當AUV沿著選取的路徑航行時，AUV的路徑長度評價值F1計算模型見式(2).

(2)

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

R=r2-1

(3)

把規劃路徑中所有路徑點的危險度進行相加就可以得到整條路徑的危險程度評價值F2計算模型見式(4).

(4)

路徑的總評價函數 路徑規劃的目的是使路徑長度與危險程度都達到最優值，對于建立的評價函數，就相當于對兩個目標進行優化求解.最直觀簡潔的方法就是采用加權的方法，通過對兩個不同的目標設置不同的權重，然后再相加，從而把兩個不同目標的優化求解轉化成一個目標的優化求解，最后得到路徑規劃總評價函數模型，見式(5).

minF=KF1+(1-K)F2=

(5)

F為路徑總評價值，權重系數K取值范圍[0,1]，根據不同的環境情況，危險度和路徑長度評價函數權重不同.

2.4 算法的實現

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

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

(6)

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

(7)

(8)

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

|pi-1pi|=

(9)

圖5 路徑點選取方法

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

圖6 路徑選取示意圖

3 路徑規劃

本文將路徑規劃的起終點設定在了環境障礙物兩側，起點坐標設置為[1,8,6]，終點坐標設置為[25,23,10],權值K=0.5.使用MATLAB軟件對模型進行求解，為了驗證所設計算法的效果，使用仿生算法中蟻群算法與本設計算法進行比較，見圖7.

圖7 路徑規劃結果示意圖

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

4 規劃路徑的優化

對應本文所建立的規劃模型，規劃航路為D維向量加起始點的一組向量.為了保證規劃路徑的精度，在規劃路徑時設置的維數較多，規劃結果呈現出曲線或者較多段線段的形態，這也導致了規劃的路徑中航向變化頻繁的問題，實際中并不適用.為了更貼近實際，仍需要對規劃路徑進行優化.

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

圖8 優化后路徑示意圖

5 結 束 語

引入分層的思想重新對環境進行表達，提出了一種適用于復雜水下三維環境的AUV路徑規劃方法.通過仿真實驗，驗證了所提出的路徑規劃方法的可行性，且較于常規的蟻群算法，此算法結構更簡單高效，仿真結果更好，提出的路徑優化方法有效減少了規劃路徑中的轉向點，解決了頻繁轉向的問題，使規劃結果更具實用性.