Ιδρυματικό Αποθετήριο
Πολυτεχνείο Κρήτης
Πολυτεχνείο Κρήτης
EN
|
EL
| URI | http://purl.tuc.gr/dl/dias/C9C8B982-C2DC-47FF-AEDC-CDB4A08B8F6E | - |
| Αναγνωριστικό | https://doi.org/10.1109/IROS.2004.1389434 | - |
| Γλώσσα | en | - |
| Μέγεθος | 8 pages | en |
| Τίτλος | Auctions with performance guarantees for multi-robot task allocation | en |
| Δημιουργός | Lagoudakis Michael | en |
| Δημιουργός | Λαγουδακης Μιχαηλ | el |
| Δημιουργός | Berhault, M. | en |
| Δημιουργός | Keskinocak, Pınar | en |
| Δημιουργός | Koenig, S. | en |
| Δημιουργός | Kleywegt, A. J | en |
| Εκδότης | Institute of Electrical and Electronics Engineers | en |
| Περίληψη | 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 |
| Τύπος | Πλήρης Δημοσίευση σε Συνέδριο | el |
| Τύπος | Conference Full Paper | en |
| Άδεια Χρήσης | http://creativecommons.org/licenses/by/4.0/ | en |
| Ημερομηνία | 2015-11-13 | - |
| Ημερομηνία Δημοσίευσης | 2004 | - |
| Θεματική Κατηγορία | Robot control | en |
| Θεματική Κατηγορία | robots control systems | en |
| Θεματική Κατηγορία | robot control | en |
| Βιβλιογραφική Αναφορά | 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
