多智能体系统故障临机处理下的快速任务重分配

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

摘要/Abstract

摘要：

为解决在执行任务过程中部分智能体可能会发生故障，无法完成预定的任务分配方案，需要进行任务重分配的问题，提出一种具有虚拟管理者基于共识的捆绑算法的局部重分配方法。首先，引入基于时序的任务优先级排序方法，提高资源利用率。然后，基于K均值聚类方法，将大规模任务场景划分为多个小规模任务组，减少任务重分配求解时间。最后，仿真实验验证所提方法的有效性。与基于共识的捆绑算法的全局重分配方法进行对比，所提该方法在大规模场景下具有更好的实时性。随着任务规模的扩大，采用该方法进行任务重分配的任务完成率上升。

关键词: 多智能体, 任务重分配, 故障临机处理, 基于共识的捆绑算法

Abstract:

To solve the problem of some intelligent agents failing to complete the predetermined task allocation plan and requiring task reallocation during task execution, a local reallocation method consensus-based bundle algorithm with virtual managers is proposed. Firstly, a time series based task priority sorting method is introduced to improve resource utilization. Secondly, based on the K-means clustering method, the large-scale task scenario is divided into multiple small-scale task groups to reduce the time required for task reallocation and solving. Finally, the effectiveness of the proposed method is verified through simulation experiments. Compared with the global reallocation method based on the consensus bundling algorithm, the proposed method has better real-time performance in large-scale scenarios. As the scale of tasks expands, the completion rate of tasks reassigned using this method increases.

Key words: multi-agent, task reassignment, emergency fault handling, consensus-based bundle algorithm

中图分类号:

TP 273

单晨宇, 李少凡, 齐瑞云. 多智能体系统故障临机处理下的快速任务重分配[J]. 系统工程与电子技术, 2026, 48(1): 185-197.

Chenyu SHAN, Shaofan LI, Ruiyun QI. Fast task reassignment in multi-agent system emergency fault handling[J]. Systems Engineering and Electronics, 2026, 48(1): 185-197.

图/表 21

图1

图2

图3

图4

表1

图5

图6

图7

图8

表2

图9

图10

图11

图12

图13

图14

图15

表3

表4

表5

图16

参考文献 31

1	李敏灿. 基于协作的多智能体系统设计与优化技术研究[D]. 长沙: 湖南大学, 2021.
	LI M C. Research on design and optimization technology of multi-agent system based on cooperation[D]. Changsha: Hunan University, 2021.
2	ZENGIN U, DOGAN A. Real-time target tracking for autonomous UAVs in adversarial environments: a gradient search algorithm[J]. IEEE Trans. on Robotics, 2007, 23 (2): 294- 307. doi: 10.1109/TRO.2006.889490
3	ZHU S Q, WANG D W. Adversarial ground target tracking using UAVs with input constraints[J]. Journal of Intelligent & Robotic Systems, 2012, 65 (1): 521- 532.
4	KIM H G, PARK J S, LEE D H. Potential of unmanned aerial sampling for monitoring insect populations in rice fields[J]. Florida Entomologist, 2018, 101 (2): 330- 334. doi: 10.1653/024.101.0229
5	LI M L, YANG W J, YI X D, et al. Swarm robot task planning based on air and ground coordination for disaster search and rescue[J]. IEEE Trans. on Electron Devices, 2019, 55 (11): 1- 9.
6	SUDHAKAR S, VIJAYAKUMAR V, SATHIYA KUMAR C, et al. Unmanned aerial vehicle （UAV） based forest fire detection and monitoring for reducing false alarms in forest-fires[J]. Computer Communications, 2020, 149, 1- 16. doi: 10.1016/j.comcom.2019.10.007
7	NUNES E, MANNER M, MITICHE H, et al. A taxonomy for task allocation problems with temporal and ordering constraints[J]. Robotics and Autonomous Systems, 2017, 90, 55- 70. doi: 10.1016/j.robot.2016.10.008
8	陈侠, 乔艳芝. 无人机任务分配综述[J]. 沈阳航空航天大学学报, 2016, 33 (6): 1- 7.
	CHEN X, QIAO Y Z. Summary of unmanned aerial vehicle task allocation[J]. Journal of Shenyang Aerospace University, 2016, 33 (6): 1- 7.
9	贾高伟, 王建峰. 无人机集群任务规划方法研究综述[J]. 系统工程与电子技术, 2021, 43 (1): 99- 111.
	JIA G W, WANG J F. Summary of research on task planning methods for drone cluster[J]. Systems Engineering and Electronic, 2021, 43 (1): 99- 111.
