范士波 李毅

（上海寬帶技術(shù)及應(yīng)用工程研究中心孿生推演與智能決策實驗室，上海，200336）

0 引言

自主式水下機器人（Autonomous Underwater Vehicle，AUV)是多學(xué)科技術(shù)的集成體，涉及到計算機技術(shù)、自動控制、流體力學(xué)、人工智能、水聲學(xué)和網(wǎng)絡(luò)通信等領(lǐng)域。AUV搭載了多種傳感設(shè)備和測量裝置，具有自主導(dǎo)航和定位能力、任務(wù)規(guī)劃、信息處理和機械手作業(yè)等功能。因此，AUV不僅能夠完成海洋資源勘探、海底管道檢測與維修、海洋生態(tài)環(huán)境調(diào)查研究等任務(wù)，還能夠勝任一些特殊的軍事使命，如援潛救生、掃雷等[1]。其中，路徑規(guī)劃是AUV智能控制的關(guān)鍵技術(shù)之一，在一定程度上直接決定著AUV智能水平的高低[2-3]。

AUV在海洋環(huán)境航行時，需要獲得所處海域的環(huán)境信息。通常AUV在小范圍的航行都是通過搭載的聲納設(shè)備來獲得相應(yīng)的數(shù)據(jù)和信息。但是，當(dāng)AUV在大范圍海洋環(huán)境航行時，借助傳感設(shè)備的方法已經(jīng)不能滿足航行的需要，而電子海圖恰好提供了詳細而準確的海洋環(huán)境信息，因此，利用預(yù)先存儲于電子海圖的海洋環(huán)境信息進行建模并完成路徑規(guī)劃是AUV發(fā)展的必然趨勢[4]。

根據(jù)對環(huán)境信息依賴程度的不同，AUV路徑規(guī)劃可分為全局路徑規(guī)劃和局部路徑規(guī)劃。其中，全局路徑規(guī)劃包括環(huán)境建模和路徑搜索策略兩個子問題，主要是根據(jù)先驗知識（如海圖等）規(guī)劃出一條從始發(fā)點到目標點的無避碰路徑；局部路徑規(guī)劃又稱動態(tài)避碰規(guī)劃，通過搭載的傳感器（如聲納、攝像機等）在線地對機器人作業(yè)環(huán)境進行探測，利用實時獲取的障礙物位置、形狀和尺寸等信息，在盡可能短的時間內(nèi)避開未知障礙物的過程[5-8]。

目前，全局路徑環(huán)境建模的主要方法有：可視圖法（V-Graph）、自由空間法（Free Space Approach）、柵格法（Grids）等[9-10]，路徑搜索策略主要有： A*算法、D*最優(yōu)算法、遺傳算法、蟻群算法、神經(jīng)網(wǎng)絡(luò)等[11-13]；局部路徑規(guī)劃的主要方法包括：人工勢場法、遺傳算法、模糊邏輯算法、強化學(xué)習(xí)等人工智能算法[14-16]。

受自然界中螞蟻覓食行為的啟示，本文研究了一種基于海圖信息的AUV蟻群路徑規(guī)劃算法，提出利用電子海圖信息進行環(huán)境建模的方法，同時，針對蟻群規(guī)劃路徑不平滑問題，設(shè)計了切割算子和插點算子，最后，在Windows平臺下，通過VC++仿真軟件，驗證了算法的可行性。

1 海洋環(huán)境建模

由于海底地形地貌的復(fù)雜性和水下存在的一些未知障礙物，對AUV的安全構(gòu)成了潛在的威脅，為了實時感知這些信息，一般在AUV本體上安裝了多波束前視聲吶傳感器，通過接口反饋的探測信息為AUV路徑規(guī)劃提供依據(jù)。

本文的海洋環(huán)境建模思路是：把某一海域建立成二維的離散空間模型，并以矩陣柵格為組織形式，柵格陣左上角為坐標點，由此可抽象出一個二維坐標系，并約定水平向右為X軸遞增方向，豎直向下為Y軸遞增方向。用集合表示柵格陣中所有的柵格，則對任意柵格根據(jù)上述設(shè)定，都有唯一的坐標（x，y）與之相對應(yīng)；記為障礙柵格集，表示此區(qū)域全部或部分被水面島礁覆蓋，是不可行區(qū)域；記為可行柵格集，表示此區(qū)域是自由可行的區(qū)域。通過對水面島礁或障礙物的輪廓按一定的規(guī)則進行擴充，并在擴充的輪廓上適當(dāng)選擇一些柵格點稱作繞行點。對于兩柵格點，若由決定的線段所經(jīng)過的任意柵格點，都有則稱是通透的，記作

圖1所示為柵格模型示意圖，其中，空白柵格點是自由可行區(qū)域，是不可行區(qū)域，柵格點是AUV的起始點，是目標點，是繞行點，點和點是通透的，和是不通透的?；谏鲜鐾ㄍ感詸z查可以建立相應(yīng)柵格模型的可視圖模型，如圖2所示。

圖1 柵格模型示意圖

圖2 可視圖示意圖

海圖中每個地方都有一定的屬性，例如，劃定一個區(qū)域可以判斷出該區(qū)域是陸地還是海洋。根據(jù)AUV實際工作的需要，規(guī)定陸地、島嶼、半島、各類灘涂、礙航物等為AUV不可通過的區(qū)域，以及把影響AUV航行安全的部分限制區(qū)域作為障礙區(qū)域，其他區(qū)域為自由區(qū)域。

