Performance of the Asynchronous Consensus Based Bundle Algorithm in Lossy Network Environments

Abstract

We study multi-agent task allocation where multiple tasks must be divided among multiple autonomous robots. Algorithms for solving such problems are typically developed under the assumption of perfect communication, without considering the lossy nature of the underlying wireless network. In this paper, leveraging a sophisticated unmanned aerial vehicle (UAV) network simulation platform, we investigate the sensitivity of a well-known decentralized task allocation framework to realistic communication constraints. In particular, we use the University at Buffalo's Airborne Networking and Communications (UB-ANC) Emulator to demonstrate that the Asynchronous Consensus Based Bundle Algorithm (ACBBA) deviates from its desired theoretical behavior when it is deployed in a realistic (lossy) network setting, especially as the number of agents (UAVs) and number of tasks increase. This may manifest in the form of the same task being assigned to multiple agents and/or some tasks not being assigned at all.