A review of graph-based multi-agent pathfinding solvers: From classical to classical

被引:3
作者
Gao, Jianqi [1 ]
Li, Yanjie [1 ]
Li, Xinyi [1 ]
Yan, Kejian [1 ]
Lin, Ke [1 ]
Wu, Xinyu [2 ]
机构
[1] Harbin Inst Technol Shenzhen, Dept Control Sci & Engn, Shenzhen 518055, Peoples R China
[2] Chinese Acad Sci, Shenzhen Inst Adv Technol, Shenzhen, Peoples R China
关键词
Multi-agent systems; Multi-agent pathfinding; Collision avoidance; Scheduling and coordination; PATH; REINFORCEMENT; SEARCH; MOTION; EXPLORATION; OPTIMIZATION; NETWORKS;
D O I
10.1016/j.knosys.2023.111121
中图分类号
TP18 [人工智能理论];
学科分类号
081104 ; 0812 ; 0835 ; 1405 ;
摘要
Multi -agent pathfinding (MAPF) is a well -studied abstract model for navigation in a multi -robot system, where every robot finds the path to its goal position without any collision. Due to its numerous practical applications of multi -robot systems, MAPF has steadily emerged as a research hotspot. The optimal solution for MAPF is NP -hard. In this paper, we offer a comprehensive analysis of different MAPF solvers. First, we review the cutting -edge solvers of classical MAPF, including optimal, bounded sub -optimal, and unbounded sub -optimal. The performance of some representative classical MAPF solvers is quantitatively compared. In the next part, we summarize the beyond classical MAPF solvers, which try to use the classical MAPF solvers in real -world scenarios. Last, we conclude some challenges that MAPF is experiencing in detail, review recent research on these issues, and make some suggestions for further work.
引用
收藏
页数:19
相关论文
共 176 条
  • [91] Visuomotor Reinforcement Learning for Multirobot Cooperative Navigation
    Liu, Zhe
    Liu, Qiming
    Tang, Ling
    Jin, Kefan
    Wang, Hongye
    Liu, Ming
    Wang, Hesheng
    [J]. IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2022, 19 (04) : 3234 - 3245
  • [92] Prediction, Planning, and Coordination of Thousand-Warehousing-Robot Networks With Motion and Communication Uncertainties
    Liu, Zhe
    Wang, Hesheng
    Wei, Huanshu
    Liu, Ming
    Liu, Yun-Hui
    [J]. IEEE TRANSACTIONS ON AUTOMATION SCIENCE AND ENGINEERING, 2021, 18 (04) : 1705 - 1717
  • [93] MAPPER: Multi-Agent Path Planning with Evolutionary Reinforcement Learning in Mixed Dynamic Environments
    Liu, Zuxin
    Chen, Baiming
    Zhou, Hongyi
    Koushik, Guru
    Hebert, Martial
    Zhao, Ding
    [J]. 2020 IEEE/RSJ INTERNATIONAL CONFERENCE ON INTELLIGENT ROBOTS AND SYSTEMS (IROS), 2020, : 11748 - 11754
  • [94] Lowe R, 2017, ADV NEUR IN, V30
  • [95] Luna R., 2011, IJCAI, P294, DOI DOI 10.5591/978-1-57735-516-8/IJCAI11-059
  • [96] Ma H, 2019, AAAI CONF ARTIF INTE, P7651
  • [97] Ma H, 2016, Arxiv, DOI arXiv:1612.05693
  • [98] Ma H, 2017, Arxiv, DOI arXiv:1702.05515
  • [99] Ma H, 2019, AAAI CONF ARTIF INTE, P7643
  • [100] Ma H, 2018, PROCEEDINGS OF THE TWENTY-SEVENTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, P417