The paper studies multi-task multi-agent pathfinding, in which several autonomous agents share an environment and must complete individual or assigned tasks without collisions. Agents know the environment but initially do not know the locations, objectives, or paths of other agents, and direct communication is limited by range. Multi-hop communication is possible within a connected component, so the entire team need not form one continuously connected network. The objective is to produce a collision-free team plan while minimizing sum-of-costs, the total cost accumulated by all agents.
PRISM contributes a framework that combines decentralized task management, online replanning, and constraint-based pathfinding for MT-MAPF. Its central communication contribution is an information-packet mechanism that carries motion-constraint information beyond the current direct communication neighborhood. These packets are incorporated into local Modified Conflict-Based Search, where relevant information can be treated similarly to virtual agents when resolving conflicts. The paper also presents a theoretical argument that PRISM is complete and can resolve solvable deadlock situations. Finally, it evaluates PRISM in five environments and 25 random scenarios against centralized CBS and decentralized Token Passing with Task Swaps, or TPTS.
PRISM uses a three-phase planning scheme together with a Modified CBS procedure for planning within local networks. Each agent maintains an identifier, its current task, a planned path, active motion constraints, and a collection of information packets, and it replans when relevant paths, tasks, or communication conditions change. A task allocator assigns valid tasks and may reassign tasks that have not started, while a mission task becomes locked to its agent once execution begins. Information packets communicate constraint adjustments to relevant agents, including agents that later move out of communication range. A regular flushing process removes stale or incorrect information so that replanning does not rely indefinitely on obsolete constraints. Local search then resolves conflicts involving relevant agents and branches over constraint alternatives until a collision-free plan is found or the search proves that no plan exists under the considered conditions.
The empirical evaluation uses environments and scenarios drawn from an established MAPF benchmark database and compares PRISM with CBS and TPTS. Communication conditions include a minimum viable range, ranges corresponding to 0.1, 0.15, and 0.2 of the environment’s longer dimension, and a full range that creates one fully connected network. The reported evaluation considers scalability, solution quality, computation time, robustness, and behavior under different connectivity conditions. A physical validation uses ROS, TurtleBots running on Raspberry Pis, motion capture for localization, and point-stabilization control for navigation. The supplied excerpt does not provide complete per-environment tables, all statistical details, or every experimental condition, so it does not establish an independently reproducible breakdown of every reported comparison.
PRISM’s main trade-off is between stronger coordination and the overhead of maintaining and processing distributed constraint information. The reported advantages are most pronounced in narrow passages, dense task allocations, and low-connectivity networks, where agents must coordinate closely and stale local knowledge can otherwise cause conflicts or deadlocks. In open environments with fewer coordination demands, the simpler TPTS method can have lower computational overhead, faster runtimes, and better scalability. PRISM also depends on assumptions about task allocation, communication, movement, and safe resting at goals, and the excerpt does not reproduce the full list of theoretical assumptions. The paper suggests adapting resting behavior through predefined parking positions or dynamically sampled locations for domains such as warehouses and search-and-rescue.
Multi-agent pathfinding coordinates autonomous agents that move through shared spaces while avoiding conflicts and pursuing efficiency objectives. It is relevant to assembly, evacuation, formation, localization, and object transportation, among other applications. Centralized solvers can use global state information to coordinate agents effectively, but their state space and interaction complexity grow rapidly, and they are often less suitable for online adaptation. Decentralized solvers distribute computation and can be more resilient to changing conditions, but they must coordinate using incomplete and local information.
In MT-MAPF, agents navigate a shared environment to complete a set of tasks, with some tasks potentially unassigned initially. Vertex conflicts occur when two agents occupy the same vertex at the same time, while edge conflicts occur when they traverse the same edge at the same time. The system seeks a collision-free plan that completes the tasks efficiently according to a sum-of-costs objective. The excerpt refers to several formal assumptions and definitions used in the proof, but it does not reproduce all of them, so the precise boundary of the formal guarantee cannot be determined from the supplied material alone.
The key technical device is the information packet, which preserves and disseminates motion constraints when agents leave one another’s communication range. PRISM performs local Modified CBS rather than requiring one central search over the entire team. Unstarted tasks may be reassigned, whereas a task already started as a mission is fixed to its current agent. The theoretical discussion uses temporarily bounded constraints and finite conflict-resolution branches to argue that, whenever a valid solution exists, the search can eventually reach a valid collision-free plan.
The described environments include random-32-32-20, ht_chantry, maze-32-32-2, room-64-64-8, and warehouse-10-20, with proximity and line-of-sight communication examples. A robustness experiment uses random-64-64-20, where randomly scattered obstacles occupy 20 percent of the space. The proposed method is compared with centralized CBS and decentralized TPTS. The physical setup uses ROS, Raspberry Pi-based TurtleBots, motion capture localization, and point stabilization, but the excerpt does not state the full robot count, trial count, or complete protocol for those experiments.
The abstract reports that PRISM supports 3.4 times more agents than CBS and handles up to 2.5 times more tasks than TPTS in narrow-passage environments. It reportedly matches CBS in solution quality while requiring less computation time, including under low-connectivity conditions. The introduction also states that PRISM maintains high solution quality with up to 30 agents and 575 tasks. The supplied evidence does not specify the full mapping between these numbers and individual environments, communication ranges, aggregation procedures, or statistical summaries.
PRISM is presented as a way to adapt constraint-based search to decentralized, online multi-agent planning through selective communication. The theoretical analysis claims completeness and deadlock avoidance for solvable cases under the paper’s assumptions. The experiments support its usefulness in difficult coordination settings, including narrow passages, dense task distributions, and limited connectivity. The conclusion does not claim universal superiority: TPTS may be preferable in spacious, lightly coupled environments because of its lower computational overhead, while PRISM’s performance still degrades as the team grows.
PRISM develops performance bottlenecks as the number of agents increases, even though the reported growth is less severe than for centralized solvers. Its operation relies on a task allocator and on assumptions concerning communication, motion, and goal locations that prevent permanent obstruction. The supplied excerpt omits the complete theorem assumptions, detailed proof steps, full experimental tables, failure rates, and sufficient replication information. Consequently, the exact scope and generalizability of the reported advantages cannot be assessed from the excerpt alone.
The work is important because it combines decentralized execution, online replanning, selective communication, and a completeness claim within one MT-MAPF framework. Information packets provide a way to retain constraints that would otherwise disappear when agents lose direct connectivity. This is relevant to settings such as search-and-rescue and warehouse operations, where communication may be intermittent and task demands may change. It also clarifies that algorithm choice should depend on coordination density and environment topology rather than on agent count alone.
This paper is well suited to researchers studying decentralized MT-MAPF, communication-limited coordination, distributed variants of CBS, and deadlock resolution. It is particularly relevant for work on narrow passages, dense task allocation, and mechanisms that propagate local constraints through intermittent networks. Readers who need to verify the formal guarantee or reproduce every experimental comparison should consult the complete paper, because those details are not all present in the supplied excerpt.