# PRISM: Complete Online Decentralized Multi-Agent Pathfinding with Rapid Information Sharing using Motion Constraints

arXiv: https://arxiv.org/abs/2505.08025 · HTML: https://mlsanity.com/paper/2505.08025/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 50 references that are in the map.
- First posted on arXiv 12 May 2025.

## Builds on (most cited first, 8 of 8)

- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [Searching with Consistent Prioritization for Multi-Agent Path Finding](https://mlsanity.com/paper/1812.06356/) (2018)
- [Lifelong Multi-Agent Path Finding for Online Pickup and Delivery Tasks](https://mlsanity.com/paper/1705.10868/) (2017)
- [Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots](https://mlsanity.com/paper/1409.2399/) (2014)
- [Representation-Optimal Multi-Robot Motion Planning using Conflict-Based Search](https://mlsanity.com/paper/1909.13352/) (2019)
- [Optimal Sequential Task Assignment and Path Finding for Multi-Agent Robotic Assembly Planning](https://mlsanity.com/paper/2006.08845/) (2020)
- [Moving Forward in Formation: A Decentralized Hierarchical Learning Approach to Multi-Agent Moving Together](https://mlsanity.com/paper/2011.02373/) (2020)
- [Distributed Planning for Rigid Robot Formations using Consensus on the Transformation of a Base Configuration](https://mlsanity.com/paper/2307.07326/) (2023)

## Abstract (arXiv)

We introduce PRISM (Pathfinding with Rapid Information Sharing using Motion Constraints), a decentralized algorithm designed to address the multi-task multi-agent pathfinding (MT-MAPF) problem. PRISM enables large teams of agents to concurrently plan safe and efficient paths for multiple tasks while avoiding collisions. It employs a rapid communication strategy that uses information packets to exchange motion constraint information, enhancing cooperative pathfinding and situational awareness, even in scenarios without direct communication. We prove that PRISM resolves and avoids all deadlock scenarios when possible, a critical challenge in decentralized pathfinding. Empirically, we evaluate PRISM across five environments and 25 random scenarios, benchmarking it against the centralized Conflict-Based Search (CBS) and the decentralized Token Passing with Task Swaps (TPTS) algorithms. PRISM demonstrates scalability and solution quality, supporting 3.4 times more agents than CBS and handling up to 2.5 times more tasks in narrow passage environments than TPTS. Additionally, PRISM matches CBS in solution quality while achieving faster computation times, even under low-connectivity conditions. Its decentralized design reduces the computational burden on individual agents, making it scalable for large environments. These results confirm PRISM's robustness, scalability, and effectiveness in complex and dynamic pathfinding scenarios.