Ιδρυματικό Αποθετήριο [SANDBOX]
Πολυτεχνείο Κρήτης
EN  |  EL

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Auctions with performance guarantees for multi-robot task allocation

Lagoudakis Michael, Berhault, M., Keskinocak, Pınar, Koenig, S., Kleywegt, A. J

Απλή Εγγραφή


URIhttp://purl.tuc.gr/dl/dias/C9C8B982-C2DC-47FF-AEDC-CDB4A08B8F6E-
Αναγνωριστικόhttps://doi.org/10.1109/IROS.2004.1389434-
Γλώσσαen-
Μέγεθος8 pagesen
ΤίτλοςAuctions with performance guarantees for multi-robot task allocationen
ΔημιουργόςLagoudakis Michaelen
ΔημιουργόςΛαγουδακης Μιχαηλel
ΔημιουργόςBerhault, M.en
ΔημιουργόςKeskinocak, Pınaren
ΔημιουργόςKoenig, S.en
ΔημιουργόςKleywegt, A. Jen
ΕκδότηςInstitute of Electrical and Electronics Engineersen
Περίληψη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 Paperen
Άδεια Χρήσηςhttp://creativecommons.org/licenses/by/4.0/en
Ημερομηνία2015-11-13-
Ημερομηνία Δημοσίευσης2004-
Θεματική ΚατηγορίαRobot controlen
Θεματική Κατηγορίαrobots control systemsen
Θεματική Κατηγορίαrobot controlen
Βιβλιογραφική Αναφορά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.1389434en

Υπηρεσίες

Στατιστικά