基于改進(jìn)蟻群算法的UUV三維路徑規(guī)劃方法

溫志文, 蔡衛(wèi)軍, 楊春武

?

基于改進(jìn)蟻群算法的UUV三維路徑規(guī)劃方法

溫志文1,2, 蔡衛(wèi)軍1, 楊春武1

(1. 中國船舶重工集團(tuán)公司 第705研究所, 陜西 西安, 710077; 2. 水下信息與控制國家重點(diǎn)實(shí)驗(yàn)室, 陜西 西安, 710077)

路徑規(guī)劃是水下無人航行器(UUV)研究領(lǐng)域的重要課題之一。針對(duì)已有蟻群算法在采用加權(quán)和法處理多個(gè)目標(biāo)同時(shí)優(yōu)化的路徑規(guī)劃問題時(shí)出現(xiàn)加權(quán)系數(shù)取值不確定性、目標(biāo)函數(shù)偏離理想值、算法運(yùn)行效率較低等問題,以及為了避免蟻群算法收斂速度慢, 容易陷入局部最優(yōu), 提出了一種基于改進(jìn)蟻群算法的路徑規(guī)劃方法。該方法基于Pareto非劣最優(yōu)解集的思想對(duì)多個(gè)目標(biāo)進(jìn)行優(yōu)化組合, 同時(shí)加入了趨向位置目標(biāo)的吸引策略, 有效克服了上述缺陷。3D環(huán)境下的仿真試驗(yàn)證明了該方法的有效性和可行性。

水下無人航行器(UUV); 路徑規(guī)劃; 蟻群算法; 多目標(biāo)優(yōu)化

0 引言

水下無人航行器(underwater unmanned vihicle, UUV)在復(fù)雜海洋環(huán)境下執(zhí)行各種使命時(shí), 首先要具備繞過障礙物向目標(biāo)靠近的能力, 即自主導(dǎo)航與避障能力。UUV路徑規(guī)劃任務(wù)需要在安全航行區(qū)域內(nèi), 按一定的優(yōu)化準(zhǔn)則搜索一條從指定起始點(diǎn)到目標(biāo)點(diǎn)的最優(yōu)路徑(或次優(yōu)路徑)。目前用于全局路徑規(guī)劃的方法主要有人工勢場法、A*搜索算法、神經(jīng)網(wǎng)絡(luò)技術(shù)等[1]。人工勢場法簡單易行, 但容易陷入局部最優(yōu)[2]; A*搜索算法隨著維數(shù)的增加, 算法的時(shí)空要求將很難得到滿足[3]; 遺傳算法計(jì)算量大, 在解決多目標(biāo)優(yōu)化問題時(shí)常出現(xiàn)易收斂到局部最優(yōu)值的情況。文獻(xiàn)[4]采用粒子群算法對(duì)有限數(shù)目的采樣航點(diǎn)進(jìn)行優(yōu)化, 使用高次B樣條曲線擬合出滿足路徑最短且威脅最小的無人戰(zhàn)斗機(jī)3D飛行路徑, 文獻(xiàn)[5]采用遺傳算法對(duì)AUV的3D路徑規(guī)劃進(jìn)行了研究, 得到了具有不同特點(diǎn)的最優(yōu)3D路徑。相較于2D空間環(huán)境, 3D空間規(guī)劃增加了空間的復(fù)雜性, 更適用于實(shí)際情況, 也對(duì)算法的搜索效率提出了較高要求。

蟻群算法是一種啟發(fā)式搜索算法, 具有較強(qiáng)的魯棒性、優(yōu)良的分布式計(jì)算以及易于與其他算法結(jié)合等優(yōu)點(diǎn)[6]。其生物機(jī)理是螞蟻在蟻巢與食物源間尋覓一條最短的可行路徑, 這恰好與路徑規(guī)劃的物理過程不謀而合, 同時(shí), 二者在內(nèi)部機(jī)理上的天然聯(lián)系, 也為基于蟻群算法的路徑規(guī)劃研究提供了有力依據(jù)[7]。

