鄒佳運, 曲泓玥, 陳志鵬

大規(guī)模水下滑翔機(jī)集群區(qū)域覆蓋探測路徑規(guī)劃

鄒佳運1,2, 曲泓玥2*, 陳志鵬3

(1. 中國人民解放軍 海軍潛艇學(xué)院, 山東 青島, 266199; 2. 青島海洋科學(xué)與技術(shù)試點國家實驗室, 山東 青島, 266237; 3. 海裝沈陽局駐葫蘆島地區(qū)軍事代表室, 遼寧 葫蘆島, 125003)

在水下滑翔機(jī)集群執(zhí)行搜索任務(wù)時, 通過合理設(shè)定各平臺的搜索路徑, 能夠有效提高集群的探測效能, 從而實現(xiàn)利用最少平臺的最大化探測區(qū)域覆蓋。為解決大規(guī)模集群任務(wù)規(guī)劃中計算量巨大的問題, 文中在柵格法的基礎(chǔ)上, 通過幾何劃定有效覆蓋區(qū)域并反演柵格序數(shù)的方法, 構(gòu)建了評價覆蓋能力的高精度布爾模型, 并以此為支撐, 利用群智能方法實現(xiàn)了大規(guī)模集群對廣域海區(qū)的快速路徑規(guī)劃。在此基礎(chǔ)上, 利用序貫思想, 提出了以較小計算量解決集群平臺數(shù)量最小化的方法。通過仿真試驗驗證了該方法的可行性。文中的方法可為大規(guī)模水下滑翔機(jī)集群的探測任務(wù)規(guī)劃提供支持。

水下滑翔機(jī)集群; 探測; 任務(wù)規(guī)劃; 區(qū)域覆蓋

0 引言

水下無人平臺能夠在惡劣環(huán)境下完成長時間的警戒任務(wù)[1], 成本較低, 但隨著水下探測任務(wù)的復(fù)雜化, 單一的水下無人平臺已無法應(yīng)對多樣的任務(wù)需求[2]。水下無人集群技術(shù)以其高魯棒性、高效率和低成本的特點[3], 越來越受到人們的重視, 并廣泛應(yīng)用于海洋觀測、搜救、反潛及掃雷等領(lǐng)域[4]。

近年來, 以水下滑翔機(jī)為代表的低速、長航程無人水下航行器, 以其更長的工作時間和更廣闊的搜索區(qū)域, 受到了越來越多的青睞。此類平臺在使用時, 一般采用順流布放的方式借助海流增加航程, 但對于集群探測問題, 受目標(biāo)海區(qū)邊界及各平臺航路間的相互影響, 單純地順流布放可能導(dǎo)致大量的平臺沖出目標(biāo)海區(qū)和航路重疊問題, 從而降低集群搜索效能。在一定條件下, 一定角度的側(cè)流航行雖然無法達(dá)到單平臺的最大區(qū)域覆蓋, 但若能夠有效地填補平臺間的空隙, 則能夠使得集群整體的探測效能最大化。

為提高該類別無人集群對水下目標(biāo)的探測效能, 需要對集群的搜索路徑進(jìn)行優(yōu)化, 以期利用最少的平臺數(shù)量實現(xiàn)區(qū)域覆蓋最大化。目前, 對水下無人集群的區(qū)域覆蓋能力研究集中于組網(wǎng)的靜止節(jié)點部署[5-6], 路徑規(guī)劃則集中于解決避碰、避障問題[7-8], 而對移動平臺的探測區(qū)域覆蓋能力研究較少, 若能夠根據(jù)海區(qū)條件及無人系統(tǒng)的性能參數(shù)對任務(wù)進(jìn)行合理規(guī)劃, 則能夠有效降低任務(wù)成本, 提高任務(wù)效能。移動平臺的最大化區(qū)域覆蓋任務(wù)規(guī)劃能力能夠?qū)Φ蜋C(jī)動能力目標(biāo)(如水雷、黑匣子等)的區(qū)域內(nèi)搜索提供參考。

