Auctions for multi-robot task allocation in communication limited environments

We consider the problem of multi-robot task allocation using auctions, and study how lossy communication between the auctioneer and bidders affects solution quality. We demonstrate both analytically and experimentally that even though many auction algorithms have similar performance when communication is perfect, different auctions degrade in different ways as communication quality decreases from perfect to nonexistent. Thus, if a multi-robot system is expected to encounter lossy communication, then the auction algorithm that it uses for task allocation must be chosen carefully. We compare six auction algorithms including: standard implementations of the Sequential Auction, Parallel Auction, Combinatorial Auction; a generalization of the Prim Allocation Auction called G-Prim; and two multi-round variants of a Repeated Parallel Auction. Variants of these auctions are also considered in which award information from previous rounds is rebroadcast by the auctioneer during later rounds. We consider a variety of valuation functions used by the bidders, including: the total and maximum distance traveled (for distance based cost functions), the expected profit or cost to a robot (assuming robots' task values are drawn from a random distribution). Different auctioneer objectives are also evaluated, and include: maximizing profit (max sum), minimizing cost (min sum), and minimizing the maximum distance traveled by any particular robot (min max). In addition to the cost value functions that are used, we are also interested in fleet performance statistics such as the expected robot utilization rate, and the expected number of items won by each robot. Experiments are performed both in simulation and on real AscTec Pelican quad-rotor aircraft. In simulation, each algorithm is considered across communication qualities ranging from perfect to nonexistent. For the case of the distance-based cost functions, the performance of the auctions is compared using two different communication models: (1) a Bernoulli model and (2) the Gilbert-Elliot model. The particular auction that performs the best changes based on the the reliability of the communication between the bidders and the auctioneer. We find that G-Prim and its repeated variant perform relatively well when communication is poor, and that re-sending winner data in later rounds is an easy way improve the performance of multi-round auctions, in general.