Publication

A. Pertzovsky, R. Stern and R. Zivan. CGA: Corridor Generating Algorithm for Multi-Agent Environments. In IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 3455-3462, 2024.

Abstract: In this paper, we solve the classical Multi-agent Pathfinding (MAPF) problem. Existing approaches struggle to solve dense MAPF instances. In this paper, we propose a Corridor Generating Algorithm for MAPF, namely CGA-MAPF. In CGA-MAPF, the agents build corridors, a set of connected vertices, from current locations towards agents' goals and evacuate other agents out of the corridors to avoid collisions and deadlocks. The proposed algorithm has a reachability property, i.e. every agent is guaranteed to reach its goal location at some point. In the experimental section, we demonstrate that CGA-MAPF outperforms baseline algorithms in terms of success rate across diverse MAPF benchmark grids, achieving state-of-the-art performance.

Download the paper in pdf.