Experimental Comparison of Decentralized Task Allocation Algorithms Under Imperfect Communication
Sharan Nayak, Suyash Yeotikar, Estefany Carrillo, Eliot Rudnick-Cohen, Mohamed Khalid M Jaffar, Ruchir Patel, Shapour Azarm, Jeffrey W. Herrmann, Huan Xu, Michael Otte
Abstract
We compare the performance of five state of the art decentralized task allocation algorithms under imperfect communication conditions. The decentralized algorithms we consider are CBAA, ACBBA, DHBA, HIPC and PI. All algorithms are evaluated using three different models of communication, including the Bernoulli model, the Gilbert-Elliot model, and the Rayleigh Fading model. All 15 of the resulting combinations of an algorithm with a communication model are evaluated in two different problem scenarios: (1) Collaborative visit, a scenario in which the agents have to collaboratively visit known stationary targets. (2) Collaborative search and visit, a scenario in which the agents have to collaboratively search for and then visit unknown stationary target locations. Each algorithm is evaluated in each scenario using two performance measures: (1) the maximum distance traveled by any agent (2) the maximum number of messages sent by any agent. Real-time experimental simulations show the trade-offs that exists between these five algorithms at different communication conditions.