Abstract

Abstract: We consider the problem of allocating a number of exploration tasks to a team of mobile robots. Each task consists of a target location that needs to be visited by a robot. The objective of the allocation is to minimize the total cost, that is, the sum of the travel costs of all robots for visiting all targets. We show that finding an optimal allocation is an NP-hard problem, even in known environments. The main contribution of this paper is Prim Allocation, a simple and fast approximate algorithm for allocating targets to robots which provably computes allocations whose total cost is at most twice as large as the optimal total cost. We then cast Prim Allocation in terms of a multi-round single-item auction where robots bid on targets, which allows for a decentralized implementation. To the best of our knowledge, Prim Allocation is the first auction-based allocation algorithm that provides a guarantee on the quality of its allocations. Our experimental results in a multi-robot simulator demonstrate that Prim Allocation is fast and results in close-to-optimal allocations despite its simplicity and decentralized nature. In particular, it needs an order of magnitude fewer bids than a computationally intensive allocation algorithm based on combinatorial auctions, yet its allocations are at least as good.

Download the paper in pdf.

Download the paper in gzipped postscript (large download time).

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.