多目标空地异构无人系统协同任务分配方法

doi:10.12382/bgxb.2022.0095

摘要/Abstract

摘要：

针对由地面无人车与多无人机组成的空地异构无人系统面向大范围、多目标的协同任务分配问题,以无人系统完成任务时间为优化目标,同时考虑无人机收放、续航能力以及任务时序等约束条件,建立空地异构无人系统的任务分配模型,提出一种多目标空地异构无人系统任务分配方法。结合密度值最大聚类和混合粒子群优化算法,对空地异构无人系统的任务分配问题进行求解,从而得到满足约束条件的全局任务分配结果;通过仿真实验对所提方法进行验证。实验结果表明,该方法能够有效地求解在不同作战环境中的空地异构无人系统的任务分配问题。

关键词: 无人系统, 任务分配, 密度值最大聚类, 混合粒子群优化算法

Abstract:

To address the collaborative task allocation problem of air-ground heterogeneous unmanned systems composed of ground unmanned vehicles (UGV) and unmanned aerial vehicles (UAVs) facing large ranges and multiple targets, the task allocation model of air-ground heterogeneous unmanned systems is established with the completion time of the unmanned systems as the optimization goal and the constraints of the UAV launch and recovery, endurance and task sequence taken in account. A task allocation method for multi-target air-ground heterogeneous unmanned systems is proposed, which combines density peak clustering and hybrid particle swarm optimization algorithm (hybrid-PSO) to solve the task allocation problem of air-ground heterogeneous unmanned systems, so as to obtain the global task allocation results that satisfy the constraints. The proposed method is verified by simulation experiments, and the results show that the method can effectively solve the task allocation problem of air-ground heterogeneous unmanned systems in different operational environments.

Key words: unmanned system, task allocation, density peak clustering algorithm, hybrid particle swarm optimization algorithm

范博洋, 赵高鹏, 薄煜明, 吴祥. 多目标空地异构无人系统协同任务分配方法[J]. 兵工学报, 2023, 44(6): 1564-1575.

FAN Boyang, ZHAO Gaopeng, BO Yuming, WU Xiang. Collaborative Task Allocation Method for Multi-Target Air-Ground Heterogeneous Unmanned System[J]. Acta Armamentarii, 2023, 44(6): 1564-1575.

图/表 20

图1 本文的研究思路

Fig.1 Main idea of this study

图2 多目标空地异构无人系统协同作战过程示意图

Fig.2 Schematic diagram of collaborative operation process of multi-target air-ground heterogeneous unmanned system

图3 多目标空地异构无人系统协同任务分配方法流程图

Fig.3 Process of the task allocation method for multi-target air-ground heterogeneous unmanned system

图4 粒子表示方法

Fig.4 A sample of the particle code

图5 交叉操作方法

Fig.5 A sample of the crossover operation

图6 变异操作方法

Fig.6 A sample of the mutation operation

图7 密度值最大聚类效果图

Fig.7 Result of density peak clustering

表1 12000m×12000m范围聚类划分结果对比

Table 1 Comparison of clustering results in the range of 12000m×12000m

聚类算法	发现簇数量	DBI值
密度值最大聚类	16	0.9281
DBSCAN算法	16	1.0168
k-means算法	16(手动设定)	1.5859

图8 6000m×6000m范围内目标分布图

Fig.8 Target distribution map in the range of 6000m×6000m

表2 6000m×6000m范围协同任务分配方法参数

Table 2 Parameters of thecollaborative task allocation method in the range of 6000m×6000m

算法	参数	数值	参数	UAV任务分配	UGV任务分配
	邻域半径/m	1000	种群数量	800	250
密度值最大聚类	密度阈值	5	混合粒子群优化	迭代次数	2400	800
	簇距离阈值/m	1500		交叉概率	0.7	0.7
				变异概率	0.7	0.7

表3 6000m×6000m范围协同任务分配结果

Table 3 Collaborative task allocation in the range of 6000m×6000m

无人系统	释放点坐标/m	任务序列	任务耗时/s	降落点	UGV抵达降落点耗时/s
UAV1		[7,38,10,4, 44,42, 23,36,12,33,49,29]	1718.11
UAV2		[11,15,8,5,14,20,28,48,46,22]	1340.85
UAV3	(365,106)	[47,9,21,34,1,39,31,16,32,3,50,27,40,6]	1562.53	目标点[40]	1335.49
UAV4		[19,45,18,17,30,26,24,43,37,13,41,35,2,25]	1643.87
UGV		[7,48,22,40,5,45,11,8,2,35,41,13,30,16,44,23,49]	4323.73

