劉雨青，向 軍，曹守啟

(上海海洋大學(xué)工程學(xué)院，上海 201306)

1 引言

水下機(jī)器人AUV(Autonomous Underwater Vehicle)路徑規(guī)劃是在環(huán)境已知或者部分已知的情況下，依據(jù)能耗最低、用時(shí)最少和路程最短等指標(biāo)為AUV規(guī)劃出一條從起始點(diǎn)到目標(biāo)點(diǎn)的無碰撞最優(yōu)路徑，路徑規(guī)劃是AUV能夠獨(dú)立自主完成各種任務(wù)的首要前提。目前國內(nèi)外已有很多用于路徑規(guī)劃的算法，如人工勢(shì)場(chǎng)法[1]、A*搜索法[2]、粒子群優(yōu)化算法[3-5]和遺傳算法[6,7]等。

蟻群算法ACO(Ant Colony Algorithm)[8-14]是一種基于模型的構(gòu)造型隨機(jī)算法，具有自組織性、較強(qiáng)的魯棒性與尋優(yōu)能力，通過與其他啟發(fā)式算法相結(jié)合，可很容易地改善算法的求解能力。該算法可以通過施加約束條件，求解水下三維空間路徑規(guī)劃的優(yōu)化問題。武小年等[7]針對(duì)啟發(fā)式算法在數(shù)字高程模型DEM(Digital Elevation Model)路徑規(guī)劃中數(shù)據(jù)量巨大、效率較低等問題，提出一種基于遺傳和蟻群的混合路徑規(guī)劃算法。封聲飛等[9]針對(duì)傳統(tǒng)蟻群算法在路徑規(guī)劃中存在收斂速度和尋優(yōu)能力不平衡，算法易陷入局部最優(yōu)等問題，提出一種自適應(yīng)改進(jìn)蟻群算法。金飛虎等[10]采用根據(jù)學(xué)習(xí)次數(shù)和與最近障礙物的距離來調(diào)節(jié)信息激素物質(zhì)的自適應(yīng)蟻群算法，彌補(bǔ)了傳統(tǒng)路徑規(guī)劃方法缺乏足夠魯棒性的問題，修改了信息激素物質(zhì)的更新方法，解決了算法在計(jì)算初期出現(xiàn)停滯的現(xiàn)象。柳長(zhǎng)安等[11]在改進(jìn)蟻群算法時(shí)，用粒子群優(yōu)化算法對(duì)重要參數(shù)進(jìn)行優(yōu)化選擇，借鑒狼群分配原則對(duì)信息素進(jìn)行更新，改進(jìn)后的算法可以避免搜索陷入局部最優(yōu)，但改進(jìn)后的算法運(yùn)行時(shí)間并未有明顯縮短。史恩秀等[12]詳細(xì)分析了蟻群算法的幾個(gè)重要參數(shù)對(duì)規(guī)劃路徑長(zhǎng)度及效率的影響，但僅限于找出具體環(huán)境下的最佳匹配參數(shù)組，仍未解決因信息素?fù)]發(fā)系數(shù)等參數(shù)取值不準(zhǔn)而影響規(guī)劃效果的問題。

為提高AUV三維路徑規(guī)劃效率，優(yōu)化規(guī)劃路徑，本文針對(duì)具有復(fù)雜時(shí)空要求的水下AUV路徑規(guī)劃問題，使用蟻群算法為基本優(yōu)化搜索算法，在多重約束條件下以能耗最低為優(yōu)化目標(biāo)，建立了AUV運(yùn)動(dòng)的能耗模型并獲得AUV運(yùn)動(dòng)的總能耗，通過改進(jìn)的蟻群算法，實(shí)現(xiàn)了路徑規(guī)劃能耗最低的優(yōu)化目標(biāo)。仿真實(shí)驗(yàn)結(jié)果表明，采用改進(jìn)的蟻群算法進(jìn)行水下自主航行機(jī)器人的路徑規(guī)劃，能夠提升路徑規(guī)劃的實(shí)時(shí)性，規(guī)劃出的路徑便于AUV控制跟蹤，符合能耗最優(yōu)的目標(biāo)。

