Research of the Methods on Multi-Agent Path Finding
DOI:
https://doi.org/10.54097/hset.v39i.6719Keywords:
Multi-Agent Path Finding; Classical Algorithms; Machine Learning.Abstract
Multi-Agent Path Finding is an essential real-life application of multi-intelligent systems for which scholars have solved many classical solutions. And with the evolution of theories related to machine learning, intelligent solutions are emerging daily. However, these algorithms have not been well summarized and concluded, and are comparatively difficult to consult. This essay's objective is to offer a thorough analysis of these issues. The paper will start with Path Finding and describe its three categories of classical algorithms. And then it will focus on the centralized planning algorithms based on the classical algorithms, and the distributed execution algorithms based on machine learning, and provide a theoretical explanation and comparison of their effectiveness. Finally, a prospection and outlook on the currently unresolved issues in the Multi-Agent Path Finding research area, including unification standards and directions for improvement, will be presented.
Downloads
References
Liu Qingzhou, WU Feng. Research progress of multi-agent path planning. Computer Engineering, 2020,46(4):1-10.
Yan J J, Zhang Q S, Hu X P. Review of path planning techniques based on reinforcement learning. Computer Engineering, 2021, 47(10):16-25.
Sternr, Sturtevantnr, et al. multi-agent pathfinding: definitions, variants, and benchmarks, Twelfth Annual Symposium on Combinatorial Search, 2019: 121-132.
Sharon G, Stern R, Goldenberg M, et al. The increasing cost tree search for optimal multi-agent pathfinding, Artificial Intelligence, 2013, 195: 470-495.
Surynek P. Towards optimal cooperative path planning in hard setups through satisfiability solving, Proceedings of the Pacific Rim International Conferences on Artificial Intelligence. Washington D. C, USA: IEEE Press, 2012:564-576.
Ryan M. Constraint-based multi-robot path planning, Proceedings of International Conference on Robotics and Automation. Washington D. C., 2010:38-54.
Shu Xiangxiang. Research on optimal path planning of multi robots. China Computer and Communication, 2017 (15):62-64.
Spiralris D K. Coordinating pebble motion on graphs, the diameter of permutation groups, and applications, https://www.computer.org/csdl/proceedings-article/focs/1984/0715921/12OmNC3FGi5.
Niu Pengfei, Wang Xiaofeng. Survey on Vehicle Reinforcement Learning in Routing Problem. College of Computer Science and Engineering, North Minzu University, 2022,58(01):41-55.
Kool W, Van Hoof H, et al. Deep policy dynamic programming for vehicle routing problems. arXiv: 2102. 11756,2021.
Goodson J C, Ohleman J W. Rollout policies for dynamic solutions to the multivehicle routing problem with stochastic demand and duration limits. Operations Research, 2013, 61 (1) :138-154.
Zhang C, Delart N P, Zhao L, et al. Single vehicle routing with stochastic demands: approximate dynamic programming. Eindhoven: Technishe Universiteit Eindhoven, 2013.
Sartoretti G, Kerr J, Shi Y, et al. Primal: path finding via reinforcement and imitation multi-agent learning. IEEE Robotics & Automation Letters, 2019, 4(3):2378-2385.
Ma Z, Luo Y, Pan J. Learning selective communication for multi-agent path finding. arXiv: 2109. 05413, 2021.
Skrynnik A, Yakovleva A, Davtdov V, et al. Hybrid policy learning for multi-agent pathfinding. IEEE Access, 2021, 9: 126034-126047.
Liu Z, Chen B, Zhou H, et al. Mapper: multi-agent path planning with evolutionary reinforcement learning inmixed dynamic environments, 2020 IEEE/RSJ International Conference on Intelligent Robots and Systems, 2020: 11748-11754.
Rivre B, Hongig G W, Yue Y, et al. Glas: global-to-local safe autonomy synthesis for multi- robot motion planning with end-to-end learning. IEEE Robotics and Automation Letters, 2020,5(3):4249-4256.
I Q, Lin W, Liu Z, et al. Message-aware graph attention networks for large-scale multi-robot path planning. IEEE Robotics and Automation Letters, 2021,6(3):5533-5540.
Skrynnik A, Yakovlva et al. Hybrid policy learning for multi-agent pathfinding, IEEE Access, 2021, 9: 126034-126047.
Ngb, Liu Z, Li Q, et al. Mobile robot path planning in dynamic environments through globally guided reinforcement learning. IEEE Robotics and Automation Letters,2020,5(4):6932-6939.
Iu Z, Liu Q, Tang L, et al. Visuomotor reinforcement learning for multirobot cooperative navigation. IEEE Transactions on Automation Science and Engineering, 2021:1-12.
Downloads
Published
Issue
Section
License
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
How to Cite