在實(shí)際的UUV路徑規(guī)劃過程中, 路徑性能要求存在多個(gè)目標(biāo), 如路徑最短、規(guī)劃時(shí)間最優(yōu)、安全性能最好、能源消耗最小等, 但這些目標(biāo)之間往往存在著沖突[8]?，F(xiàn)有的蟻群算法處理方法主要采用加權(quán)和法[9], 加權(quán)和法簡單直接地打亂了多個(gè)目標(biāo)之間的制約關(guān)系, 從而使目標(biāo)函數(shù)偏離理想值, 加權(quán)系數(shù)取值需要依靠先前經(jīng)驗(yàn), 算法運(yùn)行效率較低, 導(dǎo)致了優(yōu)化算法尋優(yōu)效果出現(xiàn)偏差。

文中通過借鑒多目標(biāo)優(yōu)化算法中Pareto非劣最優(yōu)解集的思想, 提出一種基于改進(jìn)蟻群算法的路徑規(guī)劃方法, 對(duì)多個(gè)目標(biāo)同時(shí)優(yōu)化的UUV路徑規(guī)劃問題進(jìn)行研究。同時(shí)加入趨向位置目標(biāo)的吸引策略, 提高了算法收斂速度, 從而避免搜索陷入局部最優(yōu)。

1 3D環(huán)境建模

目前電子海圖在水中兵器的應(yīng)用處于探索階段, 由于電子海圖的復(fù)雜性, 通常需要將電子海圖轉(zhuǎn)換成可以直接利用的海圖數(shù)據(jù)環(huán)境模型。

文中采用海圖信息柵格化方法對(duì)某海域的數(shù)字海圖進(jìn)行渲染, 首先將3D規(guī)劃空間均勻分解成××個(gè)等大小的單元, 以柵格單元為路徑規(guī)劃中的最小移動(dòng)單位, 柵格分辨率為1 km。如果某個(gè)柵格屬于碰撞區(qū), 記為1類柵格; 如不屬于碰撞區(qū)則記為0類柵格, 以此表示海圖的碰撞區(qū)信息; 其次對(duì)碰撞區(qū)進(jìn)行處理、合并，消除不可航行路段和陷阱路段, 將碰撞區(qū)規(guī)范成多邊形圖形, 這樣構(gòu)建出的數(shù)據(jù)空間包含了標(biāo)識(shí)起始點(diǎn)、目標(biāo)點(diǎn)、障礙區(qū)、威脅區(qū)以及航路位置信息,可方便利用算法進(jìn)行路徑規(guī)劃。文中對(duì)環(huán)境模型作如下假設(shè)。

1) 將UUV視為質(zhì)點(diǎn), 規(guī)劃路徑的長度在UUV航程內(nèi), 且UUV具有原地轉(zhuǎn)向和垂直爬升的性能。

2) 規(guī)劃環(huán)境為靜態(tài)3D空間, 將障礙物和危險(xiǎn)區(qū)域視為碰撞區(qū), 將不規(guī)則碰撞區(qū)“膨化”處理為立方體(這里假設(shè)規(guī)劃空間的長寬高相同)。

3) 不考慮潮流、海流、電子干擾等其他干擾因素的影響。

胡四一強(qiáng)調(diào)，水是生命之源、生產(chǎn)之要、生態(tài)之基，解決我國日益復(fù)雜的水資源問題，實(shí)現(xiàn)水資源高效利用和有效保護(hù)，根本上要靠制度、靠政策、靠改革。《意見》這一水資源綱領(lǐng)性文件的出臺(tái)和實(shí)施，將極大地推動(dòng)該項(xiàng)制度貫徹落實(shí)，促進(jìn)水資源合理開發(fā)利用和節(jié)約保護(hù)，保障經(jīng)濟(jì)社會(huì)可持續(xù)發(fā)展。

