Project "Market Mechanisms for Agent Coordination"
In joint research with industrial engineers, we study exploration tasks where a team of mobile robots needs to visit a number of given targets in a partially unknown terrain. Examples include environmental clean-up missions, mine clearing, space-exploration missions, and search and rescue missions. An important characteristic of these exploration tasks is that the assignment of targets to robots can turn out to be suboptimal as the robots gain more information about the terrain, for example, when a robot suddenly discovers that it is separated by a wall from one of the targets assigned to it. How to assign and re-assign targets to robots is a difficult problem. 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. Decentralized control does not have this disadvantage but can result in suboptimal team performance. Market-based approaches are decentralized but appear to perform well in many situations. Auctions, for example, 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 and can result in near-optimal solutions. So far, researchers in robotics have studied parallel single-item auctions (where robots bid on single tasks in parallel) and combinatorial auctions (where robots bid on bundles of tasks) in the context of the exploration tasks. However, single-item auctions can result in highly suboptimal team performance if there are strong synergies between the targets, and combinatorial auctions can result in a large amount of communication and computation. We therefore study which bundles robots should bid on if they use combinatorial auctions. We also study sequential single-item auctions both theoretically and experimentally and show that they provide a compromise between parallel single-item auctions and combinatorial auctions. Our theoretical results, for example, show for the first time that sequential single-item auctions can provide constant factor performance guarantees even though they run in polynomial time. Our experimental results show that the assignment of tasks to robots can indeed be close to optimal. We also study how to improve the team performance of sequential single-item auctions. For example, we have generalized them to assign more than one additional task during each round, which increases their similarity to combinatorial auctions. We show that, for a given number of additional tasks 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. The communication and winner determination costs do not depend on the number of tasks and thus scale to a large number of tasks for small bundle sizes.
Tutorial
Representative Publications on Robotics
Representative Publications on Supply Chains
Representative Publications on Non-Market-Based Agent Coordination
Some of this material is based upon work supported 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 National Science Foundation or the other 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.