A Reconnaissance Task Allocation Algorithm for Air-Ground Heterogeneous Unmanned System

doi:10.12382/bgxb.2024.0319

Abstract

Abstract:

Aiming at the reconnaissance task allocation of air-ground heterogeneous unmanned system,this paper proposes a two-stage mixed task assignment(TMTA)algorithm for reconnaissance tasks and communication relay tasks.An alternative set of reconnaissance position and communication relay position are constructed based on the reconnaissance distance,communication relay distance and target position.An reconnaissance and communication relay tasks dispatching model is built by taking the task timeliness and path cost as the objective functions,in which the combining reconnaissance/communication relay task completion constraints,coupling constraints between task location selection/task execution time and task paths,and path continuity constraints,etc.,are considered.To solve the nonlinearity of the model,the advantages of set coverage algorithm,Hungarian algorithm,and genetic algorithm are synthesized to design a TMTA algorithm,which realizes the efficient solution of the model.The proposed method is validated through experiment.The experimental results show that the proposed algorithm outperforms the baseline dispatching algorithm in terms of task timeliness and path cost.

Key words: air-ground heterogeneous, unmanned agent, reconnaissance task, communication relay task, task allocation algorithm

SUN Yujie, SU Bo, DUAN Leyi, JI Chao, YANG Chaonan. A Reconnaissance Task Allocation Algorithm for Air-Ground Heterogeneous Unmanned System[J]. Acta Armamentarii, 2024, 45(S2): 317-328.

Figures/Tables 13

Table 1 Parameter andvariable list

参数/变量	含义
k	无人智能体的索引
k₀	指挥车的索引
K_TL	合成编队中无人侦察智能体的集合
K_TX	合成编队中无人通信中继智能体的集合
K	合成编队中无人智能体的集合
o_k	智能体k的当前位置
d_k	智能体k执行完所有任务后需返回的位置
m	带目标的侦察任务
$t ¯ m$	任务m的最晚执行时间
M_q	所有智能体已接受但尚未执行的侦察任务集合
M_n	新收到的侦察任务集合
M_ZC	所有侦察任务的集合,M_ZC=M_n∪M_q
i,j	位置的索引
tl_i	位置i的最晚访问时间
$φ Z C k$ (i)	智能体k在侦察位置i可侦察到的目标的集合
$φ ˜ Z C k$ (m)	智能体k能够侦察到目标m的备选侦察位置的集合
$d T X k 0$	指挥车的通信距离
$d T X k$	智能体的通信距离
$l o k 0, i$	备选侦察位置与指挥车之间的通信距离
$γ T X k$ (i)	智能体k在位置i执行侦察任务时所需要建立通信中继的位置
$S Z C k$	智能体k的侦察位置备选集
$S Z C' k$	智能体k侦察位置备选集中超出指挥车通信范围的备选侦察位置
S_TX	通信中继位置备选集
$x i k$	表示智能体k是否选择访问位置i,若是则 $x i k$ =1,否则 $x i k$ =0
$t i k$	表示智能体k访问位置i的预计时间
$t a v a i k$	表示智能体k的空余时间
t $t i, j k$	表示智能体k到访问为止i,j的时间
$y i, j k$	表示从智能体k是否选择路径(i,j),若是则 $y i, j k$ ,否则 $y k i j$ =0
$l i, j k$	表示智能体k侦察位置i到通信中继位置j的距离
$c t k, i$	对智能体k访问位置超出最晚访问时间的惩罚值
μ_t	时间惩罚值在目标函数中的权重系数
μ_l	行驶里程费用在目标函数中的权重系数
$L m a x k$	智能体k的剩余续航里程

Table 1 Parameter andvariable list