將每個(gè)柵格的中心作為規(guī)劃算法中1個(gè)計(jì)算單位, 稱為“路徑節(jié)點(diǎn)”。在文中取, 根據(jù)從左至右、從下至上的原則為每個(gè)柵格編號(hào), 每個(gè)柵格具有1~1 000之間的唯一編號(hào)。每個(gè)柵格在3D空間中的坐標(biāo)用柵格中心點(diǎn)的位置來表示, 柵格序號(hào)與3D坐標(biāo)的對(duì)應(yīng)關(guān)系由式(1)和式(2)決定。

文中用路徑柵格節(jié)點(diǎn)序號(hào)表示UUV最終的路徑規(guī)劃結(jié)果, 如, 其中為起始點(diǎn)柵格編號(hào),為目標(biāo)點(diǎn)柵格編號(hào),為中間路徑節(jié)點(diǎn)柵格編號(hào)。

和柵格有關(guān)的示意圖分別見圖1和圖2。

2 改進(jìn)蟻群算法設(shè)計(jì)

2.1 基于非劣解集的改進(jìn)蟻群算法

文中以UUV的路徑長度、路徑平滑度、安全性和規(guī)劃時(shí)間的最優(yōu)組合為規(guī)劃目標(biāo)。UUV路徑的安全性是以UUV躲避碰撞區(qū)的能力來衡量,要求規(guī)劃出的路線有效避開碰撞區(qū)。路徑長度的評(píng)價(jià)函數(shù)為各路徑節(jié)點(diǎn)之間的距離和。路徑平滑度的評(píng)價(jià)函數(shù)為路徑轉(zhuǎn)彎角度值的函數(shù)。通過將路徑安全度合理轉(zhuǎn)化為對(duì)障礙區(qū)和威脅區(qū)的規(guī)避能力后, 路徑規(guī)劃目標(biāo)函數(shù)為路徑長度與路徑平滑度這2個(gè)評(píng)價(jià)指標(biāo)的優(yōu)化組合, 同時(shí)考慮了算法的運(yùn)行效率, 即規(guī)劃時(shí)間。這就需要對(duì)以上幾個(gè)目標(biāo)同時(shí)進(jìn)行優(yōu)化, 即多目標(biāo)優(yōu)化。

目標(biāo)函數(shù)的數(shù)學(xué)描述為

其中, 目標(biāo)函數(shù)的3個(gè)分向量分別如下。

2) 規(guī)劃路徑平滑度

文中提出基于非劣解集思想的多目標(biāo)蟻群優(yōu)化算法, 對(duì)多個(gè)目標(biāo)同時(shí)優(yōu)化流程如下。

Step1: 準(zhǔn)備2個(gè)外部非劣解集，分別命名為解集1和解集2。解集1用于存儲(chǔ)每次迭代完成后得到的較優(yōu)解, 解集2用于存儲(chǔ)所有迭代循環(huán)結(jié)束后得到的較優(yōu)解;

Step2: 外部非劣解集只允許兩類解進(jìn)入：一類是目標(biāo)函數(shù)的3個(gè)分向量評(píng)價(jià)指標(biāo)都優(yōu)于已有解集, 同時(shí)把處于劣勢的解集從外部非劣解集中刪除; 另一類是與已有解集相比較, 在保證其中一些分向量評(píng)價(jià)指標(biāo)不處于劣勢的前提下, 另一些分向量評(píng)價(jià)指標(biāo)處于優(yōu)勢;

Step3: 算法開始進(jìn)行1次迭代循環(huán)。首先,將第1個(gè)螞蟻找到的路徑作為1個(gè)解存儲(chǔ)到解集1中, 然后依次將其他螞蟻尋優(yōu)得到的解按Step2的準(zhǔn)則與解集1中已有的解進(jìn)行比較, 本次循環(huán)完成后更新解集1;

Step4: 將第1次循環(huán)完成后解集1中的解存儲(chǔ)到解集2中, 按Step3進(jìn)行下一次循環(huán)。待下一次循環(huán)完成后, 將更新后解集1中的解按Step2的準(zhǔn)則與解集2中已有的解進(jìn)行比較, 同時(shí)更新解集2;

Step5：直到所有迭代循環(huán)完成后, 非劣解集2中存儲(chǔ)的解即為路徑規(guī)劃目標(biāo)函數(shù)的解。

