(please see the main page for schedule information)
Consider the following agent-coordination task: A team of Mars rovers needs to
visit a number of rocks to take rock samples. The assignment of rocks to rovers
can turn out to be suboptimal as the rovers gain additional information about
the terrain. How to assign and re-assign rocks to rovers is a difficult
problem. For example, centralized control is inefficient in terms of both the
required amount of computation and communication since the central controller
is the bottleneck of the system. Auctions, on the other hand, are efficient in
terms of both the required amount of computation and communication since
information is compressed into numeric bids that the robots can compute in
parallel. In this talk, I will describe our recent theoretical results on how
to set up auctions so that they run in real time, yet achieve good team
performance. In particular, I will talk about our recent results that provide
the first provable constant factor performance guarantee of auction mechanisms
for agent coordination that I am aware of.
The Auction Robot Project is joint work with researchers
from 4 different universities: M. Berhault, H. Huang, S. Jain, D. Kempe, P.
Keskinocak, A. Kleywegt, M. Lagoudakis, V. Markakis, A. Meyerson, C. Tovey and
X. Zhen.
Sven Koenig is an associate professor in computer science at
the
Maintainer is
Jack MostowLast modified: 7/29/2005 7:41 PM