2 水下機(jī)器人數(shù)學(xué)建模

2.1 水下環(huán)境建模

AUV水下環(huán)境模型直接影響到路徑規(guī)劃算法所規(guī)劃出的路徑優(yōu)劣，因此合理地將三維環(huán)境抽象表達(dá)出來是AUV在三維環(huán)境中自主航行和進(jìn)行作業(yè)的關(guān)鍵。本文將三維環(huán)境空間模型的3個(gè)軸依次設(shè)為經(jīng)度、緯度和海拔增加的方向，采用柵格法將二維空間擴(kuò)展到三維空間，在三維海底地形數(shù)據(jù)的基礎(chǔ)上進(jìn)行建模，以柵格為單位離散化水下機(jī)器人工作區(qū)域。

2.2 搜索模式

從二維平面到三維空間中，由于選擇節(jié)點(diǎn)數(shù)量成倍增加，導(dǎo)致算法搜索最優(yōu)解變得異常復(fù)雜，而且很容易出現(xiàn)死鎖現(xiàn)象，使得算法收斂性差，全局搜索能力降低。為此，在搜索最優(yōu)的過程中采用一種分層前進(jìn)與柵格平面法相結(jié)合的搜索模式(如圖1所示)。以y軸為主前進(jìn)方向，設(shè)AUV起始點(diǎn)為PS,目標(biāo)點(diǎn)為PG，規(guī)定機(jī)器人最大橫向移動(dòng)距離為Xmax，最大縱向移動(dòng)距離為Zmax。首先螞蟻從PS出發(fā)，在第1個(gè)平面搜索到可行節(jié)點(diǎn)P1(x1,y1,z1)，接著在第2個(gè)平面搜索到第2個(gè)可行節(jié)點(diǎn)P2(x2,y2,z2)，螞蟻依次在各個(gè)平面選擇路徑節(jié)點(diǎn)，直到搜索到目標(biāo)點(diǎn)PG結(jié)束，即可搜索到一條最優(yōu)路徑。

Figure 1 Search mode of AUV path

2.3 能耗模型

為了求解AUV跟蹤所規(guī)劃出的路徑總能耗，首先根據(jù)航行狀態(tài)分別建立AUV水下移動(dòng)速度模型，然后利用水阻力和推進(jìn)器推力的計(jì)算公式依據(jù)功能關(guān)系求得AUV跟蹤規(guī)劃出的路徑的總能耗。

2.3.1 巡航速度模型

為了降低計(jì)算過程的復(fù)雜度，本文忽略AUV在航行過程中的加減速過程，并作如下假設(shè)：(1)AUV以勻速直線狀態(tài)開始航行，中間轉(zhuǎn)彎根據(jù)轉(zhuǎn)角大小采用相應(yīng)的低速勻速航行，最終以勻速直線航行狀態(tài)到達(dá)終點(diǎn)；(2)路徑關(guān)鍵點(diǎn)前后各一個(gè)單位長(zhǎng)度路程均為勻速航行狀態(tài)；(3)勻速直線航行狀態(tài)與勻速轉(zhuǎn)彎航行狀態(tài)間存在一個(gè)單位長(zhǎng)度的加減速航行狀態(tài)。

故AUV的航行狀態(tài)為勻速直線航行狀態(tài)、勻速轉(zhuǎn)彎航行狀態(tài)和加減速航行狀態(tài)的疊加，如圖2所示。設(shè)勻速直線航行狀態(tài)的速度為v=μm/s；AUV在轉(zhuǎn)彎時(shí)轉(zhuǎn)彎速度低于做直線運(yùn)動(dòng)時(shí)的速度，同時(shí)在不同轉(zhuǎn)彎處，轉(zhuǎn)彎半徑不一樣速度會(huì)不同，轉(zhuǎn)彎半徑越大，轉(zhuǎn)彎航行狀態(tài)的速度也就越大；從勻速直線航行狀態(tài)到轉(zhuǎn)彎航行狀態(tài)為加減速航行狀態(tài)，取其平均速度作為該過程的行駛速度。不同航行狀態(tài)下的速度計(jì)算方法如式(1)所示：

