Auction mechanism design for multi-robot coordination.

C. Bererton, G. Gordon, and S. Thrun.

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. We can show that this policy is the same as the one which would be produced by a particular centralized planning algorithm. We demonstrate the new algorithm on three simulation examples: multi-robot towing, multi-robot path planning with a limited fuel resource, and coordinating behaviors in a game of paint ball.

The full paper is available in PDF and gzipped Postscript

@INPROCEEDINGS{Bererton03a,
  AUTHOR	= {C. Bererton and G. Gordon and S. Thrun},
  TITLE		= {Auction Mechanism Design for Multi-Robot Coordination},
  YEAR		= {2003},
  BOOKTITLE	= {Proceedings of Conference on Neural Information Processing Systems (NIPS)},
  EDITOR	= {S. Thrun and L. Saul and B. Sch\"{o}lkopf},
  PUBLISHER	= {MIT Press}
}