The paper studies Multi-Agent Path Finding, in which a set of agents must move from specified start vertices to specified goal vertices on a graph without vertex or edge collisions. Time is discrete, and an agent may move to an adjacent vertex or wait at its current vertex. The central focus is the high-level search of Conflict-Based Search, where constraints are added to resolve collisions and low-level paths are recomputed. The work asks how this search can obtain stronger admissible lower bounds without losing optimality.
The first contribution is a formal analysis of the previous CG heuristic, which uses only cardinal conflicts in the current solution. The paper proves that, when both child constraint-tree nodes have solutions, resolving a single conflict cannot provide more than a one-unit admissible increase through the conflict graph in the relevant cases, so the graph cannot yield a stronger admissible value simply by counting that conflict more aggressively. The second contribution is DG, which reasons about pairwise dependencies that may appear in descendant solutions, and WDG, which additionally uses the amount of extra cost required to make a dependent pair conflict-free. The paper establishes that WDG strictly dominates DG and DG strictly dominates CG. It also presents lazy computation and memoization techniques that make the stronger heuristics practical.
A CBS high-level node contains a set of vertex and edge constraints, one cost-minimal path for every agent satisfying those constraints, and the sum of those path costs. CG builds a conflict graph from cardinal conflicts in the current solution and uses the size of a minimum vertex cover as an admissible heuristic value. DG extends the reasoning to future solutions: for a pair of agents, it constructs and explores their individual multi-value decision diagrams, or MDDs, until all possible branches lead to conflicts and cannot be extended, thereby identifying a pairwise dependency and assigning a lower bound of one when appropriate. WDG defines the pairwise dependency cost as the difference between the minimum sum of costs of conflict-free paths satisfying the node constraints and the sum of the two agents' current path costs. It assigns this difference as an edge weight and derives a weighted vertex-cover lower bound. To reduce overhead, the implementation evaluates expensive heuristic values lazily and memoizes repeated dependency, edge, weight, and MDD computations.
The experiments compare CBS, ICBS, and CBSH variants using CG, DG, or WDG on four-neighbor grids. For each map and agent count, the authors generate 50 instances with random start and goal vertices. The reported settings include 20-by-20 empty maps, 20-by-20 maps with 30 percent randomly blocked cells, maps with varying obstacle densities, and a large-map setting; a one-minute limit is used for each solver and instance in the small-map experiments. The measured quantities include root-node heuristic values, runtime per expanded constraint-tree node, success rate, number of expanded nodes, and total runtime. The implementation is written in C++ and was run on a laptop with a 2.80 GHz Intel Core i7-7700 processor and 8 GB of RAM. The supplied excerpt does not establish every map dimension, every agent-count setting, or the complete numerical result tables, so those details cannot be reconstructed reliably.
The main limitation of CG is conceptual rather than merely computational: a non-cardinal conflict in the current solution can force future conflicts after a constraint is added, but CG does not see those descendant interactions. DG captures whether a pair of agents is dependent, yet it uses one as the lower bound even when the true additional cost is larger. WDG retains that additional-cost information, producing a stronger heuristic at the price of more computation per high-level node. The experiments indicate that map structure matters: empty maps often provide many bypasses, while dense maps create stronger coupling; consequently, a larger heuristic improvement does not automatically imply the largest node-reduction factor. The paper proposes future work on admissible or inadmissible heuristics for suboptimal CBS-based algorithms, applying the approach to ICTS and MDD-SAT, and generalizing it from pairs to groups of three or four agents.
MAPF is NP-hard, but many optimal approaches have been developed, including reduction-based, A*-based, and dedicated search-based algorithms. CBS is a two-level search algorithm: its high level branches on collisions by adding constraints, while its low level computes cost-minimal paths that satisfy the current constraints. CBSH introduced an admissible high-level heuristic based on cardinal conflicts; this paper calls that heuristic CG. The work positions DG and WDG as stronger alternatives that preserve admissibility while incorporating information beyond the current set of cardinal conflicts.
The input is an undirected, unweighted graph and a set of agents, each with a start vertex and a goal vertex. Between consecutive time steps, an agent can traverse an adjacent edge or wait, with unit cost for ordinary movement and waiting; terminal waiting at the goal has zero cost. A vertex conflict occurs when two agents occupy the same vertex at the same time, and an edge conflict occurs when they traverse the same edge in opposite directions over one time step. The objective is to find collision-free paths, and a CBS node cost is the sum of the individual path costs.
CG represents cardinal conflicts as edges in a conflict graph and uses a minimum vertex cover as a lower bound. DG constructs pairwise MDD combinations and checks whether all possible minimum-cost branches eventually conflict, which indicates dependency. WDG defines a nonnegative pairwise increment as the difference between the minimum conflict-free pair cost and the current pair cost, and uses positive increments as weights in a weighted dependency graph. Lazy evaluation first inserts a node using a cheaper or weaker value before calculating an expensive value when needed. Memoization reuses results for repeated constraint sets and MDD constructions, reducing repeated work across branches.
The implementation is written in C++ and was run on a laptop with a 2.80 GHz Intel Core i7-7700 processor and 8 GB of RAM. The benchmark uses four-neighbor grids, including empty and obstacle-filled 20-by-20 maps, varying obstacle densities, and a large-map condition. CBS, ICBS, and CBSH with CG, DG, or WDG are compared, with the CBSH variants using the two runtime improvements described by the paper. Fifty randomly generated start-goal instances are used for each map-and-agent-count combination. The excerpt does not provide the complete large-map specification, all agent-count settings, or all experimental parameter values.
The paper states that WDG strictly dominates DG, and DG strictly dominates CG, in the admissible-heuristic sense. On the reported benchmarks, the new heuristics significantly increase the success rate relative to CBSH with CG, while reducing expanded constraint-tree nodes and runtime by up to a factor of 50. Memoization is reported to save more than 90 percent of the edge and weight computation time. The excerpt includes selected root heuristic values and qualitative map-dependent interpretations, but it does not provide every success rate, runtime, or node-count value, so a complete numerical ranking across all settings is not established here.
Pairwise dependency reasoning gives CBS a stronger admissible view of how resolving one interaction can create unavoidable costs elsewhere in the search tree. DG supplies a binary dependency-based lower bound, while WDG refines it with the actual extra cost needed for a conflict-free pair whenever that cost can be computed. The reported experiments support the conclusion that these heuristics improve both the number of solved instances and search efficiency with reasonable overhead. The approach therefore offers a practical way to strengthen optimal CBS without changing its admissibility-based optimality guarantee.
The proposed reasoning is fundamentally pairwise and does not fully encode dependencies involving three or more agents simultaneously. In dense maps, pairwise information may remain far from the ideal global lower bound because many agents are strongly coupled. WDG is computationally more expensive than CG and relies on implementation optimizations such as lazy evaluation and memoization. The supplied evidence does not establish statistical uncertainty, performance on non-grid graphs, behavior in real deployments, or generalization beyond the reported benchmark families. It also does not provide enough detail to verify every claimed comparison independently.
The paper shows why counting only currently visible cardinal conflicts can miss constraints that become unavoidable after branching. It turns pairwise path dependence into admissible lower bounds, offering a reusable design pattern for reducing optimal-search effort without sacrificing the underlying optimality guarantee. The reported success-rate and runtime improvements are relevant to MAPF applications such as warehouse robots, quadrotor swarms, and computer-game characters. More broadly, the work connects conflict resolution, MDD-based feasibility reasoning, and weighted graph optimization within a single CBS enhancement.
This paper is recommended for MAPF researchers studying CBS, ICBS, CBSH, admissible heuristics, or optimal multi-agent planning. It is especially useful for readers interested in MDDs, conflict graphs, vertex-cover lower bounds, pairwise dependency detection, and practical search-speed improvements. Readers who need the exact benchmark dimensions, all numerical comparisons, or evidence on domains outside the supplied grid experiments should consult the complete paper, because the excerpt does not establish those details.