图9 6000m×6000m范围内协同任务分配示意图

Fig.9 Schematic diagram of the collaborative taskallocation in the range of 6000m×6000m

图10 各UAV飞行时间曲线

Fig.10 Flight time curves of UAVs

图11 12000m×12000m范围内目标分布图

Fig.11 Target distribution map in the range of 12000m×12000m

表4 12000m×12000m范围不划分子任务区域的协同任务分配方法参数

Table 4 Parameters of the task allocation method without clustering in the range of 12000m×12000m

参数	UAV任务分配	UGV任务分配
种群数量	800	250
迭代次数	2400	800
交叉概率	0.7	0.7
变异概率	0.7	0.7

表5 12000m×12000m范围不聚类划分子任务区域的协同任务分配结果

Table 5 Task allocation result without clustering in the range of 12000m×12000m

无人系统	规划结果
无人系统	释放点坐标/m	任务序列	降落点
UAV1		[14,37,38,30,50,49,20,26,6,36,17,33,45]	目标点[5]
UAV2	(617,85)	[1,24,18,3,47,34,25,19,15,23]
UAV3		[41,35,46,8,40,9,16,39,4,44,31,7,13,27]
UAV4		[2,10,28,48,22,12,43,29,32,42,11,5,21]

表6 12000m×12000m范围协同任务分配方法参数

Table 6 Parameters of the collaborative task allocation method in the range of 12000m×12000m

算法	参数	数值	参数	子任务区域任务分配	UAV任务分配	UGV任务分配
	邻域半径/m	1000	种群数量	240	240	50
密度值最大聚类算法	密度阈值	5	混合粒子群优化算法	迭代次数	720	720	200
	簇距离阈值/m	1500		交叉概率	0.7	0.7	0.7
				变异概率	0.7	0.7	0.7

图12 子任务区域的划分和任务分配

Fig.12 Clustering and task allocation

表7 12000m×12000m范围内多目标空地异构无人系统协同任务分配结果

Table 7 Collaborative task allocation for multi-target air-ground heterogeneous unmanned system in the range of 12000m×12000m

图13 12000m×12000m范围内多目标空地异构无人系统协同任务分配示意图

Fig.13 Schematic diagram of the collaborative task allocation for multi-target air-ground heterogeneous unmanned system in the range of 12000m×12000m

参考文献 20

[1]	武文亮, 周兴社, 沈博, 等. 集群机器人系统特性评价研究综述[J]. 自动化学报, 2020, 46(13): 1-20.
	WU W L, ZHOU X S, SHEN B, et al. A review of swarm robotic systems property evaluation[J]. Acta Automatica Sinica, 2020, 46(13): 1-20. (in Chinese)
[2]	DENG Q B, YU J Q, WANG N F. Cooperative task assignment of multiple heterogeneous unmanned aerial vehicles using a modified genetic algorithm with multi-type genes[J]. Chinese Journal of Aeronautics, 2013, 26(5): 1238-1250. doi: 10.1016/j.cja.2013.07.009 URL
[3]	GARONE E, NALDI R, CASAVOLA A, et al. Cooperative mission planning for a class of carrier-vehicle systems[C]//Proceedings of the 49th IEEE Conference on Decision and Control. Piscataway, NJ, US: IEEE, 2010: 1354-1359.
[4]	WU W N, WANG X G, CUI N G. Fast and coupled solution for cooperative mission planning of multiple heterogeneous unmanned aerial vehicles[J]. Aerospace Science and Technology, 2018, 79: 131-144. doi: 10.1016/j.ast.2018.05.039 URL
[5]	CHEN M Q, CHEN Y, CHEN Z H, et al. Path planning of UAV-UGV heterogeneous robot system in road network[C]//Proceedings of International Conference on Intelligent Robotics and Applications. Cham,Switzerland:Springer, 2019: 497-507.
[6]	BAE J, PARK M. A heuristic for efficient coordination of multiple heterogeneous mobile robots considering workload balance[J]. IEEE Robotics and Automation Letters, 2021, 6(2): 4064-4070. doi: 10.1109/LRA.2021.3067286 URL
[7]	BAE J, LEE J, CHUNG W. A heuristic for task allocation and routing of heterogeneous robots while minimizing maximum travel cost[C]//Proceedings of 2019 International Conference on Robotics and Automation. Montreal, Canada: IEEE, 2019: 4531-4537.
[8]	张云飞, 林德福, 郑多, 等. 多目标时空同步协同攻击无人机任务分配与轨迹优化[J]. 兵工学报, 2021, 42(7): 1482-1495.
	ZHANG Y F, LIN D F, ZHENG D, et al. Task allocation and trajectory optimization of UAV for multi-target time-space synchronization cooperative attack[J]. Acta Armamentarii, 2021, 42(7): 1482-1495. (in Chinese) doi: 10.3969/j.issn.1000-1093.2021.07.016
