cs.MAOct 7, 2026

The Cost of Classical Multi-Agent Path Finding

Authors: Alvin Combrink, Sabino Francesco Roselli, Martin Fabian

Organizations: Chalmers University of Technology Gothenburg, Sweden

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

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 (MAPFR_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%5\% on narrow and constrained maps and 17%17\% on maps with open spaces. In some cases, the improvements exceed 20%20\%. Doubling the map resolution with classical MAPF recovers less than 3%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 MAPFR_R unlocks significantly higher-quality solutions.

Figures & tables

Figure 1 . Three levels of map connectedness. 4-connectedness includes only cardinal edges, 8-connectedness adds diagonals, and 16-connectedness adds knight’s moves. A representation of a grid map with three different levels of connectedness, known as 2k2^k-neighbourhoods, determining which direct vertex-to-vertex movements are available. Each additional level of connectedness doubles the number of edges outgoing from a vertex.
Figure 2 . The four MovingAI ( Sturtevant, 2012 ) maps on which our main experiments compare the two formulations. White cells are traversable, black cells are not. A visualisation of the four MovingAI maps \mapEmpty, \mapRoom, \mapWarehouse, and \mapMaze, which are used in the main experiments. These maps consist of cells, some traversable and some not. The composition of these cells define the type and difficulty of planning agents in it. For instance, \mapMazecontains many narrow corridors which require more coordination between the agents than, say, \mapEmptywhich is an empty and open space.
Figure 3 . The solution cost reduction of \MAPFR relative to classical MAPF, on four maps (rows) with different connectedness (columns) and agent radius (colours). Each plot shows mean bounds on the cost change, Δ∈[ΔLB,ΔUB]\Delta\in[\Delta_{\mathrm{LB}},\Delta_{\mathrm{UB}}] , together with the minimum ΔLB\Delta_{\mathrm{LB}} and maximum ΔUB\Delta_{\mathrm{UB}} , in percentage. The y-axes for the 4-connected graphs are symmetric-logarithmic while the 8- and 16-connected are linear. Each map has its own agent count on the x-axes. CBS’s success rate is shown below each corresponding plot. The results from the main experiments, showing the change in cost from using \MAPFRinstead of the classical formulation, with upper and lower bounds on the mean change, and the minimum and maximum change included. This figure shows how the difference in solution quality between classical MAPF and \MAPFRchanges depending on the context.
Figure 4 . The solution cost reduction (in percent) from using classical MAPF on the fine map, or \MAPFR with various connectedness levels on both the coarse and fine map, compared to the baseline of classical MAPF on the coarse map. For each setting, the dotted line shows ΔUB\Delta_{\mathrm{UB}} (with dots showing specifically which agent counts were tested), a corresponding thinner line showing ΔLB\Delta_{\mathrm{LB}} , and the shared area showing where the true reduction Δ∈[ΔLB,ΔUB]\Delta\in[\Delta_{\mathrm{LB}},\Delta_{\mathrm{UB}}] must be. The results from refining the map to twice the resolution, using both the classical and \MAPFRformulations. The is figure therefore shows how staying within the classical MAPF formulation and double the resolution of the map gives relatively little in return, while using the \MAPFRformulation significantly improves the solution quality when increasing the connectedness. Increasing both connectedness and the map resolution together result in even higher-quality solutions.
Figure 5 . Three types of lattices, with the agent size fixed and the edge lengths set to the minimum that classical MAPF validity permits. A visualisation of different lattices (triangular, square, and hexagonal), all which the classical MAPF formulation can be applied to. The edge lengths are set to their minimum possible without compromising a solution's validity.

Explore similar work

CardsList

  1. AOC-CBS: Anytime-Optimal Continuous-time Conflict-Based Search for Generalised Multi-Agent Path Finding

    Aug 8, 2026Alvin Combrink, Sabino Francesco Roselli, Martin FabianMulti-Agent Path FindingPath Planning

    Department of Electrical Engineering, Chalmers University of Technology, Gothenburg, Sweden.

  2. Planning over MAPF Agent Dependencies via Multi-Dependency PIBT

    Mar 24, 2026Zixiang Jiang, Yulun Zhang, Rishi Veerapaneni +1Multi-Agent Path FindingPlanning

    University Of Melbourne · Robotics Institute, Carnegie Mellon University

  3. From Discrete Plans to Real-World Execution: A World-Model-Driven Framework for Execution-Aware Multi-Agent Path Finding

    Nov 26, 2025Jingtian Yan, Shuai Zhou, He Jiang +2Multi-Agent Path FindingMulti-Robot Motion Planning

    This paper was produced by the IEEE Publication Technology Group. They are in Piscataway, NJ.