1 集群探測覆蓋模型

目前一般利用柵格法對無人集群的探測效能進(jìn)行評估。該方法將待評估海區(qū)柵格化, 令目標(biāo)在全部柵格中遍歷, 以探測系統(tǒng)對各柵格內(nèi)目標(biāo)的探測能力來評價其探測效能。單無人平臺的探測半徑一般為3~5 km, 為獲得較為連續(xù)的有效探測區(qū)域邊界, 柵格邊長需要數(shù)百米, 但大規(guī)模集群的目標(biāo)海區(qū)面積可能高達(dá)數(shù)萬平方公里, 這就會導(dǎo)致柵格數(shù)目極多, 進(jìn)而在進(jìn)行柵格遍歷時產(chǎn)生極大的運算量。

圖1 有效探測區(qū)域示意圖

圖2 有效探測區(qū)域評估示意圖

可以求得各頂點的坐標(biāo)分別為

在確定各邊解析式后, 即可計算有效評估區(qū)域內(nèi)柵格的集合。

有效探測區(qū)域篩選方法如下:

算法流程如圖3所示。

圖3 評估算法流程圖

2 集群探測路徑規(guī)劃

對于集群探測系統(tǒng), 各平臺的起始位置及航向決定了該輪探測集群對目標(biāo)海區(qū)的覆蓋能力, 為提高效能, 需要求解使得總有效探測面積最大的一組起始位置和航向解。在該問題中, 每個平臺有橫坐標(biāo)、縱坐標(biāo)及航向3個變量, 若集群規(guī)模較大, 會使得傳統(tǒng)的數(shù)學(xué)規(guī)劃等方法難以實現(xiàn)尋優(yōu), 為解決該問題, 通常采用粒子群優(yōu)化(par- ticle swarm optimization, PSO) 算法。

2.1 規(guī)劃算法

PSO算法是由Kennedy等[9]提出的一種應(yīng)用廣泛的群智能優(yōu)化算法, 該算法通過模擬鳥類覓食過程中各個體追隨自身歷史最優(yōu)解及群體最優(yōu)解的過程實現(xiàn)優(yōu)化。

假設(shè)集群有個平臺, 每個平臺需要起始點橫、縱坐標(biāo)以及搜索航向才能確定搜索區(qū)域, 故第次迭代后, 第個粒子的位置矩陣

相應(yīng)定義粒子的運動速度矩陣

矩陣中的每個元素對應(yīng)著位置矩陣中各元素的更新速度, 速度矩陣在迭代過程中依據(jù)式(7)和式(8)進(jìn)行更新

由此不斷迭代, 位置矩陣中的解會不斷向最優(yōu)解搜索靠近, 經(jīng)過足夠次數(shù)的迭代, 即可得到足夠接近最優(yōu)解的近似最優(yōu)解。

2.2 算例分析

圖4展示了優(yōu)化前后的集群區(qū)域覆蓋效果, 紅色線條為各平臺航跡, 黃色區(qū)域為有效覆蓋區(qū)域, 藍(lán)色區(qū)域為未覆蓋區(qū)域。圖4(a)為粒子隨機(jī)初始化時, 各粒子中的最優(yōu)解, 此時的航跡分布較為分散, 有效覆蓋率為40.24%; 圖4(b)為經(jīng)過500次迭代優(yōu)化后獲得的優(yōu)化結(jié)果, 優(yōu)化后, 航向大多趨向于順流, 相互之間填補了空隙, 這有利于提高搜索路程, 航跡間的交疊與沖出目標(biāo)海區(qū)的情況減少, 雖然不是所有平臺的航向都嚴(yán)格地與流向相同, 但航跡的位置分布合理, 相互有效地填補了空隙, 有效覆蓋率提高到62.28%, 達(dá)到了較好的總體效能。

圖4 優(yōu)化前后覆蓋效果圖

