Task Allocation for Multi-agent System Based on Extended Rapidly-exploring Random Tree and Contract Net

doi:10.12382/bgxb.2024.0743

Abstract

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

CLC Number:

TB114.1

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-.

Figures/Tables 24

References 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.

智能体	位置/ 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]

智能体	位置/ 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]

任务编号	位置/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)

任务编号	位置/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)

任务	方案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