Multi-goal multi-agent path finding algorithm

doi:10.3785/j.issn.1008-973X.2025.08.016

Journal of ZheJiang University (Engineering Science)

2025, Vol. 59

Issue (8): 1689-1697 DOI: 10.3785/j.issn.1008-973X.2025.08.016

Multi-goal multi-agent path finding algorithm

Jing ZHANG(

),Yi WANG,Zilong CHEN,Yunsong LI

State Key Laboratory of Integrated Services Networks, Xidian University, Xi’an 710071, China

Download:

HTML

PDF(1143KB) HTML
Export: BibTeX | EndNote (RIS)

Abstract

A multi-goal multi-agent path planning algorithm was proposed to realize the efficient assignment of tasks to each agent and plan the shortest possible paths for the agents without collision with other agents. The definition of conflict between agents in continuous time and the way of conflict resolution were defined, and the concepts of safety interval and labeling were introduced based on A* algorithm aiming at the problem of low success rate due to the use of discrete time in traditional path planning algorithms. Then the A* algorithm can plan optimal paths that satisfy continuous time constraints. A conflict hierarchical strategy was proposed to reduce the number of nodes extended in the algorithm solving process aiming at the large amount of computation caused by collision detection and conflict avoidance in the multi-agent path planning problem. The experimental results show that the proposed algorithm can solve a better solution and has better applicability, with lower total path cost and higher success rate in the scenario of densely distributed agents.

Key words： multi-agent system path finding task assignment improved A* algorithm conflict search

Received: 20 May 2024 Published: 28 July 2025

CLC:

TP 242

Fund: 国家自然科学基金资助项目 (62371362).

	Service
	E-mail this article
	Add to my bookshelf
	Add to citation manager
	E-mail Alert
	RSS
	Articles by authors
	Jing ZHANG
	Yi WANG
	Zilong CHEN
	Yunsong LI

Cite this article:

Jing ZHANG,Yi WANG,Zilong CHEN,Yunsong LI. Multi-goal multi-agent path finding algorithm. Journal of ZheJiang University (Engineering Science), 2025, 59(8): 1689-1697.

URL:

https://www.zjujournals.com/eng/10.3785/j.issn.1008-973X.2025.08.016 OR https://www.zjujournals.com/eng/Y2025/V59/I8/1689

多目标多智能体路径规划方法

为了实现高效地将任务分配给每个智能体，为智能体规划出尽可能短且不与其他智能体发生碰撞的路径，提出多目标多智能体路径规划方法. 针对传统路径规划算法使用离散时间导致成功率低的问题，该算法定义连续时间下智能体间的冲突定义与解冲突方式，在A*算法的基础上引入安全间隔与标签的概念，使得A*算法可以规划出满足连续时间约束的最优路径. 针对多智能体路径规划问题中因碰撞检测、冲突避免造成的较大计算量，提出冲突分级策略，减少了算法求解过程中扩展的节点数量. 实验结果表明，利用所提出的算法能够求解得到更优的解决方案，且该算法具有更好的适用性；在智能体分布密集的场景下，该算法表现出更低的路径总成本和更高的求解成功率.

关键词： 多智能体系统, 路径规划, 任务分配, 改进A*算法, 冲突搜索

Fig.1 Basic flow of conflict-based search with optimal task assignment algorithm

Fig.2 Schematic diagram of edge conflict and vertex conflict in continuous time

Fig.3 Schematic diagram of random obstacle scenario and storage scenario

Fig.4 Success rate of algorithm solving in different scenario

Fig.5 Average total path cost in different scenario

Tab.1 Statistics on sum of average total path cost for different scenario

Tab.2 Statistics of average total cost of paths for proposed algorithm under different neighborhood size

Tab.3 Statistics of average solution time for different number of agents

Fig.6 Average number of expanded nodes and solution success rate of algorithm after introducing conflict hierarchy

Fig.7 Schematic diagram of TA-CBS algorithm solution

Fig.8 Schematic diagram of CBS-TA algorithm solution

Fig.9 Schematic diagram of proposed algorithm solution


[1]	BNAYA Z, FELNER A. Conflict-oriented windowed hierarchical cooperative A* [C]//IEEE International Conference on Robotics and Automation. New York: IEEE, 2014: 3743-3748.

[2]	WAGNER G, CHOSET H Subdimensional expansion for multirobot path planning[J]. Artificial Intelligence, 2015, 219 (2): 1- 24

[3]	SHARON G, STERN R, GOLDENBERG M, et al The increasing cost tree search for optimal multi-agent pathfinding[J]. Artificial Intelligence, 2013, 195 (2): 470- 495

[4]	SRINIVASAN A, HAM T, MALIK S, et al. Algorithms for discrete function manipulation [C]//IEEE International Conference on Computer-Aided Design. Washington, DC: IEEE, 1990: 92-95.

[5]	SHARON G, STERN R, FELNER A, et al Conflict-based search for optimal multi-agent pathfinding[J]. Artificial Intelligence, 2015, 219 (2): 40- 66

[6]	COHEN L, WAGNER G, CHAN D, et al. Rapid randomized restarts for multi-agent path finding solvers [C]// Proceedings of the International Symposium on Combinatorial Search. Richland: AAAI, 2018: 1909-1911.

[7]	BARER M, SHARON G, STERN R, et al. Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem [C]// Proceedings of the 21st European Conference on Artificial Intelligence. NLD: IOS Press, 2014: 961-962.

