An Efficient Conflict-Free Scheduling Algorithm for Large-Space Multi-Agent Pathfinding Problem in Multi-Robot Systems

The conflict-free scheduling of multi-robot systems in large-space layouts remains a significant challenge due to the exponential growth of computational complexity, frequent conflicts, and resource-intensive path re-planning. Traditional approaches, such as the global A* search, often fail to balance scheduling efficiency, system efficiency, and system security when robots operate across multiple fire areas. A mathematical model for the large-space multi-agent pathfinding (MAPF) is presented, which aims to minimize the total completion time, scheduling time, and the number of stop-starts. An efficient conflict-free scheduling algorithm (ECSA) with cheaper computational complexity is proposed. The experimental results demonstrate that, compared with the traditional approach, the proposed approach can decrease the total completion time by 8.63%–22.92%, the scheduling time by 53.30%–69.64%, and the number of stop-starts by 44.33%–49.88%, when the number of robots ranges from 60 to 220 for large-space MAPF. Furthermore, the algorithm is adaptable to various area settings. Compared to area setups based on existing experience data, the proposed area setting further reduces the total completion time by 3.05%–4.81%, the scheduling time by 8.63%–21.42%, and the number of stop-starts by 40.25%–48.23%, when the number of robots ranges from 100 to 180. This work provides a computationally efficient solution for large-space multi-robot systems, significantly enhancing system efficiency, scheduling efficiency, and system security.