Paper deep dive
The Cost of Classical Multi-Agent Path Finding
Alvin Combrink, Sabino Francesco Roselli, Martin Fabian
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 10/8/2026, 6:04:38 AM
Summary
This paper investigates the solution quality gap between Classical Multi-Agent Path Finding (MAPF) and Continuous-time MAPF (MAPF_R). It finds that MAPF_R improves solution quality by at least 5% on narrow maps and 17% on open maps compared to classical MAPF. Increasing map resolution in classical MAPF recovers less than 3% of this loss, indicating that the forfeited quality cannot be easily regained through computational resources alone.
Entities (6)
Relation Signals (4)
AOC-CBS → implements → MAPF_R
confidence 95% · AOC-CBS (Combrink et al., 2026a) is an anytime-optimal MAPF_R algorithm
CBS → implements → Classical MAPF
confidence 95% · CBS (Sharon et al., 2015) is a classical MAPF algorithm that searches on two levels to find an optimal solution.
MAPF_R → improvessolutionqualityover → Classical MAPF
confidence 95% · 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.
Map Resolution Increase → recoverslessthan → 3%
confidence 90% · 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.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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 (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.
Tags
Links
- Source: https://arxiv.org/abs/2610.10100v1
- Canonical: https://arxiv.org/abs/2610.10100v1
Trouble viewing inline? Open PDF directly →
Full Text
58,964 characters extracted from source content.
Expand or collapse full text
The Cost of Classical Multi-Agent Path Finding Alvin Combrink Affiliation: Chalmers University of Technology, Gothenburg, Sweden email: combrink@chalmers.se , Sabino Francesco Roselli Affiliation: Chalmers University of Technology, Gothenburg, Sweden email: rsabino@chalmers.se and Martin Fabian Affiliation: Chalmers University of Technology, Gothenburg, Sweden email: fabian@chalmers.se 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 ( ) 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 significantly higher-quality solutions. Keywords: Classical MAPF, Continuous-time MAPF, Optimality 1. Introduction Multi-Agent Path Finding (MAPF) is the problem of planning agent movements on a graph, to get them from where they are to where they need to be without conflicting with each other. This is often paired with an objective function defining a solution’s quality by way of a cost, with optimal solutions minimizing the cost. The applications are many, including warehouses and factories (Wurman et al., 2008; Ma and Koenig, 2017; Brown et al., 2020; Varambally et al., 2022), video games (Snape et al., 2012; Ma et al., 2017; Harabor et al., 2022), road traffic (Li et al., 2023; Goenawan, 2025), and airport management (Morris et al., 2016; Li et al., 2019a). The overwhelming majority of MAPF research adopts the classical MAPF formulation (Stern et al., 2019), for which decades of sustained research has enabled algorithms to find optimal solutions for the low hundreds of agents (Sharon et al., 2015; Boyarski et al., 2015; Li et al., 2019b; Li et al., 2019c), and suboptimal (Ma et al., 2019; Zhang et al., 2022), bounded-suboptimal (Li et al., 2021b; Barer et al., 2014), and anytime algorithms (Li et al., 2022; Okumura, 2023; Okumura, 2024) to the thousands. Scalability is bounded in principle by NP-hardness (Yu and LaValle, 2013; Agafonov and Yakovlev, 2025), yet the proliferation of increasingly scalable algorithms suggests we have not yet reached these limits. Solution quality, on the other hand, is bounded absolutely by the chosen problem formulation; no amount of algorithmic progress can produce a higher-quality solution while remaining in the formulation’s solution space. The dominance of classical MAPF is historically well-founded since the assumptions it makes supposedly ease the search, and for much of the MAPF field’s history, more faithful formulations were simply intractable at useful scales. Simply put, a solution to a simplified model was better than no solution at all. In the classical formulation, time is discrete, graphs are limited to unit-length edges, and agents conflict when simultaneously occupying the same vertex or traversing the same edge at the same time (Stern et al., 2019). If agents model real robots in a shared physical space, this formulation restricts how and to what resolution the environment can be modelled, leaves agent shapes implicitly bounded in size to the graph, and incurs artificial delays that consequently inflate the solution cost (we elaborate on this in Section 3). Continuous-time MAPF ( ) (Andreychuk et al., 2022) is perhaps the most similar formulation to drop these assumptions, such that agents can traverse edges at any real-valued time, these traversals or waits at vertices taking any positive real-valued duration, and conflicts considering the agents’ shapes. therefore model a wider range of physical systems, including agent movements for which classical solutions cannot guarantee collision-freeness. not lift all limiting assumptions, such as agents only moving along a discrete set of trajectories instead of in the entire continuous space; we do not investigate the cost of those assumptions here. Classical MAPF nevertheless remains the wide-spread formulation. the other hand has received relatively little attention. However, recent advances (Kasaura et al., 2022; Combrink et al., 2025; Andreychuk et al., 2022; Andreychuk et al., 2021; Combrink et al., 2026b; Combrink et al., 2026a) pushing hundreds of agents demonstrate that also responds to research effort. This makes the following question increasingly relevant: What solution quality does the classical MAPF formulation forfeit relative to , and in what contexts is this forfeit substantial? Existing work only partially answers this question. Using the CCBS (Andreychuk et al., 2022) and variants of ICTS (Walker et al., 2018), solution quality improves by 55–25%25\% on average when adding non-cardinal edges (such as diagonals) to the map. Any-Angle MAPF (Daniel et al., 2010) maximises these non-cardinal edges, for which Any-Angle CCBS (Yakovlev et al., 2024) provides an illustrative example of such a solution having ∼22% 22\% lower cost compared to only using cardinal edges. CE-CBS (Janovská and Surynek, 2024), a discrete-time inexact method addressing the related problem of continuous space rather than continuous time, reports solution quality increasing as agent radius decreases. Finally, (Zang et al., 2026) compares the exact classical MAPF algorithm CBS (Sharon et al., 2015) with several inexact , finding lower-cost on only some problems. These existing works do not fully address the question: ICTS (Walker et al., 2018) relies on time discretization and reports results for only a set number of agents; CCBS is a suboptimal (Li et al., 2025; Wu et al., 2026b) (although often near-optimal (Combrink et al., 2026b)) algorithm and reports only aggregated results; and Any-Angle CCBS’s correctness guarantees build on CCBS’s without, in our opinion, delivering sufficient theoretical proof that it does not inherit CCBS’s inexactness. A suboptimal improving on the optimal classical MAPF solution still does not reveal the true magnitude of the gap, and since a classical MAPF solution is a valid 11 1 Assuming both problems use the same map and that the classical solution respects the requirements for conflict-freeness in the real system (see Section 3)., not improving on the optimal classical solution says only something about the algorithm that was used. Therefore, these existing studies work only with suboptimal , adjacent problems, or without direct and comprehensive comparisons with the classical formulation. Recent work provides an exact , OC-CBS (Combrink et al., 2026b). Our preliminary comparisons between OC-CBS and CBS, however, revealed OC-CBS’s relatively poor scalability to impede a comparison at sufficiently high agent counts within a reasonable runtime. AOC-CBS (Combrink et al., 2026a) is an anytime-optimal , building on OC-CBS, which early on provides an incumbent solution and progressively refines it until eventually converging on an optimal solution. Although AOC-CBS is comparable to OC-CBS for finding optimal solutions, it importantly provides bounds on the optimal cost, thereby enabling a comparison between the classical and at higher agent counts without necessarily converging. This work contributes the following. First, we give a direct comparison between the optimal cost of classical MAPF and . Using AOC-CBS’s bounds rather than requiring an optimal allows the comparison to reach higher agent counts while still keeping the comparison on the formulations rather than on the algorithms. Second, we quantify this cost difference over discrete versus continuous time, agent size, and map connectedness, on four maps ranging from open spaces to narrow corridors. We also test whether refining the map resolution allows classical MAPF to recover the loss. Third, we identify the contexts in which classical MAPF remains an appropriate simplification, and those in which the forfeited solution quality motivates further efforts. Our repository22 2 https://github.com/Adcombrink/classical-vs-continuous-mapf provides the full results and settings. 2. Background We formally introduce the classical MAPF and , as well as their respective algorithms CBS and AOC-CBS used here. 2.1. Classical MAPF The classical MAPF formulation (Stern et al., 2019) is posed on an undirected graph =⟨,ℰ⟩G= ,E with vertices V and edges ℰ⊆×E ×V. Each agent a∈a is initially at a unique start sa∈s_a and must reach a unique goal ga∈g_a . Time is discrete; at every timestep, each agent either waits at its current vertex for another timestep (wait action), or moves along an adjacent edge to arrive at a neighbouring vertex at the next timestep (move action). Two agents conflict if they are located at the same vertex or traverse the same edge at the same timestep. A solution consists of one plan for each agent a∈a , with a’s plan specifying a sequence of actions that start at sas_a, end at gag_a, and do not conflict with any other plans. There exist many ways to rank solutions. Here, we use the Sum-of-Costs (SOC): the cost of a plan is its duration (timestep of the last move action); SOC is the sum over all plan costs, which an optimal solution minimises. 2.2. Continuous-time MAPF The is originally introduced in (Andreychuk et al., 2022) and further generalised in (Combrink et al., 2026a). For brevity, we present a specified version in 2D space with homogeneous and circular agents. Compared to the classical formulation, time in no longer discrete: move actions can happen at any real-valued time and take any positive time to complete, and agents can wait at vertices for any positive duration. Each vertex v∈v maps to a specific position in ℝ2R^2 where an agent waiting at v is located. Similarly, an edge e∈ℰe defines a trajectory ℝ↦ℝ2R ^2 mapping from time to a position where an agent traversing e is located. Conflicts now consider the agents’ shapes, with two agents conflicting if their shapes overlap. Furthermore, since conflicts are defined by the agents’ positions and shapes instead of their location on the graph, changing the shapes also changes what an optimal solution is. For instance, multiple agents can traverse the same edge simultaneously, separated by just enough space to not conflict. 2.3. Conflict-Based Search CBS (Sharon et al., 2015) is a classical MAPF algorithm that searches on two levels to find an optimal solution. A high-level search is done in a binary constraint tree (CT): every CT node represents a candidate solution and a set of constraints; every plan in a node’s candidate solution is found using a low-level planner and has minimum duration while satisfying the node’s constraint set. The CT initially contains only the root with an empty constraint set, with every agent plan representing the shortest path without considering conflicts with other agents. At every iteration of the search, the CT leaf node with the minimum candidate solution cost is selected for expansion. If this node’s candidate solution is a solution, then it is returned as the optimal. Otherwise, the node is expanded by spawning two child nodes that inherit the current node’s constraint set, selecting a conflict, creating one constraint for each agent involved in the conflict, and adding each constraint to a respective child node. The candidate solutions at these new child nodes are replanned by the low-level planner to satisfy the expanded constraint set. This method is guaranteed to produce an optimal solution if one exists. 2.4. Anytime-Optimal Continuous-time CBS AOC-CBS (Combrink et al., 2026a) is an anytime-optimal that early on produces an incumbent solution, and over the algorithm’s runtime improves the solution to eventually return the optimal, all while providing bounds on the optimal cost. It is based on OC-CBS which in turn is based on the continuous-time version of CBS, CCBS (Andreychuk et al., 2022). AOC-CBS’s search is therefore similar in structure to CBS, consisting of a high-level search in the CT and a low-level path planner. The main difference with CBS is that the constraints in AOC-CBS are posed in continuous time, and the low-level path planner uses SIPP (Phillips and Likhachev, 2011) to work in continuous time. This search forms the lower bound on the optimal cost; just like CBS, it searches optimistically from the bottom up, starting without any conflict-avoiding constraints and progressively adding them until a conflict-free solution is produced. Since constraints are only ever added during expansions, the lowest-cost candidate solution over all CT leaf nodes provides a lower bound on the optimal cost. Unlike its predecessors, AOC-CBS runs a portfolio of policies that select and expand CT nodes in parallel, thereby using multiple CPU processors. Each policy also applies a configurable set of repair functions that search for a potentially suboptimal incumbent solution. The best-found incumbent is made available even if the optimal has yet to be found, while also forming an upper bound on the optimal cost. 3. The Cost of the Classical MAPF Assumptions This section discusses the implications of the classical MAPF assumptions and qualitatively motivates why they are believed to worsen solution quality. The discussion is set in the context of agents representing physical robots in a shared space, with conflicts representing collisions. The assumptions discussed here are that time is discrete and conflicts are defined only by the agents’ locations on the graph and not by their spatial positions or shapes. From these assumptions come interconnected and limiting implications that concern both the validity (conflict-freeness) and the quality of a solution when applied to the real system. Synchronised timesteps induce artificial delays. Consider a graph with variable-length edges. To maintain synchronicity among agents (as discrete time demands), agent 1 traversing a short edge must be delayed to match agent 2 traversing a longer edge. Whether this delay on agent 1 comes via waiting somewhere or by reducing its speed, the cost increases nonetheless. How such a delay is implemented affects the real agents’ spatial positions and therefore requires care to preserve solution validity. As clarified in the next points, using only unit-length edges does not completely avoid these issues; artificial delays will still exist and solution validity depends on more than just edge lengths. Graph-based conflicts induce artificial delays. In the common square grid map layout with unit-length edges and circular agents (Sturtevant, 2012), consider two agents with radius r, where agent 1 moves to agent 2’s vertex while at the same time agent 2 moves away. If agent 2 moves along an edge perpendicular to agent 1’s direction, then agent 1 could start moving 1−22r1-2 2r earlier than agent 2 without colliding. Taking this to the limit with agent 1 leaving at the same time as agent 2 gives the maximum radius under the classical formulation: 1−22r=0⇔r=2/41-2 2r=0 r= 2/4. On the other hand, if agent 2 moves along the edge parallel to agent 1’s direction, then agent 1 can begin its traversal 1−2r1-2r earlier than agent 2. Thus, in this parallel case, even with the classical formulation’s limit r=2/4r= 2/4, agent 1 could move 1−2r≈0.291-2r≈ 0.29 time units earlier. The smaller r is, the earlier agent 1 can traverse its edge relative to agent 2. The artificial delays induced by classical MAPF not considering agent shape therefore grow as the agents get smaller. Graph-based conflicts limit the graph resolution. With discrete time, unit-length edges, and circular agents, agent radius must satisfy r≤sin(α/2)/2r≤ (α/2)/2 units, where α is the smallest angle between any two edges in the graph. In the square grid case, α=90∘⇒r≤2/4α=90 r≤ 2/4. If the agents are any larger than this limit then the classical solution is not guaranteed to be valid. This practically means that the resolution at which the graph represents the physical environment is upper-bounded by the size of the agents. A coarser graph permits only coarser movements, leaving less freedom in how the agents are coordinated. In some cases, the size of existing agents and the required graph resolution may outright prohibit the use of classical MAPF. Graph-based conflicts inhibit spatially overlapping edges. Since conflicts are defined entirely by agent locations on the graph, no two edges can spatially overlap without risking invalidity. This prohibits, e.g., the inclusion of both diagonals of a cell: since two agents traversing each respective diagonal at the same time will be at the centre at exactly the same time, a collision occurs regardless of their shape. Classical MAPF does not consider this a conflict since the agents are on different edges. One workaround could be to only include one of the diagonals, thereby including at least some of these shorter moves. This together with time being discrete, however, leads to the same issue of synchronicity-induced delays as discussed in the first point of this section. It would also reduce the maximum allowed agent radius for validity, due to the smaller angle between edges. (a) 4-connected (b) 8-connected (c) 16-connected 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 $2^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. These limitations of classical MAPF surely reduce its achievable solution quality. After all, a diagonal between two opposing corners of a cell is ∼29% 29\% shorter than the Manhattan distance in 2D, and ∼42% 42\% shorter in 3D. Fig. 1 shows three levels of connectedness (known as 2k2^k-neighbourhoods (Rivera et al., 2017)), going from only cardinal edges (4), to adding diagonals (8), to adding knight’s moves (16). The improvements to cost with increasing connectedness are however diminishing, and is bounded by the cost of each agent travelling the Euclidean distance from their respective start to goal vertices. For instance, going from 4 to 8-connectedness shortens a knight’s move by 19.5%19.5\%, but going from 8 to 16-connectedness shortens the same move by only an additional 7.4%7.4\%. Nonetheless, the potential in cost reduction from even only adding diagonals is significant, which classical MAPF forfeits. Classical MAPF requires unit-length edges, but nothing limits this to square grids. A triangular lattice (see Fig. 5(a)) is, so to speak, 6-connected since there are six different outgoing directions from a vertex, possibly allowing agents to move more directly toward their goal vertices than with 4-connectedness (Fig. 5(b)). This representation must still respect validity limits on agent size relative to the edge length, which is even more constrained for triangles than squares due to the smaller angle between edges. We elaborate further on this in Section 6, though we only investigate square lattices in this study. 3.1. Can Map Resolution Recover the Loss? Considering that classical MAPF solution-validity upper-bounds the graph resolution based on agent size, a natural question that may arise for systems with small agents is: If agents are small, can classical MAPF achieve the same solution quality as refining the map with smaller edges? Our main experiments in Section 5 keep the map static while reducing the size of the agents, which does not test this. In practice, if the agents are small then the map can be made finer until the radius of the agents becomes 2/4 2/4 of an edge length. Using a fine map can only improve the cost, since a solution on a coarse grid is also a solution on a fine grid (assuming the coarse edges are split evenly into fine edges). We argue that the artificial delays induced by agent synchronicity and not considering agent shapes can partly be mitigated by using finer maps, up to the point when the graph cannot be made finer without risking solution validity. However, no amount of refinement can achieve the gains from using non-cardinal edges in the map. Manhattan distance is, after all, the same regardless of how fine the grid is. 4. Study Design The purpose of this study is to compare the SOC of optimal classical MAPF and over (i) discrete and continuous time, (i) various agent sizes, and (i) various levels of graph connectedness. Since the classical formulation only works in discrete time, does not exploit agent shapes, and is not able to handle non-unit-length edges, we only search for the optimal classical MAPF solution on 4-connected maps, implicitly using agents with radius r=2/4r= 2/4, which is then compared with the various along (i)–(i). Comparisons are done on different maps, with the aim of gaining a crude understanding of how graph topology affects the comparison. To this end, we use CBS for obtaining an optimal cost DToptDT_opt of a classical MAPF solution, and AOC-CBS for obtaining a lower bound CTLBCT_LB and an upper bound CTUBCT_UB on the optimal cost of a . We report the bounds ΔLB _LB and ΔUB _UB on the true cost change Δ∈[ΔLB,ΔUB] ∈ [ _LB, _UB ] that an optimal returns relative to an optimal classical MAPF solution, where ΔLB=100⋅(CTLBDTopt−1)andΔUB=100⋅min(0,CTUBDTopt−1). _LB=100· ( CT_LBDT_opt-1 ) _UB=100· (0, CT_UBDT_opt-1 ). Both bounds are multiplied by 100100 to be read in percent. ΔUB _UB is clipped to 00 since any classical solution is also a ; the optimal can only improve on the classical solution. Therefore, we already know that the optimal is less than or equal to DToptDT_opt and therefore that CTUB=DToptCT_UB=DT_opt is a valid upper bound, hence ΔUB≤0% _UB≤ 0\%. However, our repository does provide the unclipped results to allow practitioners to compare these two specific algorithms (CBS and AOC-CBS) in terms of solution quality and runtime performance, which is otherwise outside the scope of this work. We report the mean ΔLB _LB and ΔUB _UB, minimum ΔLB _LB, and maximum ΔUB _UB. For a given map and agent count, these statistics are taken over the set of scenarios (see Section 4.2) for which both ΔLB _LB and ΔUB _UB have been found at every combination of agent radii and connectedness. This is to ensure a fair comparison across these values. In practice, AOC-CBS always returns CTLBCT_LB, and ΔLB _LB is known to be at most 0%0\%, so this set of commonly solved scenarios depends entirely on CBS returning an optimal solution. We therefore also report CBS’s success rate at solving scenarios at each agent count, indicating the amount of data support for the corresponding bounds. The number of agents is increased until the success rate falls below 40%40\% (reporting only on those above) or until the spread of Δ becomes too large to provide any useful information. 4.1. Evaluation Dimensions Isolating time from agent size is not entirely possible since continuous time is required to exploit agent shapes, and agent shapes are required for continuous time else the agents can be moved arbitrarily close to each other. For this reason, the closest we get in this work to a pure comparison between discrete and continuous time is on 4-connected graphs with agent radius r=2/4r= 2/4. These tests show to what extent avoid delays induced by agent movement being synchronised and their shapes not being considered. To evaluate the impact of agent size on solution quality, we sweep over agent radii r∈2/16,2/8,2/4r∈ \ 2/16, 2/8, 2/4 \. The sweep is limited to at most 2/4 2/4 since any larger would compromise the validity of the classical MAPF solutions, while lower radii would not. As discussed in the previous section, the classical formulation enforcing synchronised actions and using shape-agnostic conflict definitions incurs artificial delays. With smaller agents, these delays grow relatively larger. We therefore aim to understand how large the impact of agent size is. The impact of graph connectedness on solution quality is evaluated by using the three levels of connectedness shown in Fig. 1: 4-connected (cardinal movements), 8-connected (+ diagonals), and 16-connected (+ knight’s moves). Non-cardinal edges are only added if an agent with r=2/4r= 2/4 can traverse it without intersecting a non-traversable cell; these same edges are used for all agent radii. The addition of more edges yields a richer set of move actions that allow both for shorter paths and a greater coverage of the space for more options when avoiding collisions. The above dimensions are cross-evaluated to understand their combined effect on solution quality. 4.2. Maps and Scenarios Our main experiments are done on four maps from the MovingAI benchmark suite (Sturtevant, 2012): Empty-32-32, Room-64-64-8, Warehouse-10-20-10-2-2, and Maze-32-32-2, shown in Fig. 2. These maps provide a crude progression from open spaces to narrow corridors and choke-points. Large open spaces allow for more non-cardinal edges and a larger number of equivalent-cost paths for agents to take. They also lead to more localised conflict avoidance since agents in general only need short delays to avoid other agents. Narrow corridors and tight spaces, on the other hand, do not allow for as many non-cardinal edges, and they also incur higher delays due to larger mutually exclusive areas. For instance, an agent must wait for another agent to clear an entire corridor before it can itself move through it. (a) Empty-32-32 (b) Room-64-64-8 (c) Warehouse-10-20-10-2-2 (d) Maze-32-32-2 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 , , , and , 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, many narrow corridors which require more coordination between the agents than, say, is an empty and open space. We use the 25 random scenarios provided by (Sturtevant, 2012) for each map: a scenario defines a list of start-goal pairs; a problem with n agents is constructed by assigning to the agents the first n start-goal pairs in the scenario. An exception is made for Empty-32-32 which instead uses scaled Empty-16-16 scenarios, to keep results on these two maps comparable for the experiments described in the next section. 4.3. Leveraging Map Resolution Based on Section 3.1, we aim to test how much of ’s solution quality the classical MAPF formulation can recover by using a finer map resolution. To do so, we compare solution quality on Empty-32-32 (a 32×3232× 32 grid) with Empty-16-16 (a 16×1616× 16 grid); Empty-32-32 has twice the resolution. Practically, we use agent radius 2/4 2/4 on Empty-32-32 and 2/8 2/8 on Empty-16-16, and use Empty-16-16’s random scenarios on both maps but with start-goal positions scaled by 22 and solution costs by 1/21/2 when applied to Empty-32-32. The problems on both maps are therefore equivalent, except that the effective graph resolution is doubled on Empty-32-32, allowing for agents to take steps of half the length compared to on Empty-16-16. We therefore say that Empty-32-32 is the finer map, while Empty-16-16 is the coarser. 4.4. Settings and Hardware All experiments are run on AMD EPYC 9755 Turin 2.7 GHz 128-core processors, with each run using at most 4-cores and 16 GB of DDR5 memory. Both CBS and AOC-CBS are given a 300 second runtime limit. We use the default CBS settings as provided in the implementation by (Li et al., 2021a). For AOC-CBS, we use a four-policy (4 CPU core) gap-cadence portfolio, which prioritises finding solutions by applying repair functions while the optimality gap upper bound is above 5%5\%, and thereafter gradually reduces repair function use to instead focus on raising CTLBCT_LB. Our repository provides detailed settings for each algorithm. 5. Results Fig. 3 shows the cost reduction of to classical MAPF on each of the maps, connectedness levels, and agent radii. For a given graph corresponding to a specific map and connectedness, each colour corresponds to a specific agent radius, for which there are four lines: the two thicker lines show the mean ΔLB _LB and ΔUB _UB over scenarios, bounding the shaded area within which the true value of Δ is; the two thinner lines above and below (overlapping in some places) show the maximum ΔUB _UB and minimum ΔLB _LB over scenarios; and the dots show which agent counts were tested. CBS’s success rate over scenarios is shown under each subplot. Figure 3. The solution cost reduction of 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] ∈[ _LB, _UB], together with the minimum ΔLB _LB and maximum ΔUB _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 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 depending on the context. To summarise the main findings before taking a closer look: on 4-connected maps, ΔLB _LB extends down to at most only a few percent, meaning that the cost reduction of classical MAPF is relatively small at these tested agent counts. That is, the direct improvement from time being continuous and agent shapes being considered is limited, despite smaller agents allowing for lower-cost solutions (most clearly seen in Fig. 3 at lower agent counts). The results instead show that the value of from admitting higher levels of connectedness, which improves the cost change by at least an order of magnitude. The advantages from higher connectedness and smaller agents appear to be additive, each contributing to tighter [ΔLB,ΔUB][ _LB, _UB] bounds at lower costs. Across the maps, we see the improvements from higher connectedness decreasing as the open spaces become less, which is expected since narrower maps allow for fewer non-cardinal edge connections. (i) Discrete versus continuous time: The 4-connected maps with r=2/4r= 2/4 provide our cleanest comparison between discrete and continuous time, without the effects of smaller agents or higher map connectedness. Keep in mind, however, that agent shapes are still considered, meaning that this is not a pure discrete/continuous time comparison. The results show ΔLB _LB reaching down to at most only a few percent, meaning that the does relatively little to improve the solution quality at these agent counts. The spread of Δ remains relatively high throughout the agent count range, which means that AOC-CBS for these specific cases is unable to narrow the bounds by much within the given runtime. (i) Smaller agents: Smaller agent radii generally improve both ΔLB _LB and ΔUB _UB across all maps and connectedness levels. The cases at low agent counts where ΔUB _UB for smaller agents is below ΔLB _LB for larger agents empirically confirms that smaller agents allow for higher-quality solutions. ΔUB _UB corresponds to actual found by AOC-CBS; the fact that smaller agent radii decreases ΔUB _UB means that smaller agents may make it easier for AOC-CBS to find solutions; the same may be true for other . This makes intuitive sense since collisions become less likely when agent sweep-volumes are smaller. However, AOC-CBS finding lower-cost solutions is confounded with the fact that smaller agents permit lower-cost solutions, and so we refrain from drawing any more conclusions regarding the impact of agent size on the ease of finding solutions. With smaller agents, the spread of Δ is narrower at the lower end of the agent range, revealing a trend of decreasing Δ with more agents. This suggests that off with more agents. However, since AOC-CBS is unable to maintain sufficiently narrow bounds as the number of agents increases, we are not able to draw any further conclusions regarding how far this trend of decreasing Δ goes. We leave these questions for future investigations using more scalable than AOC-CBS. (i) Map connectedness: Increasing map connectedness has by far the largest impact on solution quality out of all our tested dimensions. Going from 4-connectedness to 16-connectedness on Empty-32-32 improves Δ from fractions of a percent to over 17%17\% on average. This is due to the expanded set of move actions shortening paths and offering more alternatives for conflict avoidance. The results show that the largest increase can already be achieved with 8-connectedness, while 16-connectedness provides moderate further improvements. The reduction in cost from higher connectedness tapers off over the maps Empty-32-32 → -64-64-8 → -10-20-10-2-2 → -32-32-2, when qualitatively going from most to least open spaces. However, even on Maze-32-32-2 with long and narrow corridors, the average improvement is still significant. 5.1. Impact of Higher Map Resolution Fig. 4 visualises the cost improvement from doubling the map resolution. The 4-connected solutions are clipped to the solution quality of the classical MAPF solutions on the same map, since they are also a solution to the . By doubling the map resolution, with classical MAPF or , a cost reduction of less than 3%3\% is achieved for these agent counts. It is not possible to increase the resolution to achieve further improvements without compromising the validity of the classical MAPF solutions; this is therefore the extent of the improvements that are possible through a higher map resolution in this context. These gains are marginal in comparison to increasing the map connectedness, which reduces the cost by more than 16%16\% with 8-connectedness and 21%21\% with 16-connectedness. These results mirror those in Fig. 3: here we show that using a twice as fine map improves costs slightly more than what continuous-time and shape-awareness do on their own, but still relatively little compared to using higher map connectedness. Interestingly, ΔLB _LB is almost identical across resolutions, however, ΔUB _UB on the fine map (most pronounced with 4 and 8-connectedness) is significantly closer to ΔLB _LB. This means that using a finer map does not help AOC-CBS raise CTLBCT_LB that much, but it seems to help AOC-CBS find lower-cost solutions and thereby lower CTUBCT_UB. Figure 4. The solution cost reduction (in percent) from using classical MAPF on the fine map, or 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 _UB (with dots showing specifically which agent counts were tested), a corresponding thinner line showing ΔLB _LB, and the shared area showing where the true reduction Δ∈[ΔLB,ΔUB] ∈[ _LB, _UB] must be.The results from refining the map to twice the resolution, using both the classical and . 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 significantly improves the solution quality when increasing the connectedness. Increasing both connectedness and the map resolution together result in even higher-quality solutions. 6. Discussion The results show that continuous time and shape-awareness do improve solution quality on their own, but only by a few percent at the agent counts we tested. Higher connectedness improves it by at least an order of magnitude more. This is not to say that continuous-time or shape-awareness are not needed, in actuality they are necessary for enabling non-unit-length and spatially overlapping edges. A cardinal edge and a diagonal respectively have lengths 11 and 2 2, which no common timestep divides, so a formulation with synchronised timesteps cannot represent both faithfully. Besides, since classical MAPF defines conflicts by graph location, the two diagonals of a cell cannot both be included without risking the solution’s validity. Adding diagonals therefore requires relaxing both the discrete-time and graph-based conflict assumptions. This is also why, to our knowledge, no classical MAPF algorithm incorporates non-unit-length edges. Therefore, the true cost of the classical MAPF assumptions is mainly paid through ruling out a richer set of move actions. The experiments over different map topologies show that classical MAPF forfeits a significant part of the achievable solution quality on maps with open spaces, where many non-cardinal edges would otherwise be possible. This loss is more modest on maps with narrow corridors and tight spaces. The classical formulation therefore remains a reasonable simplification on these more constrained maps, especially given how scalable and robust its algorithms have become after decades of research effort. If achieve the level of scalability that real-world applications require, then the additional solution quality that they unlock becomes practically attainable. Our results also show that much of the solution quality is attained already at 8-connectedness; for this reason research effort may be best spent on these lower connectedness levels. Furthermore, although MAPF research often uses square lattice graphs, classical MAPF does not require that. Higher-quality solutions may be obtained through other lattices, such as the triangular or hexagonal lattices in Fig. 5. We acknowledge the practical difficulty of this, since many real-world settings are built around right angles. Nonetheless, with agent radius limited to r≤sin(α/2)/2r≤ (α/2)/2 where α is the smallest angle between adjacent edges in the graph, this gives for triangular lattices r≤0.25r≤ 0.25 (α=60∘α=60 ), for square lattices r≲0.35r 0.35 (α=90∘α=90 ), and for hexagonal lattices r≲0.43r 0.43 (α=120∘α=120 ). Larger permitted agent radii mean that a finer map resolution can be used; although the actual density of vertices is also decided by the lattice’s shape. The shape also determines the connectedness: six for triangles, four for squares, three for hexagons. This presents a trade-off, where more connected lattices force longer edges. However, as our results show, connectedness has a far larger impact on solution quality than map resolution. We leave investigations into the trade-off between different lattices to future work. (a) Triangle (b) Square (c) Hexagon 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. Another interesting direction, based on connectedness being the strongest improver of solution quality, is MAPF with Asynchronous Actions (Wu et al., 2026b; Ren et al., 2021). There, classical MAPF’s discrete-time assumption is relaxed to allow for non-unit-length edges, while graph-based conflicts are still kept. The latter means that agent sizes and edge lengths are still bounded to each other for solution validity, and overlapping edges are still prohibited. However, since it is more similar to the classical MAPF formulation than what , it is possible that many of the algorithmic developments extending classical MAPF scalability could be transferred to this formulation. Although, for the time being we have yet to see it applied to agent counts of the same magnitude as what classical MAPF has been applied to (Ren et al., 2021; Wu et al., 2026a; Wu et al., 2026b). AOC-CBS returns valid bounds on the optimal , so the direction and validity of our results do not depend on which specific algorithm was used. What does depend on it is the width of these bounds and the agent count that can be reached while keeping these bounds narrow enough to offer insights. This is clearest on the map Maze-32-32-2 with r=2/4r= 2/4 and 4-connectedness, where at relatively small agent counts the bounds extend from 0%0\% down to −10%-10\%, effectively offering very little insight. We suspect the cause of this to be long corridors, which are known to be particularly difficult for CBS-style algorithms. The CBS implementation used here (Li et al., 2021a) uses specific techniques to address this, however, corresponding techniques have to our knowledge not yet been developed for continuous-time and are therefore not implemented in AOC-CBS. Narrower bands would tell us whether or not Δ keeps decreasing as the agent count grows, thereby answering the question regarding whether the cost reduction from continuous-time and shape-awareness alone eventually become significant or not. Since classical MAPF, which is NP-hard (Yu and LaValle, 2013), as far as we know there will always be an agent count beyond which the bounds widen; a more scalable algorithm than AOC-CBS only moves that point further out. This study uses only 2D grid maps. A 3D diagonal is even shorter than a 2D diagonal when compared to the corresponding Manhattan distance. Both classical MAPF and also be applied to 3D; therefore, comparing these two formulations in 3D space would make for interesting future work. Furthermore, 2D grid maps do not exercise the full representational power of . Roadmaps, which need not follow any regular structure, can be adaptively tuned to have a higher resolution in parts of the environment where it is needed, such as at junctions and high-traffic areas in the environment. This freedom is not present in classical MAPF since map resolution is limited to agent size. Our results should therefore be read as a conservative estimate of what the classical formulation forfeits. Finally, classical MAPF plans for synchronous systems and generally needs post-processing before non-holonomic robots can execute them (Hönig et al., 2016; Okumura et al., 2026). kinodynamically feasible trajectories directly (Combrink et al., 2026a), so the cost gap we measure is likely a lower bound on the gap in execution. 7. Conclusion Classical MAPF has been the dominant MAPF formulation for many years, with the scalability of modern algorithms enabling the planning of thousands of agents. However, classical MAPF fundamentally assumes discrete time and graph-based conflicts, thereby forfeiting solution quality. This work investigated the extent of this forfeit by comparing optimal classical MAPF solutions to those of Continuous-time MAPF ( ), a formulation that relaxes several of the classical MAPF assumptions. A comparison was done over discrete and continuous time, various agent sizes, and graph connectedness, resolution, and topology. At our tested agent counts, continuous-time and shape-awareness alone account for marginal improvements; however, they enable an expanded set of move actions that lead to significant improvements in solution quality. Average improvements on narrow and constrained maps are at least 5%5\%, on open maps at least 17%17\%, and in some cases more than 20%20\%. We also find that naively refining the map, which cannot be done unboundedly in classical MAPF without compromising the solution’s validity, only slightly raises solution quality. Classical MAPF therefore cannot recover what its assumptions forgo through more compute. We do however pinpoint contexts where the forfeit is only moderate: maps with narrow corridors and tight spaces, where agents are relatively large compared to the graph edges, and where only cardinal movements are possible. This work therefore quantifies what classical MAPF loses through its assumptions, which had previously only been partially observed or hinted at. Acknowledgements. Computational resources on the Arrhenius supercomputer were provided by the National Academic Infrastructure for Supercomputing in Sweden (NAISS), funded by the Swedish Research Council. References Agafonov and Yakovlev (2025) A. Agafonov and K. Yakovlev Multi-agent path finding for large agents is intractable. In ECAI 2025, p. 4856–4863. External Links: Document, Link Cited by: §1. Andreychuk et al. (2021) A. Andreychuk, K. Yakovlev, E. Boyarski, and R. Stern Improving continuous-time conflict based search. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 35, p. 11220–11227. Cited by: §1. Andreychuk et al. (2022) A. Andreychuk, K. Yakovlev, P. Surynek, D. Atzmon, and R. Stern Multi-agent pathfinding with continuous time. Artificial Intelligence 305, p. 103662. External Links: Document Cited by: §1, §1, §1, §2.2, §2.4. Barer et al. (2014) M. Barer, G. Sharon, R. Stern, and A. Felner Suboptimal variants of the conflict-based search algorithm for the multi-agent pathfinding problem. In Proceedings of the international symposium on combinatorial Search, Vol. 5, p. 19–27. Cited by: §1. Boyarski et al. (2015) E. Boyarski, A. Felner, R. Stern, G. Sharon, O. Betzalel, D. Tolpin, and E. Shimony ICBS: the improved conflict-based search algorithm for multi-agent pathfinding. In Proceedings of the International Symposium on Combinatorial Search, Vol. 6, p. 223–225. Cited by: §1. Brown et al. (2020) K. Brown, O. Peltzer, M. A. Sehr, M. Schwager, and M. J. Kochenderfer Optimal sequential task assignment and path finding for multi-agent robotic assembly planning. In 2020 IEEE International Conference on Robotics and Automation (ICRA), p. 441–447. Cited by: §1. Combrink et al. (2025) A. Combrink, S. F. Roselli, and M. Fabian Prioritized planning for continuous-time lifelong multi-agent pathfinding. In 2025 11th International Conference on Control, Decision and Information Technologies (CoDIT), Vol. 1, p. 1454–1459. External Links: Document Cited by: §1. Combrink et al. (2026a) A. Combrink, S. F. Roselli, and M. Fabian AOC-CBS: anytime-optimal continuous-time conflict-based search for generalised multi-agent path finding. External Links: 2608.08175, Link Cited by: §1, §1, §2.2, §2.4, §6. Combrink et al. (2026b) A. Combrink, S. F. Roselli, and M. Fabian Optimal multi-agent path finding in continuous time. External Links: 2508.16410, Link Cited by: §1, §1, §1. Daniel et al. (2010) K. Daniel, A. Nash, S. Koenig, and A. Felner Theta*: any-angle path planning on grids. Journal of Artificial Intelligence Research 39, p. 533–579. Cited by: §1. Goenawan (2025) C. R. Goenawan ASTM : autonomous smart traffic management system using artificial intelligence CNN and LSTM. External Links: 2410.10929 Cited by: §1. Harabor et al. (2022) D. Harabor, R. Hechenberger, and T. Jahn Benchmarks for pathfinding search: iron harvest. In Proceedings of the International Symposium on Combinatorial Search, Vol. 15, p. 218–222. Cited by: §1. Hönig et al. (2016) W. Hönig, T. Kumar, L. Cohen, H. Ma, H. Xu, N. Ayanian, and S. Koenig Multi-agent path finding with kinematic constraints. In Proceedings of the International Conference on Automated Planning and Scheduling, Vol. 26, p. 477–485. Cited by: §6. Janovská and Surynek (2024) K. Janovská and P. Surynek Multi-agent path finding in continuous environment. External Links: 2409.10680, Link Cited by: §1. Kasaura et al. (2022) K. Kasaura, M. Nishimura, and R. Yonetani Prioritized safe interval path planning for multi-agent pathfinding with continuous time on 2d roadmaps. IEEE Robotics and Automation Letters 7 (4), p. 10494–10501. External Links: Document Cited by: §1. Li et al. (2025) A. Li, Z. Chen, M. Vered, and D. Harabor Revisiting conflict based search with continuous-time. External Links: 2501.07744 Cited by: §1. Li et al. (2022) J. Li, Z. Chen, D. Harabor, P. J. Stuckey, and S. Koenig MAPF-LNS2: fast repairing for multi-agent path finding via large neighborhood search. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 36, p. 10256–10265. Cited by: §1. Li et al. (2019a) J. Li, M. Gong, Z. Liang, W. Liu, Z. Tong, L. Yi, R. Morris, C. Pasareanu, and S. Koenig Departure scheduling and taxiway path planning under uncertainty. In AIAA Aviation 2019 Forum, p. 2930. External Links: Document, Link, https://arc.aiaa.org/doi/pdf/10.2514/6.2019-2930 Cited by: §1. Li et al. (2019b) J. Li, D. Harabor, P. J. Stuckey, A. Felner, H. Ma, and S. Koenig Disjoint splitting for multi-agent path finding with conflict-based search. In Proceedings of the international conference on automated planning and scheduling, Vol. 29, p. 279–283. Cited by: §1. Li et al. (2019c) J. Li, D. Harabor, P. J. Stuckey, H. Ma, and S. Koenig Symmetry-breaking constraints for grid-based multi-agent path finding. In Proceedings of the AAAI conference on artificial intelligence, Vol. 33, p. 6087–6095. Cited by: §1. Li et al. (2021a) J. Li, D. Harabor, P. J. Stuckey, H. Ma, G. Gange, and S. Koenig Pairwise symmetry reasoning for multi-agent path finding search. Artificial Intelligence 301, p. 103574. External Links: ISSN 0004-3702, Document, Link Cited by: §4.4, §6. Li et al. (2023) J. Li, T. A. Hoang, E. Lin, H. L. Vu, and S. Koenig Intersection coordination with priority-based search for autonomous vehicles. Proceedings of the AAAI Conference on Artificial Intelligence 37 (10), p. 11578–11585. External Links: Document Cited by: §1. Li et al. (2021b) J. Li, W. Ruml, and S. Koenig EECBS: a bounded-suboptimal search for multi-agent path finding. In Proceedings of the AAAI conference on artificial intelligence, Vol. 35, p. 12353–12362. Cited by: §1. Ma et al. (2019) H. Ma, D. Harabor, P. J. Stuckey, J. Li, and S. Koenig Searching with consistent prioritization for multi-agent path finding. In Proceedings of the AAAI conference on artificial intelligence, Vol. 33, p. 7643–7650. Cited by: §1. Ma and Koenig (2017) H. Ma and S. Koenig AI buzzwords explained: multi-agent path finding (MAPF). AI Matters 3 (3), p. 15–19. External Links: Document Cited by: §1. Ma et al. (2017) H. Ma, J. Yang, L. Cohen, T. K. Kumar, and S. Koenig Feasibility study: moving non-homogeneous teams in congested video game environments. Proceedings of the AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment 13 (1), p. 270–272. External Links: Document Cited by: §1. Morris et al. (2016) R. Morris, C. S. Pasareanu, K. S. Luckow, W. Malik, H. Ma, T. S. Kumar, and S. Koenig Planning, scheduling and monitoring for airport surface operations.. In AAAI Workshop: Planning for Hybrid Systems, p. 608–614. Cited by: §1. Okumura et al. (2026) K. Okumura, G. Yang, Z. Gao, H. Woo, and A. Prorok Concrete multi-agent path planning enabling kinodynamically aggressive maneuvers. npj Robotics 4 (1), p. 20. External Links: Document Cited by: §6. Okumura (2023) K. Okumura Improving LaCAM for scalable eventually optimal multi-agent pathfinding. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence, IJCAI ’23. External Links: Document Cited by: §1. Okumura (2024) K. Okumura Engineering lacam∗ : towards real-time, large-scale, and near-optimal multi-agent pathfinding. In Proceedings of International Conference on Autonomous Agents and Multiagent Systems (AAMAS), Cited by: §1. Phillips and Likhachev (2011) M. Phillips and M. Likhachev SIPP: safe interval path planning for dynamic environments. In 2011 IEEE International Conference on Robotics and Automation, Vol. , p. 5628–5635. External Links: Document Cited by: §2.4. Ren et al. (2021) Z. Ren, S. Rathinam, and H. Choset Loosely synchronized search for multi-agent path finding with asynchronous actions. In 2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), p. 9714–9719. Cited by: §6. Rivera et al. (2017) N. Rivera, C. Hernández, and J. Baier Grid pathfinding on the 2k neighborhoods. In Proceedings of the AAAI conference on artificial intelligence, Vol. 31. Cited by: §3. Sharon et al. (2015) G. Sharon, R. Stern, A. Felner, and N. R. Sturtevant Conflict-based search for optimal multi-agent pathfinding. Artificial Intelligence 219, p. 40–66. Cited by: §1, §1, §2.3. Snape et al. (2012) J. Snape, S. J. Guy, M. C. Lin, D. Manocha, and J. Van den Berg Reciprocal collision avoidance and multi-agent navigation for video games. In MAPF@AAAI, External Links: Link Cited by: §1. Stern et al. (2019) R. Stern, N. Sturtevant, A. Felner, S. Koenig, H. Ma, T. Walker, J. Li, D. Atzmon, L. Cohen, T. K. S. Kumar, E. Boyarski, and R. Bartak Multi-agent pathfinding: definitions, variants, and benchmarks. In Proceedings of the Twelfth International Symposium on Combinatorial Search (SoCS 2019), Vol. 10, p. 151–158. Cited by: §1, §1, §2.1. Sturtevant (2012) N. R. Sturtevant Benchmarks for grid-based pathfinding. IEEE Transactions on Computational Intelligence and AI in Games 4 (2), p. 144–148. External Links: Document Cited by: §3, Figure 2, Figure 2, §4.2, §4.2. Varambally et al. (2022) S. Varambally, J. Li, and S. Koenig Which MAPF model works best for automated warehousing?. In Proceedings of the International Symposium on Combinatorial Search, Vol. 15, p. 190–198. Cited by: §1. Walker et al. (2018) T. T. Walker, N. R. Sturtevant, and A. Felner Extended increasing cost tree search for non-unit cost domains. In Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI-18, p. 534–540. External Links: Document, Link Cited by: §1, §1. Wu et al. (2026a) X. Wu, S. Zhao, and Z. Ren BCBS-A: bounded sub-optimal conflict-based search for multi-agent path finding with asynchronous actions. In Proceedings of the International Symposium on Combinatorial Search, Vol. 19, p. 193–201. Cited by: §6. Wu et al. (2026b) X. Wu, S. Zhao, and Z. Ren Conflict-based search for multi agent path finding with asynchronous actions. In Proceedings of the 25th International Conference on Autonomous Agents and Multiagent Systems, AAMAS ’26, Richland, SC, p. 1174–1182. External Links: ISBN 9798400723179, Link, Document Cited by: §1, §6. Wurman et al. (2008) P. R. Wurman, R. D’Andrea, and M. Mountz Coordinating hundreds of cooperative, autonomous vehicles in warehouses. AI Magazine 29 (1), p. 9–9. Cited by: §1. Yakovlev et al. (2024) K. Yakovlev, A. Andreychuk, and R. Stern Optimal and bounded suboptimal any-angle multi-agent pathfinding. In 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), p. 7996–8001. Cited by: §1. Yu and LaValle (2013) J. Yu and S. LaValle Structure and intractability of optimal multi-robot path planning on graphs. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 27, p. 1443–1449. Cited by: §1, §6. Zang et al. (2026) C. Zang, A. Mannucci, I. Barz, P. Schillinger, F. Lier, and W. Hönig GRACE: a unified 2D multi-robot path planning simulator & benchmark for grid, roadmap, and continuous environments. External Links: 2603.10858 Cited by: §1. Zhang et al. (2022) S. Zhang, J. Li, T. Huang, S. Koenig, and B. Dilkina Learning a priority ordering for prioritized planning in multi-agent path finding. In Proceedings of the International Symposium on Combinatorial Search, Vol. 15, p. 208–216. Cited by: §1.