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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Suboptimality Conflict-Aware ECBS for Multi-Agent Path Finding

  • Honglei Shao,
  • Jinhua Wu,
  • Fangyan Dong

摘要

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.