(1)

Figure 2 Model of AUV speed

2.3.2 水阻力的計(jì)算

AUV在水下運(yùn)動(dòng)時(shí)必定受到水阻力，由于AUV是一個(gè)非線性動(dòng)力學(xué)系統(tǒng)，計(jì)算阻力需要確定的參數(shù)較多，本文根據(jù)水動(dòng)力計(jì)算公式，將AUV受到的水阻力計(jì)算簡(jiǎn)化為式(2)所示:

(2)

其中，F(xiàn)為AUV在航行過程中受到的水阻力；C為水動(dòng)力系數(shù)，該系數(shù)的取值與AUV形狀、迎流面等一系列要素有關(guān)；ρ為水的密度；v為AUV的航行速度，S為AUV的橫截面積。

2.3.3 能耗計(jì)算

AUV在作勻速運(yùn)動(dòng)時(shí)加速度為零，水阻力F與推進(jìn)器產(chǎn)生的推力相等，故由推進(jìn)器的推力根據(jù)式(2)可求得勻速航行狀態(tài)下AUV的航行速度。AUV在水下巡航時(shí)克服水阻力做功，為簡(jiǎn)化計(jì)算，本文忽略AUV推進(jìn)器之外的所有能耗，故在計(jì)算能量消耗時(shí)所有能耗均用來克服水阻力做功。

AUV在勻速航行過程中消耗的能量如式(3)所示：

E=Pt/η=Fvt/η=FL/η

(3)

將式(2)代入式(3)中得到:

E=Cρv2SL/2η

(4)

其中，L代表AUV航行的路徑長(zhǎng)度，η為機(jī)械效率，P為效率，由式(4)可知，AUV運(yùn)動(dòng)消耗的能量與其運(yùn)行的速度和工作的路徑正相關(guān)。

2.4 規(guī)劃數(shù)學(xué)模型

AUV路徑規(guī)劃問題可以定義為：在某個(gè)規(guī)劃空間中，滿足一定約束條件g(γ)=0的前提下(γ為約束條件變量)，根據(jù)某種航行性能評(píng)價(jià)指標(biāo)J，規(guī)劃得到AUV的航行路線，即為從起始點(diǎn)PS到目標(biāo)點(diǎn)PG且滿足一定約束條件的一系列路徑節(jié)點(diǎn)Γ={PS,P1,P2,…,Pn,PG}。

minγJ=Cρv2SL/2η

(5)

s.t. ?(x,y)?Rff(x,y)=0

(6)

Lg+δg

(7)

(8)

(9)

在AUV路徑規(guī)劃中，主要的約束條件包括：

(1)地形與威脅約束。AUV在航行過程中，必須避開一些地形障礙和威脅區(qū)域，以保證AUV的安全性，在水下三維環(huán)境中，地形障礙和威脅區(qū)域均可表示為AUV不可穿越的區(qū)域。假設(shè)在規(guī)劃區(qū)域中，AUV不可穿越區(qū)域集合為R′f，由于AUV具有一定的尺寸,所規(guī)劃出的路徑還要經(jīng)過平滑處理，為保證路徑的安全性，需要對(duì)障礙物和威脅區(qū)域進(jìn)行一定的膨化處理，經(jīng)膨化處理的集合Rf=εR′f，即擴(kuò)大原始障礙物及威脅區(qū)域，膨化系數(shù)ε根據(jù)AUV的實(shí)際尺寸給定。所規(guī)劃出的路徑曲線為f(x,y)=0，其中，(x,y)表示路徑上任意一點(diǎn)的經(jīng)緯度坐標(biāo)，則規(guī)劃區(qū)域中的地形與威脅約束如式(6)所示。

(2)最大航程約束。AUV自身攜帶的能源決定了其最遠(yuǎn)航行距離，故在路徑規(guī)劃時(shí)必須將其加入約束條件。AUV航程約束如式(7)所示，式中Lmax為AUV所攜帶能量能航行的最大路程；Lg為算法規(guī)劃路徑長(zhǎng)度;δg為實(shí)際航行路程與算法規(guī)劃路程的偏差，該偏差取決于AUV路徑跟蹤算法。

