Multi-Robot Task Allocation with Auctions in Harsh Communication Environments

We evaluate three different auction algorithms for multi-robot task allocation when the communication channel is lossy. These include the Sequential Auction, the Parallel Auction, and a generalization of the Prim Allocation Auction called the G-Prim Auction. Each auction is evaluated in two different scenarios: (1) task valuations are random variables drawn from a distribution, and (2) tasks represent locations that must be visited and costs are defined by the extra distance required to visit each location. We derive closed-form solutions for the expected performance of the Sequential Auction and Parallel Auction in Scenario 1, bound the performance of G-Prim in Scenario 1, and bound the performance of the Parallel and Sequential Auctions in Scenario 2.