OMCoRP: An Online Mechanism for Competitive Robot Prioritization

Authors

  • Sankar Narayan Das Accenture Labs, India
  • Swaprava Nath Indian Institute of Technology Kanpur
  • Indranil Saha Indian Institute of Technology Kanpur

DOI:

https://doi.org/10.1609/icaps.v31i1.15953

Keywords:

Multi-agent And Distributed Planning, Continuous Planning, On-line And Real-time Domains

Abstract

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.

Downloads

Published

2021-05-17

How to Cite

Das, S. N., Nath, S., & Saha, I. (2021). OMCoRP: An Online Mechanism for Competitive Robot Prioritization. Proceedings of the International Conference on Automated Planning and Scheduling, 31(1), 112-121. https://doi.org/10.1609/icaps.v31i1.15953