AAECBS: an enhanced large-scale multiagent pathfinding suboptimal algorithm based on ECBS

Multi-agent pathfinding aims to find a set of optimal paths for multiple agents to reach their respective destinations without colliding with each other. Conflict-Based Search (CBS) is an algorithm that prioritizes conflict resolution, utilizing a two-level search framework to find optimal solutions. However, its performance significantly deteriorates as the number of agents increases. Various enhancements have been proposed, such as Enhanced CBS (ECBS), which introduces focused search in its two-level framework, resulting in a notable speed improvement. In this paper, we propose improvements to the bottom-level solving framework of ECBS, by designing a bottom-level two-level A* solving method and enhancing the heuristic function of the bottom level algorithm. These enhancements greatly reduce the computation time of the bottom-level algorithm and are applicable to most map instances, allowing for faster solution generation. Experimental results show that the improved AAECBS algorithm maintains a significantly faster speed compared to ECBS while incurring only minimal quality loss, with experimental results indicating a maximum loss of no more than 5%, and sometimes no loss in quality. In numerous experiments varying the suboptimality factor, changing maps, and adjusting the number of agents, AAECBS consistently outperforms ECBS in terms of speed.