The problem is anonymous, or unlabeled, multi-agent pathfinding on a shared discrete workspace. A set of agents must reach a set of goal vertices, but it does not matter which agent reaches which goal. Agents move on a connected undirected graph in discrete time, choosing either an adjacent move or a wait action, and an agent remains at its goal after arrival. Paths must avoid both vertex conflicts, in which agents occupy the same vertex at the same time, and swapping conflicts, in which agents traverse the same edge in opposite directions at the same time. The paper focuses on the especially difficult case in which there is no central controller, agents use only local communication, and the initial goal choices may be inconsistent because multiple agents may select the same goal.
The central contribution is, according to the paper, the first solver for anonymous MAPF that operates in a fully decentralized fashion. TP-SWAP addresses duplicate or conflicting goal choices through a procedure that swaps targets and priorities while preserving a consistent assignment, meaning that no two agents are heading toward the same goal. This extends the established TSWAP approach from a centralized setting to one in which agents make decisions individually and exchange information locally. The paper also proves that TP-SWAP is complete: every target is eventually reached by some agent. Empirically, it compares the proposed solver with centralized and decentralized baselines, including a method that begins with a consistent assignment, rather than evaluating it in isolation.
TP-SWAP is built on TSWAP, a rule-based anonymous MAPF method. TSWAP first creates a consistent assignment in which each goal is assigned to one agent, then repeatedly moves agents toward their assigned goals and swaps goals when necessary while retaining assignment consistency. In the fully decentralized variant, agents independently choose goals and communicate with nearby agents, potentially through chains of communication. Target swapping resolves cases such as an agent occupying its goal while blocking another agent’s route, while priority swapping coordinates which agent should proceed when local decisions conflict. Together, these operations allow the system to recover from an inconsistent initial assignment and continue rule-based path planning without a centralized assignment authority. The completeness argument is inspired by the proof strategy for TSWAP but must handle the additional complexity created by decentralized decisions.
The evaluation compares four methods: centralized C-TSWAP, decentralized D-TSWAP-C using a random but initially consistent target assignment, naive fully decentralized D-SWAP-N, and the proposed TP-SWAP. The experiments use three MovingAI benchmark grid maps: random-32-32-10, maze-32-32-4, and den404d. For each map, the authors generate 250 scenarios, with each scenario containing 100 start and target locations, and evaluate different numbers of agents. The reported objectives are flowtime, the aggregate of agents’ arrival times, and makespan, the arrival time of the last agent; averages and standard deviations are considered. A separate experiment on maze-32-32-4 varies the communication range, while supplementary material adds results on maps of different sizes and more detailed analyses of communication subgroups. The supplied excerpt does not preserve the numerical values of the ranges, agent counts, or measured scores, so those values cannot be reconstructed reliably.
The reported findings indicate that target-priority swapping is essential rather than cosmetic for the decentralized solvers. TP-SWAP notably outperforms the naive fully decentralized D-SWAP-N in flowtime and can even outperform the decentralized alternative that starts with a consistent assignment. The paper reports that its makespan approaches that of the latter as the number of agents grows, and it suggests that higher agent density may help agents recover a consistent assignment more quickly; this is presented as an interpretation, not as a universally established causal law. Enlarging the communication range improves performance in the examined setting, but the improvement diminishes when the range is extended further. The practical implications remain conditional because the model abstracts away communication failures and assumes synchronized movements and access to the necessary subgroup information.
Multi-agent pathfinding is a foundational problem for coordinated movement in robotics, transportation, and video games. Classical MAPF assigns a specific goal to every agent, whereas anonymous MAPF supplies a goal set without fixing the agent-goal correspondence. Optimal MAPF planning with common objectives such as makespan or flowtime is computationally hard, which has motivated optimal, bounded-suboptimal, prioritized, and rule-based methods with different trade-offs between solution quality, runtime, and scalability. Many established methods assume a centralized controller and a discretized workspace. Learning-based approaches have also been used for navigation and goal assignment, but the excerpt notes that they commonly lack formal guarantees, require substantial training, and may generalize poorly outside their training distribution.
Formally, agents start at predefined vertices of a connected undirected graph and must collectively reach all predefined goal vertices. Time is discretized, and each agent may move to an adjacent vertex or wait; once an agent reaches its assigned goal, it stays there. A valid solution consists of paths that begin at the specified starts, end at goals, cover every goal, and contain no vertex or edge-swapping conflicts. In the decentralized scenario, agents can exchange information with others within a communication range, and chain communication can connect agents indirectly. For the study, communication is idealized as instantaneous and error-free, so the excerpt does not establish behavior under realistic communication delays, losses, or inaccurate observations.
The key invariant is consistency of the goal assignment: at most one agent should be pursuing each target. TP-SWAP combines target reassignment with priority changes so that agents can resolve duplicate selections, blocking situations, and local conflicts while continuing to move. Its rule-based path planner does not seek an optimal objective, and the completeness theorem should not be interpreted as an optimality guarantee. The authors describe the proof as extending the idea behind TSWAP’s completeness proof to the more complicated decentralized setting. The formal guarantee is that every target will be reached by some agent under the stated model.
The main empirical study uses three MovingAI maps and 250 scenarios per map. Each scenario is based on 100 start and target locations, and the number of active agents is varied. C-TSWAP uses the original centralized implementation with a bottleneck assignment because that assignment performed best on average in the original TSWAP study. The decentralized methods were implemented by the authors and include D-TSWAP-C, D-SWAP-N, and TP-SWAP. Communication-range experiments are conducted on maze-32-32-4, and the supplementary material reports additional map-size and communication-subgroup analyses.
Across the reported setups, TP-SWAP notably outperforms D-SWAP-N in flowtime. It can also outperform D-TSWAP-C, despite the latter relying on an initially consistent target assignment. The paper reports that makespan approaches the decentralized method’s makespan as the number of agents increases, with a possible improvement at higher density attributed to faster recovery of consistency. All evaluated methods are reported to solve the tested tasks, but the supplied excerpt does not provide enough numerical detail to state exact scores, standard deviations, agent counts, or communication radii.
The paper introduces TP-SWAP for a previously difficult anonymous MAPF setting with inconsistent initial assignments, local communication, and no central controller. Its target and priority swapping procedure produces and maintains a consistent assignment while agents use rule-based decentralized planning. Theoretical analysis establishes completeness under the paper’s assumptions, and experiments show an advantage over the naive fully decentralized competitor and competitiveness with a solver that receives a consistent initial assignment. The authors identify more general anonymous MAPF variants, communication mechanisms, and real-robot implementation and evaluation as future directions.
Agents are assumed to possess all information needed about other agents in their communication subgroup when choosing actions, which would require a practical information-sharing mechanism. Movements are synchronized, whereas real robots would need a decentralized way to coordinate motion timing. Communication is modeled as instantaneous and error-free, and the excerpt does not evaluate latency, packet loss, partial observability, or noisy localization. The method is complete but is not shown to be optimal, and performance on continuous, dynamic, or physical environments is not established by the supplied evidence.
This work expands the design space for anonymous MAPF by removing the assumption that a central authority must assign goals and coordinate paths. It demonstrates that a fully decentralized solver can retain a formal completeness guarantee while achieving competitive flowtime in the tested discrete settings. The result is particularly relevant to multi-robot systems in which agents may need to coordinate through local interactions rather than a global planner. Its importance should nevertheless be understood within the stated synchronized, discrete, and ideal-communication model.
The paper is recommended for researchers in anonymous MAPF, decentralized multi-robot navigation, local communication, and distributed goal assignment. It is useful for readers comparing centralized, decentralized, and fully decentralized rule-based planners, especially with flowtime and makespan objectives. Researchers studying how to recover from inconsistent initial assignments or how target and priority mechanisms affect completeness will find it particularly relevant. Readers seeking detailed physical-robot communication protocols or asynchronous execution techniques should treat the paper as a starting point rather than a complete implementation guide.