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

Αναζήτηση

Πλοήγηση

Ο Χώρος μου

Auctions with performance guarantees for multi-robot task allocation

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

Πλήρης Εγγραφή


URI: http://purl.tuc.gr/dl/dias/C9C8B982-C2DC-47FF-AEDC-CDB4A08B8F6E
Έτος 2004
Τύπος Πλήρης Δημοσίευση σε Συνέδριο
Άδεια Χρήσης
Λεπτομέρειες
Βιβλιογραφική Αναφορά 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 https://doi.org/10.1109/IROS.2004.1389434
Εμφανίζεται στις Συλλογές

Περίληψη

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.

Υπηρεσίες

Στατιστικά