Source-linked AI summary
The Cost of Classical Multi-Agent Path Finding
Alvin Combrink, Sabino Francesco Roselli, Martin Fabian
TL;DR
Classical MAPF’s discrete-time and graph-conflict assumptions limit its solution quality, motivating a direct comparison with continuous-time MAPF_R. The authors compare the formulations across agent and map settings using AOC-CBS bounds. Continuous time and shape-awareness alone yield only a few-percent improvement at tested agent counts, while expanded move actions provide larger gains, especially on open maps.
Problem
The paper asks how much solution quality classical MAPF forfeits relative to MAPF_R and in which contexts that loss is substantial.
Source: §1 · p. 1Method
The authors compare optimal classical MAPF and MAPF_R costs across time, agent size, map connectedness, resolution, and topology, using AOC-CBS bounds to include higher agent counts.
Source: §1 · p. 2Results
Takeaways & Limitations
Classical MAPF remains a reasonable simplification on narrow, constrained maps, while MAPF_R can unlock additional quality where its scalability meets real-world application needs.
Source: §6 · p. 7The measured cost gap is a conservative estimate because classical MAPF limits map resolution by agent size, and the gap in execution may be larger for non-holonomic robots.
Source: §6 · p. 8
Abstract
from arXiv · showhide
Multi-Agent Path Finding (MAPF) is the problem of planning conflict-free paths for multiple agents in a shared space, each from its start to its goal. Classical MAPF has been the dominant formulation for many years, with its assumptions of discrete time and graph-based conflicts presumably easing the search for solutions. These assumptions limit the physical environments and agents for which a solution is truly collision-free, and also place an upper bound on solution quality that no algorithmic improvements can lift. This work investigates how much solution quality, and in what contexts, the classical MAPF formulation forfeits. Continuous-time MAPF (MAPF$_R$) relaxes these assumptions, making it a natural counter-formulation to compare against across various agent counts and sizes, and graph connectedness, topologies, and resolutions. We find that continuous time and agent shape consideration are worth relatively little on their own; their value comes from enabling an expanded range of move actions, on average improving solution quality by at least $5\%$ on narrow and constrained maps and $17\%$ on maps with open spaces. In some cases, the improvements exceed $20\%$. Doubling the map resolution with classical MAPF recovers less than $3\%$, meaning that little of what is forfeited can be bought back through more compute. This work therefore provides insight on when classical MAPF is a reasonable simplification, and when MAPF$_R$ unlocks significantly higher-quality solutions.
1 Introduction
Classical MAPF’s long-standing dominance reflects its historical tractability, but its assumptions impose a ceiling on solution quality that algorithmic progress within the formulation cannot lift. This work directly compares classical MAPF with continuous-time MAPF_R to measure that cost and identify where it matters.
1 Introduction
- Classical MAPF’s solution quality is bounded by its formulation, while decades of algorithmic work have enabled optimal solutions for low hundreds of agents and suboptimal variants for thousands.The formulation’s solution space, unlike search scalability, sets an absolute ceiling on achievable quality.Source: §1 · p. 1
- The study asks how much solution quality classical MAPF forfeits relative to MAPF_R, and in which contexts that loss is substantial.Source: §1 · p. 1
- Prior comparisons do not fully answer this question because they rely on suboptimal MAPF_R solutions, adjacent problems, or lack direct and comprehensive comparisons with classical MAPF.A suboptimal MAPF_R result that beats optimal classical MAPF still does not reveal the true gap; classical solutions are valid MAPF_R solutions.Source: §1 · pp. 1–2
- The authors compare optimal classical MAPF and MAPF_R costs across time, agent size, connectedness, and four maps, using AOC-CBS bounds to reach higher agent counts without requiring MAPF_R convergence.They also test whether refining map resolution lets classical MAPF recover the loss.Source: §1 · p. 2
2 Background
The paper sets up classical MAPF and MAPF_R, then describes CBS and AOC-CBS as the algorithms used to compare their solutions. Classical MAPF uses discrete actions and graph-based conflicts, while MAPF_R permits continuous timing and shape-aware conflicts.
2.1 Classical MAPF
- Classical MAPF plans agents on an undirected graph using discrete waits and moves, vertex or edge conflicts, and sum-of-costs as the objective to minimize.A plan’s cost is its duration, and the SOC sums these costs across agents.Source: §2.1 · p. 2
2.2 Continuous-time MAPF
- MAPF_R allows real-valued action times and durations, and defines conflicts by overlapping agent shapes rather than shared graph locations.This can allow agents to traverse the same edge simultaneously when spatially separated.Source: §2.2 · p. 2
2.3 Conflict-Based Search
- CBS expands a binary constraint tree by selecting a conflict and adding one constraint for each involved agent, returning an optimal solution if one exists.Each candidate plan is found by a low-level planner under its node’s constraints.Source: §2.3 · p. 2
2.4 Anytime-Optimal Continuous-time CBS
- AOC-CBS produces an incumbent early, progressively improves it, and provides bounds on the optimal MAPF_R cost.Its continuous-time constraints and SIPP low-level planner support the lower-bound search; repair functions can provide an incumbent upper bound before optimality is reached.Source: §2.4 · pp. 2–3
3 The Cost of the Classical MAPF Assumptions
The section explains how discrete timing and graph-based conflicts can impose artificial delays, constrain valid agent size and map resolution, and exclude spatially overlapping moves. Finer maps can partly mitigate some losses, but cannot reproduce the gains from non-cardinal moves.
3 The Cost of the Classical MAPF Assumptions
- Synchronized timesteps can delay an agent traversing a short edge so its arrival matches another agent traversing a longer edge, increasing cost.The delay may be implemented as waiting or reduced speed, and either choice affects real agents’ positions and solution validity.Source: §3 · p. 3
- Graph-based conflicts can impose extra delays even on unit-length square grids, and the delays from ignoring agent shape grow as agents get smaller.The section contrasts perpendicular and parallel traversals and notes the smaller-agent effect.Source: §3 · p. 3
- For circular agents, classical MAPF’s validity constraint limits radius according to the smallest angle between graph edges, thereby upper-bounding map resolution by agent size.If agents exceed the stated size limit, a classical solution is not guaranteed valid; the required agent size and resolution can sometimes prohibit classical MAPF.Source: §3 · p. 3
- Graph-based conflicts prevent safely including both diagonals of a cell, because agents on the crossing diagonals can collide at the center without being registered as conflicting.Including only one diagonal still brings synchronicity delays and reduces the maximum agent radius allowed for validity.Source: §3 · p. 3
- Adding diagonals to classical MAPF is potentially valuable because a 2D diagonal is about 29% shorter than Manhattan distance, while further connectedness gains diminish.The section compares 4-, 8-, and 16-connected maps; the same knight’s move is shortened by 19.5% from 4 to 8-connectedness and a further 7.4% from 8 to 16.Source: §3 · p. 3, Figure 1 · p. 3
- A triangular lattice can offer six movement directions, but its smaller angle between edges makes the agent-size validity constraint tighter; this study investigates only square lattices.Source: §3 · p. 3
3.1 Can Map Resolution Recover the Loss?
- Finer maps can partly mitigate artificial delays from synchronization and ignored agent shapes, but cannot recover gains from non-cardinal edges because Manhattan distance is unchanged by grid refinement.The experiments keep the map static while varying agent size; finer maps improve cost only up to the point where validity is at risk.Source: §3.1 · pp. 3–4
4 Study Design
Section 4 defines a bounded comparison of optimal classical MAPF and MAPF𝑅 costs, then specifies the evaluation axes, benchmark scenarios, resolution test, and run settings.
4 Study Design
- CBS supplies optimal classical MAPF cost, while AOC-CBS supplies MAPF𝑅 cost bounds; the upper bound is clipped at 0% because classical solutions are also MAPF𝑅-valid.The comparison covers discrete versus continuous time, agent sizes, connectedness, and different maps.Source: §4 · p. 4
- Reported means use only scenarios solved across every radius and connectedness setting; agent counts stop below 40% CBS success or when the Δ spread becomes uninformative.CBS success rates indicate the data support for the corresponding bounds.Source: §4 · p. 4
4.1 Evaluation Dimensions
- The study varies agent radius and 4-, 8-, and 16-connected moves; added edges offer shorter paths and more collision-avoidance options.A pure time comparison is approximated on 4-connected graphs with radius r=2/4, where the tests measure delays from synchronized movement and unconsidered shapes.Source: §4.1 · p. 4
4.2 Maps and Scenarios
- Four MovingAI maps span open spaces through narrow corridors and choke-points; each uses 25 scenarios, except Empty-32-32 uses scaled Empty-16-16 scenarios.For each scenario, an n-agent problem uses the first n start-goal pairs.Source: §4.2 · p. 4, Figure 2 · p. 5
4.3 Leveraging Map Resolution
- Empty-32-32 is treated as finer than Empty-16-16: equivalent start-goal scenarios are scaled, costs halved, and effective resolution doubles to permit half-length steps.The two maps use the same Empty-16-16 random scenarios, with start-goal positions scaled by 2 on Empty-32-32.Source: §4.3 · p. 5
4.4 Settings and Hardware
- Runs used AMD EPYC 9755 128-core processors, at most 4 cores and 16 GB memory, with 300-second limits for CBS and AOC-CBS.AOC-CBS used a four-policy, four-core gap-cadence portfolio.Source: §4.4 · p. 5
5 Results
Across the tested maps, MAPF_R's largest gains come from higher graph connectedness, while continuous time and agent-shape consideration alone yield relatively small reductions on 4-connected maps. Doubling map resolution recovers less than 3% in the reported setting.
5 Results
- On 4-connected maps, ΔLB reaches down to only a few percent, so continuous time plus shape consideration yields relatively small cost reductions at tested agent counts.These are the cleanest available comparisons of discrete and continuous time, but they still include agent shapes and AOC-CBS cannot narrow the bounds much within the runtime.Source: §5 · p. 5
- Smaller agent radii generally improve both ΔLB and ΔUB, but their effect on search ease cannot be isolated from their permitting lower-cost solutions.Lower-cost solutions found by AOC-CBS are confounded with the lower costs smaller agents permit.Source: §5 · p. 5
- With smaller agents, Δ trends downward at lower agent counts, but widening bounds prevent conclusions about how far that trend extends.The authors leave this question for more scalable MAPF_R algorithms than AOC-CBS.Source: §5 · p. 5
- Empty-32-32 improves Δ from fractions of a percent to over 17% on average; the largest increase comes at 8-connectedness, with moderate further gains at 16-connectedness.Gains taper as maps become less open; higher connectedness offers shorter paths and more alternatives for conflict avoidance.Source: §5 · pp. 5, 7, Figure 3 · p. 6
5.1 Impact of Higher Map Resolution
- Doubling resolution reduces cost by less than 3%, versus more than 16% with 8-connectedness and 21% with 16-connectedness.The finer map brings ΔUB closer to ΔLB, while ΔLB remains almost identical across resolutions.Source: §5.1 · p. 7
6 Discussion
Continuous time and shape-awareness improve solution quality only modestly on their own; their larger value is enabling richer moves. The loss from classical MAPF is greatest on open maps and more modest on constrained maps, while the discussion also identifies limits and directions for further study.
6 Discussion
- Continuous time and shape-awareness alone improve solution quality by only a few percent, while higher connectedness improves it by at least an order of magnitude more.The discussion attributes the larger gains to enabling non-unit-length and spatially overlapping edges, which classical MAPF assumptions exclude.Source: §6 · p. 7
- Classical MAPF forfeits more achievable solution quality on open maps than on narrow corridors and tight spaces, where it remains a reasonable simplification.The authors note that MAPF_R’s additional quality becomes practically attainable if its algorithms reach the scalability required by real-world applications.Source: §6 · p. 7
- Alternative lattices trade connectedness against edge length and permitted agent size, but the authors leave comparisons of their trade-offs to future work.The passage gives connectedness values of six for triangular, four for square, and three for hexagonal lattices.Source: §6 · p. 7
- Asynchronous Actions relax discrete time while retaining graph-based conflicts, but their scalability has not yet reached the agent counts used with classical MAPF.The authors suggest that algorithmic developments for classical MAPF might transfer to this formulation.Source: §6 · p. 8
- On Maze-32-32-2 with r=2/4 and 4-connectedness, AOC-CBS bounds span 0% to −10% at relatively small agent counts, limiting insight into the cost reduction.The authors suspect long corridors contribute to the wide bounds; corresponding techniques used by the classical CBS implementation are not yet developed for continuous time.Source: §6 · p. 8
- The study covers only 2D grid maps; the authors identify 3D comparisons and adaptive roadmaps as future directions.They note that roadmaps can use higher resolution where needed, such as junctions and high-traffic areas.Source: §6 · p. 8
- The measured cost gap is a conservative estimate because classical MAPF plans generally need post-processing for non-holonomic robots, while MAPF_R supports kinodynamically feasible trajectories directly.The authors therefore say the gap in execution is likely larger than the measured gap.Source: §6 · p. 8
7 Conclusion
This work compares optimal classical MAPF solutions with continuous-time MAPF across agent sizes, connectedness, resolution, and topology. It finds that richer moves can yield substantial gains, especially on open maps, while higher resolution alone recovers little and constrained maps can remain suitable for classical MAPF.
7 Conclusion
- On average, richer move actions improve solution quality by at least 5% on narrow and constrained maps and at least 17% on open maps, with some improvements exceeding 20%.Continuous time and shape-awareness alone account for marginal improvements at the tested agent counts; they enable the expanded move set.Source: §7 · p. 8
- Refining the map resolution only slightly raises solution quality, and classical MAPF cannot recover through more compute what its assumptions forgo.Unbounded refinement is not possible without compromising classical MAPF solution validity.Source: §7 · p. 8
- The forfeit is moderate on maps with narrow corridors and tight spaces, where agents are relatively large compared with graph edges and only cardinal movements are possible.The paper presents these settings as contexts where classical MAPF can be a reasonable simplification.Source: §7 · p. 8