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 tasks among themselves as they learn more about the terrain, as robots fail or as additional tasks get introduced. Applications include environmental clean up, mine clearing, space exploration and search and rescue. AI and robotics researchers had 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 must operate in real-time, which raises a completely different set of issues.

My collaborators and I created a theoretical foundation for auction-based coordination systems that assign locations to agents (that then need to visit these locations), allowing one to understand the behavior of these auction-based coordination systems better and extend their capabilities. In particular, we demonstrated the advantages of auction-based coordination systems based on sequential single-item auctions. We exploited the fact that such auction-based coordination systems perform a form of hill climbing search to analyze their performance and improved them via methods such as rollouts, bundle bids and regret clearing. We showed that they can - perhaps surprisingly - provide constant-factor quality guarantees in some cases even though they run in polynomial time and, more generally, that they combine advantageous properties of parallel and combinatorial auctions. We generalized them to assign more than one additional location during each round, which increases their similarity to combinatorial auctions. We showed that, for a given number of additional locations to be assigned during each round, every agent needs to submit only a constant number of bids per round and the runtime of winner determination is linear in the number of agents. Thus, the communication and winner determination times do not depend on the number of locations, which helps the resulting auction-based coordination systems to scale up to many locations for small bundle sizes. We also developed other auction-based coordination systems, such as ones based on sequential incremental-value auctions.

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