In recent years, the field of embodied intelligence has witnessed significant advancements, with applications ranging from autonomous robotics and smart transportation systems to interactive gaming and virtual agents. These systems rely on the ability to perceive, reason, and act within complex environments, often involving multiple agents that must coordinate their actions to achieve shared goals. As the complexity and scale of these applications increase, the need for efficient coordination mechanisms becomes paramount. One critical challenge in this domain is the multi-agent pathfinding (MAPF) problem, which plays a vital role in ensuring that multiple agents can navigate their environments without conflict while optimizing their paths. The solver of the MAPF problem has been widely used in diverse applications, including aircraft towing vehicles, traffic management, mail sortation, and video games.
In practice, the calculation time is the most significant bottleneck in solving MAPF problems. Optimal solving of the MAPF problem has been proven to be NP-hard in many settings, including general graphs, planar graphs, and 2D grid graphs, implying that the calculation time will grow exponentially with an increasing number of agents. Excessively long calculation time is unacceptable in some practical applications. For example, if the calculation time of the path of the delivery robot in a warehouse is too long, the throughput rate of the logistics system will decrease, resulting in economic losses.
Conflict-based search (CBS) is a prevalent two-level solver for addressing the MAPF problem. The high-level solver constructs a constraint tree (CT) to assign time-space constraints for each agent to avoid collisions, and the low-level solver calculates a path under these constraints, including both the vertex constraints and edge constraints. Prior arts mainly enable efficient CBS by reducing the number of nodes explored by the high-level or low-level solver. Beyond the above techniques, to improve the efficiency of time-consuming algorithms, GPU-acceleration has been a promising approach in recent years. However, there has been no research exploring GPU-acceleration specifically for CBS computing. This paper takes a new perspective to improve the computational efficiency of CBS by significantly exploiting the parallel computing capabilities of the GPU.
The deployment of GPU acceleration for the CBS algorithm presents several challenges. First, the CBS algorithm is a two-level structure with a high degree of coupling, which complicates the decomposition of the computation process into components with low data dependency. This decomposition is crucial for effective parallel computation. Second, the synchronous operations among different components must be lightweight, as heavy synchronous operations can significantly limit the parallel capabilities of the GPU. Third, a concurrent pathfinding solver for single-agent must be developed within the CBS algorithm. This solver should work in cooperation with the high-level solver while considering the relevant constraints.
In this work published in Machine Intelligence Research, researchers propose the GPU-accelerated conflict-based search, namely GACBS, to significantly improve the computational performance of the CBS by efficiently leveraging GPU parallelism. GACBS utilizes the task coordination framework (TCF) to facilitate cooperation between two-level solvers with lightweight synchronous operations based on the observation that the expansion of different CT nodes is independent once the constraints are determined. For the low-level solver of GACBS, the GPU-accelerated time-space A* (GATSA) algorithm is proposed to compute the optimal path for an individual agent under constraints concurrently. In addition, researchers conduct experimental evaluations to demonstrate the effectiveness and efficiency of the GACBS algorithm. The experimental results indicate that GACBS significantly outperforms CPU-based CBS with a maximal speedup ratio of over 46. To the best of researchers' knowledge, GACBS is the first work to parallelize the solver for the MAPF problem on the GPU, considering the conflict between different agents.
Section 2 is about the related work. It first reviews CBS developments, with variants categorized into those reducing nodes explored by high-level solvers and those by low-level solvers. Then, it also notes GPU acceleration in pathfinding tasks.
Section 3 formulates the MAPF problem on a graph with n agents, each having a start and goal node. At every time step, every agent has the option to either remain in the current node or traverse to one of the neighboring nodes. It defines a set of collision-free paths for each agent and aims to minimize the total cost of all the paths, assuming agents remain at goal nodes after completion.
Section 4 is about the preliminary. It presents conflict-based search (CBS), a two-level solver for MAPF. It comprises a high-level solver and a low-level solver. The high-level solver is responsible for constructing a CT that ensures conflict avoidance among various agents. The low-level solver is tasked with calculating the path of an agent while adhering to specified constraints. Within the CT, each node maintains information about the constraint set, the path of each agent, and the total cost.
Section 5 presents GPU-accelerated conflict-based search (GACBS), a parallel processing algorithm that leverages a two-level solver to significantly boost CBS efficiency through GPU acceleration. GACBS integrates three core components: the TCF, high-level solver, and low-level solver. The TCF facilitates inter-solver communication, while the high-level solver constructs the CT and generates the task list. Notably, the proposed parallel GATSA algorithm serves as the low-level solver, determining optimal paths for agents based on assigned tasks. This framework efficiently tackles the challenges of MAPF problems on GPU acceleration.
Section 6 presents theoretical analysis, starting with Lemma 1 which states that the optimal solution is found under specific conditions when the heuristic function is admissible and consistent. Theorem 1 proves that GATSA is optimal and complete under such a heuristic. Theorem 2 further demonstrates that GACBS is also optimal and complete with an admissible and consistent low-level heuristic.
In Section 7, researchers empirically examine the performance of GACBS on 4-neighbor grid maps. Five algorithms are employed in the experiments: CPUCBS, MixCBS, GACBS, GACBS-NC, and NRFSAT. Researchers employ the success rate and the successful average running time (SART) as metrics, where SART is the average running time over the instances that all three algorithms can solve. Researchers present the results and discussions from five aspects: Acceleration of GPU relative to CPU, acceleration of TCF, memory optimization, comparison with the SOTA algorithm, and acceleration of components.
Section 8 is the conclusion. In this paper, researchers investigated the use of GPU computational capacity to solve the MAPF problem. They presented the GACBS, a GPU-accelerated parallel two-level algorithm designed to significantly reduce computation time for solving the multi-agent pathfinding problem. Researchers proposed the task coordination framework to facilitate the collaboration between the high-level and the low-level solvers with merely lightweight synchronization operations. Researchers also introduced the GATSA as the low-level solver for the GACBS, enabling efficient parallel processing for the SAPF problem under constraints.
Researchers conducted experiments to evaluate the computational efficiency of the GACBS algorithm on three graphs with varying scales. The experimental results demonstrated that GACBS significantly accelerates conflict-based search on the CPU, achieving a speedup ratio of over 46 in specific scenarios. Furthermore, GACBS outperforms the SOTA reduction-based method for the MAPF problem, achieving a speedup ratio of up to 8.
While GACBS demonstrates the first successful GPU parallelization of CBS, it primarily speeds up existing computation and has not yet integrated new techniques that reduce search complexity. Future work will combine CPU-based CBS optimizations with GPU parallelization to decrease search complexity and address memory limitations. In addition, GACBS employs fixed-size arrays instead of dynamic arrays to prioritize computational efficiency. However, GACBS requires the adjustment of array sizes to accommodate the specific needs of real-world applications. Future efforts will aim to implement a dynamic memory allocation mechanism to enhance the adaptability of GACBS.
See the article:
GPU-accelerated Conflict-based Search for Multi-agent Embodied Intelligence
http://doi.org/10.1007/s11633-025-1568-y
