Robotics: Science and Systems I

Auction-Based Multi-Robot Routing

Michail G. Lagoudakis, Evangelos Markakis, David Kempe, Pinar Keskinocak, Anton Kleywegt, Sven Koenig, Craig Tovey, Adam Meyerson, Sonal Jain

Abstract: Recently, auction methods have been investigated as effective, decentralized methods for multi-robot coordination. Experimental research has shown great potential, but has not been complemented yet by theoretical analysis. In this paper we contribute a theoretical analysis of the performance of auction methods for multi-robot routing.We suggest a generic framework for auction-based multi-robot routing and analyze a variety of bidding rules for different team objectives. This is the first time that auction methods are shown to offer theoretical guarantees for such a variety of bidding rules and team objectives.

Download:

Bibtex:

@INPROCEEDINGS{ Lagoudakis-RSS-05,
    AUTHOR    = {Michail G. Lagoudakis and Evangelos Markakis and 
                 David Kempe and Pinar Keskinocak and Anton Kleywegt
		 and Sven Koenig and Craig Tovey and Adam Meyerson and 
                 Sonal Jain},
    TITLE     = {Auction-Based Multi-Robot Routing},
    BOOKTITLE = {Proceedings of Robotics: Science and Systems},
    YEAR      = {2005},
    ADDRESS   = {Cambridge, USA},
    MONTH     = {June},
    DOI       = {10.15607/RSS.2005.I.045} 
}