復雜環境下UUV完全遍歷路徑規劃方法

溫志文, 楊春武, 蔡衛軍, 毛金明

?

復雜環境下UUV完全遍歷路徑規劃方法

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

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

針對復雜環境下無人水下航行器(UUV)完全遍歷路徑規劃方法的不足, 文中基于蟻群算法和生物激勵神經網絡, 提出了一種高覆蓋率、低重復率的完全遍歷路徑規劃方法。該方法基于柵格法和生物激勵神經網絡進行環境建模, 將神經元活性值引入螞蟻轉移概率公式中, 既克服了蟻群算法需要對環境提前掃描學習, 運算復雜的不足, 又避免了生物激勵神經網絡隨機性強, 重復率高的缺陷。仿真試驗表明, 文中方法不僅有效實現了復雜環境下UUV完全遍歷路徑規劃, 而且能夠以最短路線跳出死角, 具有覆蓋率大、重復率小, 實用性強的優點。該研究可為進一步開展動態環境中的UUV完全遍歷路徑規劃提供參考。

無人水下航行器(UUV); 蟻群算法; 生物激勵神經網絡; 完全遍歷路徑規劃

0 引言

隨著民用和軍用無人水下航行器(unmanned underwater vehicle, UUV)的快速發展, UUV完全遍歷路徑規劃的研究越來越受到關注。完全遍歷路徑規劃是一種在2D環境中特殊的路徑規劃, 指在滿足某種性能指標最優或準優的前提下, 尋找一條在設定區域內從始點出發經過所有可達點的連續路徑[1]。

目前, 常用的完全遍歷路徑規劃主要有模板算法和分塊算法兩類[2]。模板算法對整個環境缺乏整體的規劃, 效率低且容易落入“陷阱”, 進入死循環狀態; 分塊方法根據障礙物分布情況將環境空間劃分為一系列不重合的、有限個無障礙子區域, 然后在此基礎上進行每個區域的遍歷[3]。文獻[4]采用模糊控制方法實現移動機器人的遍歷路徑規劃; 文獻[5]運用生物激勵神經網絡實現機器人的遍歷路徑規劃; 文獻[6]基于生物激勵神經網絡、滾動窗口、啟發式搜索, 提出了一種新的遍歷路徑規劃方法。

蟻群算法是一種啟發式搜索算法, 具有較強的魯棒性、優良的分布式計算以及易于與其他算法結合等優點[7]。然而, 將蟻群算法直接應用于完全遍歷路徑規劃需要對環境進行先驗的掃描學習過程, 使得算法運算復雜、實時性差, 計算機存儲量大[8]。生物激勵神經網絡是由SimonX. Yang提出來的一種新穎的路徑規劃方法[9]。與其他路徑規劃方法比較, 該方法不需要對環境做出任何提前掃描, 不受環境中障礙物的形狀和位置的影響, 不需要學習過程, 并且計算復雜度小、計算機存儲量小、反應速度快。但生物激勵神經網絡方法, 在應用于遍歷路徑規劃時會出現遍歷無規律, 重復遍歷次數多的不合理現象, 其規劃的路徑效率不高, 最大的不足就是跳出“死角”的路徑不是最優的。由于以上各種方法的局限性, 方法之間的融合得到了廣泛關注。

文中將蟻群算法與生物激勵神經網絡進行融合, 提出了一種完全遍歷路徑規劃方法。該方法基于柵格法和生物激勵神經網絡進行環境建模, 將神經元活性值的變化與螞蟻轉移概率公式結合, 克服了蟻群算法需要對環境提前掃描學習的不足。在遍歷過程中遇到“死角”時, 采用蟻群優化算法實現UUV以最優路徑跳出“死角”, 避免了生物激勵神經網絡出現隨機性選擇和重復覆蓋多的缺陷。仿真結果表明, 該方法覆蓋率高, 重復率小, 在復雜環境條件下實用性更強。

1 環境建模

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

