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

溫志文, 蔡衛軍, 楊春武

?

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

溫志文1,2, 蔡衛軍1, 楊春武1

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

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

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

0 引言

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

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

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

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

1 3D環境建模

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

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

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

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

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

胡四一強調，水是生命之源、生產之要、生態之基，解決我國日益復雜的水資源問題，實現水資源高效利用和有效保護，根本上要靠制度、靠政策、靠改革。《意見》這一水資源綱領性文件的出臺和實施，將極大地推動該項制度貫徹落實，促進水資源合理開發利用和節約保護，保障經濟社會可持續發展。

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

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

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

2 改進蟻群算法設計

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

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

目標函數的數學描述為

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

2) 規劃路徑平滑度

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

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

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

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

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

Step5：直到所有迭代循環完成后, 非劣解集2中存儲的解即為路徑規劃目標函數的解。

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

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

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

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

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

2.3 算法流程設計

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

3 仿真試驗及分析

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

表1 仿真試驗結果

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

定義1: 各代平均代價函數值指每次循環搜索完成后, 所有螞蟻規劃路徑長度的平均值。

定義2: 各代最優路徑的代價函數值指每次循環搜索完成后, 所有螞蟻規劃路徑長度的最小值。

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

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

4 結束語

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

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

[2] 李曉麗, 謝敬, 傅衛平, 等. 一種改進勢場法在多移動機器人避碰規劃中的應用[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] 漆陽華, 楊戰平, 黃清華. A*的改進路徑規劃算法[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] 張雷, 王道波, 段海濱. 基于粒子群優化算法的無人戰斗機路徑規劃方法[J]. 系統工程與電子技術, 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三維海底路徑規劃[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] 張銀玲, 牛小梅. 蟻群算法在移動機器人路徑規劃中的仿真研究[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] 趙濤, 劉明雍, 周良榮. 自主水下航行器的研究現狀與挑戰[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]. 中國科學技術大學學報, 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]. 計算機工程與科學, 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-), 男, 在讀碩士, 主要研究方向為魚雷總體技術.

(責任編輯: 楊力軍)