SPARCAS: A Decentralized, Truthful Multi-Agent Collision-free Path Finding Mechanism
This addresses the problem of scalable and truthful path planning for competitive robots in decentralized settings, offering a novel solution with practical applications in robotics.
The paper tackles decentralized collision avoidance for competitive robots by proposing SPARCAS, a mechanism that ensures truthful information revelation and prevents collisions and deadlocks, scaling well for large numbers of robots while maintaining near-optimal path efficiency.
We propose a decentralized collision-avoidance mechanism for a group of independently controlled robots moving on a shared workspace. Existing algorithms achieve multi-robot collision avoidance either (a) in a centralized setting, or (b) in a decentralized setting with collaborative robots. We focus on the setting with competitive robots in a decentralized environment, where robots may strategically reveal their information to get prioritized. We propose the mechanism SPARCAS in this setting that, using principles of mechanism design, ensures truthful revelation of the robots' private information and provides locally efficient movement of the robots. It is free from collisions and deadlocks, and handles a dynamic arrival of robots. In practice, this mechanism scales well for a large number of robots where the optimal collision-avoiding path-finding algorithm (M*) does not scale. Yet, SPARCAS does not compromise the path optimality too much. Our mechanism prioritizes the robots in the order of their `true' higher needs, but for a higher payment. It uses monetary transfers which is small enough compared to the value received by the robots.