Multi-agent pathfinding (MAPF) asks for a set of paths that moves multiple agents from start vertices to goal vertices without collisions. Time is discrete: an agent can wait at its current vertex or move to an adjacent vertex at each step. The paper considers both vertex conflicts, in which two agents occupy the same vertex at the same time, and swapping conflicts, in which agents exchange positions across an edge. Complete and optimal solvers can become difficult to scale on large, dense instances, whereas scalable methods may sacrifice optimality or even completeness. The work therefore targets practical, high-density MAPF with a polynomial-time rule-based strategy rather than exact optimization.
The main contribution is the Multi-Agent Corridor Generating Algorithm, or MACGA. For an agent being planned, MACGA constructs a connected sequence of vertices leading from its current location toward its goal, then tries to evacuate other agents from that corridor so that the advancing agent does not encounter collisions or deadlocks. The paper also introduces MACGA+PIBT, which incorporates the rule-based PIBT procedure into the MACGA planning process with the goal of improving runtime and solution quality. Both methods are presented as polynomial-time algorithms with a reachability property: each agent is guaranteed eventually to reach its goal under the stated theoretical framework. This property does not mean that all agents reach their goals simultaneously, nor does it establish finite-time global completion in every instance; the authors explicitly characterize the algorithms as suboptimal and incomplete.
MACGA maintains an order over the agents and assigns each agent an active plan, meaning a sequence of one or more actions. At every step, agents execute the first action of their active plans, while the planning phase chooses a corridor for the agent currently being handled, searches for ways to evacuate agents that obstruct it, and then assigns a plan through the corridor. The ordering is updated so that every agent eventually has an opportunity to become first in the order. The construction uses graph structure involving separating vertices, defined as vertices whose removal increases the number of connected components, and non-separating vertices. In MACGA+PIBT, when PIBT selects a non-separating vertex, the movement can be represented as a trivial corridor of size two; otherwise the regular MACGA planning procedure is used. According to the excerpt, MACGA can also be activated online while agents physically execute their moves.
The evaluation compares MACGA and MACGA+PIBT with Prioritized Planning (PrP), LNS2, PIBT, LaCAM, and LaCAM*. The experiments use six MAPF benchmark grids: empty-32-32, random-32-32-10, random-32-32-20, room-32-32-4, maze-32-32-2, and maze-32-32-4. The number of agents ranges from 100 to 700, and 20 random instances are run for every combination of map, agent count, and algorithm. Each instance has a 30-second time limit; success rate is the ratio solved within that limit. Runtime and makespan are also reported. All implementations are in Python and run on a MacBook Air with an Apple M1 chip and 8 GB of RAM. The paper warns that implementation languages and hardware differ from prior work, so the results should not be blindly compared with numbers published elsewhere.
Across the evaluated settings, MACGA and MACGA+PIBT solve a majority of the tested problems more often than the compared algorithms. Their relative advantage is strongest on maps with narrow spaces, such as room-32-32-4 and maze-32-32-2. In the maze-32-32-2 example, the proposed methods solve most instances up to 450 agents, while none of the baseline algorithms solves any of those instances according to the supplied excerpt. MACGA+PIBT has a higher success rate than MACGA on almost all maps and is substantially faster than MACGA. The trade-off is solution cost: MACGA often returns substantially larger makespans, whereas MACGA+PIBT usually keeps makespans closer to those of the baselines. The evidence supports a practical advantage in throughput and solvability, not optimality.
MAPF appears in robotics, automated warehouses, digital entertainment, and other multi-agent applications. The literature contains complete and optimal solvers, as well as scalable suboptimal methods such as Prioritized Planning, PIBT, LNS2, LaCAM, and LaCAM*. Search-based methods such as CBS and LaCAM-family approaches can require heavy computation on large instances. The paper positions MACGA as a tractable alternative that uses local, structured movement and evacuation rather than extensive global search.
An instance is defined over an undirected graph with a number of agents, a start-vertex mapping, and a goal-vertex mapping. A solution consists of one applicable action sequence per agent, starting at its start vertex and ending at its goal, with no vertex or swapping conflicts. The classical objective requires all agents to eventually be at their goals, but the proposed algorithms do not guarantee optimal cost or complete solution finding for every solvable instance. The focus is on dense instances where narrow passages and agent interactions make conventional planning difficult.
A corridor is a sequence of connected vertices used as a temporary route for an agent moving toward its goal. Evacuation is central: agents that interfere with the selected corridor are moved away before the main agent is assigned a plan through it. Separating vertices provide a graph-theoretic way to reason about bottlenecks and corridor structure. The theoretical section discusses the runtime of components such as corridor creation, evacuation, and pushing, along with conditions for finding evacuation vertices and reachability. However, the supplied excerpt omits several displayed complexity expressions and the full statements and proofs of some theorems, so it does not establish the exact polynomial degree or every condition of applicability.
The benchmark suite contains six 32-by-32 grid maps with different degrees of openness, randomness, rooms, and maze-like structure. Agent counts range from 100 through 700, with 20 random instances per map, count, and algorithm, and a 30-second limit per instance. The baselines are PrP, LNS2, PIBT, LaCAM, and LaCAM*, with PrP and LNS2 implemented using SIPPS. Other rule-based algorithms such as PS and PR are excluded because the paper cites prior evidence that they are significantly inferior to PIBT. The experiments use Python on an Apple M1 MacBook Air with 8 GB of RAM, which limits direct comparability with studies using different implementations or machines.
The proposed methods generally achieve the strongest success-rate behavior among the evaluated algorithms. The clearest advantage appears on narrow maps, where MACGA and MACGA+PIBT retain solvability at high agent counts. In maze-32-32-2, the excerpt reports that the proposed methods solve most instances with 450 agents, while every listed baseline fails to solve them. MACGA+PIBT is faster than MACGA on all grids in the reported runtime comparison and usually has lower makespan than MACGA. MACGA itself is often slower and returns considerably higher makespans than the baselines, so its success-rate advantage comes with a clear quality trade-off.
The paper presents MACGA and MACGA+PIBT as incomplete, rule-based MAPF algorithms based on corridor generation and evacuation. Their claimed theoretical advantages are polynomial-time operation and reachability, while the experiments show strong success rates on several dense benchmark domains. The PIBT integration is the more balanced variant in the reported results because it improves runtime and usually keeps makespan near the baselines. The authors identify adapting the methods to lifelong MAPF and to multi-agent path planning in continuous spaces as future directions.
Neither algorithm guarantees an optimal solution, and the reachability claim should not be confused with simultaneous arrival of all agents or guaranteed completion within a fixed finite time. The excerpt states that there is no global runtime guarantee for MACGA, even though its procedures are analyzed as polynomial-time components. The empirical study covers six benchmark maps, a specific Python implementation, one hardware platform, and a 30-second cutoff, so broader generalization is not established. The supplied evidence does not provide the full numerical curves, exact runtime values, detailed failure analyses, or the complete assumptions behind every theorem.
The work is important as a design for dense MAPF in which the main challenge is not merely choosing priorities, but actively clearing a route through a congested graph. By treating a route as a corridor and evacuating obstructing agents, MACGA addresses bottlenecks and deadlock risks with a structured local policy. Its results suggest that sacrificing optimality can yield a substantial solvability advantage on narrow maps. The MACGA+PIBT combination further illustrates how complementary rule-based mechanisms can balance throughput, speed, and solution cost.
This paper is a good fit for researchers studying dense MAPF, narrow passages, online rule-based coordination, or scalable alternatives to computationally heavy search. It is especially relevant when success rate and runtime matter more than optimal makespan. Readers whose primary interest is optimality proofs, complete solving, or directly comparable benchmark numbers should treat the claims cautiously because the methods are incomplete and the implementation environment differs from prior studies. The paper is also useful as a starting point for work on lifelong MAPF and continuous-space extensions.