范士波 李毅

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

0 引言

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

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

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

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

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

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

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

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

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

圖1 柵格模型示意圖

圖2 可視圖示意圖

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

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

圖3 某海域電子海圖

圖4 某海域海圖柵格化

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

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

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

2.1 符號(hào)描述與定義

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

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

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

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

2）精英信息素強(qiáng)化更新。

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

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

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

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

信息素更新后，再按式（5）進(jìn)行處理。

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

3 路徑平滑

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

3.1 切割算子

圖5 正向切割示意圖

圖6 反向切割示意圖

3.2 插點(diǎn)算子

圖7 插點(diǎn)算子示意圖

4 仿真結(jié)果

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

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

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

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

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

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

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

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

5 結(jié)論

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