Distributed Systems
PRISM
We introduce PRISM (Pathfinding with Rapid Information Sharing using Motion Constraints), a novel decentralized algorithm designed to address the multi-task multi-agent pathfinding (MT-MAPF) challenge. 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 theoretically prove that PRISM resolves and avoids all deadlock scenarios when possible, a critical hurdle 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 exceptional 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 lowconnectivity conditions. Its decentralized design significantly reduces the computational burden on individual agents, making it highly scalable for large-scale environments. These results confirm PRISM’s robustness, scalability, and effectiveness in addressing complex and dynamic pathfinding scenarios.
This video on the extended abstract was presented at the 2024 ICRA conference.
Publications
- Lee, H. , Serlin, Z. , Motes, J. , Long, B. , Morales, M. , & Amato, N.M. (2025). PRISM: Complete Online Decentralized Multi-Agent Pathfinding with Rapid Information Sharing using Motion Constraints. ArXiv Preprint. arXiv
- Lee, H. , Motes, J. , Serlin, Z. , Morales, M. , & Amato, N.M. (2024). Distributed Constraint-Based Search using Multi-Hop Communication. Extended Abstract for IEEE International Conference on Robotics and Automation @ 40 (ICRA@40).