文中采用海圖信息柵格化方法對某海域的數字海圖進行渲染, 首先將2D規劃空間均勻分解成個柵格單元, 以柵格單元為路徑規劃中的最小移動單位, 柵格分辨率根據UUV的尺寸自適應調整。如果某個柵格屬于碰撞區, 記為1類柵格; 如不屬于碰撞區則記為0類柵格, 以此表示海圖的碰撞區信息。其次對碰撞區進行處理、合并, 消除不可航行路段和陷阱路段, 將碰撞區規范成多邊形圖形, 這樣構建出的數據空間包含了標識起始點、目標點、障礙區、威脅區以及航路位置信息, 可方便利用算法進行路徑規劃。文中對環境模型作如下假設: 1) 將UUV視為質點, 規劃路徑的長度在UUV航程內; 2) 規劃環境為2D空間, 將障礙物和危險區域統稱為碰撞區, 以不規則區域表示; 3) 不考慮潮流、海流、電子干擾等其他干擾因素的影響。

文中采用柵格法和生物激勵神經網絡相結合的建模方法。UUV運動空間由若干柵格組成, 每個柵格作為1個神經元, 則整個空間就是神經網絡組成的拓撲狀態空間, 每個神經元的狀態由分流方程確定[10]

(2)

通過計算并對每一個柵格賦予相應的活性值, 未遍歷柵格活性值被賦予較大值, 碰撞區柵格活性值被賦予較小值, 已遍歷過的柵格活性值減為0。每個神經元都有橫向連接其相鄰的神經元, 這些神經元間的規范互連構成了平面拓撲網絡區域, 從而生成文中的地圖環境模型。

2 UUV完全遍歷路徑規劃

2.1 算法融合

文中將蟻群算法與生物激勵神經網絡相融合, 提出了新的完全遍歷路徑規劃方法。該方法采用基于柵格法和生物激勵神經網絡建立的環境模型, 使螞蟻在上述構建的拓撲網絡結構中搜索前進。新的螞蟻轉移概率

基本原理為柵格未遍歷時, 其活性值最大, 對螞蟻的吸引力也最大, 吸引螞蟻對其進行遍歷。當螞蟻對其遍歷后, 活性值變為0, 對螞蟻沒有吸引力。而碰撞區的柵格由于其活性值為負, 對螞蟻具有排斥力, 避免螞蟻對其進行遍歷。由上述螞蟻轉移概率公式可知, 螞蟻在選擇下一遍歷柵格時, 與柵格信息素、活性值、距離及轉彎角度都有關系, 通過蟻群算法的迭代尋優, 可以得到最優的遍歷路徑。

文中搜索策略采用內螺旋覆蓋方法。內螺旋搜索策略是指UUV在遍歷搜索過程中, 當遍歷到某一處之后, 發現相鄰的若干個未被遍歷柵格具有相同的最大轉移概率, 此時UUV將優先選擇其中某一柵格, 使得這個柵格與已遍歷柵格組成的搜索路徑總體來看呈逆時針向內螺旋搜索狀態。這種方法可以最大限度減少UUV轉彎的次數, 使得能源消耗最小。

2.2 跳出“死角”

在遍歷路徑規劃過程中, “死角”為比較惡劣的環境區域, 也是最能體現算法優越性的環境模型。它是指UUV遍歷到某一處后, 相鄰的8個柵格是障礙區或者已遍歷區, 此時判定UUV陷入“死角”。UUV陷入“死角”有2種情況, 情況1: UUV所在柵格的鄰域內除上一步經過的柵格外其余全是障礙柵格, 這種情況為UUV落入“死角”, 如圖1所示。

情況2: UUV在一個區域內遍歷很多柵格之后, 遍歷到某一個柵格, 該柵格鄰域內所有的可遍歷柵格都已經被遍歷過, 如圖2所示。

在圖1中, 黑色柵格表示障礙區。當UUV從柵格44走到柵格34完成柵格34的遍歷后, 發現相鄰的柵格除柵格44(已遍歷)外, 其余的都是障礙區, 此時UUV落入情況1所示的“死角”。UUV沿路線實行回退策略。在柵格54處, UUV檢測出臨近神經元活性值最大的有多個, 如果僅僅采用生物激勵神經網絡進行遍歷, UUV將隨機選取具有最大活性值的神經元其中的一個進行移動, 如此, UUV所走的路徑將有可能繞遠, 而不是最優路徑, 出現覆蓋無規律和重復覆蓋多的缺陷。

