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

?

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

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

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

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

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

0 引言

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

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

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

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

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

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

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

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

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

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

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

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

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

和柵格有關的示意圖分別見圖1和圖2。

2 改進蟻群算法設計

2.1 基于非劣解集的改進蟻群算法

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

目標函數(shù)的數(shù)學描述為

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

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

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

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

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

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

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

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

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

2.2 趨向位置目標的吸引策略

其中,(,)為當前節(jié)點與下一節(jié)點之間的距離。

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

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

2.3 算法流程設計

改進后的蟻群算法流程圖如圖3所示。

3 仿真試驗及分析

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

表1 仿真試驗結果

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

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

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

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

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

4 結束語

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

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

[2] 李曉麗, 謝敬, 傅衛(wèi)平, 等. 一種改進勢場法在多移動機器人避碰規(guī)劃中的應用[J]. 計算機工程與應用, 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*的改進路徑規(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)斗機路徑規(guī)劃方法[J]. 系統(tǒng)工程與電子技術, 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]. 中國工程科學, 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] 段海濱. 蟻群算法原理及其應用[M]. 北京: 科學出版社, 2005.

[7] 張銀玲, 牛小梅. 蟻群算法在移動機器人路徑規(guī)劃中的仿真研究[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] 唐良, 方廷健. 基于改進蟻群算法的路徑規(guī)劃方法[J]. 中國科學技術大學學報, 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] 胡薈, 蔡秀珊. 機器人三維路徑規(guī)劃問題的一種改進蟻群算法[J]. 計算機工程與科學, 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-), 男, 在讀碩士, 主要研究方向為魚雷總體技術.

(責任編輯: 楊力軍)