基于改进快速搜索树和合同网的多智能体目标分配算法

doi:10.12382/bgxb.2024.0743

摘要/Abstract

摘要：

针对多智能体任务目标分配中航迹代价估算不准确的问题,提出一种基于改进快速搜索树算法的航迹代价计算方法,在合理地规划智能体运动轨迹的同时提高智能体航迹代价估算的准确性;针对改进合同网算法投标过程中优势智能体过早签约的问题,提出一种智能体投标状态转化机制,使得优势智能体可以多次参与任务竞标,实现智能体系统任务负载的均衡。仿真结果表明,新提出的航迹代价计算方法能够较好地计算智能体与目标、目标与目标之间的航迹;智能体投标转化机制解决了优势智能体过早签约导致的资源浪费,智能体系统完成任务的执行时间较之前降低6.54%,但处理优势智能体问题时新的机制会增加整个任务分配的投标轮次。

关键词: 多智能体系统, 目标分配, 航路规划, 改进合同网算法

Abstract:

For the inaccurate track cost estimation in task allocation for multi-agent systems, a track cost calculation method based on extended rapidly-exploring random tree is proposed to rationally plan the motion trajectories of agents and improve the accuracy of track cost estimation. In order to solve the problem of premature contracting of dominant agents in improved contract net algorithm, an agent bidding transformation mechanism is proposed to make the dominant agents participate in the task bidding for multiple times and achieve the balance of task load between agents in a system. The simulated results show that the proposed track cost calculation method can be used to accurately calculate the trajectory between agent and target, and the trajectory between target and target. The agent bidding transformation mechanism solves the resource waste caused by the premature contracting of dominant agent, and the time of the agents to complete all tasks is reduced by 6.54%. However, when dealing with the dominant agent problem, the new mechanism will increase the bidding rounds of the entire task allocation.

Key words: multi-agent system, task allocation, path planning, improved contract net algorithm

中图分类号:

TB114.1

王义涛, 王俊森, 石章松, 徐慧慧, 朱伟明. 基于改进快速搜索树和合同网的多智能体目标分配算法[J]. 兵工学报, 2025, 46(5): 240743-.

WANG Yitao, WANG Junsen, SHI Zhangsong, XU Huihui, ZHU Weiming. Task Allocation for Multi-agent System Based on Extended Rapidly-exploring Random Tree and Contract Net[J]. Acta Armamentarii, 2025, 46(5): 240743-.

图/表 24

图1 RRT算法(上)与ERRT算法(下)对比

Fig.1 Comparison of RRT algorithm(upper) and ERRT algorithm(below)

图2 智能体投标状态转换示意图

Fig.2 Agent bidding transformation

图3 改进智能体投标状态转换示意图

Fig.3 Improved agent bidding transformation

图4 本文算法流程图

Fig.4 Flow chart of the proposed algorithm

图5 场景DEM数据

Fig.5 DEM of test scene

图6 三维场景设置

Fig.6 3-D test scene

表1 智能体信息

Table 1 Information of agents

智能体	位置/ km	速度/ (m·s^-1)	任务序列
A1	(1,1,1.68)	150	[6,3,7,8,5,1,2,4,9,10]
A2	(1,10.0,1.49)	150	[6,3,7,8,5,1,2,4,9,10]
A3	(1,20.0,2.95)	150	[6,3,7,8,5,1,2,4,9,10]
A4	(1,30.0,2.5)	150	[6,3,7,8,5,1,2,4,9,10]
A5	(1,40.0,1.26)	150	[6,3,7,8,5,1,2,4,9,10]

图7 智能体与目标位置示意图

Fig.7 Positions of agents and targets

图8 航迹代价与均值示意图

Fig.8 Track costs and average

图9 ERRT算法计算智能体与目标点的航迹代价

Fig.9 Track costs of agents and targets calculated by ERRT algorithm

图10 ERRT算法计算智能体在目标点转移的航迹代价

Fig.10 Track costs of targets calculated by ERRT algorithm

表2 目标任务信息

Table 2 Information of tasks