[8]	PEARL J, KIM J H Studies in semi-admissible heuristics[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1982, 4 (4): 392- 399

[9]	LI J, TINKA A, KIESEL S, et al. Lifelong multi-agent path finding in large-scale warehouses [C]// Proceedings of the AAAI Conference on Artificial Intelligence. Richland: AAAI, 2020: 1898-1900.

[10]	LI J, HOANG T A, LIN E, et al. Intersection coordination with priority-based search for autonomous vehicles [C]// Proceedings of the AAAI Conference on Artificial Intelligence. Palo Alto: AAAI Press, 2023: 11578-11585.

[11]	李家碧, 韩曙光考虑客户等级和时变路况的无人物流配送路径[J]. 浙江大学学报: 工学版, 2023, 57 (10): 2018- 2027 LI Jiabi, HAN Shuguang Unmanned logistics distribution route considering customer level and time-varying road conditions[J]. Journal of Zhejiang University: Engineering Science, 2023, 57 (10): 2018- 2027

[12]	杨京帅, 杨玉娥, 李嫚嫚, 等末端配送服务模式与路径联合优化[J]. 浙江大学学报: 工学版, 2023, 57 (5): 900- 910 YANG Jingshuai, YANG Yu’e, LI Manman, et al Joint optimization of terminal distribution service mode and distribution routing[J]. Journal of Zhejiang University: Engineering Science, 2023, 57 (5): 900- 910

[13]	靳佳澳, 沈洪垚, 孙扬帆, 等面向电弧增材的单线激光扫描路径规划[J]. 浙江大学学报: 工学版, 2023, 57 (1): 21- 31 JIN Jiaao, SHEN Hongyao, SUN Yangfan, et al Single-line laser scanning path planning for wire arc and additive manufacturing[J]. Journal of Zhejiang University: Engineering Science, 2023, 57 (1): 21- 31

[14]	ZHONG X, LI J, KOENIG S, et al. Optimal and bounded-suboptimal multi-goal task assignment and path finding [C]// International Conference on Robotics and Automation. New York: IEEE, 2022: 10731-10737.

[15]	STERN R. Multi-agent path finding: an overview [C]// 5th RAAI Summer School on Artificial Intelligence. Cham: Springer, 2019: 96-115.

[16]	HÖNIG W, KIESEL S, TINKA A, et al. Conflict-based search with optimal task assignment [C]// Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems. Richland: AAMAS, 2018: 757-765.

[17]	GUY S J, KARAMOUZAS I. Guide to anticipatory collision avoidance [M]// RABIN S. Game AI Pro 360: guide to movement and pathfinding. Boca Raton: CRC Press, 2019: 159-172.

[18]	LI J, TINKA A, KIESEL S, et al. Lifelong multi-agent path finding in large-scale warehouses [C]// Proceedings of the AAAI Conference on Artificial Intelligence. Palo Alto: AAAI Press, 2021: 11272-11281.

[19]	YU J, LAVALLE S M Optimal multirobot path planning on graphs: complete algorithms and effective heuristics[J]. IEEE Transactions on Robotics, 2016, 32 (5): 1163- 1177 doi: 10.1109/TRO.2016.2593448

[1]	Yu WANG,Chunrong MA,Mingyue ZHAO. Collaborative multi-task assignment of heterogeneous UAVs based on hybrid strategies based multi-objective particle swarm[J]. Journal of ZheJiang University (Engineering Science), 2025, 59(4): 821-831.

[2]	Yuting LIU,Shijie GUO,Shufeng TANG,Xuewei ZHANG,Tiantian LI. *Path planning based on fusion of improved A and ROA-DWA for robot**[J]. Journal of ZheJiang University (Engineering Science), 2024, 58(2): 360-369.

[3]	Hang-lei SHAO,Dong-mei ZHANG. Synchronization of multi-agent systems based on static output feedback protocol[J]. Journal of ZheJiang University (Engineering Science), 2020, 54(7): 1308-1315.

[4]	Xia-sheng SHI,Rong-hao ZHENG,Zhi-yun LIN,Gang-feng YAN. Saddle dynamic based distributed algorithm for economic dispatch problem[J]. Journal of ZheJiang University (Engineering Science), 2020, 54(4): 678-683.

[5]	AI Jie-qing, GAO Ji, PENG Yan-bin, ZHENG Zhi-jun. Negotiation decision model based on transductive support vector machine[J]. Journal of ZheJiang University (Engineering Science), 2012, 46(6): 967-973.

[6]	OU Li-Yong, DU Shu-Xin. Multi-agent based coordination of public detection resources[J]. Journal of ZheJiang University (Engineering Science), 2010, 44(1): 81-86+123.

[7]	HU Bin, GAO Ji, GUO Hang. Dynamic model of normative multi-agent system and its property verification mechanism[J]. Journal of ZheJiang University (Engineering Science), 2009, 43(6): 1014-1019.

[8]	ZHANG Bao-Jun, BO Xue-Ceng, WANG Jie-Bing, et al. Multi-agent based hybrid Intrusion detection system[J]. Journal of ZheJiang University (Engineering Science), 2009, 43(6): 987-993.

[9]	XU Ping, GAO Ji, GUO Hang. Reliable reputation computing based on double-layer reputation and feedback mechanism[J]. Journal of ZheJiang University (Engineering Science), 2009, 43(12): 2160-2164.

Viewed

Full text

Abstract

Cited

Shared

Discussed