未知城市环境下的多机协同目标搜索方法研究

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

摘要/Abstract

摘要：

在城市环境中, 建筑物或不可达区域等因素的影响易造成多无人机(unmanned aerial vehicle, UAV)协同路径规划策略失效, 从而导致目标搜索任务的失败。针对此问题, 提出未知城市环境下的多UAV协同搜索(multi-unmanned aerial vehicle cooperative search, MUCS)方法。首先, 对城市环境进行建模, 其中涵盖密集建筑物群的设计和运动状态多样的目标, 以增强目标搜索任务的挑战性; 然后, 在此基础上, 综合考虑UAV编队飞行约束和信息交互能力, 构建基于信息共享代价和区域覆盖收益的协同优化模型; 最后, 根据多UAV协同编队特点, 利用群智能方法进行优化求解, 确保每架UAV均能得到最优路径可行解, 从而提高多UAV协同目标搜索效率。与现有搜索方法相比, MUCS方法的平均目标发现成功率提升了20%, 区域覆盖率提升了10%。实验结果表明, MUCS方法具有较强的目标搜索能力和区域覆盖能力。

关键词: 未知城市环境, 多机协同, 目标搜索, 信息共享, 区域覆盖

Abstract:

In the urban environment, the influence of factors such as buildings or inaccessible regions is easy to cause the failure of the multi-unmanned aerial vehicle (UAV) cooperative path planning strategy, which results in the failure of the target search task. To solve these issues above, a multi-UAV cooperative search (MUCS) method in the uncertain urban environment is proposed. Firstly, the urban environment is modeled, which includes the design of dense building clusters and targets with various motion states, so as to enhance the challenge of the target search task. Then on this basis, a cooperative optimization model based on information sharing cost and regional coverage benefit is constructed by comprehensively considering the flight constraint and the information interaction capability of UAV formation. Finally, according to the characteristics of the multi-UAV cooperative formation, the swarm intelligence method is used to solve the optimization problem, which ensures that each UAV can obtain the feasible solution of the optimal path and improve the efficiency of the multi-UAV cooperative target search. Compared with the existing search methods, the average target discovery success rate of MUCS method is increased by 20%, and the regional coverage rate is increased by 10%. The experimental results illustrate that MUCS has the strong capability of the target search and regional coverage.

Key words: unknown urban environment, multi-unmanned aerial vehicle (UAV) cooperation, target search, information sharing, regional coverage

中图分类号:

刘大千, 包卫东, 费博雯, 朱晓敏. 未知城市环境下的多机协同目标搜索方法研究[J]. 系统工程与电子技术, 2023, 45(12): 3896-3907.

Daqian LIU, Weidong BAO, Bowen FEI, Xiaomin ZHU. Research on multi-UAV cooperative target search method under unknown urban environment[J]. Systems Engineering and Electronics, 2023, 45(12): 3896-3907.

图/表 25

图1

图2

图3

图4

图5

图6

表1

表2

表3

图7

图8

图9

图10

图11

图12

图13

图14

图15

图16

表4

表5

图17

表6

图18

表7

参考文献 31

1	LIU D Q , BAO W D , ZHU X M , et al. Cooperative path optimization for multiple UAVs surveillance in uncertain environment[J]. IEEE Internet of Things Journal, 2022, 9 (13): 10676- 10692. doi: 10.1109/JIOT.2021.3125784
2	GUPTA A , FERNANDO X . Simultaneous localization and mapping (SLAM) and data fusion in unmanned aerial vehicles: recent advances and challenges[J]. Drones, 2022, 6 (4): 85. doi: 10.3390/drones6040085
3	DUAN H B , ZHAO J , DENG Y M , et al. Dynamic discrete pigeon-inspired optimization for multi-UAV cooperative search-attack mission planning[J]. IEEE Trans.on Aerospace and Electronic Systems, 2021, 57 (1): 706- 720. doi: 10.1109/TAES.2020.3029624
4	HAN R , WEN Y Q , BAI L , et al. Age of information aware UAV deployment for intelligent transportation systems[J]. IEEE Trans.on Intelligent Transportation Systems, 2022, 23 (3): 2705- 2715. doi: 10.1109/TITS.2021.3117974
5	NIELSEN L , SUNG I , NIELSEN P . Convex decomposition for a coverage path planning for autonomous vehicles: interior extension of edges[J]. Sensors, 2019, 19 (19): 4165. doi: 10.3390/s19194165
6	谢朋志, 魏晨. 单侧区域分割的多无人机扫描线搜索方法研究[J]. 航空兵器, 2020, 27 (3): 67- 72.
	XIE P Z , WEI C . Research on scanning line search method for multi-UAV based on unilateral region segmentation[J]. Aero Weaponry, 2020, 27 (3): 67- 72.
