Repeated auctions for robust task execution by a robot team.

University of Minnesota Ph.D. dissertation. December 2010. Major: Computer science. Advisor: Prof. Maria Gini. 1 computer file (PDF); ix, 102 pages. Ill. (some col.)We study the use of auction based methods for allocation of tasks in a team of cooperative robots. The thesis makes contributions to this topic in three main directions: 1. We propose a novel auction algorithm for task allocation to robots that is specially suited for dynamic environments where unexpected obstacles, loss of communication, and other delays may prevent a robot from completing its allocated tasks. We present theoretical properties of the algorithm and experimental results, obtained both in simulation and using real robots in a variety of environments. 2. We extend combinatorial auctions for tasks that have precedence constraints and that require robots to visit task locations within assigned time windows. We present experimental results obtained in simulation and compare the allocation generated by the combinatorial auction algorithm with allocations generated by other auction algorithms. 3. We apply auctions to the RoboCup search and rescue scenario, a city-level simulation of a disaster situation where heterogeneous agents have to clear debris, extinguish fires, and rescue civilians. We propose an auction mechanism to coordinate the agents, and show its effectiveness