Multi-agent pathfinding (MAPF) asks for paths that move multiple agents from their current configurations to goal states without any pair of agent shapes overlapping at the same time. Classic MAPF usually uses point agents on a two-dimensional grid, with movements of unit duration. The paper also considers continuous-time MAPF, called MAPF R in the supplied evidence, where a weighted graph may be non-planar, edges have positive real-valued or rational-valued durations, waiting is represented by self-directed edges, and collisions can occur while agents traverse edges. A feasible solution has no conflicts, and solvers commonly optimize makespan or flowtime.
The main contribution is Temporally-Relative Duplicate Pruning, or TRDP, introduced for CBS. TRDP detects states that are duplicates in a temporally relative sense, even when their absolute timestamps differ, and prevents them from being expanded as distinct useful states. The authors prove that TRDP does not remove an optimal feasible solution and that CBS augmented with TRDP terminates whether or not the instance is solvable. They also describe a bypass procedure for agent-dense settings and report that TRDP usually has little runtime impact while sometimes improving performance.
Standard CBS searches a conflict tree whose nodes contain one path per agent. The root is obtained by planning for agents independently; when conflicts are found, CBS adds a constraint for one involved agent, replans, and generates successor nodes. TRDP searches individual or multi-agent paths for a loop whose later state has the same relevant future behavior as an earlier state after a temporal shift. Such a loop is suboptimal because the loop can be removed or avoided without preventing the agent from reaching its goal, so the corresponding duplicate expansion can be pruned. In dense environments, a temporally relative duplicate may otherwise create a large multi-way split, so the method can try a bypass: an alternative path that avoids the loop, does not increase path cost, and introduces no additional conflicts; if none is found, the resulting constraints and replanned paths are used to generate successors.
The evaluation compares CBS with and without TRDP on the complete set of MAPF benchmark problems across 4-, 8-, 16-, and 32-neighbor grid domains. The 4-neighbor cases represent classic MAPF, while the higher-connectivity cases are treated as MAPF Q instances in the supplied evidence. For each problem, experiments start with two agents and increase the count by one until the instance can no longer be solved within a 30-second limit. The reported measures include runtime, the number of agents solved within the limit, conflict-tree size, the number of TRD encounters, and the fraction of runtime spent on duplicate detection. Hand-crafted unsolvable and agent-dense cases are also examined, but the excerpt does not establish every experimental condition or a complete result for every instance.
The theoretical result addresses a long-standing CBS problem: returning a solution on solvable instances is not sufficient for completeness if an unsolvable instance can make the algorithm run indefinitely. Under the paper's assumptions, TRDP makes the relevant search space finite, allowing CBS to terminate with failure without relying on an external timeout or parallel mitigation procedure. On ordinary benchmarks, the extra work is usually small because TRDs are rare and the check often exits early when no single-agent loop is present. The trade-off appears in agent-dense environments, especially narrow corridors, where many TRDs can cause expensive multi-way splits. Bypassing can mitigate this cost, but the supplied excerpt does not establish that it removes all scaling problems or proves performance for every continuous-time model, agent shape, or alternative solver.
CBS is a prominent optimal, decoupled approach to MAPF. Unlike coupled methods such as multi-agent A*, which aggregate all agents into one joint state space, CBS combines individual paths with constraints generated from detected conflicts. The paper states that other decoupled optimal methods have also faced difficulty terminating when no solution exists. Completeness has two parts: finite termination with a solution when one exists, and finite termination reporting that no solution exists when none exists.
The central problem is the second part of completeness. Even on a finite map, including time can create an infinite state space because an agent may wait at a location indefinitely. CBS can repeatedly generate states that differ only by temporal offset and therefore lacks a finite stopping guarantee on some unsolvable instances. In continuous-time MAPF, larger agent shapes and intersecting edges introduce conflicts that do not occur for point agents in classic MAPF, so solvability cannot always be inferred by analyzing only the underlying graph.
TRDP uses temporally relative future behavior rather than exact equality of absolute states to identify duplicates. If a later occurrence has the same relevant behavior as an earlier occurrence after shifting time, continuing around the loop is unnecessary and cannot be required by an optimal path. The theoretical argument establishes that loops are suboptimal, that TRD constraints do not block an optimal feasible solution, and that duplicate removal gives the conflict tree a finite upper bound. The approach therefore targets classic and continuous-time domains without requiring a separate solvability oracle.
The paper reports roughly 32,000 benchmark experiments and millions of generated conflict-tree nodes. Across the tested grid domains, only 29 TRDs were encountered, and fewer than 0.01 percent of the grid benchmark instances triggered the TRDP logic. TRDs were most common in small mazes with corridors of width one, where the agent density is high relative to the available space. Hand-crafted unsolvable and dense cases were also used to examine termination, tree size, and runtime, but the excerpt does not fully specify every generation procedure or comparison condition.
On the illustrative unsolvable place-swapping instance, CBS with TRDP terminates after five high-level expansions. Across the benchmark suite, duplicate detection is reported to add no significant runtime cost in the majority of instances, and its measured runtime share is generally small. In selected high-density cases, TRDP finds a solution at a shallower conflict-tree depth or reduces the conflict-tree size compared with regular CBS. The evidence supports termination on unsolvable instances and occasional performance gains, but it does not justify a universal speedup claim or provide enough information to reconstruct every numerical comparison.
TRDP makes CBS natively complete by preventing temporally shifted duplicate states from causing unbounded search. The theoretical analysis says that pruning preserves optimality and guarantees finite termination regardless of whether a solution exists. Empirically, the technique is rarely activated on standard benchmarks, so its normal overhead is small, while dense cases can benefit from duplicate removal and bypassing. The paper therefore presents TRDP primarily as a reliability improvement and secondarily as a potential performance improvement.
The paper explicitly emphasizes completeness rather than making CBS scale to substantially larger problem instances. Standard MAPF benchmark sets are described as containing no unsolvable instances, and unsolvable cases may be rare or hand-crafted depending on the domain, limiting how often the termination benefit is exercised in routine benchmarks. Dense settings can generate many TRDs and large multi-way splits, so TRDP is not cost-free in every case. The supplied excerpt does not establish behavior under all continuous-time semantics, all agent shapes, other MAPF algorithms, or workloads outside the evaluated benchmarks.
An optimal planner that can run forever on an impossible request is difficult to use safely in a real coordination system. TRDP addresses this failure mode inside the CBS search rather than depending on a separate timeout or parallel mitigation procedure. Its combination of an optimality-preservation argument, a completeness guarantee, and low reported overhead makes it relevant to researchers building dependable MAPF and continuous-time MAPF solvers. It also shows why duplicate detection must account for temporal equivalence rather than only exact repetition of a graph state.
This paper is recommended for researchers studying CBS, MAPF completeness, unsolvable instances, continuous-time collision checking, or duplicate detection in search. It is especially relevant to solver designers who need an optimality-preserving finite-termination guarantee and to researchers working in narrow, agent-dense environments. Readers whose primary goal is large-scale throughput should treat the paper as a completeness contribution and consult fuller experimental evidence before drawing broad scaling conclusions.