任务编号	位置/km	任务编号	位置/km
T1	(12.3,35.8,1.65)	T6	(23.1,20.0,4.86)
T2	(24.0,36.7,2.31)	T7	(37.9,15.9,2.73)
T3	(20.8,28.8,2.22)	T8	(36.8,8.6,3.80)
T4	(35.1,32.2,2.62)	T9	(32.9,13.5,4.94)
T5	(37.0,26.1,2.21)	T10	(27.5,9.7,2.83)

图11 智能体与目标点欧氏距离

Fig.11 Euclidean distances among agents and targets

图12 目标点之间的欧氏距离

Fig.12 Euclidean distances between targets

表3 目标打击代价

Table 3 Target strike cost

T1	T2	T3	T4	T5	T6	T7	T8	T9	T10
0.847	0.717	0.867	0.887	0.820	0.368	0.608	0.779	0.894	0.905

表4 任务分配对比

Table 4 Comparision of task allocations

任务	方案1	方案2	任务	方案1	方案2
T1	A5	A4	T6	A3	A2
T2	A5	A4	T7	A2	A1
T3	A4	A4	T8	A1	A3
T4	A5	A5	T9	A1	A1
T5	A4	A5	T10	A1	A1

表5 智能体投标结果

Table 5 Bidding results of agents

任务	签约智能体	签约时投标轮次	任务	签约智能体	签约时投标轮次
T1	A4	3	T6	A2	2
T2	A4	3	T7	A1	4
T3	A4	3	T8	A3	5
T4	A5	4	T9	A1	5
T5	A5	4	T10	A1	5

表6 智能体任务负载

Table 6 Task loads of agents

智能体	执行任务的总航迹代价/km	智能体	执行任务的总航迹代价/km
A1	70.4	A4	65.16
A2	34.74	A5	63.8
A3	59.04

表7 智能体投标值

Table 7 Bidding values of agents

智能体	T1	T2	T3	T4	T5	T6	T7	T8	T9	T10
A1	188	203	54	219	143	41	91	101	256	265
A2	183	197	49	213	138	35	86	95	251	260
A3	195	210	61	226	150	48	98	108	263	272
A4	184	198	50	214	139	36	87	96	252	261
A5	190	204	56	220	145	42	93	102	258	267

表8 智能体投标结果

Table 8 Bidding results of agents

任务	签约智能体	签约时投标轮次	任务	签约智能体	签约时投标轮次
T1	A4	3	T6	A2	2
T2	A4	3	T7	A1	4
T3	A4	3	T8	A2	7
T4	A5	4	T9	A3	8
T5	A5	4	T10	A3	8

表9 智能体任务负载

Table 9 Task loads of agents

智能体	任务负载/km	智能体	任务负载/km
A1	54.76	A4	65.16
A2	59.62	A5	63.8
A3	65.79

图13 智能体任务负载对比

Fig.13 Comparison of agents’ task loads

表10 任务序列

Table 10 Task sequence

智能体	任务序列
A1	[6,3,7,8,5,1,2,4,9,10]
A2	[10,3,1,9,5,8,6,7,2,4]
A3	[3,6,5,7,4,8,9,1,10,2]
A4	[2,7,10,9,6,5,4,1,3,8]
A5	[9,5,8,3,10,4,1,2,5,6]

表11 任务分配对比

Table 11 Comparision of task allocations

任务	方案3	方案4	任务	方案3	方案4
T1	A4	A4	T6	A1	A1
T2	A4	A4	T7	A1	A1
T3	A2	A2	T8	A5	A5
T4	A3	A3	T9	A5	A5
T5	A1	A1	T10	A2	A2

参考文献 26

[1]	孙海文, 于邵祯, 江源, 等. 海上无人机蜂群目标威胁评估方法[J]. 兵工学报, 2022, 43(增刊2):32-39.
	SUN H W, YU S Z, JIANG Y, et al. Target threat assessment method for UAV swarm at sea[J]. Acta Armamentarii, 2022, 43(S2): 32-39. (in Chinese) doi: 10.12382/bgxb.2022.B006
