通信距离约束下的无人船集群覆盖搜索方法

doi:10.12305/j.issn.1001-506X.2022.12.27

摘要/Abstract

摘要：

针对通信距离受限时水面无人船(unmanned surface vessel, USV)集群对未知水域的覆盖搜索问题, 提出一种竞拍协同边界探索算法。首先根据边界探索的思想提取地图探测边界, 然后以基于层次聚类思想进行改进的K-means++聚类算法划分任务区间, 消除不安全或低收益的目标搜索点, 再以分布式竞拍算法为USV集群动态分配搜索任务, 使集群搜索效率最大化, 各艇经过多轮分配、执行搜索任务直至覆盖全水域。仿真实验表明，在相同集群规模下, 相较于无协作的几种边界探索算法, 该算法任务用时和集群航行总路程更少; 在相同任务地图下, 覆盖搜索效率随USV集群规模增大而提高。

关键词: 集群协同, 边界探索, 任务分配, 路径规划

Abstract:

Aiming at the coverage search problem of unmanned surface vessel (USV) cluster in unknown environment, an auction collaborate frontier algorithm is proposed. Firstly, the map detection boundary is extracted according to the idea of boundary exploration. Secondly, the task interval is divided by the improved K-means++ clustering algorithm based on the idea of hierarchical clustering to eliminate unsafe or low-yielding target search points. Finally, the search task is dynamically assigned to the USV cluster by the distributed bidding algorithm to maximize the cluster search efficiency, and each boat goes through multiple rounds of assignment and executes the search task until the whole water is covered. Simulation results show that the algorithm takes less time for the task and the total distance travelled by the cluster compared to several boundary exploration algorithms without collaboration at the same cluster size, and the coverage search efficiency improves with increasing USV cluster size at the same task map.

Key words: cluster collaboration, frontier exploration, task assignment, path planning

中图分类号:

TP319.56

尹洋, 杨全顺, 王征, 刘洋. 通信距离约束下的无人船集群覆盖搜索方法[J]. 系统工程与电子技术, 2022, 44(12): 3821-3828.

Yang YIN, Quanshun YANG, Zheng WANG, Yang LIU. USV cluster coverage search method with communication distance constraint[J]. Systems Engineering and Electronics, 2022, 44(12): 3821-3828.

图/表 11

图1

图2

图3

图4

图5

表1

图6

表2

图7

图8

图9

参考文献 25

1	张卫东, 刘笑成, 韩鹏. 水上无人系统研究进展及其面临的挑战[J]. 自动化学报, 2020, 46 (5): 847- 857.
	ZHANG W D , LIU X C , HAN P . Progress and challenges of overwater unmanned systems[J]. Acta Automatica Sinica, 2020, 46 (5): 847- 857.
2	朱健楠, 虞梦苓, 杨益新. 无人水面艇感知技术发展综述[J]. 哈尔滨工程大学学报, 2020, 41 (10): 1486- 1492.
	ZHU J N , YU M L , YANG Y X . Overview of unmanned surface vehicles sensing technology development[J]. Journal of Harbin Engineering University, 2020, 41 (10): 1486- 1492.
3	苗润龙, 庞硕, 姜大鹏, 等. 海洋自主航行器多海湾区域完全遍历路径规划[J]. 测绘学报, 2019, 48 (2): 256- 264.
	MIAO R L , PANG S , JIANG D P , et al. Complete coverage path planning for autonomous marine vehicle used in multibay areas[J]. Acta Geodaetica et Cartographica Sinica, 2019, 48 (2): 256- 264.
4	王琦斐, 杨军. 基于内螺旋覆盖算法的多AUV协作反水雷路径规划研究[J]. 计算机测量与控制, 2012, 20 (1): 144- 146.144-146, 160
	WANG Q F , YANG J . Path planning of multiple AUVs for cooperative mine countermeasure using internal spiral coverage algorithm[J]. Computer Measurement and Control, 2012, 20 (1): 144- 146.144-146, 160
5	吕霞付, 程啟忠, 李森浩, 等. 基于改进A^*算法的无人船完全遍历路径规划[J]. 水下无人系统学报, 2019, 27 (6): 695- 703.
	LYU X F , CHENG Q Z , LI S H , et al. Unmanned surface vehicle full traversal path planning based on improved A^* algorithm[J]. Journal of Unmanned Undersea System, 2019, 27 (6): 695- 703.
