Walk, Stop, Count, and Swap: Decentralized Multi-Agent Path Finding With Theoretical Guarantees
Walk, Stop, Count, and Swap: Decentralized Multi-Agent Path Finding With Theoretical Guarantees
复制标题
DOI：
10.1109/lra.2020.2967317
复制
发表时间：
2020-01
影响因子：
5.2
通讯作者：
Hanlin Wang;Michael Rubenstein
中科院分区：
文献类型：
--
作者：
Hanlin Wang;Michael Rubenstein
对于多智能体路径寻找（MAPF）问题，寻找最优解已被证明是NP完全的。在这里，我们提出了WSCaS（步行，停止，计数和交换），一个分散的多智能体路径查找算法，可以提供理论上的完整性和最优性保证。也就是说，WSCaS能够在没有狭窄通道的正方形网格上为MAPF实例提供最坏情况的$\mathbf {\mathcal {O}（1）}$近似距离最优解。此外，该算法的成本是独立的群体的规模方面的计算复杂度，内存复杂度，以及通信复杂度，因此，该算法可以很好地扩展与代理的数量在实践中。该算法在1024个模拟智能体和100个物理机器人上执行，结果表明WSCaS对现实世界的非理想性具有鲁棒性。
For multi-agent path finding (MAPF) problems, finding the optimal solution has been shown to be NP-Complete. Here we present WSCaS (Walk, Stop, Count, and Swap), a decentralized multi-agent path-finding algorithm that can provide theoretical completeness and optimality guarantees. That is, WSCaS is able to deliver a worst case $\mathbf {\mathcal {O}(1)}$-approximate distance-optimal solution to MAPF instances on square grids without narrow passages. Moreover, the algorithm‘s cost is independent of the swarm's size with respect to computation complexity, memory complexity, as well as communication complexity, therefore the algorithm can scale well with the number of agents in practice. The algorithm is executed on 1024 simulated agents as well as 100 physical robots, the results show that the WSCaS is robust to real-world non-idealitys.