[2]	邱志明, 孟祥尧, 马焱, 等. 海上无人系统跨域协同运用与技术发展[J]. 水下无人系统学报, 2024, 32(2):184-193.
	QIU Z M, MENG X R, MA Y, et al. Cross-domain collaborative application and technology development of maritime unmanned systems[J]. Journal of Unmanned Undersea Systems, 2024, 32(2): 184-193. (in Chinese)
[3]	唐苏妍, 朱一凡, 李群, 等. 多Agent系统任务分配方法综述[J]. 系统工程与电子技术, 2010, 32(10):2155-2161.
	TANG S Y, ZHU Y F, LI Q, et al. Survey of task allocation in multi agent systems[J]. Systems Engineering and Electronics, 2010, 32(10): 2155-2161. (in Chinese) doi: 10.3969/j.issn.1001-506X.2010.10.30
[4]	齐小刚, 李博, 范英盛, 等. 多约束下多无人机的任务规划研究综述[J]. 智能系统学报, 2020, 15(2):204-217.
	QI X G, LI B, FAN 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. (in Chinese)
[5]	马婵. 多无人机任务分配与航迹规划协同方法研究[D]. 石家庄: 河北科技大学, 2023.
	MA C. Research on cooperative method of multi-UAV task assignment and path planning[D]. Shijiazhuang: School of Electrical Engineering, 2023. (in Chinese)
[13]	RENNA P. Deteriorating job scheduling problem in a job-shop manufacturing system by multi-agent system[J/OL]. International Journal of Computer Integrated Manufacturing, 2015, 28(9): 936-945.
[14]	CARPANZANO E, CESTA A, ORLANDINI A, et al. Design and implementation of a distributed part-routing algorithm for reconfigurable transportation systems[J/OL]. International Journal of Computer Integrated Manufacturing, 2016, 29(12): 1317-1334.
[15]	万路军, 姚佩阳, 周翔翔, 等. 有人/无人作战智能体分布式协同目标分配方法[J]. 系统工程与电子技术, 2014, 36(2):278-287.
	WAN L J, YAO P Y, ZHOU X X, et al. Distributed cooperative target assignment method of maned combat agents and unmanned combat agents[J]. Systems Engineering and Electronics, 2014, 36(2): 278-287. (in Chinese)
[16]	张梦颖, 王蒙一, 王晓东, 等. 基于改进合同网的无人机群协同实时任务分配问题研究[J]. 航空兵器, 2019, 26(4):38-46.
	ZHANG M Y, WANG M Y, WANG X D, et al. Cooperative real-time task assignment of UAV group based on improved contract net[J]. Aero Weaponry, 2019, 26(4): 38-46. (in Chinese)
[17]	王强, 贾强. 基于改进合同网的多无人机动态任务分配[J/OL]. 火炮发射与控制学报, 2023. https://doi.org/10.19323/j.issn.1673-6524.202304010.
	WANG Q, JIA Q. A Multi-UAV dynamic task allocation method based on improved contract net protocol[J/OL]. Journal of Gun Launch & Control, 2023. https://doi.org/10.19323/j.issn.1673-6524.202304010. (in Chinese)
[18]	唐安如. 无人机航迹规划与任务分配方法研究[D]. 无锡: 江南大学, 2023.
	TANG A R. Research on UAV trajectory planning and Mission assignment methods[D]. Wuxi: Jiangnan University, 2023. (in Chinese)
[19]	赵明. 多无人机系统的协同目标分配和航迹规划方法研究[D]. 哈尔滨: 哈尔滨工业大学, 2016.
[6]	周晶, 赵晓哲, 许震, 等. 基于D-NSGA-Ⅲ算法的无人机群高维多目标任务分配方法[J]. 系统工程与电子技术, 2021, 43(5):1240-1247. doi: 10.12305/j.issn.1001-506X.2021.05.11
	ZHOU J, ZHAO X J, XU Z, et al. Many-objective task allocation method based on D-NSGA-Ⅲ algorithm for multi-UAVs[J]. Systems Engineering and Electronics, 2021, 43(5): 1240-1247. (in Chinese) doi: 10.12305/j.issn.1001-506X.2021.05.11
