Project "Market Mechanisms for Agent Coordination (Auction-Based Coordination Systems)"
(scroll down for publications)

Auction-based coordination systems coordinate teams of agents, such as teams of mobile robots that have to repeatedly reassign targets among themselves as they learn more about the terrain, as robots fail or as additional targets get introduced (for example, Mars rovers have to collect rock probes from additional Mars rocks). Applications include environmental clean up, mine clearing, space exploration and search and rescue. Artificial intelligence and robotics researchers have explored auction-based coordination systems at least since the introduction of contract networks, but mostly from an experimental perspective. Auctions in economics deal with competitive agents that often have long decision cycles, while auction-based coordination systems deal with cooperative agents that often have to operate in real-time, which raises a completely different set of issues. We have exploited the fact that auction-based coordination systems based on sequential single-item auctions perform a form of hillclimbing search to analyze their performance and improve them via methods such as rollouts, bundle bids and regret clearing. For example, we have shown that they can provide constant factor performance guarantees even though they run in polynomial time and, more generally, that they combine advantageous properties of parallel and combinatorial auctions. We have generalized them to assign more than one additional target during each round, which increases their similarity to combinatorial auctions. We have shown that, for a given number of additional targets to be assigned during each round, every robot needs to submit only a constant number of bids per round and the runtime of winner determination is linear in the number of robots. Thus, the communication and winner determination times do not depend on the number of targets, which helps the resulting auction-based coordination systems to scale up to a large number of targets for small bundle sizes. Overall, we work on creating a theoretical foundation for auction-based coordination systems, understanding their behavior better and extending their capabilities.

Tutorial

Representative Overview Publications

Representative Publications on Auctions

Representative Publications on Techniques other than Auctions

Some of this material is based upon work supported by the U.S. Army Research Office under contract/grant number W911NF-08-1-0468, by the National Science Foundation under Grant No. 0413196 and 0113881 as well as a seed grant by NASA's Jet Propulsion Laboratory. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the sponsoring organizations.

Many publishers do not want authors to make their papers available electronically after the papers have been published. Please use the electronic versions provided here only if hardcopies are not yet available. If you have comments on any of these papers, please send me an email! Also, please send me your papers if we have common interests.

This page was automatically created by a bibliography maintenance system that was developed as part of an undergraduate research project, advised by Sven Koenig.


Home Page of Sven Koenig