JCBBA-based Cooperative Task Assignment with Time Precedence for Munition Swarms

doi:10.12382/bgxb.2025.0533

Abstract

Abstract:

For the task assignment of loitering munition swarm cooperatively conducting the reconnaissance，attack and assessment （RAA） tasks，a joint-bidding-based consensus-based bundle algorithm （JCBBA） is proposed by taking into account the constraint of time precedence，the heterogeneous characteristics of target property and the requirement of supporting the multiple munitions to jointly execute an identical task.Munition swarm task assignment of cooperative RAA is first formulated as combinatorial optimization problems.Then based on the structure of CBBA，a task bundle construction mechanism，an individual biding strategy and a marginal benefits computation method considering joint biding are tailored to achieve the fast and robust assignment of task with time precedence constraint in non-center communication networks.Numerical simulations under different scenarios show that JCBBA can achieve reasonable allocation of time precedence tasks while multiple constraints are satisfied，and the comparison tests demonstrate that JCBBA could better trade-off the computation efficiency and optimality with the solving time reduced by approximately 40% compared to consensus-based coalition algorithm.

Key words: task assignment, time precedence constraint, auction algorithm, joint bidding

SUN Jing, WANG Zhu, SONG Ziqiang, SUN Jingliang. JCBBA-based Cooperative Task Assignment with Time Precedence for Munition Swarms[J]. Acta Armamentarii, 2025, 46(S1): 250533-.

Figures/Tables 12

References 21

[1]	龙腾, 徐广通, 曹严, 等. 智能弹群协同任务规划技术进展与展望[J]. 前瞻科技, 2022, 1(4):18-39. doi: 10.3981/j.issn.2097-0781.2022.04.002
	LONG T, XU G T, CAO Y, et al. Review and prospect on cooperative mission planning technology of intelligent munition swarms[J]. Science and Technology Foresight, 2022, 1(4):18-39. (in Chinese) doi: 10.3981/j.issn.2097-0781.2022.04.002
[2]	WANG Z H, ZHANG J L. A task allocation algorithm for a swarm of unmanned aerial vehicles based on bionic wolf pack method[J]. Knowledge-Based Systems, 2022, 250:109072.
[3]	GAO X H, WANG L, YU X Y, et al. Conditional probability based multi-objective cooperative task assignment for heterogeneous UAVs[J]. Engineering Applications of Artificial Intelligence, 2023, 123:106404.
[4]	王磊, 徐超, 李淼, 等. 多飞行器协同任务分配的改进粒子群优化算法[J]. 兵工学报, 2023, 44(8):2224-2232. doi: 10.12382/bgxb.2022.0968
	WANG L, XU C, LI M, et al. Improved particle swarm optimization algorithm for cooperative task assignment of multiple vehicles[J]. Acta Armamentarii, 2023, 44(8):2224-2232. (in Chinese) doi: 10.12382/bgxb.2022.0968
[5]	QIAN F, SU K, LIANG X, et al. Task assignment for UAV swarm saturation attack:a deep reinforcement learning approach[J]. Electronics, 2023, 12(6):1292.
[6]	LIU B, WANG S L, LI Q H, et al. Task assignment of UAV swarms based on deep reinforcement learning[J]. Drones, 2023, 7(5):297.
[7]	伍国华, 李冰洁, 袁于斐, 等. 基于任务分解与强化学习的多平台协同火力分配方法[J]. 控制与决策, 2024, 39(5):1727-1735.
	WU G H, LI B J, YUAN Y P, et al. Multi-platform collaborative firepower allocation method based on task decomposition and reinforcement learning[J]. Control and Decision, 2024, 39(5):1727-1735. (in Chinese)
