Auction Mechanism Design for Multi-Robot Coordination

(a.k.a. Multi-Robot Coordination Using Markov Decision Processes)

Curt Bererton

Abstract

The design of cooperative multi-robot systems is a highly active research area in robotics. Two lines of research in particular have generated interest: the solution of large, weakly coupled MDPs, and the design and implementation of market architectures. We propose a new algorithm which joins together these two lines of research. For a class of coupled MDPs, our algorithm automatically designs a market architecture which causes a decentralized multi-robot system to converge to a consistent policy. For some problems we can guarantee the optimality of this policy, while for others we can show that it is the same as the policy which would be produced by a particular centralized planning algorithm. We demonstrate the new algorithm on two examples: multi-robot towing in laser tag and multi-robot path planning with a limited fuel resource.

Back to the Main Page