Auction-Based Multi-Robot Routing

By Michail G. Lagoudakis, Evangelos K. Markakis, David Kempe, Pinar Keskinocak, Anton J. Kleywegt, Sven Koenig, Craig A. Tovey, Adam Meyerson, Sonal Jain. Robotics: Science and Systems Conference, 2005

336 citations recorded by the source corpus.

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.

Subfields: Computer Networks and Communications, Industrial and Manufacturing Engineering, Management Science and Operations Research

View Paper: https://www.semanticscholar.org/paper/cc5fe5327d91cde307d9f53772c4cbb903b0bc3f

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Industrial and Manufacturing Engineering

In Management Science and Operations Research

Citations in the corpus

A Formal Analysis and Taxonomy of Task Allocation in Multi-Robot Systems (2004, background): “Theorem 1 ((Lagoudakis et al. 2005)) The team costs of SSI auctions can be at least a factor of Ω(|T |1/3) larger than minimal, even if each robot calculates its robot costs exactly.”
Market-Based Multirobot Coordination: A Survey and Analysis (2006, background): “[27] provide a set of approximation bounds on solution quality for sequential single-task auctions for various team objective functions and bidding rules.”
Consensus-Based Decentralized Auctions for Robust Task Allocation (2009, methodology): “The algorithm is designed to minimize the total distance traveled by the fleet to accomplish the tasks; however, other heuristics have been developed in [ 56 ] and [57] that can be used as well.”
A comprehensive taxonomy for multi-robot task allocation (2013, background): “For example, the basic multi-robot routing problem (Lagoudakis et al., 2005) in which a team of robots visits a set of locations with routes that optimize criteria such as travel distance or time, is outside the space covered by Gerkey and Matarić’s taxonomy.”