GPU Acceleration Transforms Multi-Agent Pathfinding With Record Speedups

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 to minimize interference. The solver of the MAPF problem has been widely applied in various domains, including aircraft towing vehicles, traffic management, mail sorting, and video games.

In practice, the calculation time is the most significant bottleneck in solving MAPF problems. The optimal solution 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 for the delivery robot's path in a warehouse is too long, the logistics system's throughput rate will decrease, resulting in economic losses.

Conflict-Based Search and the Need for Acceleration

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, GPU acceleration has been a promising approach for improving the efficiency of time-consuming algorithms in recent years. However, there has been no research specifically exploring GPU acceleration for CBS computing. This paper presents a novel approach to enhance the computational efficiency of CBS by effectively leveraging the parallel computing capabilities of the GPU.

Introducing GACBS: A GPU-Accelerated CBS Algorithm

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 elements must be lightweight, as heavy synchronous operations can significantly limit the GPU's parallel capabilities. Third, a concurrent pathfinding solver for a single agent must be developed within the CBS algorithm. This solver should work in conjunction with the high-level solver, considering the relevant constraints.

In this work, published in the journal 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, achieving a maximum speedup ratio of over 46. However, on very small maps or when the number of agents is low, CPU-based CBS can outperform due to kernel-launch and synchronization overheads. 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.

Technical Foundations and Algorithm Structure

Section 2 discusses related work. It first reviews CBS developments, categorizing variants into those 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 boost CBS efficiency through GPU acceleration significantly. 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. Here, GATSA addresses the single-agent pathfinding (SAPF) subproblem under constraints.

Theoretical Analysis and Experimental Evaluation

Section 6 presents a 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 both optimal and complete, utilizing 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 use the success rate and the successful average running time (SART) as metrics, noting that in three-way comparisons, SART is averaged over instances solved by all three algorithms, while in the NRFSAT comparison, it is averaged over instances solved by both algorithms.

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. They also report that in some specific instances, GACBS shows a slightly lower success rate than NRFSAT due to a large number of high-level nodes, and suggest that symmetry-breaking may alleviate this issue. 

Additionally, the “Compact” memory optimization operation is crucial for preventing memory overflows and reducing the number of low-level nodes, which explains why the GACBS-NC variant underperforms.

Conclusion and Future Work

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 a task coordination framework to facilitate collaboration between high-level and low-level solvers using merely lightweight synchronization operations. Researchers also introduced the GATSA as the low-level solver for the GACBS, enabling efficient parallel processing for the single-agent pathfinding (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 accelerates existing computations 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. Additionally, GACBS utilizes fixed-size arrays instead of dynamic arrays to prioritize computational efficiency. However, GACBS requires adjustments to 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.