6	YAMAUCHI B. A frontier-based approach for autonomous exploration[C]//Proc. of the IEEE International Symposium on Computational Intelligence in Robotics and Automation, 1997: 146-151.
7	GAUTAM A, MURTHY J K, KUMAR G, et al. Cluster, allocate, cover: an efficient approach for multi-robot coverage[C]//Proc. of the IEEE International Conference on Systems, 2015: 197-203.
8	NIROUI F , ZHANG K , KASHINO Z , et al. Deep reinforcement learning robot for search and rescue applications: exploration in unknown cluttered environments[J]. IEEE Robotics and Automation Letters, 2019, 4 (2): 610- 617. doi: 10.1109/LRA.2019.2891991
9	CAO X , SUN C Y , YAN M Z . Target search control of AUV in underwater environment with deep reinforcement learning[J]. IEEE Access, 2019, 7, 96549- 96559. doi: 10.1109/ACCESS.2019.2929120
10	FANG B F , DING J F , WANG Z J . Autonomous robotic exploration based on frontier point optimization and multistep path planning[J]. IEEE Access, 2019, 7, 46104- 46113. doi: 10.1109/ACCESS.2019.2909307
11	况阳, 顾颖闽. 基于几何力学的水面无人艇艇群控制技术[J]. 舰船科学技术, 2019, 41 (23): 123- 126.
	KUANG Y , GU Y M . Control technology of USV group based on geometry mechanics[J]. Ship Science and Technology, 2019, 41 (23): 123- 126.
12	顾颖闽. 水面无人艇艇群技术发展概述[J]. 舰船科学技术, 2019, 41 (23): 35- 38.
	GU Y M . Overview of technology development of the USV group[J]. Ship Science and Technology, 2019, 41 (23): 35- 38.
13	向庭立, 王红军, 史英春. 区域覆盖的多机协同探测任务分配策略[J]. 空军工程大学学报(自然科学版), 2019, 20 (6): 33- 38.33-38, 71
	XIANG T L , WANG H J , SHI Y C . A multi-UAV cooperative detection task allocation strategy based on area coverage[J]. Journal of Air Force Engineering University (Natural Science Edition), 2019, 20 (6): 33- 38.33-38, 71
14	高春庆, 寇英信, 李战武, 等. 小型无人机协同覆盖侦察路径规划[J]. 系统工程与电子技术, 2019, 41 (6): 1294- 1299.
	GAO C Q , KOU Y X , LI Z W , et al. Cooperative coverage path planning for small UAVs[J]. Systems Engineering and Electronics, 2019, 41 (6): 1294- 1299.
15	张耀中, 谢松岩, 张蕾, 等. 异构型多UAV协同侦察最优化任务决策研究[J]. 西北工业大学学报, 2017, 35 (3): 385- 392.
	ZHANG Y Z , XIE S Y , ZHANG L , et al. Research on optimization task decision of heterogeneous UAVs cooperative reconnaissance[J]. Journal of Northwestern Polytechnical University, 2017, 35 (3): 385- 392.
16	WANG Y B , BAI P , LIANG X L , et al. Reconnaissance mission conducted by UAV swarms based on distributed PSO path planning algorithms[J]. IEEE Access, 2019, 7, 105086- 105099.
17	张民强, 宋建梅, 薛瑞彬. 通信距离受限下多无人机分布式协同搜索[J]. 系统工程理论与实践, 2015, 35 (11): 2980- 2986.
	ZHANG M Q , SONG J M , XUE R B . Multiple UAVs coope-rative search under limited communication range[J]. Systems Engineering Theory and Practice, 2015, 35 (11): 2980- 2986.
18	王宁, 李哲, 梁晓龙, 等. 通信距离受限条件下的无人机集群协同区域搜索[J]. 系统工程与电子技术, 2022, 44 (5): 1615- 1625.
	WANG N , LI Z , LIANG X L . Cooperative region search of UAV swarm with limited communication distance[J]. Systems Engineering and Electronics, 2022, 44 (5): 1615- 1625.
19	符小卫, 李建, 高晓光. 带通信约束的多无人机协同搜索中的目标分配[J]. 航空学报, 2014, 35 (5): 1347- 1356.
	FU X W , LI J , GAO X G . Target allocation in multi-UAV cooperative search with communication constraints[J]. Acta Aeronautica et Astronautica Sinica, 2014, 35 (5): 1347- 1356.
20	SINAGA K P , YANG M . Unsupervised K-means clustering algorithm[J]. IEEE Access, 2020, 8, 80716- 80727.
21	庄宇飞, 李亚南, 黄海滨, 等. 基于集群运动控制的无人艇覆盖部署方法[J]. 中国造船, 2020, 61 (S1): 52- 59.
	ZHUANG Y F , LI Y N , HUANG H B , et al. Unmanned surface vessel coverage deployment method based on cluster motion control[J]. Shipbuilding of China, 2020, 61 (S1): 52- 59.
22	陈璞, 严飞, 刘钊, 等. 通信约束下异构多无人机任务分配方法[J]. 航空学报, 2021, 42 (8): 313- 326.
	CHEN P , YAN F , LIU Z , et al. Communication constrained task allocation of heterogeneous UAVs[J]. Acta Aeronautica et Astronautica Sinica, 2021, 42 (8): 313- 326.
23	林君灿, 贾高伟, 侯中喜. 异构UAV编队反雷达作战中任务分配方法[J]. 系统工程与电子技术, 2018, 40 (9): 1986- 1992.
	LIN J C , JIA G W , HOU Z X . Research on task assignment of heterogeneous UAV formation in the anti-radar combat[J]. Systems Engineering and Electronics, 2018, 40 (9): 1986- 1992.
