采用能耗最優(yōu)改進蟻群算法的自治水下機器人路徑優(yōu)化

劉貴杰,劉鵬,穆為磊,王壽軍

(中國海洋大學機電工程系,266100,山東青島)

?

采用能耗最優(yōu)改進蟻群算法的自治水下機器人路徑優(yōu)化

劉貴杰,劉鵬,穆為磊,王壽軍

(中國海洋大學機電工程系,266100,山東青島)

針對傳統(tǒng)路徑優(yōu)化算法中“距離最短能耗非最低”的問題,提出了一種基于能耗最優(yōu)改進蟻群算法的自治水下機器人路徑優(yōu)化算法。該算法通過對水下機器人進行水動力學分析,建立了水下機器人移動過程中的受力模型;得到了機器人移動路徑的能耗計算公式;提出了能耗最優(yōu)的改進蟻群算法,采用路徑能耗的倒數(shù)作為路徑信息素值,實現(xiàn)了能耗指導蟻群進化的目的。實驗結果表明:該算法規(guī)劃的路徑長433.51 m,水下機器人能耗12 235.17 J,算法尋優(yōu)迭代次數(shù)22次;傳統(tǒng)距離最優(yōu)算法規(guī)劃的路徑長393.56 m,水下機器春能耗12 864.99 J,算法尋優(yōu)迭代次數(shù)33次。該算法規(guī)劃的路徑距離雖比傳統(tǒng)算法長10%,但是能耗卻降低了5%,收斂速度明顯比傳統(tǒng)算法快,對降低水下機器人能耗、提高續(xù)航能力有一定的優(yōu)勢。

能耗;蟻群算法;自治水下機器人;距離

自治水下機器人(autonomous underwater vehicle,AUV)具有高自動化和智能化的特點,可以獨立自主地完成水下作業(yè)任務和水下巡航。路徑規(guī)劃是一種典型的優(yōu)化問題,也是水下自治機器人領域的研究熱點,按照某一性能指標(最小工作代價、最短路徑等)得到一條最優(yōu)的水下路徑對水下自治機器人具有重要的意義[1]。通常情況下,AUV優(yōu)化路徑評價指標包括時間最優(yōu)、距離最優(yōu)、能耗最優(yōu),但是AUV的能源需要自身攜帶,從而限制了水下機器人的行動范圍和工作時間,因此在AUV巡航過程中尋找一條能耗最低的優(yōu)化路徑具有重要的實用價值。

在機器人路徑規(guī)劃的算法領域中,常用的全局路徑規(guī)劃方法很多,例如柵格法[2]和人工勢場法[3]。柵格法思想簡單,但是柵格粒度劃分與計算復雜度之間很難找到平衡點;人工勢場法模型簡單、計算量小且實時性好,但是容易產(chǎn)生局部最優(yōu)解問題和死鎖現(xiàn)象。隨著智能控制技術的發(fā)展,出現(xiàn)了A*算法[4]、遺傳算法[5]、蟻群算法[6]、人工魚群算法[7]、粒子群算法[8]和免疫算法[9]等。蟻群算法是一種群體智能隨機優(yōu)化算法,具有正反饋、分布式計算,較強的通用性和魯棒性等特點。

傳統(tǒng)路徑規(guī)劃研究以距離最短為目標函數(shù),選取距離最短的路徑作為最優(yōu)的路徑。這種方法假設機器人移動過程中能耗與移動距離成正比關系,不考慮機器人加減速、轉彎等過程的影響,然而水下AUV移動時存在加減速、定速巡航和轉彎等過程,因此,距離最短的路徑不一定是能耗最低的路徑。

為了使水下AUV獲得能耗最小的優(yōu)化路徑,從而為AUV長時間巡航提供理論基礎,本文提出以能耗最低為目標函數(shù),通過建立AUV運動的速度模型和能耗模型,獲得AUV規(guī)劃路徑的總能耗,并采用路徑能耗更新蟻群算法的信息素,實現(xiàn)路徑向能耗最小的方向進化。

1 拐點速度和總能耗的計算方法

為了準確求解AUV路徑的總能耗,首先需要建立AUV移動速度模型,然后根據(jù)水阻力、推進器推力和效率的計算公式,求得AUV移動時規(guī)劃路徑的總能耗。

1.1 巡航速度模型