本文將海圖信息柵格化，柵格分辨率為18''，然后，取范圍18''×18''的正方形區(qū)域?qū)⑵湟暈橐粋€柵格節(jié)點。每個柵格節(jié)點與海圖的相應(yīng)區(qū)域做相交檢測，得到相交區(qū)域具有的屬性編碼。不同的屬性都有各自的編碼，根據(jù)相應(yīng)的編碼對應(yīng)shapefile電子海圖數(shù)據(jù)字典的相應(yīng)屬性，可以確定該柵格為障礙區(qū)域還是自由區(qū)域，最后將轉(zhuǎn)換好的柵格文件作為AUV進行全局路徑規(guī)劃的海圖信息文件。圖3是某海域電子海圖，圖4為根據(jù)要求柵格化的海圖信息。

圖3 某海域電子海圖

圖4 某海域海圖柵格化

本文主要對AUV在某一特定深度進行路徑規(guī)劃研究，并且不考慮海流等的影響。因此，AUV前視聲納探測模型的相關(guān)變量的設(shè)置均基于二維空間來考慮。

2 蟻群算法的原理及其實現(xiàn)過程

經(jīng)研究發(fā)現(xiàn)：螞蟻在覓食過程中能夠在所經(jīng)過的路徑上留下一種稱為信息素的物質(zhì)，而且能夠感知這種物質(zhì)的存在及其強度，并以此指引著自己的前進方向，它們傾向于朝著該物質(zhì)強度高的方向移動。因此，大量螞蟻集體覓食的行為便表現(xiàn)出一種信息正反饋現(xiàn)象：某一路徑越短，該路徑上走過的螞蟻就越多，則留下的信息素強度就越大，后來者選擇該路徑的概率就越大。螞蟻個體之間就是通過這種信息交流來選擇最短路徑并達到搜索食物的目的。蟻群算法就是模擬蟻群這一覓食行為的優(yōu)化算法。

2.1 符號描述與定義

2.2 狀態(tài)轉(zhuǎn)移規(guī)則

2.3 蟻群信息素更新規(guī)則

1）全局信息素更新規(guī)則。

全局信息素更新規(guī)則如式（2）計算。

2）精英信息素強化更新。

為了引導(dǎo)蟻群在更優(yōu)路徑上尋食，本文對每代最優(yōu)路徑的信息素進行了強化更新，主要分兩步完成。

步驟1：找出本次迭代過程中蟻群中路徑最優(yōu)的螞蟻（若有多只，只算其中的一只），設(shè)為按式（3）對信息素進行強化更新。

步驟2：若本代蟻群中路徑最優(yōu)螞蟻的代價比上代蟻群中路徑最優(yōu)螞蟻的代價大，則不做本次局部更新，否則設(shè)本代蟻群中路徑最優(yōu)螞蟻為上代為按式（4）進行信息素強化更新。

3）信息素更新后的處理。

信息素更新后，再按式（5）進行處理。

2.4 蟻群全局路徑規(guī)劃的步驟

3 路徑平滑

利用上述算法所得的規(guī)劃結(jié)果是構(gòu)成路徑點的序列，路徑點的連線為折線，必須加以平滑來提高AUV的穩(wěn)定性，故本文開發(fā)了兩個簡單的算子對規(guī)劃出來的路徑進行了平滑。

3.1 切割算子

圖5 正向切割示意圖

圖6 反向切割示意圖

3.2 插點算子

圖7 插點算子示意圖

4 仿真結(jié)果

本文在Windows平臺下，設(shè)置了1000m×1000m的矩形海域仿真環(huán)境。當(dāng)AUV起點S經(jīng)度為緯度為終點G經(jīng)度為緯度為時，采用蟻群算法，初始化種群選用100個個體，終止條件為迭代800代，交叉概率為0.8，變異概率為0.4，假設(shè)海流較弱，不考慮海流因素，其規(guī)劃結(jié)果如圖8（a）所示；采用算法，和圖8（a）中有相同的起點和終點坐標，以路徑最短為啟發(fā)信息規(guī)劃出結(jié)果，如圖8（b）所示。

圖8 全局路徑規(guī)劃試驗1

圖9 全局路徑規(guī)劃試驗2

在海流較弱、無需考慮海流因素影響的情況下，對兩種全局路徑規(guī)劃方法的結(jié)果進行比較，具體見表1。

表1 試驗結(jié)果比較

當(dāng)海洋環(huán)境中海流較強，需要考慮海流因素影響時，采用蟻群算法的規(guī)劃結(jié)果如圖10所示。其中，箭頭表示該區(qū)域海流流向，箭頭分布密度表示海流的大小。

圖10 海流較強時的路徑規(guī)劃結(jié)果

由試驗結(jié)果可知，在AUV自身消耗能量一定，AUV盡量沿海流方向航行，盡可能利用海流的能量的情況下，其航行距離最遠。

5 結(jié)論

本文以電子海圖信息為基礎(chǔ)對AUV進行環(huán)境建模，解決了對大范圍海洋環(huán)境建模的問題；采用蟻群算法作為搜索策略對機器人進行全局路徑規(guī)劃；在基于柵格法表示的路徑規(guī)劃中，引入通透性的概念，根據(jù)實際問題，對信息素不僅進行了全局更新，而且對每代中的最優(yōu)代價路徑進行了強化，從而使蟻群算法很快收斂到最優(yōu)路徑；針對規(guī)劃路徑不平滑的問題，本文設(shè)計了兩個算子（切割算子和插點算子）進行解決，同時使路徑的長度更短；最后，在Windows平臺下，通過VC++仿真軟件驗證了本文設(shè)計的算法的有效性和實用性。