同理, 在圖2中UUV由柵格44遍歷到柵格34后, 發現相鄰的柵格除了障礙區都已被遍歷(如柵格24已被遍歷), 此時UUV落入情況2所示的“死角”。文中方法將蟻群算法和生物激勵神經網絡進行融合, 引入規則制導策略。當UUV落入上述“死角”時, 根據神經元拓撲網絡結構, UUV搜索附近最近的未被遍歷過的神經元, 然后運用蟻群算法, 以當前柵格34為起始點, 目標柵格為終點, 規劃一條路徑最短的線路, 使得UUV以最短路徑跳出死角, 避免了UUV遇到“死角”隨機無規律的移動, 減少了重復率, 其中跳出“死角”時的螞蟻轉移概率公式(3)所示。

2.3 性能評價指標

完全遍歷路徑規劃常用的性能評價指標主要有覆蓋率和重復率。覆蓋率是指已遍歷區域的面積與UUV可達區域面積的比值, 數學定義為

重復率是指UUV重復遍歷區域的面積與可達區域面積的比值,數學定義

顯然, UUV進行遍歷搜索路徑規劃時, 覆蓋率越大, 重復率越小, 則其性能更優。

2.4 方法流程

文中遍歷路徑規劃方法的流程如圖3所示。

3 仿真結果及分析

為驗證文中完全遍歷路徑規劃方法的有效性和可行性, 運用上述建立的環境模型進行仿真試驗。文中采用VS2005設計仿真平臺界面, 在該界面中, 可隨意設計任意形狀的碰撞區域, 也可單步查看UUV任一時刻遍歷搜索的進程, 仿真結果以直觀、形象的方式顯示。其中, 蟻群算法使用經過試驗測試的參數: 螞蟻數量, 迭代循環次數, 初始信息素, 標準值。生物激勵神經網絡方法也使用經過測試的參數:=10,==1,。

由圖4可以看出, UUV很好地避開不規則碰撞區, 有效地完成了遍歷路徑規劃, 驗證了文中方法的有效性和可行性。表1為對環境地圖1的仿真結果。由表中可知, 文中方法規劃路徑覆蓋率為100%, 重復率為7.548%。相比文獻[8]覆蓋率95%, 重復率10.000%的結果, 文中方法不僅達到了完全覆蓋的效果, 而且降低了重復率, 因此更具優越性。

表1 環境地圖1仿真結果

相比于文獻[8]提出的完全遍歷路徑規劃方法僅僅適用于碰撞區為規則形狀的簡單環境模型的缺陷, 文中提出的規劃方法適用于不規則碰撞區且隨機分布的復雜環境模型。建立可以隨意布置不規則碰撞區的復雜環境地圖2, 其由個柵格的神經網絡組成。圖5為復雜環境模型中, UUV遍歷到第102步跳出“死角”的仿真圖。

由圖5可以看出, 當UUV落入“死角”時,文中方法能以最優的路徑使UUV跳出“死角”。

圖6為復雜環境2中UUV完全遍歷路徑規劃仿真結果圖。由圖6可以看出, 在復雜環境模型中, UUV遍歷路徑規劃的覆蓋率仍達100%, 重復率低于10%, 表明文中提出的規劃方法更具實用性。

通過以上仿真結果可以看出, 文中的遍歷路徑規劃方法不僅能夠有效地實現UUV遍歷路徑規劃, 而且在覆蓋率和重復率等性能指標方面優于文獻[8]的遍歷路徑規劃方法。同時, 文中方法能夠以最短路線跳出“死角”, 在復雜環境下更具實用性。

4 結束語

文中提出蟻群算法與生物激勵神經網絡相融合的完全遍歷路徑規劃方法, 利用柵格法和生物激勵神經網絡建立環境建模, 將神經元活性值的變化與螞蟻轉移概率公式結合, 克服了蟻群算法需要對環境提前掃描學習的不足。在遍歷過程中遇到“死角”時, 采用蟻群優化算法實現UUV以最短路徑跳出“死角”, 避免了生物激勵神經網絡隨機性強, 重復覆蓋多的缺陷。仿真結果表明, 文中方法不僅能夠有效地實現UUV的遍歷路徑規劃, 而且提高了覆蓋率, 降低了重復率, 在復雜環境下具有較高的規劃效率。后續, 將在此工作基礎上進一步展開動態環境中的UUV完全遍歷路徑研究。

[1] Choset H. Coverage for Robotics——A Survey of Recent Results[J]. Annals of Mathematics & Artificial Intelligence, 2001, 31(1-4): 113-126.