為了簡化計算過程的復雜度,忽略AUV移動路徑中的加減速過程,并做如下假設:①AUV勻速開始直線航行,中間轉彎采用低速航行,最終以勻速到達終點;②AUV由直線航行狀態(tài)進入轉彎航行狀態(tài)以及由轉彎航行狀態(tài)重新進入長直線航行狀態(tài)時忽略加減速過程。距離拐角頂點兩側各5 m處為轉彎航行階段。因此,AUV巡航過程可劃分為直線勻速航行和轉彎勻速航行2種,如圖1所示,其中長直線航行速度取2.5 m/s。

圖1 速度模型示意圖

AUV在轉彎時必定要適當減速,因此AUV的轉彎速度低于其做長直線運動時的速度。本文假設不同的轉彎角度對應不同的轉彎速度,對應關系為

vi=0.01αi+0.7

(1)

式中:vi為轉彎速度;αi為轉彎角度,范圍為0°<αi≤180°。

AUV在巡航過程中,巡航過的任意連續(xù)3個點可以構成一個三角形,以中間點為頂點的角為三角形的一個內(nèi)角,如圖1中α1,α2,α3,…,αn所示。

1.2 水阻力的計算

AUV在水下航行時受到水阻力,根據(jù)水動力學公式,得出機器人受到的水阻力為

F=1/(2Cρv2S)

(2)

式中:F為AUV航行時受到的水阻力;C為水動力系數(shù),C的取值不僅與介質性質有關,還與機器人形狀、迎流面積等一系列要素有關,根據(jù)經(jīng)驗一般取0.7;ρ為水的密度;v為AUV的航行速度;S為AUV的橫截面積,實驗樣機的橫截面積為0.035 m2。

由式(2)得

v=(2F/Cρs)1/2

(3)

在AUV勻速移動時水阻力F與推進器產(chǎn)生的推力FT相等,故由推進器的推力可求得勻速航行狀態(tài)下AUV的航行速度。

AUV在水下巡航時克服水阻力做功,如忽略AUV推進器之外的部件發(fā)熱和能耗,AUV能量的消耗為克服水阻力做功,故在計算能量消耗問題時所有能耗均用來克服水阻力做功。

1.3 推進器的推力曲線

本文針對研究團隊研發(fā)的AUV樣機的巡航問題開展研究。該樣機采用TECNADYNE公司的Model 150推進器,該推進器為無刷直流電機,通過改變供電的占空比達到調速的目的。

由牛頓第二定律可知,AUV恒速航行時所受的合力為零,此時推進器產(chǎn)生的推力與水阻力相等。為了獲得推進器的推力曲線,搭建了推進器測試平臺,獲得的推進器推力曲線如圖2所示。

圖2 推進器推力曲線

1.4 速度與效率的關系

Model 150推進器采用無刷直流電機,由無刷直流電機特有的機械特性可知,在一定轉速范圍內(nèi),隨著電機轉速的提高,機械效率逐漸提高,而無刷直流電機的轉速又影響到AUV的航行速度。假設AUV的能量消耗全部轉化為AUV推進器無刷直流電機的能量消耗,那么推進器無刷直流電機的效率直接決定了AUV的工作效率,因此AUV的航行速度與AUV的工作效率存在如下關系

ηi=FTivi/Pi

(4)

式中:ηi為AUV的工作效率;FTi為推進器推力;vi為AUV的航行速度,可由式(1)求出;Pi為輸出功率。

圖3 AUV速度效率曲線

為預測任意速度下AUV的工作效率,用三次函數(shù)擬合AUV航行速度與AUV工作效率曲線,得AUV航行速度vi與AUV的工作效率為

(5)

1.5 能耗計算

假設AUV在巡航過程中以2.5 m/s的初速度從起點出發(fā),經(jīng)過中間各點之后最終以2.5 m/s的速度到達終點。整個運動過程分解為5個長直線航行與轉彎航行的組合以及倒數(shù)第二個巡航點與終點的長直線航行,由此運動過程計算能量消耗。

AUV在勻速航行過程中消耗的能量為

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

(6)

將式(1)代入式(6)得

E=Cρv2SL/2η

(7)

將式(5)代入式(7)得運動過程中的總能耗為

(8)

當vi≠0時,式(8)等價于