3 改進(jìn)蟻群算法

3.1 基于Dijkstra算法的初始信息素分配

在蟻群算法中，螞蟻通常根據(jù)路徑上信息素濃度的差異來尋找最優(yōu)路徑，在信息素的引導(dǎo)下選擇一條從起始點(diǎn)到目標(biāo)點(diǎn)的完整路徑。由于傳統(tǒng)蟻群算法初始信息素濃度是均勻分配的，這樣算法初期搜索具有較強(qiáng)的盲目性進(jìn)而導(dǎo)致收斂速度慢，容易使算法陷入局部最優(yōu)，影響算法的尋優(yōu)能力[8]。

為了避免因信息素導(dǎo)致算法陷入局部最優(yōu)，減少錯(cuò)誤的啟發(fā)信息對(duì)螞蟻的誤導(dǎo)，提高算法路徑規(guī)劃能力，本文在Dijkstra算法[15-17]所規(guī)劃出的最短路徑基礎(chǔ)上改進(jìn)初始信息素的分配。

由于水下自主航行機(jī)器人所消耗的能量在很大程度上取決于所需跟蹤路徑的長(zhǎng)度，使用Dijkstra算法能規(guī)劃出最短路徑。如圖3所示，將在最短路徑上的點(diǎn)的信息素設(shè)置為τ0，最短路徑兩邊的點(diǎn)的信息素設(shè)置為τ=τ0-λn，其中λ為信息素遞減系數(shù)，n為路徑點(diǎn)距離最短路徑點(diǎn)的柵格數(shù)，即最短路徑周圍的點(diǎn)的信息素濃度隨著與最短路徑點(diǎn)距離增大逐漸減少。

Figure 3 Initial pheromone allocation for improved ant colony algorithm

3.2 啟發(fā)式函數(shù)改進(jìn)

啟發(fā)式函數(shù)對(duì)于算法快速、高效地規(guī)劃出一條安全合理的路徑起著重要的作用，是路徑規(guī)劃算法中的重要組成部分。構(gòu)造函數(shù)時(shí)所考慮的各項(xiàng)因素綜合體現(xiàn)了算法構(gòu)建路徑的優(yōu)化目標(biāo)。本文路徑規(guī)劃算法的優(yōu)化目標(biāo)是安全、能耗最低、路徑盡可能最短的等深航行路線。根據(jù)這一目標(biāo)設(shè)計(jì)的環(huán)境抽象模型中任意點(diǎn)(x,y,z)的啟發(fā)式函數(shù)H(x,y,z)如式(10)所示：

H(x,y,z)=

en·[E(x,y,z)]ζ·[S(x,y,z)]ξ+uc

(10)

其中，ζ和ξ為相關(guān)影響因子；考慮到機(jī)器人路徑中的安全因素，在構(gòu)造三維環(huán)境模型時(shí)，將柵格分為安全區(qū)域K和禁止航行區(qū)域N，安全區(qū)域系數(shù)en的取值如式(11)所示：

(11)

E(x,y,z)為路徑點(diǎn)(x,y,z)所需要消耗的能量，由式(4)可知，選擇下一個(gè)路徑點(diǎn)所需的能量與選擇該路徑點(diǎn)后的路徑長(zhǎng)度和AUV在該點(diǎn)處的速度相關(guān)，AUV在實(shí)際的運(yùn)動(dòng)過程中會(huì)根據(jù)路徑的轉(zhuǎn)彎半徑?(x,y,z)調(diào)節(jié)速度，轉(zhuǎn)彎處轉(zhuǎn)彎半徑越大，相應(yīng)運(yùn)動(dòng)速度會(huì)加快，故下一個(gè)路徑點(diǎn)處所消耗的能量如式(8)所示：

E(x,y,z)=K1/(L1+L2)+K2*?(x,y,z)

(12)