顯然, 對(duì)于多目標(biāo)優(yōu)化問題, 并沒有真正的最優(yōu)解, 所以每次蟻群算法優(yōu)化完畢后外部非劣解集2中存儲(chǔ)的解不可能唯一, 其中的每一個(gè)解都為本次路徑規(guī)劃的較優(yōu)解。

2.2 趨向位置目標(biāo)的吸引策略

其中,(,)為當(dāng)前節(jié)點(diǎn)與下一節(jié)點(diǎn)之間的距離。

這種選擇方式使得螞蟻總是會(huì)優(yōu)先選擇與當(dāng)前節(jié)點(diǎn)距離最近的待選柵格, 忽略了路徑規(guī)劃全局性尋優(yōu)的需求。按此方法尋找到的規(guī)劃路徑往往會(huì)出現(xiàn)“兜圈子”的情況, 致使算法不僅搜索速度慢, 而且得不到全局最優(yōu)路徑。針對(duì)上述問題, 將能見度重新定義為與當(dāng)前節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)之間的距離有關(guān), 采用這一策略, 螞蟻將不再盲目進(jìn)行搜索, 而是優(yōu)先選取待選路徑節(jié)點(diǎn)中與目標(biāo)點(diǎn)距離最近的節(jié)點(diǎn), 提高了算法搜索速度和全局尋優(yōu)能力。新的轉(zhuǎn)移概率公式與能見度定義分別為

采用這一策略后, 螞蟻不再盲目地進(jìn)行路徑搜索, 而是優(yōu)先選擇待選柵格集中離目標(biāo)點(diǎn)最近的柵格, 因此稱該策略為位置目標(biāo)吸引策略。位置目標(biāo)吸引策略將大大提高算法搜索速度, 增強(qiáng)了螞蟻尋優(yōu)的“方向性”, 同時(shí)避免算法陷入局部最優(yōu)。

2.3 算法流程設(shè)計(jì)

改進(jìn)后的蟻群算法流程圖如圖3所示。

3 仿真試驗(yàn)及分析

為驗(yàn)證文中改進(jìn)蟻群算法的可行性與有效性, 進(jìn)行了對(duì)比仿真試驗(yàn)。仿真結(jié)果參見表1。試驗(yàn)采用MATLAB仿真平臺(tái), 運(yùn)用上述建立的3D空間環(huán)境模型。蟻群算法使用經(jīng)過試驗(yàn)測試的參數(shù): 螞蟻數(shù)量, 迭代循環(huán)次數(shù)為50,, 初始信息素, 標(biāo)準(zhǔn)值0。

表1 仿真試驗(yàn)結(jié)果

文中采用文獻(xiàn)[10]中已有的改進(jìn)蟻群算法作為對(duì)比, 并將其命名為參考蟻群算法以示區(qū)別。

定義1: 各代平均代價(jià)函數(shù)值指每次循環(huán)搜索完成后, 所有螞蟻規(guī)劃路徑長度的平均值。

定義2: 各代最優(yōu)路徑的代價(jià)函數(shù)值指每次循環(huán)搜索完成后, 所有螞蟻規(guī)劃路徑長度的最小值。

仿真試驗(yàn)表明, 2種算法都能找到UUV從起點(diǎn)到終點(diǎn)的有效路徑, 但從表1可以看出, 改進(jìn)蟻群算法規(guī)劃出的UUV路徑長度比參考蟻群算法規(guī)劃出的UUV路徑長度平均提高了26.8%。從圖8的各代平均代價(jià)函數(shù)值可以看出的各代平均代價(jià)函數(shù)值,改進(jìn)蟻群算法的各代平均代價(jià)函數(shù)值均優(yōu)于參考蟻群算法,改進(jìn)蟻群算法更能有效地找到較優(yōu)解, 有效避免了陷入局部最優(yōu)。從圖9各代最優(yōu)路徑的代價(jià)函數(shù)值可以看出, 改進(jìn)蟻群算法在第2次迭代就可以找到長度最短的路徑, 而參考蟻群算法需要將近10次迭代才能找到長度最短的路徑, 改進(jìn)蟻群算法搜索效率高于基本蟻群算法。

