PRISM让大量智能体高效协作规划路径，避免碰撞和死锁。
PRISM: Complete Online Decentralized Multi-Agent Pathfinding with Rapid Information Sharing using Motion Constraints
- 通过运动约束信息包实现快速去中心化通信，提升协同效率。
- 支持3.4倍于CBS的智能体数量，窄道环境下任务处理能力达TPTS的2.5倍。
- 无需直接通信也能避免死锁，适合大规模动态场景中的多智能体系统。
我们提出PRISM（基于运动约束的快速信息共享路径规划），一种去中心化算法，用于解决多任务多智能体路径规划（MT-MAPF）问题。PRISM使大规模智能体团队能同时为多个任务规划安全高效的路径，并避免碰撞。该算法采用快速通信策略，通过信息包交换运动约束信息，增强协作路径规划与态势感知能力，即使在无直接通信条件下亦可运行。我们证明，当可能时，PRISM能完全消除所有死锁情形，这是去中心化路径规划的关键挑战。我们在五个环境和25个随机场景中评估了PRISM，对比了集中式冲突搜索（CBS）和去中心化令牌传递带任务交换（TPTS）算法。结果表明，PRISM具有出色的可扩展性与解质量：支持的智能体数量是CBS的3.4倍，窄道环境中任务处理能力达到TPTS的2.5倍；同时在解质量上媲美CBS，且计算速度更快，即使在低连通性条件下仍表现优异。其去中心化设计减轻了单个智能体的计算负担，适用于大规模复杂动态路径规划场景。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。