[7]	侯鹏, 葛玉雪, 裴扬, 等. 基于毁伤评估结果的无人机对地攻击任务分配方法[J]. 兵工学报, 2025, 46(2):240212. doi: 10.12382/bgxb.2024.0212
	HOU P, GE Y X, PEI Y, et al. UAV ground attack task assignment method based on damage assessment results[J]. Acta Armamentarii, 2025, 46(2):240212. (in Chinese)
[8]	薛雅丽, 李寒雁, 欧阳权, 等. 战场环境下遗传黏菌算法的多机协同任务分配[J]. 浙江大学学报(工学版), 2024, 58(8):1748-1756.
	XUE Y L, LI H Y, OUYANG Q, et al. Multi-UAVs collaborative task allocation based on genetic slime mould algorithm in battlefield environment[J]. Journal of Zhejiang University (Engineering Science), 2024, 58(8): 1748-1756. (in Chinese)
[9]	胡月. 有人/无人机协同作战任务分配与航迹规划研究[D]. 南京: 南京航空航天大学, 2020.
	HU Y. Research on mission assignment and flight path planning of panned/unmanned aerial vehicles cooperative operations[D]. Nanjing: Nanjing University of Aeronautics and Astronautics, 2020. (in Chinese)
[10]	YAO W R, QI N M, LIU Y F. Online trajectory generation with rendezvous for UAVs using multistage path prediction[J]. Journal of Aerospace Engineering, 2017, 30(3):04016092.
[11]	SMITH R G. The contract net protocol: high-level communication and control in a distributed problem solver[J]. IEEE Transactions on Computers, 1980, 29(12): 1104-1113.
[12]	BARENJI A V, BARENJI R V, ROUDI D, et al. A dynamic multi-agent-based scheduling approach for SMEs[J/OL]. The International Journal of Advanced Manufacturing Technology, 2017, 89(9): 3123-3137.
[19]	ZHAO M. Research on cooperative assignment and path planning for multi-unmanned aircraft system[D].Harbin: Harbin Institute of Technology, 2016. (in Chinese)
[20]	霍凤财, 迟金, 黄梓健, 等. 移动机器人路径规划算法综述[J]. 吉林大学学报(信息科学版), 2018, 36(6):639-647.
	HUO F C, CHI J, HUANG Z J, et al. Review of path planning for mobile robots[J]. Journal of Jilin University(Information Science Edition), 2018, 36(6): 639-647. (in Chinese)
[21]	KARUR K, SHARMA N, DHARMATTI C, et al. A survey of path planning algorithms for mobile robots[J]. Vehicles, 2021, 3(3):448-468.
[22]	BRUCE J, VELOSO M. Real-time randomized path planning for robot navigation[C]// Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems. Lausanne, Switzerland: IEEE,2002: 2383-2388.
[23]	WANG Z, BOVIK A C, RSHEIKH H, et al. Image quality assessment: from error visibility to structural similarity[J]. IEEE Transactions on Image Processing, 2004, 13(4): 600-612. doi: 10.1109/tip.2003.819861 pmid: 15376593
[24]	刘跃峰, 张安. 有人机/无人机编队协同任务分配方法[J]. 系统工程与电子技术, 2010, 32(3):584-588.
	LIU Y F, ZHANG A. Cooperative task assignment method of manned/unmanned aerial vehicle formation[J]. Systems Engineering and Electronics, 2010, 32(3): 584-588. (in Chinese)
[25]	邓启波. 多无人机协同任务规划技术研究[D]. 北京: 北京理工大学, 2014.
	DENG Q B. Cooperative task planning of multiple unmanned aerial vehicles[D]. Beijing: Beijing Institute of Technology, 2014. (in Chinese)
[26]	LUO L Z, CHAKRABORTY N, SYCARA K. Competitive analysis of repeated greedy Auction algorithm for online multi-robot task assignment[C]// Proceedings of 2012 IEEE International Conference on Robotics and Automation. Saint Paul,MN, US:IEEE,2012:14-18.