在參考蟻群算法中, 螞蟻選擇下一路徑節(jié)點(diǎn)時(shí), 只考慮當(dāng)前節(jié)點(diǎn)與下一節(jié)點(diǎn)之間的距離, 忽視了全局路徑規(guī)劃“方向性”和“全局性”的要求, 導(dǎo)致出現(xiàn)了很多“拐點(diǎn)”, 甚至出現(xiàn)“繞彎子”的情況。而改進(jìn)蟻群算法中, 螞蟻選擇下一路徑節(jié)點(diǎn)考慮了與目標(biāo)點(diǎn)之間的距離, 賦予螞蟻具有“方向性”的特點(diǎn), 避免了“繞彎子”的情況, 有效縮短了規(guī)劃路徑長度。在路徑平滑度以及規(guī)劃時(shí)間方面, 更是以44.7%和53.0%的提高幅度遠(yuǎn)遠(yuǎn)優(yōu)于參考蟻群算法, 加快了算法搜索速度, 實(shí)現(xiàn)了UUV路徑長度、平滑度和安全度多個(gè)目標(biāo)的同時(shí)優(yōu)化。參考蟻群算法僅僅以UUV路徑長度作為評(píng)價(jià)路徑規(guī)劃好壞的標(biāo)準(zhǔn), 不能將優(yōu)化問題考慮全面, 文中則采用非劣解集的改進(jìn)蟻群算法, 同時(shí)對(duì)多個(gè)目標(biāo)進(jìn)行優(yōu)化組合, 在保證路徑長度非劣的情況下, 對(duì)UUV路徑平滑度和規(guī)劃時(shí)間也進(jìn)行了優(yōu)化, 規(guī)劃出的路徑更具實(shí)用性。

4 結(jié)束語

針對(duì)已有蟻群算法在采用加權(quán)和法處理多個(gè)目標(biāo)同時(shí)優(yōu)化的路徑規(guī)劃問題時(shí)出現(xiàn)的一系列問題, 基于柵格化數(shù)字海圖環(huán)境模型, 借鑒多目標(biāo)優(yōu)化算法中Pareto非劣最優(yōu)解集的思想, 同時(shí)加入了趨向位置目標(biāo)的吸引策略, 采用改進(jìn)的蟻群算法對(duì)UUV路徑規(guī)劃方法進(jìn)行了研究。仿真試驗(yàn)結(jié)果表明, 改進(jìn)后的蟻群算法提高了算法搜索效率、避免蟻群算法陷入局部最優(yōu)、能有效處理多個(gè)目標(biāo)優(yōu)化組合的UUV路徑規(guī)劃問題。

[1] 柳長安. 無人機(jī)航路規(guī)劃方法研究[D]. 西安: 西北工業(yè)大學(xué), 2003.

[2] 李曉麗, 謝敬, 傅衛(wèi)平, 等. 一種改進(jìn)勢場法在多移動(dòng)機(jī)器人避碰規(guī)劃中的應(yīng)用[J]. 計(jì)算機(jī)工程與應(yīng)用, 2005, 41(17): 56-58.
Li Xiao-li, Xie Jing, Fu Wei-ping, et al. An Evolutionary Artificial Potential Field Method Used to Obstacle- avoidance Planning of Multiple Mobile Robots[J]. Com- puter Engineering and Applications, 2005, 41(17): 56-58.

[3] 漆陽華, 楊戰(zhàn)平, 黃清華. A*的改進(jìn)路徑規(guī)劃算法[J].信息與電子工程, 2009, 7(4): 326-329.
Qi Yang-hua, Yang Zhan-ping, Huang Qing-hua. Improved Path Planning Algorithm Based on A* Algorithm [J]. Information and Electronic Engineering, 2009, 7(4): 326-329.

