Walk, Stop, Count, and Swap: Decentralized Multi-agent Path Finding with Theoretical Guarantees

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.