GPU-accelerated Conflict-based Search for Multi-agent Embodied Intelligence

Embodied intelligence applications, such as autonomous robotics and smart transportation systems, require efficient coordination of multiple agents in dynamic environments. A critical challenge in this domain is the multi-agent pathfinding (MAPF) problem, which ensures that agents can navigate conflict-free while optimizing their paths. Conflict-based search (CBS) is a well-established two-level solver for the MAPF problem. However, as the scale of the problem expands, the computation time becomes a significant challenge for the implementation of CBS. Previous optimizations have mainly focused on reducing the number of nodes explored by the high-level or low-level solver. This paper takes a different perspective by proposing a parallel version of CBS, namely GPU-accelerated conflict-based search (GACBS), which significantly exploits the parallel computing capabilities of GPU. GACBS employs a task coordination framework to enable collaboration between the high-level and low-level solvers with lightweight synchronous operations. Moreover, GACBS leverages a parallel low-level solver, called GATSA, to efficiently find the shortest path for a single agent under constraints. Experimental results show that the proposed GACBS significantly outperforms CPU-based CBS, with the maximum speedup ratio reaching over 46.