Researchers Compare CBS, LNS, PBS, and PIBT in the Race to Speed Up Multi-Agent Pathfinding

Table Of Links

ABSTRACT

I. INTRODUCTION

II. RELATED WORKS

III. PRELIMINARIES

IV. METHODOLOGY

V. RESULTS OF DECOMPOSITION

VI. RESULTS OF DECOMPOSITION’S APPLICATION

VII. CONCLUSION, ACKNOWLEDGMENTS AND REFERENCES

II. RELATED WORKS

In this section, we provide an overview of existing works aimed at reducing the time cost of MAPF methods. MAPF methods typically involve searching for paths connecting the starting and target locations for multiple agents. Broadly, there are two approaches to determining the paths of agents:

1, move one agent from its start to target while keeping other agents static and attempting to avoid conflicts with the paths of other agents. This approach is adopted by CBS-based methods, HCA*, LNS, and PBS.

2, move all agents simultaneously by avoiding conflicts with each other at each time step. This approach is employed by LaCAM, PIBT, and Push and Swap. We refer to the first approach as serial MAPF methods and the second approach as parallel MAPF methods. This distinction is crucial in understanding how the decomposition of a MAPF instance applies to them. Further details about this difference can be found in Section IV-D.

A. Conflict based search

Conflict-Based Search (CBS) [16] is a two-level complete and optimal multi-agent pathfinding algorithm. At the high level, CBS employs a conflict tree in which nodes represent conflicts between paths of two agents. By splitting a conflict, CBS obtains constraints for the related two agents, respectively. The low level utilizes heuristic single-agent searches to find new paths that satisfy all constraints imposed by the highlevel conflict tree node. Therefore, CBS operates as a serial MAPF method. If CBS finds a new path, it checks for conflicts between the new path and previous paths. If no new conflicts are found, CBS exits with a conflict-free solution; otherwise, it inserts the new conflict as nodes into the conflict tree and repeats the process of splitting conflicts and searching for new paths. While CBS can find optimal solutions, it can be timeconsuming in certain cases. To accelerate CBS, various improvements have been proposed.

1. Trade off solution quality for efficency: Bounded CBS (BCBS) [3] incorporates focal search into the low-level search of CBS, enabling the low-level search to consider avoiding conflicts with other agents’ paths and generate bounded suboptimal solutions. Enhanced CBS (ECBS) [3] utilizes the same low-level search as BCBS and applies focal search to the high-level search of CBS, aiming to minimize the number of nodes from the current conflict tree (CT) node to the CT node representing the conflict-free solution. Similar to BCBS, ECBS also produces bounded suboptimal solutions.

   Explicit Estimation CBS (EECBS) [4] employs online learning to estimate the cost of the solution beneath each high-level node. It utilizes Explicit Estimation Search (EES) [20] to select high-level nodes for expansion, mitigating two drawbacks of ECBS: (1) the cost of the solution beneath a CT node N might exceed the cost of N and thus could surpass the suboptimality bound; (2) the lower bound of ECBS seldom increases, leading to difficulties in finding a solution within a reasonable time if the optimal sum of costs is not within the initial suboptimality bound.

2. Bypassing conflicts: Bypassing Conflicts [1] is a conflict resolution technique that alters the paths of agents involved in a chosen conflict instead of splitting a conflict tree (CT) node and searching for paths to avoid related constraints. When expanding a CT node N and generating child CT nodes, if the cost of a child CT node equals the cost of N and the number of conflicts of the paths in the child node is smaller than the number of conflicts of N, then the child node is used to replace N, and all generated child CT nodes are discarded. Otherwise, N is split as before. It has been demonstrated that bypassing conflicts often results in smaller CTs and reduces the runtime of CBS.

3. Prioritizing conflicts: Prioritizing Conflicts [1] is a conflict-selection technique. A conflict is considered cardinal if, when CBS uses the conflict to split a conflict tree (CT) node N, the costs of both child CT nodes are larger than the cost of N. It is semi-cardinal if the cost of one child CT node is larger than the cost of N, and the cost of the other node is not. It is non-cardinal if the costs of both child CT nodes are equal to the cost of N. CBS can significantly enhance its efficiency by resolving cardinal conflicts first, then semi-cardinal conflicts, and finally non-cardinal conflicts. This prioritization is effective because generating CT nodes with larger costs first typically improves the lower bound of the CT (i.e., the minimum cost of the CT nodes in the open list) faster, thereby producing a smaller conflict tree and accelerating CBS.

4. Symmetry reasoning: S Symmetry Reasoning [9, 8] is a technique aimed at avoiding the repeated resolution of conflicts between the same pair of agents due to symmetric paths and conflicts. It efficiently identifies each symmetry and resolves it through a single splitting action with specialized constraints. This process results in a smaller conflict tree and reduces the time cost of CBS.

5. Weighted Dependency Graph (WDG): The Weighted Dependency Graph (WDG) heuristic [6] is an admissible heuristic employed in the high-level search of CBS. It operates by constructing a weighted dependency graph for each conflict tree (CT) node N. In these graphs, vertices represent agents, and edges denote dependency between agents. This dependency is defined as follows: the minimum sum of costs of their conflict-free paths satisfying N’s constraints (computed via solving a 2-agent MAPF instance using CBS) is greater than the sum of costs of their paths in N’s paths (the shortest paths satisfying N’s constraints but not necessarily conflictfree).