其中,L1表示下一步將要選擇的點(diǎn)與上一個(gè)路徑點(diǎn)的距離;L2表示下一步將要選擇的點(diǎn)與規(guī)劃路徑目標(biāo)點(diǎn)的距離，若下一步選擇的點(diǎn)處于上一個(gè)點(diǎn)與目標(biāo)點(diǎn)所連線段上，則L1+L2的值達(dá)到最小，該點(diǎn)的啟發(fā)信息會(huì)較大；K1和K2分別為路程影響因子和轉(zhuǎn)彎半徑影響因子。

考慮規(guī)劃路徑平滑度因素S(x,y,z)，使得規(guī)劃出來的航線盡可能地平滑以利于控制器求解跟蹤。S(x,y,z)表示考慮環(huán)境障礙時(shí)可行點(diǎn)(x,y,z)的平滑程度，其計(jì)算如式(13)所示:

(13)

其中，yg為下一個(gè)路徑點(diǎn)的坐標(biāo)值,K3為路徑平滑系數(shù)。

海洋往往存在海流，海流隨深度的不同而有所變化，在同一深度，一般表現(xiàn)為水平方向上的均勻流。海流的流速和流向均會(huì)對(duì)AUV的能量消耗產(chǎn)生巨大的影響，海流模型如圖4所示。順海流方向航行時(shí)AUV可以節(jié)省部分能耗，頂流時(shí)AUV需要額外耗費(fèi)能量以保持航速，側(cè)流時(shí)不但需要消耗能量以保持航速，而且海流還會(huì)使AUV偏離原來的航向，加大了控制難度。設(shè)海底存在漸變的速度為Vc，流向?yàn)棣牡臒o旋海流，uc和vc分別為海流投影到水下機(jī)器人橫向和縱向的速度，其計(jì)算分別如式(14)和式(15)所示：

(14)

(15)

Figure 4 AUV current model

3.3 基于線性回歸的信息素更新

信息素是螞蟻尋路的重要依據(jù)，指導(dǎo)螞蟻向更優(yōu)的路徑前進(jìn)。本文通過改進(jìn)信息素更新方式優(yōu)化算法收斂速度與求解質(zhì)量。

3.3.1 基于線性回歸更新全局信息素

由于算法具有隨機(jī)性，每一次迭代的m只螞蟻選擇的路徑點(diǎn)都有可能距離最優(yōu)路徑點(diǎn)較遠(yuǎn)，甚至有些螞蟻在搜索路徑的過程中遇到死鎖，無法找到一條可行的路徑，因此合理的路徑更新方式是螞蟻能夠?qū)ふ业揭粭l可達(dá)路徑的保證。本文采用線性回歸模型[18,19](如式(16)所示)將本輪迭代最具有代表性的路徑點(diǎn)的信息更新一次，強(qiáng)化下一輪螞蟻搜索路徑的方向性，從而提高算法的收斂性能，改善解的質(zhì)量。

(16)

(17)

(18)

(19)

以上各式中，(xi,yi)為第i只螞蟻所選擇路徑點(diǎn)的坐標(biāo)，hω(x)為線性回歸模型，ω為線性回歸模型中的權(quán)重參數(shù)向量，x表示路徑點(diǎn)的橫坐標(biāo)向量，J(ω)為采用梯度下降法求解線性回歸模型的目標(biāo)函數(shù)，η′為學(xué)習(xí)率。

3.3.2 自適應(yīng)調(diào)節(jié)信息素?fù)]發(fā)因子

蟻群算法中的人工螞蟻具有記憶功能，隨著時(shí)間的推移，以前留下的信息素會(huì)逐漸消失，信息素?fù)]發(fā)因子ρi的大小直接影響到蟻群算法的全局搜索能力及其收斂速度。若求解問題的規(guī)模比較大時(shí)，會(huì)使得那些從未被搜索到的路徑上的信息素減少到接近于零，降低了算法的全局搜索能力。本文采用前后2次迭代后線性回歸路徑的長(zhǎng)度來自動(dòng)調(diào)節(jié)信息素?fù)]發(fā)因子，當(dāng)回歸路徑長(zhǎng)度差較大時(shí)，增強(qiáng)信息素的啟發(fā)作用，適當(dāng)調(diào)小ρi，當(dāng)回歸路徑長(zhǎng)度差較小時(shí)，為提升螞蟻尋找新路徑的能力，增強(qiáng)全局搜索能力，適當(dāng)增大ρi，具體調(diào)節(jié)如式(20)所示：

