Consensus-Based Decentralized Auctions for Robust Task Allocation
This paper addresses task allocation to coordinate a fleet of autonomous vehicles by presenting two decentralized algorithms: the consensus-based auction algorithm (CBAA) and its generalization to the multi-assignment problem, i.e., the consensus-based bundle algorithm (CBBA). These algorithms utili...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers
2010
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/1721.1/52330 https://orcid.org/0000-0001-8576-1930 |
| _version_ | 1811089112570003456 |
|---|---|
| author | Choi, Han-Lim Brunet, Luc How, Jonathan P. |
| author2 | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics |
| author_facet | Massachusetts Institute of Technology. Department of Aeronautics and Astronautics Choi, Han-Lim Brunet, Luc How, Jonathan P. |
| author_sort | Choi, Han-Lim |
| collection | MIT |
| description | This paper addresses task allocation to coordinate a fleet of autonomous vehicles by presenting two decentralized algorithms: the consensus-based auction algorithm (CBAA) and its generalization to the multi-assignment problem, i.e., the consensus-based bundle algorithm (CBBA). These algorithms utilize a market-based decision strategy as the mechanism for decentralized task selection and use a consensus routine based on local communication as the conflict resolution mechanism to achieve agreement on the winning bid values. Under reasonable assumptions on the scoring scheme, both of the proposed algorithms are proven to guarantee convergence to a conflict-free assignment, and it is shown that the converged solutions exhibit provable worst-case performance. It is also demonstrated that CBAA and CBBA produce conflict-free feasible solutions that are robust to both inconsistencies in the situational awareness across the fleet and variations in the communication network topology. Numerical experiments confirm superior convergence properties and performance when compared with existing auction-based task-allocation algorithms. |
| first_indexed | 2024-09-23T14:13:53Z |
| format | Article |
| id | mit-1721.1/52330 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T14:13:53Z |
| publishDate | 2010 |
| publisher | Institute of Electrical and Electronics Engineers |
| record_format | dspace |
| spelling | mit-1721.1/523302022-09-28T19:20:36Z Consensus-Based Decentralized Auctions for Robust Task Allocation Choi, Han-Lim Brunet, Luc How, Jonathan P. Massachusetts Institute of Technology. Department of Aeronautics and Astronautics How, Jonathan P. Choi, Han-Lim How, Jonathan P. Distributed robot systems networked robots task allocation for multiple mobile robots This paper addresses task allocation to coordinate a fleet of autonomous vehicles by presenting two decentralized algorithms: the consensus-based auction algorithm (CBAA) and its generalization to the multi-assignment problem, i.e., the consensus-based bundle algorithm (CBBA). These algorithms utilize a market-based decision strategy as the mechanism for decentralized task selection and use a consensus routine based on local communication as the conflict resolution mechanism to achieve agreement on the winning bid values. Under reasonable assumptions on the scoring scheme, both of the proposed algorithms are proven to guarantee convergence to a conflict-free assignment, and it is shown that the converged solutions exhibit provable worst-case performance. It is also demonstrated that CBAA and CBBA produce conflict-free feasible solutions that are robust to both inconsistencies in the situational awareness across the fleet and variations in the communication network topology. Numerical experiments confirm superior convergence properties and performance when compared with existing auction-based task-allocation algorithms. United States. Air Force Office of Scientific Research (Grant FA9550-08-1-0086) United States. Air Force Office of Scientific Research, Small Business Technology Transfer (Contract FA9550-06-C-0088) 2010-03-05T14:48:30Z 2010-03-05T14:48:30Z 2009-06 2009-04 Article http://purl.org/eprint/type/JournalArticle 1552-3098 http://hdl.handle.net/1721.1/52330 Han-Lim Choi, L. Brunet, and J.P. How. “Consensus-Based Decentralized Auctions for Robust Task Allocation.” Robotics, IEEE Transactions on 25.4 (2009): 912-926. © 2009 Institute of Electrical and Electronics Engineers https://orcid.org/0000-0001-8576-1930 en_US http://dx.doi.org/10.1109/tro.2009.2022423 IEEE Transactions on Robotics Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Institute of Electrical and Electronics Engineers IEEE |
| spellingShingle | Distributed robot systems networked robots task allocation for multiple mobile robots Choi, Han-Lim Brunet, Luc How, Jonathan P. Consensus-Based Decentralized Auctions for Robust Task Allocation |
| title | Consensus-Based Decentralized Auctions for Robust Task Allocation |
| title_full | Consensus-Based Decentralized Auctions for Robust Task Allocation |
| title_fullStr | Consensus-Based Decentralized Auctions for Robust Task Allocation |
| title_full_unstemmed | Consensus-Based Decentralized Auctions for Robust Task Allocation |
| title_short | Consensus-Based Decentralized Auctions for Robust Task Allocation |
| title_sort | consensus based decentralized auctions for robust task allocation |
| topic | Distributed robot systems networked robots task allocation for multiple mobile robots |
| url | http://hdl.handle.net/1721.1/52330 https://orcid.org/0000-0001-8576-1930 |
| work_keys_str_mv | AT choihanlim consensusbaseddecentralizedauctionsforrobusttaskallocation AT brunetluc consensusbaseddecentralizedauctionsforrobusttaskallocation AT howjonathanp consensusbaseddecentralizedauctionsforrobusttaskallocation |