Tutorial on Auction-Based Robot Coordination at ICRA 2006
Abstract
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.
Speakers
The speakers will be Bernardine Dias, Nidhi Kalra and Sven Koenig. The presented material is provided by the researchers listed below and includes material by their co-workers A. Stentz, D. Kempe, A. Meyerson, V. Markakis, A. Kleywegt and C. Tovey. Special thanks go to Anthony Stentz, a research professor with the Robotics Institute of Carnegie Mellon University and the associate director of the National Robotics Engineering Consortium at Carnegie Mellon University, and Craig Tovey, a professor in Industrial and System Engineering at Georgia Institute of Technology.
Bernardine Dias (Carnegie Mellon University, USA)
M. Bernardine Dias is research faculty at the Robotics Institute at Carnegie
Mellon University. Her research interests are in technology for developing
communities, multirobot coordination, space robotics, and diversity in
computer science. Her dissertation developed the TraderBots framework for
market-based multirobot coordination and she has published extensively on a
variety of topics in robotics.
E. Gil Jones (Carnegie Mellon University, USA)
E. Gil Jones is a Ph.D. student at the Robotics Institute at Carnegie Mellon
University. His primary interest is market-based multi-robot coordination. He
received his BA in Computer Science from Swarthmore College in 2001, and spent
two years as a software engineer at Bluefin Robotics in Cambridge, Mass.
Nidhi R. Kalra (Carnegie Mellon University, USA)
Nidhi R. Kalra is a Ph.D. student at the Robotics Institute at Carnegie Mellon
University. She is interested in developing coordination strategies for robots
working on complex real-world problems. To this end, she is developing the
market-based Hoplites framework for tight multirobot coordination.
Pinar Keskinocak (Georgia Institute of Technology, USA)
Pinar Keskinocak is an associate professor at Georgia Institute of Technology.
She is interested in electronic commerce, routing and scheduling applications,
production planning, multi-criteria decision making, approximation algorithms,
and their application to a variety of problems. Pinar has published
extensively in operation research.
Sven Koenig (University of Southern California, USA)
Sven Koenig is an associate professor at the University of Southern
California. From 1995 to 1997, Sven demonstrated that it is possible to
combine ideas from different decision-making disciplines by developing a
robust mobile robot architecture based on POMDPs from operations
research. Since then, he has published over 100 papers in robotics and
artificial intelligence, continuing his interdisciplinary research.
Michail G. Lagoudakis (Technical University of Crete, Greece)
Michail G. Lagoudakis is an assistant professor at the Technical University of
Crete. He is interested in machine learning (reinforcement learning), decision
making under uncertainty, numeric artificial intelligence, as well as robots
and other complex systems. He has published extensively in artificial
intelligence and robotics.
Robert Zlot (Carnegie Mellon University, USA)
Robert Zlot is a PhD student at the Robotics Institute at Carnegie Mellon
University, where he earned a Master's degree in Robotics in 2002. Robert's
main interests are in multirobot coordination and space robotics. His current
research focuses on market-based algorithms for tasks that exhibit complex
structure.
Tutorial Material
Here are the tutorial slides:
Additional Information
Here are pointers to additional material:
For questions or requests for additional information, please send email to Sven Koenig (skoenig@usc.edu).