[2] De Carvalho R N, Vidal H A, Vieira P, et al. Complete Coverage Path Planning and Guidance for Cleaning Robots[C]//IEEE International Symposium on Industrial Electronics: Portugal, 1997(2): 677-682.

[3] Acar E U, Choset H. Robust Sensor——Based Coverage of Unstructured Environments[C]//Proceedings of the 2001 IEEE/RSJ on Intelligent Robots and Systems. Maui: IEEE, 2001: 61-68.

[4] 陳鵬, 李彩虹. 移動機器人混合式全遍歷覆蓋路徑規劃算法[J]. 山東理工大學學報:自然科學版, 2013, 27(5): 22-27. Chen Peng, Li Cai-hong. A Hybrid Algorithm of Com- plete Coverage Path Planning for Mobile Robot[J]. Journal of Shandong University of Technology(Natural Science Edition), 2013, 27(5): 22-27.

[5] 朱博, 鄧三鵬, 王英飛, 等. 基于生物激勵神經網絡的移動機器人遍歷路徑規劃[J]. 裝備制造技術, 2014(12): 30-32.

[6] 邱雪娜, 劉士榮, 宋加濤, 等. 不確定動態環境下移動機器人的完全遍歷路徑規劃[J]. 機器人, 2006, 28(6): 586-592.Qiu Xue-na, Liu Shi-rong, Song Jia-tao, et al. A Complete Coverage Path Planning Method for Mobile Robots in Uncertain Dynamic Environments[J]. Robot, 2006, 28(6): 586-592.

[7] 段海濱, 王道波, 于秀芬. 蟻群算法的研究現狀及其展望[J]. 中國工程科學, 2007, 9(2): 98-102.

Duan Hai-bin, Wang Dao-bo, Yu Xiu-fen. Ant Colony Algorithm: Survey and Prospect[J]. Engineering Science, 2007, 9(2): 98-102.

[8] 張赤斌, 王興松. 基于蟻群算法的完全遍歷路徑規劃研究[J]. 中國機械工程, 2008, 19(16): 1945-1949.Zhang Chi-bin, Wang Xing-Song.Complete Coverage Path Planning Based on Ant Colony Algorithm[J]. China Mechanical Engineering, 2008, 19(16): 1945-1949.

[9] Yang S X, Meng M. Neural Network Approaches to Dynamic Collision-free Trajectory Generation[J]. IEEE Tr- ansactions on Systems Man & Cybernetics Part B Cybe- rnetics A Publication of the IEEE Systems Man & Cybernetics Society, 2001, 31(3): 302-318.

[10] Bernabucci I, Conforto S, Capozza M, et al. A Biologically Inspired Neural Network Controller for Ballistic Arm Movements[J]. Journal of Neuroengineering & Rehabilitation, 2007, 4(1): 1-17.

(責任編輯: 楊力軍)

A Complete Coverage Path Planning Method of UUV under Complex Environment

WEN Zhi-wenYANG Chun-wuCAI Wei-junMAO Jin-ming

(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 new method with high coverage rate and low repetition rate is presented to solve the complete coverage path planning problem for an unmanned underwater vehicle(UUV) under complex environment. The method integrates ant colony algorithm and biologically inspired neural network. In this method, environment is modeled with grid cell and biologically inspired neural network, and the neuronic activity is introduced into the ant transition probability formula. As a result, the shortcomings of ant colony algorithm, e.g., scanning and learning environment in advance are needed and computation is complicated, are overcome, and the defects of high complexity, high randomness and high repetition rate of the biologically inspired neural network are avoided. Simulation experiment in complex environment shows that complete coverage path planning of UUV can be efficiently implemented by the proposed method, and the method can get rid of the dead corner in the shortest route. The present method has higher coverage rate and lower repetition rate. This research may provide a reference for further improvement of the UUV complete coverage path planning in dynamic environment.

unmanned underwater vehicle(UUV); ant colony algorithm; biologically inspired neural network; complete coverage path planning

10.11993/j.issn.1673-1948.2017.01.005

TJ630.33; TP24

A

1673-1948(2017)01-0022-05

2016-10-08;

2016-12-13.

溫志文(1992-), 男, 在讀碩士, 主要研究方向為魚雷總體技術.