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

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

Abstract

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

CLC Number:

TP319.56

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.

Figures/Tables 11

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Table 1

Fig.6

Table 2

Fig.7

Fig.8

Fig.9

References 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]	Haobo FENG, Qiao HU, Zhenyi ZHAO. AUV swarm path planning based on elite family genetic algorithm [J]. Systems Engineering and Electronics, 2022, 44(7): 2251-2262.
[2]	Dou CHEN, Xiuyun MENG. UAV offline path planning based on self-adaptive coyote optimization algorithm [J]. Systems Engineering and Electronics, 2022, 44(2): 603-611.
[3]	Qingqing YANG, Yingying GAO, Yu GUO, Boyuan XIA, Kewei YANG. Target search path planning for naval battle field based on deep reinforcement learning [J]. Systems Engineering and Electronics, 2022, 44(11): 3486-3495.
[4]	Tong HAN, Andi TANG, Huan ZHOU, Dengwu XU, Lei XIE. Multiple UAV cooperative path planning based on LASSA method [J]. Systems Engineering and Electronics, 2022, 44(1): 233-241.
[5]	Weiqiang MA, Yongqi GAO, Miao ZHAO. Global-best difference-mutation brain storm optimization algorithm [J]. Systems Engineering and Electronics, 2022, 44(1): 270-278.
[6]	Lei LAI, Kun ZOU, Dewei WU, Baozhong LI. Multi-UAV cooperative path planning based on improved MOFA evolution of interactive strategy [J]. Systems Engineering and Electronics, 2021, 43(8): 2282-2289.
[7]	Zhiqiang JIAO, Jieyong ZHANG, Peiyang YAO, Xun WANG, Yichao HE. Distributed evolution method of C4ISR service deployment based on hierarchical structure [J]. Systems Engineering and Electronics, 2021, 43(6): 1572-1585.
[8]	Wenming WANG, Jialu DU. Agent path planning based on regular hexagon grid JPS algorithm [J]. Systems Engineering and Electronics, 2021, 43(12): 3635-3642.
[9]	Yanan LI, Haibin HUANG, Liangming CHEN, Yufei ZHUANG, Xiaoli WANG. Energy-optimal three-dimensional path planning for AUV under changing ocean current environment [J]. Systems Engineering and Electronics, 2021, 43(12): 3667-3674.
[10]	Wengang LI, Liujiang WANG, Dexiang FANG, Yuwei LI, Jun Huang. Path planning algorithm combining A^* with DWA [J]. Systems Engineering and Electronics, 2021, 43(12): 3694-3702.
[11]	Yao HAN, Shaohua LI. UAV path planning based on improved artificial potential field [J]. Systems Engineering and Electronics, 2021, 43(11): 3305-3311.
[12]	Daidai CHEN, Wanyou LI. Local path planning algorithm for USV with towed cable [J]. Systems Engineering and Electronics, 2020, 42(9): 1988-1994.
[13]	Quanxian ZHANG, Bin ZENG, Houpu LI. Underway replenishment path planning method for distributed naval warfare under the influence of sea conditions [J]. Systems Engineering and Electronics, 2020, 42(10): 2312-2319.
[14]	Sheng GAO, Jianliang AI, Zhihao WANG. Mixed population RRT algorithm for UAV path planning [J]. Systems Engineering and Electronics, 2020, 42(1): 101-107.
[15]	YANG Xiuxia, CAO Weiyi, ZHANG Yi. Bi-arc path planning with time and angle constraints [J]. Systems Engineering and Electronics, 2019, 41(8): 1835-1843.

USV cluster coverage search method with communication distance constraint

RichHTML

PDF (PC)

Knowledge

Abstract

Cite this article

share this article

Figures/Tables 11

References 25

Related Articles 15

Recommended Articles

Metrics

Comments