7	戴健, 许菲, 陈琪锋. 多无人机协同搜索区域划分与路径规划研究[J]. 航空学报, 2020, 41 (S1): 723770.
	DAI J , XU F , CHEN Q F . Study on multi-UAV cooperative search on region division and path planning[J]. Acta Aeronautica et Astronautica Sinica, 2020, 41 (S1): 723770.
8	WU Y , WU S B , HU X T . Multi-constrained cooperative path planning of multiple drones for persistent surveillance in urban environments[J]. Complex & Intelligent Systems, 2021, 7, 1633- 1647.
9	WU Y , WU S B , HU X T . Cooperative path planning of UAVs & UGVs for a persistent surveillance task in urban environments[J]. IEEE Internet of Things Journal, 2021, 8 (6): 4906- 4919. doi: 10.1109/JIOT.2020.3030240
10	YU H , MEIER K , ARGYLE M , et al. Cooperative path planning for target tracking in urban environments using unmanned air and ground vehicles[J]. IEEE Trans.on Mechatronics, 2015, 20 (2): 541- 552. doi: 10.1109/TMECH.2014.2301459
11	刘重, 高晓光, 符小卫. 带信息素回访机制的多无人机分布式协同目标搜索[J]. 系统工程与电子技术, 2017, 39 (9): 1998- 2011.
	LIU C , GAO X G , FU X W . Multi-UAVs distributed cooperative target search algorithm with controllable revisit mechanism based on digital pheromone[J]. Systems Engineering and Electronics, 2017, 39 (9): 1998- 2011.
12	肖东, 江驹, 周俊, 等. 通信受限下多无人机协同运动目标搜索[J]. 哈尔滨工程大学学报, 2018, 39 (11): 1823- 1829.
	XIAO D , JIANG J , ZHOU J , et al. Multi-UAV cooperation search for moving targets under limited communication[J]. Journal of Harbin Engineering University, 2018, 39 (11): 1823- 1829.
13	TANG Q R , YU F C , ZHANG Y , et al. A stigmergetic method based on vector pheromone for target search with swarm robots[J]. Journal of Experimental & Theoretical Artificial Intelligence, 2019, 32 (3): 533- 555.
14	黄杰, 孙伟, 高渝. 双属性概率图优化的无人机集群协同目标搜索[J]. 系统工程与电子技术, 2020, 42 (1): 118- 127.
	HUANG J , SUN W , GAO Y . Cooperative searching for the multi-UAVs based on dual-attribute probability model optimization[J]. Systems Engineering and Electronics, 2020, 42 (1): 118- 127.
