OMCoRP: An Online Mechanism for Competitive Robot Prioritization

摘要

We propose a collision-avoiding mechanism for a group of robots moving on a shared workspace. Existing algorithms solve this problem either (a) in an offline manner using the source-destination information of all the robots or (b) in an online manner with cooperative robots. We take a paradigm shift to the setting with competitive robots, that may strategically reveal their urgency of reaching the destinations and design online mechanisms that take decisions on-the-fly, reducing the overhead of an offline planning. We propose a mechanism OMCoRP in this setting that ensures truthful revelation of the robots' priorities using principles of economic theory and provides locally efficient movement of the robots. It is free from collisions and deadlocks, and handles dynamic arrival of robots. In practice, this mechanism gives a smaller delay for robots of higher priority and scales well for a large number of robots without compromising on the path optimality too much.