参数/变量	含义
k	无人智能体的索引
k₀	指挥车的索引
K_TL	合成编队中无人侦察智能体的集合
K_TX	合成编队中无人通信中继智能体的集合
K	合成编队中无人智能体的集合
o_k	智能体k的当前位置
d_k	智能体k执行完所有任务后需返回的位置
m	带目标的侦察任务
$t ¯ m$	任务m的最晚执行时间
M_q	所有智能体已接受但尚未执行的侦察任务集合
M_n	新收到的侦察任务集合
M_ZC	所有侦察任务的集合,M_ZC=M_n∪M_q
i,j	位置的索引
tl_i	位置i的最晚访问时间
$φ Z C k$ (i)	智能体k在侦察位置i可侦察到的目标的集合
$φ ˜ Z C k$ (m)	智能体k能够侦察到目标m的备选侦察位置的集合
$d T X k 0$	指挥车的通信距离
$d T X k$	智能体的通信距离
$l o k 0, i$	备选侦察位置与指挥车之间的通信距离
$γ T X k$ (i)	智能体k在位置i执行侦察任务时所需要建立通信中继的位置
$S Z C k$	智能体k的侦察位置备选集
$S Z C' k$	智能体k侦察位置备选集中超出指挥车通信范围的备选侦察位置
S_TX	通信中继位置备选集
$x i k$	表示智能体k是否选择访问位置i,若是则 $x i k$ =1,否则 $x i k$ =0
$t i k$	表示智能体k访问位置i的预计时间
$t a v a i k$	表示智能体k的空余时间
t $t i, j k$	表示智能体k到访问为止i,j的时间
$y i, j k$	表示从智能体k是否选择路径(i,j),若是则 $y i, j k$ ,否则 $y k i j$ =0
$l i, j k$	表示智能体k侦察位置i到通信中继位置j的距离
$c t k, i$	对智能体k访问位置超出最晚访问时间的惩罚值
μ_t	时间惩罚值在目标函数中的权重系数
μ_l	行驶里程费用在目标函数中的权重系数
$L m a x k$	智能体k的剩余续航里程

Fig.1 Illustration of reconnaissance position alternate set

Fig.2 Illustration of communication relay position alternate set

Fig.3 Illustration of set covering problem

Table 2 List of reconnaissance task

目标编号	位置/km	任务最晚执行时间/min
0	(9.796,1.797)	8
1	(0.342,4.638)	10
2	(10.208,9.224)	18
3	(1.026,9.717)	20
4	(7.78,9.436)	28
5	(9.82,8.957)	28
6	(6.46,1.884)	28
7	(10.834,3.814)	31
8	(9.282,10.343)	33
9	(5.505,7.088)	36

Table 3 State of reconnaissance agents

侦察智能体	位置/km	剩余续航里程/km	既有任务序列
侦察无人车1	(4.166,2.596)	22	目标0,1
侦察无人车2	(2.394,4.703)	35	目标2
侦察无人机	(0.863,1.719)	21	目标3

Table 4 State of communication relay agents

通信中继智能体	位置/km	剩余续航里程/km
通信无人机1	(3.544,5.858)	13
通信无人机2	(4.436,4.967)	41

Table 5 Reconnaissance agent task sequence of the proposed dispatching algorithm

侦察智能体	任务序列
侦察智能体	第1个任务位置/km	目标编号	第2个任务位置/km	目标编号
侦察无人车1	(4.845, 2.499)	目标0,1, 6,9	(6.526, 6.170)	目标2,4, 5,7,8
侦察无人车2	(2.394, 4.703)	目标3
侦察无人机

Table 6 Communication relay agent task sequence of the proposed dispatching algorithm

通信中继智能体	任务序列
通信中继智能体	第1个任务位置/km	所通信中继的智能体及其任务位置/km	第2个任务位置/km	所通信中继的智能体及其任务位置/km
通信无人机1
通信无人机2	(3.263, 3.085)	侦察无人车1 (6.526,6.170)

Table 7 Reconnaissance agent task sequence of the baseline dispatching algorithm

侦察智能体	任务序列
侦察智能体	第1个任务位置/km	目标编号	第2个任务位置/km	目标编号
侦察无人车1	(4.845, 2.499)	目标0,1, 6,9	(5.915, 2.915)	目标7
侦察无人车2	(5.880, 6.719)	目标2,4, 5,8
侦察无人机	(0.883, 2.718) 目标3

Table 8 Communication relay agent task sequence of the baseline dispatching algorithm

通信中继智能体体	任务序列
通信中继智能体体	第1个任务位置/km	所通信中继的智能体及其任务位置/km	第2个任务位置/km	所通信中继的智能体及其任务位置/km
通信无人机1	(2.940, 3.359)	侦察无人车2 (5.880,6.719)
通信无人机2

Fig.4 Comparison of the total delay times

Fig.5 Comparison of the total travelling distances

References 22

[1]	毕文豪, 张梦琦, 高飞, 等. 无人机集群任务分配技术研究综述[J]. 系统工程与电子技术, 2024, 46(3):922-934. doi: 10.12305/j.issn.1001-506X.2024.03.18
	BI W H, ZHANG M Q, GAO F, et al. Review on UAV swarm task allocation technology[J]. Systems Engineering and Electronics, 2024, 46(3):922-934. (in Chinese) doi: 10.12305/j.issn.1001-506X.2024.03.18