10	齐小刚, 李博, 范英盛, 等. 多约束下多无人机的任务规划研究综述[J]. 智能系统学报, 2020, 15 (2): 204- 217.
	QI X G, LI B, FANG Y S, et al. A survey of mission planning on UAVs systems based on multiple constraints[J]. CAAI Transactions on Intelligent Systems, 2020, 15 (2): 204- 217.
11	JIA Z Y, YU J Q, AI X, et al. Cooperative multiple task assignment problem with stochastic velocities and time windows for heterogeneous unmanned aerial vehicles using a genetic algorithm[J]. Aerospace Science and Technology, 2018, 76, 112- 125. doi: 10.1016/j.ast.2018.01.025
12	BAI X S, YAN W S, SAMGE S, et al. An integrated multi-population genetic algorithm for multi-vehicle task assignment in a drift field[J]. Information Sciences, 2018, 453, 227- 238. doi: 10.1016/j.ins.2018.04.044
13	WANG Z, LIU L, LONG T, et al. Multi-UAV reconnaissance task allocation for heterogeneous targets using an opposition-based genetic algorithm with double-chromosome encoding[J]. Chinese Journal of Aeronautics, 2018, 31 (2): 339- 350. doi: 10.1016/j.cja.2017.09.005
14	马华伟, 朱益民, 胡笑旋. 基于粒子群算法的无人机舰机协同任务规划[J]. 系统工程与电子技术, 2016, 38 (7): 1583- 1588.
	MA H W, ZHU Y M, HU X X. Unmanned aerial vehicle ship aircraft collaborative task planning based on particle swarm optimization algorithm[J]. Systems Engineering and Electronic, 2016, 38 (7): 1583- 1588.
15	杜晓凯. 无人机集群混合式任务实时分配算法研究[D]. 西安: 西安电子科技大学, 2020.
	DU X K. Research on real time task allocation algorithm for hybrid UAV cluster[D]. Xi’an: Xidian University, 2020.
16	LEE D H. Resource-based task allocation for multi-robot systems[J]. Robotics and Autonomous Systems, 2018, 103, 151- 161. doi: 10.1016/j.robot.2018.02.016
17	LIANG H T, KANG F J. A novel task optimal allocation approach based on contract net protocol for agent-oriented UUV swarm system modeling[J]. Optik, 2016, 127 (8): 3928- 3933. doi: 10.1016/j.ijleo.2016.01.071
18	ZHAO M, LI D C.. Collaborative task allocation of heterogeneous multi-unmanned platform based on a hybrid improved contract net algorithm[J]. IEEE Access, 2021, 9, 78936- 78946. doi: 10.1109/ACCESS.2021.3084238
19	SUN C H, WANG X C, QIU H X, et al. Game theoretic self-organization in multi-satellite distributed task allocation[J]. Aerospace Science and Technology, 2021, 112, 106650. doi: 10.1016/j.ast.2021.106650
20	PONDA S, REDDING J, CHOI H L, et al. Decentralized planning for complex missions with dynamic communication constraints[C]// Proc. of the American Control Conference, 2010.
21	ALITAPPEH R J, JEDDISARAVI K. Multi-robot exploration in task allocation problem[J]. Applied Intelligence, 2022, 52 (2): 2189- 2211. doi: 10.1007/s10489-021-02483-3
22	QIE H, SHI D X, SHEN T L, et al. Joint optimization of multi-UAV target assignment and path planning based on multi-agent reinforcement learning[J]. IEEE Access, 2019, 7, 146264- 146272. doi: 10.1109/ACCESS.2019.2943253
23	FARUQ F, PARKER D, LACCRDA B, et al. Simultaneous task allocation and planning under uncertainty[C]// Proc. of the IEEE/RSJ International Conference on Intelligent Robots and Systems, 2018.
24	CAO R Y, LI S C, JI Y H, et al. Task assignment of multiple agricultural machinery cooperation based on improved ant colony algorithm[J]. Computers and Electronics in Agriculture, 2021, 182, 105993. doi: 10.1016/j.compag.2021.105993
25	谷旭平, 唐大全. 基于细菌觅食算法的多异构无人机任务规划[J]. 系统工程与电子技术, 2021, 43 (11): 3312- 3320.
	GU X P, TANG D Q. Multi heterogeneous unmanned aerial vehicle mission planning based on bacterial foraging algorithm[J]. Systems Engineering and Electronics, 2021, 43 (11): 3312- 3320.
