启发式搜索的多智能体异速轨迹规划

doi:10.3778/j.issn.1002-8331.2308-0085

摘要/Abstract

摘要： 在多智能体系统研究中，多智能体路径规划（multi-agent path finding，MAPF）是一个核心难题，其目标是为各个智能体规定独立路径，确保智能体在移动过程中不发生碰撞。这是一个NP难题，亟须高效解决算法。创新性地提出了一种多智能体路径规划算法——启发式导向冲突搜索（heuristic guided conflict-based search，HG-CBS），以解决复杂的MAPF场景，如智能体移动速度不同或各条边的道路长度不同。为优化HG-CBS算法，构建了三种独特的启发式计算方法：（1）加权求和法，以所有启发式的加权总和作为最终启发式；（2）帕累托集合法，构建一个帕累托集并从中选择节点；（3）交替法，在搜索迭代过程中交替使用各种启发式。实验结果显示，相比于传统方法，带有启发值的HG-CBS在成功率、运行时间及扩展节点数量等关键性能指标上均表现更优。例如，在包含16个智能体的复杂场景下，HG-CBS-h3（交替法）将运行时间缩短了89%，将拓展节点的数目减少了95%。此外，随着场景复杂度的提升，HG-CBS-h3的性能优势更加明显。这些结果证明了HG-CBS算法的有效性和高效性，对多智能体轨迹规划问题具有显著的理论和应用价值。

关键词: 多智能体路径规划, 启发式导向冲突搜索, 启发式搜索, 帕累托集

Abstract: Multi-agent path finding (MAPF) is a core challenge in multi-agent systems research, aiming to assign independent paths to each agent to avoid collisions during movement. As an NP-hard problem, it is highly sought after to develop efficient algorithms. This paper proposes an innovative multi-agent path planning algorithm called heuristic guided conflict-based search (HG-CBS), designed to address complex MAPF scenarios such as heterogeneous agent speeds and varying edge lengths. To optimize HG-CBS, the paper develops three unique heuristic computation methods: (1) weighted sum method, using the weighted sum of all heuristics as the final heuristic; (2) Pareto set method, constructing a Pareto set and selecting nodes from it; (3) alternating method, alternating between various heuristics during search iterations. Experimental results demonstrate that HG-CBS with heuristics outperforms conventional methods in terms of success rate, runtime, and number of expanded nodes. For instance, in a complex scenario with 16 agents, HG-CBS-h3 (alternating method) reduces the runtime by 89% and the number of expanded nodes by 95%. Moreover, the performance advantage of HG-CBS-h3 becomes even more prominent as the complexity of the scenario increases. These findings validate the effectiveness and efficiency of the HG-CBS algorithm, highlighting its significant theoretical and practical implications for multi-agent trajectory planning.

Key words: multi-agent path finding, heuristic guided conflict-based search, heuristic search, Pareto set

鲁宇, 匡金骏, 肖峣, 龚建伟. 启发式搜索的多智能体异速轨迹规划[J]. 计算机工程与应用, 2025, 61(2): 344-354.

LU Yu, KUANG Jinjun, XIAO Yao, GONG Jianwei. Heuristic Search-Based Multi-Agent Heterogeneous Speed Path Planning[J]. Computer Engineering and Applications, 2025, 61(2): 344-354.

参考文献

[1] SILVER D, VENESS J. Monte-Carlo planning in large POMDPs[C]//Proceedings of the 23rd International Conference on Neural Information Processing Systems, 2010: 2164-2172.
[2] MA H, LI J, KUMAR T K S, et al. Lifelong multi-agent path finding in large-scale warehouses[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2021: 1898-1900.
[3] LI J, HARABOR D, STUCKEY P J, et al. Symmetry-breaking constraints for grid-based multi-agent path finding[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2019: 6087-6095.
[4] ?áP M, NOVáK P, KLEINER A, et al. Prioritized planning algorithms for trajectory coordination of multiple mobile robots[J]. IEEE Transactions on Automation Science and Engineering, 2015, 12(3): 835-849.
[5] PAIKRAY H K, DAS P K, PANDA S. Optimal multi-robot path planning using particle swarm optimization algorithm improved by sine and cosine algorithms[J]. Arabian Journal for Science and Engineering, 2021, 46: 3357-3381.
[6] LI W, CHEN H, JIN B, et al. Multi-agent path finding with prioritized communication learning[C]//Proceedings of the International Conference on Robotics, 2022.
[7] MA H. Graph-based multi-robot path finding and planning[J]. Current Robotics Reports, 2023, 3: 77-84.
[8] ERDEM D, ERDEM E, INCEOGLU M K. Search-based optimal solvers for the multi-agent pathfinding problem: summary and challenges[C]//Proceedings of the 10th International Symposium on Combinatorial Search, 2017: 29-37.
[9] PIANPAK, SON T C. DMAPF: a decentralized and distributed solver for multi-agent path finding problem with obstacles[J]. arXiv: 2109. 08288, 2021.
[10] 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 AAAI Conference on Artificial Intelligence, 2014: 961-962.
[11] HARABOR D, STUCKEY P J, GRASTIEN A. Conflict-based search with optimal task assignment[C]//Proceedings of the International Conference on Automated Planning and Scheduling, 2019: 757-765.
[12] LI Y, GAO J, LI X, et al. Multi-agent path finding with prioritized communication learning[J]. arXiv:2202.03634, 2022.
[13] MA H, LI J, STANDLEY T, et al. Multi-agent path finding with delay probabilities[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2020: 3605-3612.
[14] GAO J, LI Y, LI X, et al. A review of graph-based multi-agent path finding solvers: from classic to beyond classic [J]. Knowledge-Based Systems, 2023, 283: 111121.
[15] ANDREYCHUK A, YAKOVLEV K, BOYARSKI E, et al. Improving continuous-time conflict based search[C]//Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
[16] FELNER A, LI J, BOYARSKI E, et al. Adding heuristics to conflict-based search for multi-agent path finding[C]//Proceedings of the International Joint Conference on Artificial Intelligence, 2021.
[17] SHARON G, STERN R, FELNER A, et al. Conflict-based search for optimal multi-agent pathfinding[J]. Artificial Intelligence, 2021, 219: 40-66.
[18] HUANG T, KOENIG S, DILKINA B. Learning to resolve conflicts for multi-agent path finding with conflict-based search[J]. arXiv: 2012. 06005, 2021.
[19] JIANG H, ZHANG Y, VEERAPANENI R, et al. Scaling lifelong multi-agent path finding to more realistic settings: research challenges and opportunities[J]. arXiv:2404.16162,2024.
[20] LI J, HARABOR D, STUCKEY P J. Adaptive anytime multi-agent path finding using bandit-based large neighborhood search[J]. arXiv:2312.16767, 2023.
[21] TANG Y, KOENIG S, LI J. ITA-ECBS: a bounded-suboptimal algorithm for the combined target-assignment and path-finding problem[J]. arXiv:2404.05223, 2024.
[22] ZHANG L, KOENIG S. Scalable mechanism design for multi-agent path finding[C]//Proceedings of the International Conference on Artificial Intelligence, 2024: 58-66.