[4] 張雷, 王道波, 段海濱. 基于粒子群優(yōu)化算法的無人戰(zhàn)斗機(jī)路徑規(guī)劃方法[J]. 系統(tǒng)工程與電子技術(shù), 2008, 30(3): 506-510.
Zhang Lei, Wang Dao-bo, Duan Hai-bin. Study on Unin- habited Combat Arial Vehicle Path Planning Method Based on |Particle Swarm Optimization Algorithm[J]. Systems Engineering and Electronics, 2008, 30(3): 506- 510.

[5] 郝燕玲, 張京娟. 基于遺傳算法的AUV三維海底路徑規(guī)劃[J]. 中國工程科學(xué), 2003, 5(11): 56-60.
Hao Yan-ling, Zhang Jing-juan. AUV Path Planning in 3D Seabed Environment Using Genetic Algorithm[J]. Engi- neering Science, 2003, 5(11): 56-60.

[6] 段海濱. 蟻群算法原理及其應(yīng)用[M]. 北京: 科學(xué)出版社, 2005.

[7] 張銀玲, 牛小梅. 蟻群算法在移動(dòng)機(jī)器人路徑規(guī)劃中的仿真研究[J]. 計(jì)算機(jī)仿真, 2011, 28(6): 231-234.
Zhang Yin-ling, Niu Xiao-mei. Simulation Research on Mobile Robot Path Planning Based on Ant Colony Optimization[J]. Computer Simulation, 2011, 28(6): 231-234.

[8] 趙濤, 劉明雍, 周良榮. 自主水下航行器的研究現(xiàn)狀與挑戰(zhàn)[J]. 火力與指揮控制, 2010, 35(6): 1-6.
Zhao Tao, Liu Ming-Yong, Zhou Ling-Rong. A Survey of Autonomous Underwater Vehicle Recent Advances and Future Challenges[J]. Fire Control & Command Control, 2010, 35(6): 1-6.

[9] 唐良, 方廷健. 基于改進(jìn)蟻群算法的路徑規(guī)劃方法[J]. 中國科學(xué)技術(shù)大學(xué)學(xué)報(bào), 2009, 39(9): 980-983.
Tang Ling, Fang Ting-Jian. Path Planning Method Based on Improved ant Colony Algorithm[J]. Journal of University of Science and Technology of China, 2009, 39(9): 980-983.

[10] 胡薈, 蔡秀珊. 機(jī)器人三維路徑規(guī)劃問題的一種改進(jìn)蟻群算法[J]. 計(jì)算機(jī)工程與科學(xué), 2012, 34(11): 153-157.
Hu Hui, Cai Xiu-shan. An Improved Ant Colony Algo- rithm for Three-dimensional Path Planning of Robots[J]. Computer Engineering and Science, 2012, 34(11): 153- 157.

Three-dimensional Path Planning Method Based on Improved Ant Colony Algorithm for UUV

WEN Zhi-wen1,2, CAI Wei-jun1, YANG Chun-wu1

(1. The 705 Research Institute, China Shipbuilding Industry Corporation, Xi′an 710077, China; 2. Science and Technology on Underwater Information and Control Laboratory, Xi′an 710077, China)

A path planning method based on improved ant colony algorithm is presented for an UUV to solve the problem that the current ant colony algorithm exists uncertainty of weight coefficient, deviation of objective function values from ideal value, low efficiency, slow convergence speed, and possibility falling into local optimum in dealing with the path planning of multi-objective optimization by using its weighted sum method. This method optimizes the combination of multiple objectives according to the idea of Pareto noninferior optimal solution set, and applies the attraction strategy of trend position object to effectively overcome the above defects. Simulation experiment in three-dimensional environment shows that the present method is effective and feasible.

underwater unmanned vehicle(UUV); path planning; ant colony algorithm; multi-objective optimization

10.11993/j.issn.1673-1948.2016.02.008

TJ630.33

A

1673-1948(2016)02-0120-06

2016-03-02;

2016-03-21.

. 溫志文(1992-), 男, 在讀碩士, 主要研究方向?yàn)轸~雷總體技術(shù).

(責(zé)任編輯: 楊力軍)