(20)

其中，ΔL為前后2次線性回歸路徑的長(zhǎng)度差;σ為路徑長(zhǎng)度系數(shù)，表征路徑長(zhǎng)度對(duì)信息素的影響程度，為防止ρi過大和過小影響算法收斂速度和求解質(zhì)量，將其限制在[ρmin,ρmax]之間，以此來優(yōu)化蟻群算法。

3.4 路徑平滑

在柵格地圖中規(guī)劃出來的路徑是根據(jù)規(guī)劃出的路徑點(diǎn)坐標(biāo)序列在柵格的中心依序連接而成的折線段，在線段的連接處存在尖峰，容易損壞AUV上的零部件，不利于AUV進(jìn)行路徑的跟蹤，為了解決該問題，本文采用Bezier曲線對(duì)尖峰進(jìn)行平滑處理[20]。

3.5 求解流程

改進(jìn)蟻群算法求解流程如下所示：

(1)首先進(jìn)行參數(shù)初始化，主要包括2類參數(shù)，環(huán)境信息參數(shù)和蟻群算法本身的參數(shù)，這2類參數(shù)對(duì)仿真的結(jié)果有重要的影響。環(huán)境信息參數(shù)包括各個(gè)柵格點(diǎn)上的初始信息素、路徑的起止點(diǎn)和障礙物信息的表達(dá)等；與算法相關(guān)的參數(shù)主要包括算法迭代次數(shù)、同時(shí)尋找路徑的螞蟻只數(shù)、信息素影響因子、信息素常量和啟發(fā)函數(shù)因子等。

(2)開始進(jìn)行迭代，一群螞蟻同步或異步地在問題的相鄰狀態(tài)之間轉(zhuǎn)移，利用關(guān)聯(lián)在每個(gè)狀態(tài)中的信息素和啟發(fā)信息，采用狀態(tài)轉(zhuǎn)移規(guī)則選擇移動(dòng)的方向，逐步構(gòu)造出問題的可行解；每只螞蟻在構(gòu)造可行解時(shí)，可以局部地構(gòu)造信息素；每一代的所有螞蟻都完成了解的構(gòu)造后，依據(jù)獲得的解對(duì)信息素進(jìn)行全局更新。

(3)同時(shí)，完成一次迭代后，根據(jù)優(yōu)化準(zhǔn)則在當(dāng)代中選擇一條最優(yōu)路徑，保留該路徑直到下一次迭代產(chǎn)生更優(yōu)的路徑。

(4)該迭代過程持續(xù)到完成規(guī)定的迭代次數(shù)或者連續(xù)多代迭代結(jié)果一致為止。滿足停止尋優(yōu)條件后，表明已經(jīng)得到一條滿足能耗最低的路徑，再通過平滑路徑得到一條適合AUV跟蹤的平滑路徑。

4 AUV路徑規(guī)劃仿真實(shí)驗(yàn)

4.1 實(shí)驗(yàn)參數(shù)設(shè)置

蟻群算法作為一種啟發(fā)式算法，性能優(yōu)化在很大程度上取決于參數(shù)的設(shè)置，參數(shù)是影響蟻群算法求解效率和全局收斂性能的關(guān)鍵因素之一。由于蟻群算法參數(shù)空間的龐大性以及各參數(shù)之間的關(guān)聯(lián)性，如何確定一組優(yōu)質(zhì)參數(shù)組合使得算法求解性能最佳是一個(gè)復(fù)雜的優(yōu)化問題，本文通過大量的實(shí)驗(yàn)和經(jīng)驗(yàn)，選取了如表1所示的參數(shù)。

Table 1 Parameter setting of improved ant colony algorithm

4.2 規(guī)劃路徑分析