圖5為優(yōu)化后的區(qū)域覆蓋率隨迭代次數(shù)的變化規(guī)律。隨著迭代的進(jìn)行, 各粒子不斷向最優(yōu)解靠近, 在一定次數(shù)的迭代后, 粒子已足夠接近最優(yōu)解, 故進(jìn)化曲線趨于平緩, 通過多次測試, 進(jìn)化曲線都會在500次迭代內(nèi)收斂, 故對該問題推薦進(jìn)行500次迭代優(yōu)化。基于該快速評估模型的500次粒子群優(yōu)化僅用時46.1758 s。

圖5 優(yōu)化后區(qū)域覆蓋率隨迭代次數(shù)的變化規(guī)律

3 集群平臺數(shù)量優(yōu)化

3.1 規(guī)劃算法

為追求任務(wù)中的最小資源投入, 需要通過合理安排搜索任務(wù)使得所需的平臺數(shù)量最少。上一節(jié)中的路徑優(yōu)化方法需要已知的平臺數(shù)目, 而在該問題中, 平臺數(shù)目及各平臺的搜索策略均為待優(yōu)化變量。

為解決最少平臺數(shù)目未知的問題, 這里采用序貫的思想: 先以一定數(shù)目的平臺進(jìn)行路徑規(guī)劃, 在此基礎(chǔ)上依次添加平臺至最優(yōu)位置, 直至達(dá)到覆蓋要求。

平臺數(shù)量優(yōu)化的步驟如下(參見圖6):

4) 在步驟3)的最優(yōu)方案基礎(chǔ)上, 新增一個平臺,利用PSO算法進(jìn)行單平臺路徑優(yōu)化, 使得該新增平臺能夠最大化覆蓋步驟3)方案中的探測盲區(qū), 并記錄新方案;

圖6 平臺數(shù)量優(yōu)化流程

5) 判斷新方案是否滿足任務(wù)覆蓋需求, 是則輸出覆蓋方案, 反之則回到步驟3)。

3.2 算例分析

海區(qū)條件、水下滑翔機(jī)平臺參數(shù)同2.2節(jié)中算例, 現(xiàn)要求有效覆蓋率達(dá)到85%, 對平臺數(shù)量及平臺搜索路徑優(yōu)化。

圖7為對42個平臺進(jìn)行預(yù)優(yōu)化的進(jìn)化曲線, 經(jīng)過500次迭代, 進(jìn)化曲線已收斂, 且集群的覆蓋能力達(dá)到59.57%, 為進(jìn)一步求解覆蓋率達(dá)到85%所需要的最少平臺數(shù)目, 依次在之前已形成的搜索策略基礎(chǔ)上添加1個平臺, 并對新增平臺的起始位置、航向進(jìn)行優(yōu)化。序貫過程中, 隨平臺數(shù)目遞增, 區(qū)域覆蓋率的變化規(guī)律如圖8所示逐步提高, 當(dāng)平臺數(shù)增至67個時, 區(qū)域覆蓋率首次超過85%達(dá)到85.30%。

由此得到結(jié)論: 最少利用65個平臺可以達(dá)到預(yù)定區(qū)域覆蓋需求, 最優(yōu)覆蓋方案如圖9所示, 優(yōu)化過程總用時53.22 s。

圖7 未知平臺數(shù)下預(yù)優(yōu)化進(jìn)化曲線

圖8 未知平臺數(shù)下覆蓋率隨平臺數(shù)變化規(guī)律

圖9 未知平臺數(shù)下滿足覆蓋需求的覆蓋方案

在流速更高的環(huán)境下, 水下滑翔機(jī)能夠獲得更高的順流航速, 單平臺的效能更高, 故所需平臺更少。圖10可見, 經(jīng)過500次迭代, 算法將初始35個平臺的覆蓋能力優(yōu)化到了60.28%, 而后依次添加平臺并利用PSO算法規(guī)劃至最優(yōu)航路。序貫過程中, 隨平臺數(shù)增多, 區(qū)域覆蓋率的變化過程如圖11所示, 當(dāng)平臺數(shù)目增至54個時, 區(qū)域覆蓋率首次超過85%達(dá)到85.04%。