[8]	CHOPRA S, NOTARSTEFANO G, RICE M, et al. A distributed version of the hungarian method for multirobot assignment[J]. IEEE Transactions on Robotics, 2017, 33(4):932-947.
[9]	LINDSAY N, BUEHLING R K, SUN L. A sequential task addition distributed assignment algorithm for multi-robot systems[J]. Journal of Intelligent & Robotic Systems, 2021, 102(2):51.
[10]	陈璞, 严飞, 刘钊, 等. 通信约束下异构多无人机任务分配方法[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. (in Chinese)
[11]	高程, 都延丽, 步雨浓, 等. 基于顺序扩展一致性包算法的多无人机分布式任务分配[J]. 控制与决策, 2023, 38(11):3242-3250.
	GAO C, DU Y L, BU Y N, et al. Distributed task allocation of multiple UAVs based on sequential extended consensus based bundle algorithm[J]. Control and Decision, 2023, 38(11):3242-3250. (in Chinese)
[12]	CHOI H L, BRUNET L, HOW J P. Consensus-based decentralized auctions for robust task allocation[J]. IEEE Transaction on Robotics, 2009, 25(4):912-926.
[13]	BERTUCCELLI L F, CHOI H L, CHO P, et al. Real-time multi-UAV task assignment in dynamic and uncertain environments[C]// Proceedings of the AIAA Guidance,Navigation,and Control Conference.Chicago,Illinois, US:AIAA,2012:2009-5776.
[14]	CHOI H L, WHITTEN A K, HOW J P. Decentralized task allocation for heterogeneous teams with cooperation constraints[C]// Proceedings of the 2010 American Control Conference.Baltimore,MD, US:IEEE,2010:3057-3062.
[15]	MERCKER T, CASBEER D W, MILLET P T, et al. An extension of consensus-based auction algorithms for decentralized,time-constrained task assignment[C]// Proceedings of the 2010 American Control Conference.Baltimore,MD, US:IEEE,2010:6324-6329.
[16]	JOHNSON L, PONDA S, CHOI H L, et al. Improving the efficiency of a decentralized tasking algorithm for UAV teams with asynchronous communications[C]// Proceedings of AIAA Guidance,Navigation,and Control Conference.Toronto,Ontario, Canada:AIAA,2012:2010-8421.
[17]	HUNT S, MENG Q, HINDE C J. An extension of the consensus-based bundle algorithm for multi-agent tasks with task based requirements[C]// Proceedings of the 2012 11th International Conference on Machine Learning and Applications.Boca Raton,FL, US:IEEE,2012:451-456.
[18]	唐嘉钰, 李相民, 代进进, 等. 复杂约束条件下异构多智能体联盟任务分配[J]. 控制理论与应用, 2020, 37(11):2413-2422.
	TANG J Y, LI X M, DAI J J, et al. Coalition task allocation of heterogeneous multiple agents with complex constraints[J]. Control Theory and Technology, 2020, 37(11):2413-2422. (in Chinese)
[19]	李相民, 唐嘉钰, 代进进, 等. 异构多智能体联盟动态任务分配[J]. 西北工业大学学报, 2020, 38(5):1094-1104.
	LI X M, TANG J Y, DAI J J, et al. Dynamic coalition task allocation of heterogeneous multiple agents[J]. Journal of Northwestern Polytechnical University, 2020, 38(5):1094-1104. (in Chinese)
[20]	WANG T N, WANG Z, LI W, et al. Flexible combinatorial-bids-based auction for cooperative target assignment of unmanned aerial vehicles[J]. Aerospace, 2024, 11(11):895.
[21]	WU X L, YIN Y N, XU L, et al. Multi-UAV task allocation based on improved genetic algorithm[J]. IEEE Access, 2021, 9:100369-100379.

巡飞弹i'认为任务k的中标者	巡飞弹i认为任务k的中标者	采取的更新规则
i'	i	if y_i'k>y_ik→update
	i'	update
	m∉{i，i'}	if s_i'm>s_im or y_i'k>y_ik→update
	none	update
i	i	leave
	j	reset
	m ∉{i，i'}	if s_i'm>s_im→reset
	none	leave
m∉{i，i'}	i	if s_i'm>s_im and y_i'k>y_ik→update
	i'	if s_i'm>s_im→update，else→reset
	m	s_i'm>s_im→update
	n∉{i，i'，m}	if s_i'm>s_im and s_i'n>s_in→update if s_i'm>s_im and y_i'k>y_i'k→update if s_i'n>s_in and s_im>s_i'm→reset
	none	if s_i'm>s_im→update
none	i	leave
	j	update
	m∉{i，i'}	if s_i'm>s_im→update
	none	leave

巡飞弹i'认为任务k的中标者	巡飞弹i认为任务k的中标者	采取的更新规则
i'	i	if y_i'k>y_ik→update
	i'	update
	m∉{i，i'}	if s_i'm>s_im or y_i'k>y_ik→update
	none	update
i	i	leave
	j	reset
	m ∉{i，i'}	if s_i'm>s_im→reset
	none	leave
m∉{i，i'}	i	if s_i'm>s_im and y_i'k>y_ik→update
	i'	if s_i'm>s_im→update，else→reset
	m	s_i'm>s_im→update
	n∉{i，i'，m}	if s_i'm>s_im and s_i'n>s_in→update if s_i'm>s_im and y_i'k>y_i'k→update if s_i'n>s_in and s_im>s_i'm→reset
	none	if s_i'm>s_im→update
none	i	leave
	j	update
	m∉{i，i'}	if s_i'm>s_im→update
	none	leave

目标类型	任务类型	任务价值	任务时间	单弹执行成功概率/%
建筑	侦察	300	60	40
	打击	750	15	40
	评估	150	10	40
阵地	侦察	300	30	60
	打击	750	15	20
	评估	150	10	60
车辆	侦察	300	5	90
	打击	750	15	80
	评估	150	10	90

目标类型	任务类型	任务价值	任务时间	单弹执行成功概率/%
建筑	侦察	300	60	40
	打击	750	15	40
	评估	150	10	40
阵地	侦察	300	30	60
	打击	750	15	20
	评估	150	10	60
车辆	侦察	300	5	90
	打击	750	15	80
	评估	150	10	90

目标编号	任务类型	巡飞弹编号
1（建筑）	侦察	50、52、59、62
	打击	26、50、52、59、62
	评估	18、34、41、53
2（阵地）	侦察	6、13、16
	打击	6、10、13、16、30、31、35、42、47、60
	评估	21、32、56
3（车辆）	侦察	11、46
	打击	11、46、61
	评估	5、23
4（车辆）	侦察	12、24
	打击	12、15、24
	评估	21、48