本文根據(jù)建立的三維環(huán)境模型和目標(biāo)函數(shù)(式(5))，利用傳統(tǒng)蟻群算法、改進(jìn)蟻群算法和遺傳算法分別對(duì) AUV 基于能耗最優(yōu)進(jìn)行等深路徑規(guī)劃仿真實(shí)驗(yàn)，最后利用本文所改進(jìn)的蟻群算法對(duì) AUV 定深航行進(jìn)行了路徑規(guī)劃仿真實(shí)驗(yàn)。

本文將AUV航行高度設(shè)為300 m，使用傳統(tǒng)蟻群算法、遺傳算法和改進(jìn)蟻群算法分別進(jìn)行路徑規(guī)劃仿真實(shí)驗(yàn)，各算法分別進(jìn)行80次，其中將改進(jìn)蟻群算法中所需的參數(shù)設(shè)置成表1所示，其統(tǒng)計(jì)結(jié)果如表2所示。圖5～圖10分別為使用傳統(tǒng)蟻群算法、遺傳算法和改進(jìn)蟻群算法所規(guī)劃出的路徑，圖11～圖13是3種算法目標(biāo)函數(shù)的收斂趨勢(shì)圖。

仿真實(shí)驗(yàn)統(tǒng)計(jì)結(jié)果表明，采用改進(jìn)蟻群算法規(guī)劃出的路徑其消耗的能量較傳統(tǒng)蟻群算法和遺傳算法的低，其長(zhǎng)度較傳統(tǒng)蟻群算法和遺傳算法的短。改進(jìn)蟻群算法具有比遺傳算法和傳統(tǒng)蟻群算法更強(qiáng)的求解能力，得到最優(yōu)解的概率更大，能夠規(guī)劃出航程較短、能耗最小的全局路徑,滿足AUV等深度、低能耗航行的要求。

圖5和圖6分別給出了基于傳統(tǒng)蟻群算法所規(guī)劃出的路徑的三維立體視圖和俯視圖。該路徑并非全局最優(yōu)路徑，其原因在于蟻群算法是一種隨機(jī)搜索算法，每只螞蟻要搜索的解空間規(guī)模較大，為了加快算法構(gòu)造解的速度，在算法中增加了啟發(fā)信息所占的比重，即增加了算法的確定性，犧牲了算法的全局尋優(yōu)能力。

Figure 5 3D view of path planning using traditional ant colony algorithm

Figure 6 Vertical view of path planning using traditional ant colony algorithm

Table 2 Statistical results of simulation experiment

算法在迭代的初期，信息素均勻分配導(dǎo)致其正反饋?zhàn)饔貌粡?qiáng)，路徑啟發(fā)信息與當(dāng)前所在路徑點(diǎn)到下一個(gè)路徑點(diǎn)的距離有關(guān)，在啟發(fā)信息的引導(dǎo)下螞蟻更傾向于選擇使得整條路徑長(zhǎng)度更短的路徑點(diǎn)，啟發(fā)信息的方向性較弱，故規(guī)劃出的路徑轉(zhuǎn)折點(diǎn)較多，路徑較長(zhǎng)，AUV消耗的能量較多。

與傳統(tǒng)蟻群算法相比，遺傳算法從串集開始搜索，覆蓋面廣，利于全局擇優(yōu)，路徑搜索不易陷入局部最優(yōu)，由圖7和圖8可知道，由遺傳算法規(guī)劃出的路徑還是不夠平滑，AUV難以跟蹤該路徑。同時(shí)，由于遺傳算法的局部搜索能力較差，導(dǎo)致未經(jīng)改進(jìn)的遺傳算法比較費(fèi)時(shí)，在進(jìn)化后期搜索效率較低，求解時(shí)間較長(zhǎng)。

Figure 7 3D view of path planning using genetic algorithm

Figure 8 Vertical view of path planning using genetic algorithm

改進(jìn)蟻群算法所規(guī)劃的路徑如圖9和圖10所示，該路徑轉(zhuǎn)折點(diǎn)較少，使用Bezier曲線改善路徑的平滑性后，便于AUV跟蹤該路徑，AUV依靠慣性就能很好地跟蹤該路徑，從而減少了能量的消耗，保護(hù)了AUV的機(jī)械結(jié)構(gòu)和電子元器件。

