[robotics-worldwide] Tutorial on "Auction-Based Robot Coordination" at ICRA 2006

Sven Koenig skoenig at usc.edu
Sun Apr 23 18:18:22 PDT 2006

Tutorial at ICRA 2006
Friday, May 19, 2006 - morning
TF1: Auction-Based Robot Coordination
Bernardine Dias (CMU), Nidhi Kalra (CMU), and Sven Koenig (USC)


Robot teams are increasingly becoming a popular alternative to single robots
for a variety of difficult tasks, such as planetary exploration or planetary
base assembly. An important factor for the success of a robot team is the
ability to coordinate the team members in an effective way. Coordination
involves the allocation and execution of individual tasks through an efficient
(preferably decentralized) mechanism. The tutorial on "Auction-Based Robot
Coordination" covers algorithmic and theoretical aspects of auction-based
methods for robot coordination, where robots bid on tasks and the tasks are
then allocated to the robots by methods that resemble winner determination
methods in auctions. Auction-based methods balance the trade-off between
totally centralized coordination methods and absolutely decentralized
coordination methods without any communication, both in terms of communication
efficiency, computation efficiency and quality.

The tutorial covers auction-based robot coordination using examples of
multi-robot routing tasks, a class of problems where a team of mobile robots
must visit a given set of locations (for example, to deliver material at
construction sites or acquire rock probes from Martian rocks) so that their
routes optimize given criteria, for example, minimize the consumed energy,
completion time, or average latency. Examples include search-and-rescue in
areas hit by disasters, surveillance, placement of sensors, material delivery,
and localized measurements. We give an overview of various auction-based
methods for robot coordination, discuss their advantages and disadvantages and
compare them to each other and other coordination methods. The tutorial covers
recent theoretical advances (including constant-factor performance guarantees)
as well as experimental results and implementation issues.

Intended Audience

The tutorial makes no assumptions about the background of the audience, other
than a very general understanding of algorithms. It will introduce the
audience to the state of the art in auction-based robot coordination. Thus,
the tutorial is appropriate for students (both undergraduate and graduate
students), researchers and practitioners who are interested in learning more
about how to coordinate teams of mobile robots using auction-based mechanisms.

Additional Information



Sven Koenig
University of Southern California
Computer Science Department
Henry Salvatori Computer Center (SAL) 312
941 W 37th Street
Los Angeles, CA 90089-0781, USA
Tel:   213-740-6491
Fax:   213-740-7285
Email: skoenig at usc.edu
WWW:   idm-lab.org (= www-rcf.usc.edu/~skoenig/)

More information about the robotics-worldwide mailing list