Event Driven CBBA with Reduced Communication

Abstract

In numerous applications, such as multi-drone surveillance and search-and-rescue missions, the deployment of multiple robots is essential to accomplish several tasks simultaneously. As the vehicles have limited communication range, it is essential to have a decentralized task allocation algorithm to allocate tasks to robots effectively. One such algorithm is the consensus-based bundle algorithm (CBBA), which has shown promise in working with multi-robots and has theoretical guarantees. However, CBBA requires communication at every instance, which can cause communication congestion and packet dropouts that lead towards performance degradation. In this paper, we propose an event-driven communication mechanism to overcome communication issues while retaining the theoretical properties of CBBA in terms of convergence and performance bounds. Theoretically, we show that the solution quality remains the same as that of CBBA and validate through Monte-Carlo simulations for varying numbers of targets, agents and bundles. The results show that the proposed algorithm (EDCBBA) achieves up to <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$52\%$</tex> reduction in the number of messages transmitted.