∑E=∑0.5CρSL/(-0.073vi+

(9)

令

(10)

由式(6)、式(9)、式(10)可得

∑E∝L/f(vi)

(11)

做函數(shù)f(vi)趨勢曲線,如圖4所示。

圖4 f(vi)趨勢曲線

由式(11)可知,AUV的能耗只與AUV的航行速度和航行距離有關,因此在研究AUV能耗問題上將速度與距離作為直接研究對象。由圖4分析可知,在AUV最大航速2.5 m/s的范圍內(nèi),速度越高能耗越低。

2 基于能耗最優(yōu)的改進蟻群算法

蟻群算法是模擬自然界中螞蟻的覓食行為而形成的一種群體智能優(yōu)化算法。螞蟻在尋找食物的過程中會釋放信息素,而且在尋找食物的過程中會根據(jù)信息素強度指導下一步的移動方向。一條路徑上信息素濃度越高就表明該路徑上通過的螞蟻的數(shù)量越多,其他螞蟻選擇該路徑的可能性越大。

2.1 算法實現(xiàn)步驟

步驟1 參數(shù)設置。本文中為體現(xiàn)路徑以能耗最優(yōu)為主,因此設置信息啟發(fā)式因子α=1.5,期望啟發(fā)式因子β=1,信息素揮發(fā)因子Δ=0.1。對每一代螞蟻來說,將允許搜索的點加入allowed表中,將已巡航的點加入禁忌表tabu中,并在各因子的作用下指導螞蟻尋找路徑,最終獲取每一代螞蟻的最優(yōu)路徑。

步驟2 種群初始化。一般地,種群中個體越多,求出的最優(yōu)解的品質越好,但是計算量也越大。為了兼顧求解效率和求解品質,螞蟻個體數(shù)m取為20,種群進化代數(shù)取為50。

(12)

式中:t為螞蟻編號;i、j、k表示螞蟻當前處于j點,i為j之前經(jīng)過的點,k為j之后待搜索點,k∈allowed;τijk(t)為信息素因數(shù),由能耗決定;δjk(t)為能見度因數(shù),由距離決定。

直到該螞蟻到達終點為止,一個螞蟻個體完成一次路徑搜索。

步驟4 更新信息素。每個螞蟻個體完成一次路徑搜索后進行一次信息素更新,信息素更新為

τ(t+1)=(1-Δ)τ(t)+Δτ(t)

(13)

步驟5 終止條件。當50代螞蟻全部完成搜索后,算法終止。在每一代的搜索過程中記錄算法尋找的最優(yōu)路徑,最終對比50代蟻群尋找出最優(yōu)路徑進行輸出,完成路徑搜尋。

2.2 算法關鍵要素

在每一代蟻群中第一個螞蟻進行搜索時,各巡航點之間的信息素均為1。當每只螞蟻搜尋完所有路徑點后進行信息素更新,信息素的更新由能量決定

(14)

式(14)表明,路徑的總能量影響到信息素的更新。將式(14)代入式(10)中完成信息素更新。路徑能耗越低,信息素的積累量越大,下一只螞蟻選擇低能耗路徑的可能性就越大。

能見度因數(shù)δjk(t)由j、k兩點間的距離djk決定

δjk(t)=1/djk

(15)

兩點之間的距離越小,能見度因數(shù)就越大,螞蟻的選擇概率越高。

3 仿真實驗及分析

3.1 巡航點地圖

選取如圖5所示的海域地圖為測試對象,地圖中包含11個巡航點,巡航點坐標見表1。要求AUV從起點出發(fā)遍歷所有目標點并最終到達終點。

圖5 海域巡航點地圖

巡航點x/my/m113.0423.12237.1213.99323.7029.75425.6217.56537.1516.78637.8022.12740.2928.38835.0723.67933.9426.431031.4035.501143.865.70

3.2 實驗結果及分析

將以上參數(shù)輸入至改進蟻群算法中,經(jīng)過50代螞蟻的搜尋,得到能耗最少的遍歷所有巡航點的路徑,如圖6所示。在此路徑下,AUV航行距離為433.51 m,能耗為12 235.17 J。

圖6 能耗最優(yōu)蟻群算法規(guī)劃路線

為了驗證本文算法的優(yōu)越性,針對同一巡航地圖,采用同樣的蟻群參數(shù)進行了路徑優(yōu)化,得到了基于傳統(tǒng)距離最優(yōu)算法的最優(yōu)路徑,如圖7所示。在此路徑下,AUV航行距離為393.56 m,能耗為12 864.99 J。

圖7 距離最優(yōu)蟻群算法規(guī)劃路線

算法求解過程記錄每次迭代尋優(yōu)路徑的最小能耗和平均能耗,通過算法最優(yōu)迭代次數(shù)比較本文提出的基于能耗最優(yōu)改進蟻群算法和傳統(tǒng)的基于距離最優(yōu)蟻群算法的收斂速度。圖8所示為基于能耗最優(yōu)改進蟻群算法的尋優(yōu)過程,圖9為基于距離最優(yōu)蟻群算法的尋優(yōu)過程,兩種算法的對比見表2。

圖8 能耗最優(yōu)改進蟻群算法的尋優(yōu)過程

圖9 傳統(tǒng)距離最優(yōu)蟻群算法的尋優(yōu)過程

算法質量的好壞會影響程序執(zhí)行效率。時間復雜度和空間復雜度是評價算法性能的重要指標[10],在蟻群優(yōu)化算法中其評價指標公式可做如下簡化[11]。時間復雜度是巡航點的四階函數(shù),記為O(n4)

O(n4)=n(n-1)mT/2

(16)

空間復雜度是巡航點的二階函數(shù),記為O(n2)

O(n2)=3n2+nm

(17)

式中:n為巡航點數(shù);m為螞蟻數(shù);T為迭代次數(shù)。

表2 能耗、距離最優(yōu)蟻群算法的對比

從表2仿真結果來看,基于能耗最優(yōu)改進蟻群算法得到的路線航行距離為433.51 m,比基于傳統(tǒng)距離最優(yōu)算法得到的路線航行距離393.56 m長10%。然而,基于能耗最優(yōu)改進蟻群算法的路線能耗為12 235.17 J,比傳統(tǒng)算法路線能耗12 864.99 J低5%,從收斂速度來看,本文提出的改進算法在尋優(yōu)迭代22次開始收斂,而傳統(tǒng)算法迭代33次才開始收斂,兩種算法的空間復雜度評價值相同,但是本文改進算法的時間復雜度評價值要遠小于傳統(tǒng)算法的時間復雜度評價值。

4 結 論

(1)AUV路徑規(guī)劃問題中實現(xiàn)低能耗才是最終目的。本文提出了一種基于能耗最優(yōu)改進蟻群算法的水下AUV路徑優(yōu)化算法,該方法從AUV的工作效率作為切入點,從能耗因素來考慮AUV的路徑規(guī)劃問題,從仿真實驗結果可以看出,本文提出的規(guī)劃算法比傳統(tǒng)的基于距離最優(yōu)規(guī)劃算法得到的路線雖然距離長一些,但是能耗卻更低,從而有利于提高AUV的續(xù)航能力。本文提出的改進算法以能耗最小為主,距離較短為輔,使尋優(yōu)路徑趨向于能耗最低、距離較短的優(yōu)化路徑,由于優(yōu)化參量的增加,縮小了蟻群搜索空間,從算法的復雜度分析,本文提出的優(yōu)化算法的時間復雜度評價值比傳統(tǒng)算法大幅減小,有利于提高算法收斂速度。

(2)本文提出的能耗最優(yōu)算法雖然較好地實現(xiàn)了AUV的更低能耗,但是在算法的實現(xiàn)過程中忽略了AUV的加減速過程,會對最優(yōu)結果求解產(chǎn)生影響。接下來會考慮加減速過程對AUV能耗的影響。

[1] YUAN Mingxin, WANG Sun’an, WU Canyang, et al. Hybrid ant colony and immune network algorithm based on improved APF for optimal motion planning [J]. Robotica, 2010, 28(6): 833-846.

[2] 王醒策, 張汝波, 顧國昌. 基于勢場柵格法的機器人全局路徑規(guī)劃 [J]. 哈爾濱工程大學學報, 2003, 24(2): 171-174. WANG Xingce, ZHANG Rubo, GU Guochang. Potential grid based global path planning for robots [J]. Journal of Harbin Engineering University, 2003, 24(2): 171-174.

[3] 李擎, 王麗君, 陳博. 一種基于遺傳算法參數(shù)優(yōu)化的改進人工勢場法 [J]. 北京科技大學學報, 2012, 34(2): 202-206. LI Qing, WANG Lijun, CHEN Bo. An improved artificial potential field method with parameters optimization based on genetic algorithms [J]. Journal of University of Science and Technology Beijing, 2012, 34(2): 202-206.

[4] 王殿君. 基于改進A*算法的室內(nèi)移動機器人路徑規(guī)劃 [J]. 清華大學學報(自然科學版), 2012, 52(8): 1085-1089. WANG Dianjun. Indoor mobile-robot path planning based on an improved A*algorithm [J]. Journal of Tsinghua University (Science and Technology), 2012, 52(8): 1085-1089.

[5] 石鐵峰. 改進遺傳算法在移動機器人路徑規(guī)劃中的應 [J]. 計算機仿真, 2011, 28(4): 193-195. SHI Tiefeng. Research on path planning for mobile robot based on improved genetic algorithm [J]. Computer Simulation, 2011, 28(4): 193-195.

[6] 張銀玲, 牛小梅. 蟻群算法在移動機器人路徑規(guī)劃中的仿真研究 [J]. 計算機仿真, 2011, 28(6): 231-234. ZHANG Yinling, NIU Xiaomei. Simulation research on mobile robot planning based on ant colony optimization [J]. Computer Simulation, 2011, 28(6): 231-234.

[7] 周利坤, 劉宏昭. 自適應人工魚群算法在清罐移動機器人路徑規(guī)劃中的應用 [J]. 機械科學與技術, 2012, 31(7): 1085-1089. ZHOU Likun, LIU Hongzhao. An adaptive artificial fish school algorithm for path planning of mobile tank-clearing robot [J]. Mechanical Science and Technology, 2012, 31(7): 1085-1089.

[8] 李擎, 徐銀梅, 張德政. 基于粒子群算法的移動機器人全局路徑規(guī)劃策略 [J]. 北京科技大學學報, 2010, 32(3): 397-402. LI Qing, XU Yinmei, ZHANG Dezheng. Global path planning method form mobile robots based on the particle swarm algorithm [J]. Journal of University of Science and Technology Beijing, 2010, 32(3): 397-402.

[9] 葉兆莉, 袁明新, 程帥. 移動機器人的一種煙花爆炸式新免疫規(guī)劃算法 [J]. 計算機仿真, 2013, 30(3): 323-326. YE Zhaoli, YUAN Mingxin, CHENG Shuai. New fireworks explosive immune planning algorithm for mobile robots [J]. Computer Simulation, 2013, 30(3): 323-326.

[10]張宇山. 進化算法的收斂性與時間復雜度分析的若干研究 [D]. 廣州: 華南理工大學, 2013: 10-17.

[11]傅鵬. 多目標廣義蟻群算法的收斂性、收斂速度和算法復雜度研究及其應用 [D]. 南京: 南京郵電大學, 2014: 16-32.

(編輯 武紅江)

A Path Optimization Algorithm for AUV Using an Improved Ant Colony Algorithm with Optimal Energy Consumption

LIU Guijie,LIU Peng,MU Weilei,WANG Shoujun

(Department of Mechanical and Electrical engineering, Ocean University of China, Qingdao, Shandong 266100, China)

A path optimization algorithm for autonomous underwater vehicles is proposed to solve the problem of the shortest distance with not the lowest energy consumption in the traditional path optimization algorithm. The algorithm bases on an improved ant colony algorithm with optimal energy consumption. A stress model of movement process of AUV in water is built by studying the hydrodynamic analysis of AUV and a formula to calculate the energy consumption of AUV moving path is derived. Then, the improved ant colony algorithm with optimal energy consumption is presented. The inverse of the path energy consumption is used as a path pheromone value to guide evaluation of ant colonies by energy consumption. Experimental results show that the proposed algorithm uses 22 iterations to plan a 433.51 m long path with 12 235.17 J AUV energy consumption, while a traditional algorithm uses 33 iterations to plan a 393.65 m long path with 12 864.99 J AUV energy consumption. The path distance planned by the proposed algorithm is 10% longer than that planned by the traditional algorithm, but it's energy consumption is lower by 5%. It is clear that the algorithm has advantages of reducing the energy consumption and improving the battery life.

energy consumption; ant colony algorithm; autonomous underwater vehicle; distance

2016-03-15

劉貴杰(1968—),男,教授;穆為磊(通信作者),男,講師。

國家自然科學基金資助項目(61540010,61501418)。

時間:2016-09-02

http:∥www.cnki.net/kcms/detail/61.1069.T.20160902.1630.008.html

10.7652/xjtuxb201610014

TP242

A

0253-987X(2016)10-0093-06