Figure 9 3D view of path planning using improved ant colony algorithm

Figure 10 Vertical view of path planning using improved ant colony algorithm

本文通過對(duì)啟發(fā)函數(shù)、信息素初始化及更新方式的改進(jìn)，從而保證了規(guī)劃出的路徑平滑且能耗較低，使該算法更適合運(yùn)用到水下機(jī)器人的路徑規(guī)劃上。

4.3 能耗分析

從3組算法所規(guī)劃的路徑中分別隨機(jī)地選擇一次實(shí)驗(yàn)結(jié)果，其收斂過程如圖11～圖13所示。從路徑尋優(yōu)的過程中不難發(fā)現(xiàn)，在尋求能耗最優(yōu)的路徑時(shí)，路徑的總長(zhǎng)度并非持續(xù)縮短，這就意味著能耗與路徑長(zhǎng)度在某些情況下會(huì)存在矛盾，影響AUV能耗的因素除路徑長(zhǎng)度外還有AUV轉(zhuǎn)彎幅度和水流等因素。

Figure 11 Convergence process of traditional ant colony algorithm

Figure 12 Convergence process of genetic algorithm

Figure 13 Convergence process of improved ant colony algorithm

遺傳算法同傳統(tǒng)蟻群算法相比，規(guī)劃出的路徑雖然在能量消耗和路徑長(zhǎng)度方面有所改善，但需要更長(zhǎng)的時(shí)間去優(yōu)化路徑，路徑規(guī)劃實(shí)時(shí)性不高。改進(jìn)蟻群算法的求解能力和求解速度相比傳統(tǒng)蟻群算法和遺傳算法都有了很大的提升，較傳統(tǒng)蟻群算法求解時(shí)間縮短了10.74%，較遺傳算法求解時(shí)間縮短了28.05%。

同傳統(tǒng)蟻群算法規(guī)劃出的路徑(如圖5和圖6所示)相比，在改進(jìn)蟻群算法初始化前基于Dijkstra算法分配信息素，這些信息素集中分配在最短路徑附近，在算法的初期，為尋找路徑的螞蟻指明了方向，同時(shí)在每一輪迭代完成后，基于線性回歸模型進(jìn)行全局信息素更新，線性回歸模型路徑上的路徑點(diǎn)更能代表本次迭代的最優(yōu)路徑，加快了算法的收斂速度，提高了算法求解質(zhì)量。最終規(guī)劃出的路徑(如圖9和圖10所示)，能量消耗比傳統(tǒng)蟻群算法降低了20.44%，路徑長(zhǎng)度減少了11.51%。

基于傳統(tǒng)蟻群算法、遺傳算法和改進(jìn)蟻群算法3種路徑規(guī)劃算法的能耗分析見表3。

Table 3 Energy consumption analysis of path planning

由表3可知改進(jìn)蟻群算法求解效率較高，所規(guī)劃出的機(jī)器人路徑符合能量消耗最少的優(yōu)化目標(biāo)，改進(jìn)蟻群算法用于水下機(jī)器人路徑規(guī)劃具有較強(qiáng)的工程意義。

5 結(jié)束語

本文基于蟻群算法對(duì)AUV路徑規(guī)劃問題進(jìn)行了研究，詳細(xì)設(shè)計(jì)了三維空間環(huán)境建模以及蟻群算法在該模型中的搜索模式，結(jié)合能耗最低的優(yōu)化目標(biāo)改進(jìn)了蟻群算法的啟發(fā)函數(shù)、信息素初始分配方式及更新方式，在規(guī)劃出的路徑點(diǎn)上采用貝塞爾曲線改善了路徑的平滑性，便于AUV跟蹤該路徑，最后給出了改進(jìn)蟻群算法的具體流程。實(shí)驗(yàn)結(jié)果表明，改進(jìn)蟻群算法在一定的約束條件下，基于能耗最優(yōu)所規(guī)劃出的路徑較傳統(tǒng)蟻群算法能耗降低了20.44%，較遺傳算法能耗降低了15.20%，適合用于水下三維環(huán)境中AUV的路徑規(guī)劃。