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 mult...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.展开更多
文摘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.