15	LIU Z , GAO X G , FU X W . A cooperative search and coverage algorithm with controllable revisit and connectivity maintenance for multiple unmanned aerial vehicles[J]. Sensors, 2018, 18 (5): 1472. doi: 10.3390/s18051472
16	YAO P , WANG H L , JI H X . Multi-UAVs tracking target in urban environment by model predictive control and improved grey wolf optimizer[J]. Aerospace Science and Technology, 2016, 55, 131- 143. doi: 10.1016/j.ast.2016.05.016
17	CARABAZA S , BESADA P E , LPREZ O J , et al. Ant colony optimization for multi-UAV minimum time search in uncertain domains[J]. Applied Soft Computing, 2018, 62, 789- 806. doi: 10.1016/j.asoc.2017.09.009
18	PURBOLINGGA Y, JAZIDIE A, EFFENDI R. Modified ant colony algorithm for swarm multi agent exploration on target searching in unknown environment[C]//Proc. of the International Conference of Artificial Intelligence and Information Technology, 2019. DOI: 10.1109/ICAⅡT.2019.8834573.
19	ZHEN Z Y , CHEN Y , WEN L D , et al. An intelligent coope-rative mission planning scheme of UAV swarm in uncertain dynamic environment[J]. Aerospace Science and Technology, 2020, 100, 105826. doi: 10.1016/j.ast.2020.105826
20	YANG J , WANG X , BAUER P . Extended PSO based collaborative searching for robotic swarms with practical constraints[J]. IEEE Access, 2019, 7, 76328- 76341.
21	SAADAOUI H , BOUANANI F , ILLI E . Information sharing based on local PSO for UAVs cooperative search of moved targets[J]. IEEE Access, 2021, 9, 134998- 135011.
22	MEN T, LIU D Q, ZHU X, et al. Cooperative target search for UAVs in urban environment[C]//Proc. of the IEEE International Conference on Smart City and Informatization, 2021. DOI: 10.1109/ISCI53438.2021.00011.
23	JUANG C F , YEH Y T . Multi-objective evolution of biped robot gaits using advanced continuous ant-colon optimized recurrent neural networks[J]. IEEE Trans.on Cybernetics, 2018, 48 (6): 1910- 1922.
24	LIU D Q, BAO W D, FEI B W, et al. Multi-UAV cooperative obstacle avoidance and surveillance in intelligent transportation[C]// Proc. of the IEEE 20th International on Trust, Security and Privacy in Computing and Communcations, 2021.
25	LI J , XIONG Y H , SHE J H , et al. A path planning method for sweep coverage with multiple UAVs[J]. IEEE Internet of Things Journal, 2020, 7 (9): 8967- 8978.
26	BO N, LI X M, DAI J J, et al. A hierarchical optimization strategy of trajectory planning for multi-UAVs[C]//Proc. of the 9th International Conference on Intelligent Human-Machine Systems and Cybernetics, 2017: 294-298.
27	XUE J K , SHEN B . A novel swarm intelligence optimization approach: sparrow search algorithm[J]. Systems Science & Control Engineering, 2020, 8 (1): 22- 34.
28	FEI B W , BAO W D , ZHU X M , et al. Autonomous cooperative search model for multi-UAV with limited communication network[J]. IEEE Internet of Things Journal, 2022, 9 (19): 19346- 19361.
29	KASHINO Z , NEJAT G , BENHABIB B . A hybrid strategy for target search using static and mobile sensors[J]. IEEE Trans.on Cybernetics, 2020, 50 (2): 856- 868.
30	YUE W , XI Y , GUAN X H . A new searching approach using improved multi-ant colony scheme for multi-UAVs in unknown environments[J]. IEEE Access, 2019, 7, 161094- 161102.
31	HU X X , LIU Y H , WANG G Q . Optimal search for moving targets with sensing capabilities using multiple UAVs[J]. Journal of Systems Engineering and Electronics, 2017, 28 (3): 526- 535.

无人机	初始位置	网格索引	初始方向
U₁	(50, 750)	(1, 15)	4
U₂	(50, 1 500)	(1, 30)	0
U₃	(50, 2 250)	(1, 45)	4
U₄	(750, 50)	(15, 1)	6
U₅	(1 500, 50)	(30, 1)	6
U₆	(2 250, 50)	(45, 1)	2
U₇	(3 050, 50)	(61, 1)	0
U₈	(3 050, 750)	(61, 15)	4
U₉	(3 050, 1 500)	(61, 30)	0
U₁₀	(750, 3 050)	(15, 61)	6
U₁₁	(1 500, 3 050)	(30, 61)	4
U₁₂	(2 250, 3 050)	(45, 61)	4

目标	初始位置	网格索引	初始方向
T₁	(850, 850)	(17, 17)	0
T₂	(850, 1 650)	(17, 33)	4
T₃	(850, 2 250)	(17, 45)	2
T₄	(1 650, 850)	(33, 17)	0
T₅	(1 650, 1 650)	(33, 33)	2
T₆	(1 650, 2 250)	(33, 45)	4
T₇	(2 250, 850)	(45, 17)	0
T₈	(2 250, 1 650)	(45, 33)	2
T₉	(2 250, 2 250)	(45, 45)	4

指标参数	SSA
最大迭代次数	100
候选样本数量	10
样本维度	24
发现者数量	6
追随者数量	6
警戒者数量	3
位移量	[－2, 2]

发现目标位置	搜索方法
发现目标位置	MUCS	SSA	DMP
T₁	(17, 11)	(17, 11)	(17, 19)
T₂	(45, 17)	(37, 42)	-
T₃	(25, 28)	-	(21, 57)
T₄	(33, 38)	(33, 42)	(33, 10)
T₅	(35, 33)	(28, 41)	(33, 33)
T₆	(33, 36)	(37, 56)	(46, 57)
T₇	(45, 14)	(45, 15)	(45, 19)
T₈	(42, 41)	(51, 29)	-
T₉	(47, 41)	(41, 49)	(29, 49)

搜索方法	搜索周期/s	发现目标数量/个	区域覆盖率/%
MUCS	100	2	23.28
	200	6	42.57
	400	9	73.58
SSA	100	2	20.34
	200	6	41.53
	400	8	72.49
DPM	100	4	19.20
	200	6	39.36
	400	7	61.09