圖10 更高海流流速下預(yù)優(yōu)化進(jìn)化曲線

圖11 更高海流流速下覆蓋率隨平臺數(shù)變化規(guī)律

最優(yōu)航路方案如圖12所示, 相比于0.2 m/s的海流, 0.4 m/s的海流使得單平臺擁有更大的覆蓋區(qū)域, 多數(shù)平臺趨向于海流方向有序排列, 部分平臺則填補平臺間空隙, 使得集群的總覆蓋面積最優(yōu)。

圖12 更高海流流速下滿足覆蓋需求的覆蓋方案

4 結(jié)束語

合理地安排水下滑翔機(jī)集群中各平臺的搜索路徑, 能夠有效提高集群探測的搜索效能, 并可在滿足任務(wù)需求的前提下降低平臺需求量, 節(jié)約任務(wù)成本。文中通過劃定有效探測區(qū)域, 反演有效探測區(qū)域內(nèi)柵格序數(shù)的方法, 實現(xiàn)了對大區(qū)域、大集群探測覆蓋問題的快速優(yōu)化。在該優(yōu)化模型的基礎(chǔ)上, 利用序貫思想, 采用依次添加平臺至最優(yōu)位置的方法, 實現(xiàn)了最少平臺數(shù)目的區(qū)域覆蓋優(yōu)化。通過算例分析, 優(yōu)化算法能夠有效地提高區(qū)域覆蓋率, 且優(yōu)化速度快, 對于約10×104km2的海區(qū)、45個平臺的大規(guī)模系統(tǒng), 能夠在1 min內(nèi)給出精度為500 m的優(yōu)化方案; 在給出預(yù)期的區(qū)域覆蓋率后, 最少平臺數(shù)量優(yōu)化算法成功地給出了低資源消耗的區(qū)域覆蓋方案。

反演柵格序數(shù)的區(qū)域覆蓋能力評估方法具有快速、高精度的特點, 但該方法為降低運算量, 簡單地規(guī)定平臺只能沿直線運動, 一定程度上限制了集群的靈活性, 使得該方法僅適用于對平臺轉(zhuǎn)向需求較弱的開闊海區(qū)。有效探測區(qū)域的矩形近似, 使得探測效果評估僅能使用布爾感知模型, 無法體現(xiàn)集群多源信息融合對目標(biāo)探測的增益。

[1] Ridao P, Carreras M, Ribas D, et al. Intervention AUVs: The Next Challenge[J]. Annual Reviews in Control, 2015, 40: 227-241.

[2] 周菁, 慕德俊. 多機(jī)器人系統(tǒng)任務(wù)分配研究[J]. 西北大學(xué)學(xué)報(自然科學(xué)版), 2014, 44(3): 403-410.

Zhou Jing, Mu De-jun. Study of Multi-robot System on Task Allocation[J]. Journal of Northwest University(Na- tural Science Edition), 2014, 44(3): 403-410.

[3] Sotzing C C. The Design and Implementation of A Multi-Agent Architecture to Increase Coordination Efficiency in Multi-AUV Operations[D]. Edinburgh, Scotland: Her- iot-Watt University, 2009.

[4] 金建海, 陳偉華, 張波, 等. UUV集群技術(shù)概述[C]// 2018年水下無人系統(tǒng)技術(shù)高峰論壇論文集. 西安: 水下無人系統(tǒng)技術(shù)高峰論壇, 2018: 32-36.

[5] 生雪莉, 李鵬飛, 郭龍翔, 等. 基于單平臺探測概率模型的水下無人集群部署規(guī)劃算法[J]. 水下無人系統(tǒng)學(xué)報, 2019, 27(2): 194-199.

