Multi-Agent Corridor Generating Algorithm

Pertzovskiy, Arseni; Stern, Roni; Zivan, Roie; Felner, Ariel

doi:10.24963/ijcai.2025/28

Multi-Agent Corridor Generating Algorithm

Arseni Pertzovskiy, Roni Stern, Roie Zivan, Ariel Felner

Download BibTeX Cite

Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 240-247.

https://doi.org/10.24963/ijcai.2025/28

Keywords

Robotics: ROB: Multi-robot systems
Planning and Scheduling: PS: Distributed and multi-agent planning
Search: S: Heuristic search
Agent-based and Multi-agent Systems: MAS: Multi-agent planning

Abstract

In this paper, we propose the Multi-Agent Corridor Generating Algorithm (MACGA) for solving the Multi-agent Pathfinding (MAPF) problem, where a group of agents need to find non-colliding paths to their target locations. Existing approaches struggle to solve dense MAPF instances. In MACGA, the agents build corridors, which are sequences of connected vertices, from current locations towards agents' goals, and evacuate other agents out of the corridors to avoid collisions and deadlocks. We also present the MACGA+PIBT algorithm, which integrates the well-known rule-based PIBT algorithm into MACGA to improve runtime and solution quality. The proposed algorithms run in polynomial time and have a reachability property, i.e., every agent is guaranteed to reach its goal location at some point. We demonstrate experimentally that MACGA and MACGA+PIBT outperform baseline algorithms in terms of success rate, runtime, and makespan across diverse MAPF benchmark grids.

Arseni Pertzovskiy, Roni Stern, Roie Zivan, and Ariel Felner. 2025. Multi-Agent Corridor Generating Algorithm. In Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25. IJCAI, 240–247. https://doi.org/10.24963/ijcai.2025/28

@inproceedings{ijcai2025p28,
  title     = {Multi-Agent Corridor Generating Algorithm},
  author    = {Pertzovskiy, Arseni and Stern, Roni and Zivan, Roie and Felner, Ariel},
  booktitle = {Proceedings of the Thirty-Fourth International Joint Conference on
               Artificial Intelligence, {IJCAI-25}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {James Kwok},
  pages     = {240--247},
  year      = {2025},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2025/28},
  url       = {https://doi.org/10.24963/ijcai.2025/28},
}

TY  - CPAPER
TI  - Multi-Agent Corridor Generating Algorithm
AU  - Pertzovskiy, Arseni
AU  - Stern, Roni
AU  - Zivan, Roie
AU  - Felner, Ariel
T2  - Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-25
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2025
SP  - 240
EP  - 247
DO  - 10.24963/ijcai.2025/28
UR  - https://doi.org/10.24963/ijcai.2025/28
ER  -