[2]	SONG J, ZHAO K, LIU Y. Survey on mission planning of multiple unmanned aerial vehicles[J]. Aerospace, 2023(3):10,208.
[3]	KIM M H, LEE S, BAIK H. Response threshold model based UAV search planning and task allocation[J]. Journal of Intelligent &Robotic Systems, 2014, 75(3/4):625-640.
[4]	ZHU Q, ZENG H B, ZHENG W, et al. Optimization of task allocation and priority assignment in hard real-time distributed systems[J]. ACM Transactions on Embedded Computing Systems, 2013, 11(4):85.
[5]	YAN P, TAN B. Evolutionary group theoretic tabu search approach to task allocation of autonomous unmanned aerial vehicles[C]// Proceedings of the IEEE International Conference on Control and Automation.Washington,DC,US:IEEE, 2013:687-692.
[6]	沈林成, 陈璟, 王楠. 飞行器任务规划技术综述[J]. 航空学报, 2014, 35(3):593-606. doi: 10.7527/S1000-6893.2013.0500
	SHEN L C, CHEN J, WANG N. Overview of air vehicle mission planning techniques[J]. Acta Aeronautica et Astronautica Sinica, 2014, 35(3):593-606. (in Chinese) doi: 10.7527/S1000-6893.2013.0500
[7]	YOUNAS I, KAMRANI F, BASHIR M, et al. Efficient genetic algorithms for optimal assignment of tasks to teams of agents[J]. Neurocomputing, 2018, 314:409-428.
[8]	CAPITAN J, SPAAN M, MERINO L, et al. Decentralized multi-robot cooperation with auctioned POMDPs[J]. The International Journal of Robotics Research, 2013, 32(6):650-671.
[9]	MARTIN J G, FREJO J R D, GARCÍA R A, et al. Multi-robot task allocation problem with multiple nonlinear criteria using branch and bound and genetic algorithms[J]. Intelligent Service Robotics. 2021,14,707-727.
[10]	MILLS-TETTEY G A, STENTZ A, DIAS M B. The dynamic Hungarian algorithm for the assignment problem with changing costs[J]. carnegie mellon university, 2007.
[11]	范博洋, 赵高鹏, 薄煜明, 等. 多目标空地异构无人装备协同任务分配方法[J]. 兵工学报, 2023, 44(6):1564-1575. doi: 10.12382/bgxb.2022.0095
	FAN B Y, ZHAO G P, BO Y M, et al. Collaborative task allocation method for multi-target air-ground heterogeneous unmanned system[J]. Acta Armamentarii, 2023, 44(6):1564-1575. (in Chinese) doi: 10.12382/bgxb.2022.0095
[12]	张国辉, 张雅楠, 高昂, 等. 空地异构无人装备侦察任务规划方法[J]. 系统仿真学报, 2024, 36(2):497-510. doi: 10.16182/j.issn1004731x.joss.23-0103
	ZHANG G H, ZHANG Y N, GAO A, et al. Reconnaissance mission planning method for air-ground heterogeneous unmanned Systems[J]. Journal of System Simulation, 2024, 36(2):497-510. (in Chinese) doi: 10.16182/j.issn1004731x.joss.23-0103
[13]	张雷, 王道波, 高宇辉, 等. 基于粒子群优化的无人战斗机编队任务协调方法研究[J]. 系统工程与电子技术, 2009, 31(2):439-442.
	ZHANG L, WANG D B, GAO Y H, et al. Study on uninhabited combat air vehicle formation tasks scheduling method based on particle swarm optimization algorithm[J]. Systems Engineering and Electronics, 2009, 31(2):439-442. (in Chinese)
[14]	田震, 王晓芳. 基于多基因遗传算法的异构多无人机协同任务分配[J]. 飞行力学, 2019, 37(1):39-44.
	TIAN Z, WANG X F. Cooperative multiple task assignment for heterogeneous multi-UAVs with multi-chromosome genetic algorithm[J]. Flight Dynamics, 2019, 37(1):39-44 (in Chinese)
[15]	康旭超, 何广军, 陈峰, 等. 求解无人机ISR任务分配问题的离散萤火虫算法[J]. 弹箭与制导学报, 2019, 39(5):131-134,138.
	KANG X C, HE G J, CHEN F, et al. Discrete firefly algorithm for solving ISR task assignment problem of UAV[J]. Journal of Projectiles,Rockets,Missiles and Guidance, 2019, 39(5):131-134,138. (in Chinese)