[9]	MURRAY C C, CHU A G. The flying sidekick traveling salesman problem: Optimization of drone-assisted parcel delivery[J]. Transportation Research Part C: Emerging Technologies, 2015, 54: 86-109. doi: 10.1016/j.trc.2015.03.005 URL
[10]	HA Q M, DEVILLE Y, PHAM Q D, et al. On the min-cost traveling salesman problem with drone[J]. Transportation Research Part C: Emerging Technologies, 2018, 86: 597-621. doi: 10.1016/j.trc.2017.11.015 URL
[11]	CHEN J C, DU C L, LU X, et al. Multi-region coverage path planning for heterogeneous unmanned aerial vehicles systems[C]//Proceedings of 2019 IEEE International Conference on Service-Oriented System Engineering. San Francisco Bay, CA, US: IEEE, 2019: 356-365.
[12]	CHEN J C, DU C L, ZHANG Y, et al. A clustering-based coverage path planning method for autonomous heterogeneous UAVs[J]. IEEE Transactions on Intelligent Transportation Systems, 2021, 23(12): 25546-25556. doi: 10.1109/TITS.2021.3066240 URL
[13]	BANFI J, MESSING A, KRONINGER C, et al. Hierarchical planning for heterogeneous multi-robot routing problems via learned subteam performance[J]. IEEE Robotics and Automation Letters, 2022, 7(2): 4464-4471. doi: 10.1109/LRA.2022.3148489 URL
[14]	ARBANAS B, IVANOVIC A, CAR M, et al. Decentralized planning and control for UAV-UGV cooperative teams[J]. Autonomous Robots, 2018, 42(8): 1601-1618. doi: 10.1007/s10514-018-9712-y
[15]	SHIMA T, RASMUSSEN S J, SPARKS A G, et al. Multiple task assignments for cooperating uninhabited aerial vehicles using genetic algorithms[J]. Computers & Operations Research, 2006, 33(11): 3252-3269. doi: 10.1016/j.cor.2005.02.039 URL
[16]	EDISON E, SHIMA T. Integrated task assignment and path optimization for cooperating uninhabited aerial vehicles using genetic algorithms[J]. Computers & Operations Research, 2011, 38(1): 340-356. doi: 10.1016/j.cor.2010.06.001 URL
[17]	FEO-FLUSHING E, GAMBARDELLA L M, DI CARO G A. Spatially-distributed missions with heterogeneous multi-robot teams[J]. IEEE Access, 2021, 9: 67327-67348. doi: 10.1109/ACCESS.2021.3076919 URL
[18]	ZHAO X Y, ZONG Q, TIAN B L, et al. Fast task allocation for heterogeneous unmanned aerial vehicles through reinforcement learning[J]. Aerospace Science and Technology, 2019, 92: 588-594. doi: 10.1016/j.ast.2019.06.024 URL
[19]	CHEN L, LIU W L, ZHONG J. An efficient multi-objective ant colony optimization for task allocation of heterogeneous unmanned aerial vehicles[J]. Journal of Computational Science, 2022, 58: 101545. doi: 10.1016/j.jocs.2021.101545 URL
[20]	王晶, 夏鲁宁, 荆继武. 一种基于密度最大值的聚类算法[J]. 中国科学院大学学报, 2009, 26(4): 539-548. doi: 10.7523/j.issn.2095-6134.2009.4.016
	WANG J, XIA L N, JING J W. Maximum density clustering algorithm[J]. Journal of University of Chinese Academy of Sciences, 2009, 26(4): 539-548. (in Chinese) doi: 10.7523/j.issn.2095-6134.2009.4.016