Suboptimality Conflict-Aware ECBS for Multi-Agent Path Finding
摘要
With the rapid development of intelligent logistics and automated warehousing systems, the Multi-Agent Pathfinding (MAPF) problem has emerged as a critical technical challenge in urgent need of resolution. This paper proposes an enhanced suboptimal conflict-based search algorithm called Suboptimality Conflict-Aware ECBS (SC-ECBS) to improve path planning efficiency in dynamic multi-agent systems. Building upon the traditional ECBS framework, the algorithm introduces a conflict graph modeling mechanism to capture the structural characteristics of agent conflicts during the search process. Based on the topology and density of the conflict graph, it dynamically adjusts the suboptimality factor throughout the search. In addition, the algorithm prioritizes path conflicts according to the frequency of conflicts between agents, thereby resolving critical collisions more effectively and reducing overall computational overhead. This approach enhances search efficiency while maintaining solution quality. Experimental results on multiple standard MAPF benchmark maps demonstrate that SC-ECBS exhibits stronger adaptability and a more stable success rate decline in conflict-dense scenarios, and it shows superior scalability and robustness under high-complexity tasks.