Lazy Auctions for Multi-robot Collision Avoidance and Motion Control under Uncertainty

We present an auction-flavored multi-robot planning mechanism where coordination is to be achieved on the occupation of atomic resources modeled as binary inter-robot constraints. Introducing virtual obstacles, we show how this approach can be combined with particle-based obstacle avoidance methods, offering a decentralized, auction-based alternative to previously established centralized approaches for multi-robot open-loop control. We illustrate the effectiveness of our new approach by presenting simulations of typical spatially-continuous multi-robot path-planning problems and derive bounds on the collision probability in the presence of uncertainty.