26	ZHOU J, ZHAO X Z, ZHANG X P, et al. Task allocation for multi-agent systems based on distributed many-objective evolutionary algorithm and greedy algorithm[J]. IEEE Access, 2020, 8, 19306- 19318. doi: 10.1109/ACCESS.2020.2967061
27	TANG J, CHEN X, ZHU X M, et al. Dynamic reallocation model of multiple unmanned aerial vehicle tasks in emergent adjustment scenarios[J]. IEEE Trans. on Aerospace and Electronic Systems, 2022, 59(2): 1139−1155.
28	鞠锴, 冒泽慧, 姜斌, 等. 基于势博弈的异构多智能体系统任务分配和重分配[J]. 自动化学报, 2022, 48 (10): 2416- 2428.
	JU K, MAO Z H, JIANG B, et al. Task allocation and reassignment of heterogeneous multi-agent system based on potential game[J]. Journal of Automation, 2022, 48 (10): 2416- 2428.
29	张安, 毕文豪, 邱鹏, 等. 基于改进合同网的多UAV打击地面TST任务重分配[J]. 战术导弹技术, 2019, (2): 39- 46. doi: 10.16358/j.issn.1009-1300.2019.7.213
	ZHANG A, BI W H, QIU P, et al. Multi UAV strike ground TST task reassignment based on improved contract network[J]. Tactical Missile Technology, 2019, (2): 39- 46. doi: 10.16358/j.issn.1009-1300.2019.7.213
30	JAIN A K, DUBES R C. Algorithms for clustering data[M]. Upper Saddle River: Prentice-Hall, 1988.
31	CHOI H L, BRUNET L, HOW J P. Consensus-based decentralized auctions for robust task allocation[J]. IEEE Trans. on Robotics, 2009, 25 (4): 912- 926. doi: 10.1109/TRO.2009.2022423

发送方$ k $认为$ {z}_{jk} $	接收方$ i $认为是$ {z}_{ij} $	接收方行为（默认：保持）
$ k $	$ i $	若$ {y}_{kj} \gt {y}_{ij}\rightarrow $更新
	$ k $	更新
	$ m\notin \left\{i,~k\right\} $	若$ {s}_{km} \gt {s}_{im} $或$ {y}_{kj} \gt {y}_{ij}\rightarrow $更新
	$ \varnothing $	更新
$ i $	$ i $	保持
	$ k $	重置
	$ m\notin \left\{i,~k\right\} $	若$ {s}_{km} \gt {s}_{im}\rightarrow $重置
	$ \varnothing $	保持
$ m\notin \left\{i,~k\right\} $	$ i $	若$ {s}_{km} \gt {s}_{im} $或$ {y}_{kj} \gt {y}_{ij}\rightarrow $更新
	$ k $	若$ {s}_{km} \gt {s}_{im} $更新，否则$ \rightarrow $重置
	m	若$ {s}_{km} \gt {s}_{im}\rightarrow $更新
	$ n\notin \left\{i,~k,~m\right\} $	若$ {s}_{km} \gt {s}_{im} $且$ {s}_{kn} \gt {s}_{in}\rightarrow $更新
		若$ {s}_{km} \gt {s}_{im} $且$ {y}_{kj} \gt {y}_{ij}\rightarrow $更新
		若$ {s}_{im} \gt {s}_{km} $且$ {s}_{kn} \gt {s}_{in}\rightarrow $重置
	$ \varnothing $	若$ {s}_{km} \gt {s}_{im}\rightarrow $更新
$ \varnothing $	$ i $	保持
	$ k $	更新
	$ m\notin \left\{i,~k\right\} $	若$ {s}_{km} \gt {s}_{im}\rightarrow $更新
	$ \varnothing $	保持

参数	参数值
任务区域/km²	100 ×100
任务数量	10~15, 15~20, 30~35, 45~50
时间窗大小Δ/min	10 ~20
性能类型	3
智能体类型	3
总智能体数量	3~6倍任务数
智能体速度/ms^-1	25, 30, 40
智能体故障比例/%	8~15
时间衰减系数	0.05

任务规模	传统CBBA全局重分配方法/s	分组CBBA-VMLR 重分配方法/s
任务规模1	1.2815	1.5803
任务规模2	8.0521	1.7854
任务规模3	117.75	3.5069
任务规模4	—	4.4139

任务规模	传统CBBA全局重分配方法/%	分组CBBA-VMLR 重分配方法/%
任务规模1	89.990 1	82.777 6
任务规模2	91.617 5	87.838 5
任务规模3	92.945 4	90.783 4
任务规模4	—	93.231 0

任务规模/个	智能体规模/个	平均任务完成率/%
10	50	81.5761
15	75	83.0638
20	100	85.7378
25	125	88.0974
30	150	89.2187
35	175	90.2367
40	200	90.3706
45	225	91.7993
50	250	92.2185
55	220	93.3630
60	240	93.3782
65	260	94.3542
70	280	94.5754
75	300	94.5792