The edge weights signify the difference between the minimum sum of costs of conflict-free paths satisfying N’s constraints and the sum of costs of their paths in N’s paths. The value of the edge-weighted minimum vertex cover of the graph serves as an admissible heuristic for the high-level search of CBS. Despite the runtime overhead associated with building the weighted dependency graphs and determining their edge-weighted minimum vertex cover, incorporating the WDG heuristic often leads to a reduction in conflict tree size and a decrease in the runtime of CBS.

B. Large neighborhood search

At one end of the spectrum are (bounded-sub) optimal algorithms capable of finding high-quality solutions for small problems. At the opposite end are unbounded-suboptimal algorithms, which can handle large problems but typically produce low-quality solutions. Li et al. proposed MAPF-LNS [5], presenting a third approach that combines the strengths of both. MAPF-LNS starts with a given solution and deletes a portion of it, referred to as a neighborhood, while treating the remaining part as fixed. This simplifies the original problem, making it easier to solve. If the newly found solution is superior to the current one, it replaces the existing solution.

Consequently, MAPF-LNS is both complete and capable of iteratively enhancing solution quality towards near-optimality. During each iteration, LNS selects a subset of agents and updates their paths without modifying those of other agents. Thus, MAPF-LNS operates as a serial MAPF method. MAPFLNS can employ any desired approach to solve the simplified problem, provided it can account for the fixed information. Building on this work, Li et al. introduced MAPF-LNS2 [7], which efficiently finds a solution (rather than improving a given solution) for a MAPF instance. Initially, MAPF-LNS2 invokes a MAPF algorithm to solve the instance and acquire a (partial or complete) plan. For agents lacking a path, MAPFLNS2 devises a path that minimizes collisions with existing paths.

C. Priority based search

Priority-Based Search (PBS) [11] is an incomplete, suboptimal algorithm designed for prioritized planning. It employs a depth-first search at the high level to dynamically construct a priority ordering, thereby forming a priority tree (PT). When confronted with a collision, PBS greedily determines which agent should be assigned a higher priority. It efficiently backtracks and explores alternative branches only if no solution is found in the current branch.

Consequently, PBS incrementally constructs a single partial priority ordering until all collisions are resolved. Once each agent is assigned a unique priority, PBS computes a minimum-cost path (in priority order) from its starting vertex to its target vertex without colliding with the paths of agents with higher priorities that have already been planned. Therefore, PBS operates as a serial MAPF method. PBS ranks among the most efficient methods for solving MAPF. However, prioritized planning with an arbitrary priority ordering does not guarantee completeness or optimality in general [11].

1. Greedy PBS: Given that PBS becomes less effective for MAPF instances with high densities of agents and obstacles, [2] introduced Greedy PBS (GPBS). GPBS utilizes greedy strategies to enhance PBS by minimizing the number of collisions between agents. In essence, GPBS employs the numbers of conflicts and conflicting pairs as heuristics to guide the search on its low and high levels, respectively. PBS can be regarded as a special decomposition of MAPF instances, where each subproblem involves only one agent. Unlike PBS, our decomposition does not necessitate that every subproblem contain only one agent, while still preserving completeness. Additionally, our decomposition serves as an auxiliary component rather than an isolated method, making it applicable to a wide range of MAPF algorithms.

   D. PIBT and LaCAM

   1. Priority Inheritance with Backtracking (PIBT): PIBT [14] is an incomplete and suboptimal MAPF method that assigns a unique priority to each agent at every timestep. This prioritization ensures that all movements are ordered, and all agents act within a single timestep according to their priority, making it a parallel MAPF method. Priority inheritance is utilized to effectively handle priority inversion in path adjustment within a small time window, and a backtracking protocol prevents agents from becoming stuck.

   Based on priorities and assuming only local interactions, PIBT is easily adaptable to decentralized contexts. Intuitively, PIBT is well-suited for large environments where intensive communication is prevalent, and path efficiency improves with a lower density of agents. In PIBT, for each timestep, each agent must evaluate distances from surrounding nodes to its goal. While this operation could be implemented by calling A* on demand, it may also become a bottleneck. To address this issue, the authors of PIBT proposed PIBT+ [15], which saves computation time by preparing distance tables from each agent’s goal.

   2. Lazy constraints addition for MAPF (LaCAM): LaCAM [13] is a complete and suboptimal two-level MAPF method. At the high level, it explores a sequence of configurations, where each search node corresponds to one configuration. At the low level, it searches for constraints specifying which agents go where in the next configuration, making it a parallel MAPF method. For each high-level node, LaCAM performs a low-level search that generates constraints determining the agents’ positions in the next configuration.

      Successors at the high level (i.e., configurations) are lazily generated while adhering to constraints from the low level, resulting in a significant reduction in search effort. The successor generator of LaCAM is implemented using PIBT. It is noteworthy that when LaCAM encounters a known configuration, it reinserts the corresponding high-level node into the open set (which stores nodes for high-level search). This action prevents repeated appearance of configurations, thereby preventing LaCAM from accepting external paths as dynamic obstacles to avoid, as all agents may need to wait at times to avoid conflicts with external paths.

      Okumura et al. proposed LaCAM2 [12], which introduces two enhancements to LaCAM. The first enhancement is its anytime version, called LaCAM*, which converges to optimality eventually, provided that solution costs accumulate transition costs. The second enhancement adds a swap action to the successor generator of LaCAM, enabling the quick generation of initial solutions.