Consensus-Based Decentralized Auctions for Robust Task Allocation

By Han-Lim Choi, Luc Brunet, Jonathan P. How. 2009

1,074 citations recorded by the source corpus.

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.

Subfields: Computer Networks and Communications, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Management Science and Operations Research

Citations in the corpus

A Survey on Aerial Swarm Robotics (2018, background): “Parallel or distributed algorithms to solve target assignment include many variants of distributed auction algorithms [16], [25], [109]–[111] and decentralized hierarchical strategies [112] that approximate true optimality of Kuhn’s centralized Hungarian method.”
A Comprehensive Survey on the Multiple Travelling Salesman Problem: Applications, Approaches and Taxonomy (2021, methodology): “Inspired by the Consensus Based Bundle Algorithm (CBBA) [72], and the Market Based Approach with Look-ahead Agents (MALA) [73], the authors of [74] introduced a market-based solution for MTSP.”
Survey of advances in guidance, navigation, and control of unmanned rotorcraft systems (2012, methodology): “It is available today as a commercial autopilot (Christophersen et al., 2006) and it is also integrated into commercially available autonomous helicopters.17 Several extensions of the standard adaptive flight controller have been published. In Yavrucuk, Prasad, and Unnikrishnan (2009) for example, t”
Multi-robot Task Allocation: A Review of the State-of-the-Art (2015, methodology): “In [35], two decentralized auctionbased approaches, namely, the consensus-based auction algorithmand the consensusbased bundle algorithm are proposed for solving the MRTA problem of a fleet of autonomous mobile robots.”