Collaborative Task Allocation Method for Multi-Target Air-Ground Heterogeneous Unmanned System

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

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.

Figures/Tables 20

Fig.1 Main idea of this study

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

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

Fig.4 A sample of the particle code

Fig.5 A sample of the crossover operation

Fig.6 A sample of the mutation operation

Fig.7 Result of density peak clustering

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

Fig.8 Target distribution map in the range of 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

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

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

Fig.10 Flight time curves of UAVs

Fig.11 Target distribution map in the range of 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

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]

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

Fig.12 Clustering and task allocation

Table 7 Collaborative task allocation for multi-target air-ground heterogeneous unmanned system in the range of 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

References 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