Multi-Agent Corridor Generating Algorithm

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.

Authors

• Arseni Pertzovskiy Ben-Gurion University of the Negev
• Roni Stern
• Roie Zivan Ben-Gurion University
• Ariel Felner Ben-Gurion University of the Negev

Keywords

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