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

?

復(fù)雜環(huán)境下UUV完全遍歷路徑規(guī)劃方法

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

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

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

無人水下航行器(UUV); 蟻群算法; 生物激勵神經(jīng)網(wǎng)絡(luò); 完全遍歷路徑規(guī)劃

0 引言

隨著民用和軍用無人水下航行器(unmanned underwater vehicle, UUV)的快速發(fā)展, UUV完全遍歷路徑規(guī)劃的研究越來越受到關(guān)注。完全遍歷路徑規(guī)劃是一種在2D環(huán)境中特殊的路徑規(guī)劃, 指在滿足某種性能指標(biāo)最優(yōu)或準(zhǔn)優(yōu)的前提下, 尋找一條在設(shè)定區(qū)域內(nèi)從始點出發(fā)經(jīng)過所有可達(dá)點的連續(xù)路徑[1]。

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

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

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

1 環(huán)境建模

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

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

文中采用柵格法和生物激勵神經(jīng)網(wǎng)絡(luò)相結(jié)合的建模方法。UUV運動空間由若干柵格組成, 每個柵格作為1個神經(jīng)元, 則整個空間就是神經(jīng)網(wǎng)絡(luò)組成的拓?fù)錉顟B(tài)空間, 每個神經(jīng)元的狀態(tài)由分流方程確定[10]

(2)

通過計算并對每一個柵格賦予相應(yīng)的活性值, 未遍歷柵格活性值被賦予較大值, 碰撞區(qū)柵格活性值被賦予較小值, 已遍歷過的柵格活性值減為0。每個神經(jīng)元都有橫向連接其相鄰的神經(jīng)元, 這些神經(jīng)元間的規(guī)范互連構(gòu)成了平面拓?fù)渚W(wǎng)絡(luò)區(qū)域, 從而生成文中的地圖環(huán)境模型。

2 UUV完全遍歷路徑規(guī)劃

2.1 算法融合

文中將蟻群算法與生物激勵神經(jīng)網(wǎng)絡(luò)相融合, 提出了新的完全遍歷路徑規(guī)劃方法。該方法采用基于柵格法和生物激勵神經(jīng)網(wǎng)絡(luò)建立的環(huán)境模型, 使螞蟻在上述構(gòu)建的拓?fù)渚W(wǎng)絡(luò)結(jié)構(gòu)中搜索前進(jìn)。新的螞蟻轉(zhuǎn)移概率

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

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

2.2 跳出“死角”

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

情況2: UUV在一個區(qū)域內(nèi)遍歷很多柵格之后, 遍歷到某一個柵格, 該柵格鄰域內(nèi)所有的可遍歷柵格都已經(jīng)被遍歷過, 如圖2所示。

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

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

2.3 性能評價指標(biāo)

完全遍歷路徑規(guī)劃常用的性能評價指標(biāo)主要有覆蓋率和重復(fù)率。覆蓋率是指已遍歷區(qū)域的面積與UUV可達(dá)區(qū)域面積的比值, 數(shù)學(xué)定義為

重復(fù)率是指UUV重復(fù)遍歷區(qū)域的面積與可達(dá)區(qū)域面積的比值,數(shù)學(xué)定義

顯然, UUV進(jìn)行遍歷搜索路徑規(guī)劃時, 覆蓋率越大, 重復(fù)率越小, 則其性能更優(yōu)。

2.4 方法流程

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

3 仿真結(jié)果及分析

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

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

表1 環(huán)境地圖1仿真結(jié)果

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

由圖5可以看出, 當(dāng)UUV落入“死角”時,文中方法能以最優(yōu)的路徑使UUV跳出“死角”。

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

通過以上仿真結(jié)果可以看出, 文中的遍歷路徑規(guī)劃方法不僅能夠有效地實現(xiàn)UUV遍歷路徑規(guī)劃, 而且在覆蓋率和重復(fù)率等性能指標(biāo)方面優(yōu)于文獻(xiàn)[8]的遍歷路徑規(guī)劃方法。同時, 文中方法能夠以最短路線跳出“死角”, 在復(fù)雜環(huán)境下更具實用性。

4 結(jié)束語

文中提出蟻群算法與生物激勵神經(jīng)網(wǎng)絡(luò)相融合的完全遍歷路徑規(guī)劃方法, 利用柵格法和生物激勵神經(jīng)網(wǎng)絡(luò)建立環(huán)境建模, 將神經(jīng)元活性值的變化與螞蟻轉(zhuǎn)移概率公式結(jié)合, 克服了蟻群算法需要對環(huán)境提前掃描學(xué)習(xí)的不足。在遍歷過程中遇到“死角”時, 采用蟻群優(yōu)化算法實現(xiàn)UUV以最短路徑跳出“死角”, 避免了生物激勵神經(jīng)網(wǎng)絡(luò)隨機性強, 重復(fù)覆蓋多的缺陷。仿真結(jié)果表明, 文中方法不僅能夠有效地實現(xiàn)UUV的遍歷路徑規(guī)劃, 而且提高了覆蓋率, 降低了重復(fù)率, 在復(fù)雜環(huán)境下具有較高的規(guī)劃效率。后續(xù), 將在此工作基礎(chǔ)上進(jìn)一步展開動態(tài)環(huán)境中的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] 陳鵬, 李彩虹. 移動機器人混合式全遍歷覆蓋路徑規(guī)劃算法[J]. 山東理工大學(xué)學(xué)報:自然科學(xué)版, 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īng)網(wǎng)絡(luò)的移動機器人遍歷路徑規(guī)劃[J]. 裝備制造技術(shù), 2014(12): 30-32.

[6] 邱雪娜, 劉士榮, 宋加濤, 等. 不確定動態(tài)環(huán)境下移動機器人的完全遍歷路徑規(guī)劃[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] 段海濱, 王道波, 于秀芬. 蟻群算法的研究現(xiàn)狀及其展望[J]. 中國工程科學(xué), 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] 張赤斌, 王興松. 基于蟻群算法的完全遍歷路徑規(guī)劃研究[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.

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

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-), 男, 在讀碩士, 主要研究方向為魚雷總體技術(shù).