Institutional Repository
Technical University of Crete
Technical University of Crete
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/C9C8B982-C2DC-47FF-AEDC-CDB4A08B8F6E | - |
| Identifier | https://doi.org/10.1109/IROS.2004.1389434 | - |
| Language | en | - |
| Extent | 8 pages | en |
| Title | Auctions with performance guarantees for multi-robot task allocation | en |
| Creator | Lagoudakis Michael | en |
| Creator | Λαγουδακης Μιχαηλ | el |
| Creator | Berhault, M. | en |
| Creator | Keskinocak, Pınar | en |
| Creator | Koenig, S. | en |
| Creator | Kleywegt, A. J | en |
| Publisher | Institute of Electrical and Electronics Engineers | en |
| Content Summary | 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 allow 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. | en |
| Type of Item | Πλήρης Δημοσίευση σε Συνέδριο | el |
| Type of Item | Conference Full Paper | en |
| License | http://creativecommons.org/licenses/by/4.0/ | en |
| Date of Item | 2015-11-13 | - |
| Date of Publication | 2004 | - |
| Subject | Robot control | en |
| Subject | robots control systems | en |
| Subject | robot control | en |
| Bibliographic Citation | M.G. Lagoudakis, M. Berhault, P.Keskinocak, S, Koenig, and A. Kleywegt, “Auctions with performance guarantees for multi-robot task allocation,” in 2004 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), 2004, pp. 698–705. doi:10.1109/IROS.2004.1389434 | en |
Copyright © DIAS 2013