[16]	许可, 宫华, 秦新立, 等. 基于分布式拍卖算法的多无人机分组任务分配[J]. 信息与控制, 2018, 47(3):341-346.
	XU K, GONG H, QIN X L, et al. Multi-UAV task assignment for grouped tasks based on distribution auction algorithm[J]. Information and Control, 2018, 47(3):341-346. (in Chinese)
[17]	赵晓林, 魏兆恬, 赵博欣, 等. 异构资源类型下多无人机任务分配[J]. 国防科技大学学报, 2023, 45(4):232-242.
	ZHAO X L, WEI Z T, ZHAO B X, et al. Task allocation of multiple UAVs under heterogeneous resource types[J]. Journal of national university of defense technology, 2023, 45(4):232-242. (in Chinese)
[18]	吕晔, 周锐, 李兴, 等. 基于多轮次分布式拍卖的异构多任务分配算法[J/OL]. 北京航空航天大学学报, 2023(2023-08-03)[2024-04-15].https://doi.org/10.13700/j.bh.1001-5965.2023.0156.
	LÜ Y, ZHOU R, LI X, et al. Multi-task assignment algorithm based on multi-round distributed auction[J/OL]. Journal of Beijing University of Aeronautics and, 2023(2023-08-03)[2024-04-15].https://doi.org/10.13700/j.bh.1001-5965.2023.0156. (in Chinese)
[19]	竺殊荣. 动态环境下多无人机协同任务规划方法[D]. 南京: 南京邮电大学, 2020.
	ZHU S R. Cooperativetask planning method of multi-UAV in dynamic environment[D]. Nanjing: Nanjing University of Posts and Telecommunications, 2020. (in Chinese)
[20]	龙泓, 魏晨, 段海滨. 基于无监督学习离散鸽群优化的多无人机侦察任务分配[J]. 空军工程大学学报, 2023, 24(5):16-22,32.
	LONG H, WEI C, DUAN H B. Task allocation for multi-UAV reconnaissance via unsupervised learning discrete pigeon-inspired optimization[J]. Journal of Air Force Engineering University, 2023, 24(5):16-22,32. (in Chinese)
[21]	林萌龙, 陈涛, 任棒棒, 等. 基于多智能体深度强化学习的体系任务分配方法[J]. 指挥与控制学报, 2023, 9(1):93-102.
	LIN M L, CHEN T, REN B B, et al. Task assignment method of operation system of systems based on multi-agent deep reinforcement learning[J]. Journal of Command and Control, 2023, 9(1):93-102. (in Chinese)
[22]	严钰文, 毕文豪, 张安, 等. 基于序列生成对抗网络的无人机集群任务分配方法[J]. 兵工学报, 2023, 44(9):2672-2684. doi: 10.12382/bgxb.2022.0931
	YAN Y W, BI W H, ZHANG A, et al. Task allocation method of UAV clusters based on sequence generative adversarial network[J]. Acta Armamentarii, 2023, 44(9):2672-2684. (in Chinese) doi: 10.12382/bgxb.2022.0931

通信中继智能体	任务序列
通信中继智能体	第1个任务位置/km	所通信中继的智能体及其任务位置/km	第2个任务位置/km	所通信中继的智能体及其任务位置/km
通信无人机1
通信无人机2	(3.263, 3.085)	侦察无人车1 (6.526,6.170)

通信中继智能体	任务序列
通信中继智能体	第1个任务位置/km	所通信中继的智能体及其任务位置/km	第2个任务位置/km	所通信中继的智能体及其任务位置/km
通信无人机1
通信无人机2	(3.263, 3.085)	侦察无人车1 (6.526,6.170)

通信中继智能体体	任务序列
通信中继智能体体	第1个任务位置/km	所通信中继的智能体及其任务位置/km	第2个任务位置/km	所通信中继的智能体及其任务位置/km
通信无人机1	(2.940, 3.359)	侦察无人车2 (5.880,6.719)
通信无人机2

通信中继智能体体	任务序列
通信中继智能体体	第1个任务位置/km	所通信中继的智能体及其任务位置/km	第2个任务位置/km	所通信中继的智能体及其任务位置/km
通信无人机1	(2.940, 3.359)	侦察无人车2 (5.880,6.719)
通信无人机2