Sheng Xue-li, Li Peng-fei, Guo Long-xiang, et al. Deployment Planning Algorithm of Unmanned Underwater Swarm Based on Probability Model of Single-platform Detection[J]. Journal of Unmanned Undersea Systems, 2019, 27(2): 194-199.

[6] Dong W, Sheng X, Jiang X, et al. Energy Constrained Multi-Platform Network Underwater Detection Performance[C]//International Conference on Underwater Networkd & Systems. Rome, Italy: ACM, 2014: 43.

[7] 馬焱, 肖玉杰, 陳軼, 等. 基于改進(jìn)煙花-蟻群算法的海流環(huán)境下水下無人潛航器的避障路徑規(guī)劃[J]. 導(dǎo)航與控制, 2019, 18(1): 51-59.

Ma Yan, Xiao Yu-jie, Chen Yi, et al. Obstacle Avoidance Path Planning of Unmanned Underwater Vehicle in Ocean Current Environment Based on Improved Fireworks-ant Colony Algorithm[J]. Navigation and Control, 2019, 18(1): 51-59.

[8] 嚴(yán)浙平, 鄧超, 遲冬南, 等. 雙種群粒子群算法及其在UUV路徑規(guī)劃中的應(yīng)用[J]. 計算機(jī)工程與應(yīng)用, 2013, 49(15): 1-5.

Yan Zhe-ping, Deng Chao, Chi Dong-nan, et al. Two- Subpopulation Particle Swarm Optimization and its Application in UUV Path Planning[J]. Computer Engineering and Applications, 2013, 49(15): 1-5.

[9] Kennedy J, Eberhart R. Particle Swarm Optimization[C]// Proceedings of ICNN’95-International Conference on Neural Networks. Australia Council, Perth: IEEE, 1995.

[10] Shi Y, Eberhart R C. Empirical Study of Particle Swarm Optimization[C]//Evolutionary Computation, 1999. Proc- eedings of the 1999 Congress on Evolutionary Computation. Washington, DC, USA: IEEE, 1999.

Path Planning of a Large-scale Underwater Glider Swarm Area Coverage Detection

ZOU Jia-yun1,2, QU Hong-yue2*, CHEN Zhi-peng3

(1. Navy Submarine Academy, Qingdao 266199, China; 2. Pilot National Laboratory for Marine Science and Technology(Qingdao), Qingdao 266237, China; 3. Military Representative Office of Shenyang Bureau in Huludao, Huludao 125003, China)

When search tasks in an underwater glider swarm are conducted, the detection efficiency of the swarm can be improved effectively by setting the search path of each platform reasonably, thereby maximizing the coverage of the detection area with the least platform.To solve the problem of large calculations in large-scale swarm mission planning, this study constructs a high-precision Boolean model based on the grid method to evaluate the coverage ability of an underwater glider swarm by delimiting the effective coverage area geometrically and inverting the grid number. With this as a support, a swarm intelligence algorithm can then be used to realize fast path planning of a large-scale swarm in a wide sea area. Accordingly, this research proposes a method for solving the minimum number of swarm platforms with only few calculations by using sequential thought. The feasibility of this method is verified through a simulation experiment. The proposed method can support mission planning for large-scale underwater glider swarms.

underwater glider swarm; detection; mission planning; area coverage

TJ630.33; TB566

A

2096-3920(2021)01-0023-07

10.11993/j.issn.2096-3920.2021.01.04

鄒佳運, 曲泓玥, 陳志鵬. 大規(guī)模水下滑翔機(jī)集群區(qū)域覆蓋探測路徑規(guī)劃[J]. 水下無人系統(tǒng)學(xué)報, 2021, 29(1): 23-29.

2020-04-16;

2020-06-02.

國家重點研發(fā)計劃項目(2019YFC0311700); 青島海洋科學(xué)與技術(shù)試點國家實驗室“問海”計劃項目(2017WHZZB0601).

曲泓玥(1995-), 女, 碩士, 主要研究方向為聲吶系統(tǒng)仿真.

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