24	贾高伟, 王建峰. 无人机集群任务规划方法研究综述[J]. 系统工程与电子技术, 2021, 43 (1): 99- 111.
	JIA G W , WANG J F . Research review of UAV swarm mission planning method[J]. Systems Engineering and Electro-nics, 2021, 43 (1): 99- 111.
25	LIM J K , KIM K H , YOSHIMOTO K , et al. A dispatching method for automated guided vehicles by using a bidding concept[J]. OR Spectrum, 2003, 25 (1): 25- 44.

参数名称	取值
探测距离D/units	5
权重因子ω	0.3
避障半径R/units	1
通信距离H/units	10
集群大小N_u/艘	7
行驶速度v/(units·s^-1)	1

USV编号	分布式AC-Frontier			主从式AC-Frontier			Near-Frontier			Random-Frontier
USV编号	R	L	G	R	L	G	R	L	G	R	L	G
USV1	532	155.8	3.41	683	187.5	3.64	599	251.3	2.38	272	345.4	0.787
USV2	852	148.6	5.73	747	186.1	4.01	983	264.1	3.72	115	346.8	0.332
USV3	568	144.3	3.94	505	108.5	4.65	600	237.3	2.53	64	345.5	0.185
USV4	653	140.6	4.64	717	189.5	3.78	1 299	254.4	5.11	1 389	1 168	1.189
USV5	784	137.8	5.68	735	179.9	4.08	552	246.3	2.24	847	1 014	0.835
USV6	684	148.8	4.59	847	180.7	4.68	612	244.1	2.51	1 050	1 153	0.911
USV7	826	150.5	5.48	666	184.2	3.61	295	210.5	1.40	1 177	1 111	1.059
CV	0.179	0.042	0.252	0.148	0.167	0.109	0.467	0.70	0.425	0.775	0.526	0.487

[1]	冯豪博, 胡桥, 赵振轶. 基于精英族系遗传算法的AUV集群路径规划[J]. 系统工程与电子技术, 2022, 44(7): 2251-2262.
[2]	岳程斐, 薛正华, 姚蔚然, 曹喜滨. 基于机群关系特征的多机协同作战任务分配[J]. 系统工程与电子技术, 2022, 44(6): 1897-1906.
[3]	杨清清, 高盈盈, 郭玙, 夏博远, 杨克巍. 基于深度强化学习的海战场目标搜寻路径规划[J]. 系统工程与电子技术, 2022, 44(11): 3486-3495.
[4]	马威强, 高永琪, 赵苗. 基于全局最优和差分变异的头脑风暴优化算法[J]. 系统工程与电子技术, 2022, 44(1): 270-278.
[5]	刘钢, 汤俊, 刘陈, 李武. 无人飞行器集群协同行为建模技术综述[J]. 系统工程与电子技术, 2021, 43(8): 2221-2231.
[6]	来磊, 邹鲲, 吴德伟, 李保中. 交互策略改进MOFA进化的多UAV协同航迹规划[J]. 系统工程与电子技术, 2021, 43(8): 2282-2289.
[7]	焦志强, 张杰勇, 姚佩阳, 王勋, 何宜超. 基于分层结构的C4ISR服务部署分布式演化方法[J]. 系统工程与电子技术, 2021, 43(6): 1572-1585.
[8]	周晶, 赵晓哲, 许震, 林众, 张晓盼. 基于D-NSGA-Ⅲ算法的无人机群高维多目标任务分配方法[J]. 系统工程与电子技术, 2021, 43(5): 1240-1247.
[9]	李翰, 张洪海, 张连东, 刘皞. 城市区域多物流无人机协同任务分配[J]. 系统工程与电子技术, 2021, 43(12): 3594-3602.
[10]	王文明, 杜佳璐. 基于正六边形栅格JPS算法的智能体路径规划[J]. 系统工程与电子技术, 2021, 43(12): 3635-3642.
[11]	李亚南, 黄海滨, 陈亮名, 庄宇飞, 王晓丽. 变化海流环境下AUV能量最优三维路径规划[J]. 系统工程与电子技术, 2021, 43(12): 3667-3674.
[12]	李文刚, 汪流江, 方德翔, 李玉玮, 黄郡. 联合A^*与动态窗口法的路径规划算法[J]. 系统工程与电子技术, 2021, 43(12): 3694-3702.
[13]	陈岱岱, 李玩幽. 带拖线阵的水面无人艇局部路径规划算法[J]. 系统工程与电子技术, 2020, 42(9): 1988-1994.
[14]	张泉先, 曾斌, 李厚朴. 海况影响下的分布式海战补给路径规划方法[J]. 系统工程与电子技术, 2020, 42(10): 2312-2319.
[15]	杨秀霞, 曹唯一, 张毅. 时间和角度约束下的双圆弧路径规划[J]. 系统工程与电子技术, 2019, 41(8): 1835-1843.