Clark School researchers test decentralized task allocation algorithms for UAV teams

A new paper appearing in IEEE Robotics and Automation Letters experimentally compares the performance of five state-of-the-art decentralized task allocation algorithms under imperfect communication conditions for teams of unmanned aerial vehicles (UAVs).

Experimental Comparison of Decentralized Task Allocation Algorithms Under Imperfect Communication was written by Clark School Aerospace Engineering graduate students Sharan Nayak, Mohamed Khalid M. Jaffar, and Estefany Carrillo; robotics graduate student Suyash Yeotikar; alumnus Eliot Rudnick-Cohen (ME Ph.D. 2019); Mechanical Engineering graduate student Ruchir Patel; Professor Jeffrey Herrmann (ME/ISR), Assistant Professor Huan Xu (AE/ISR), Professor Shapour Azarm (ME), and Assistant Professor Michael Otte (ME). The authors also are affiliated with the Maryland Robotics Center.

UAV teams have potential for search and rescue operations, firefighting and surveillance and reconnaissance missions. To be useful, the team members or “agents” need to communicate with each other, enabling task assignment coordination and verifying task completion. However, wireless communication in the real world is often unreliable, degraded or constrained, due to fading, path loss and interference, and other issues. These problems affect the ability of agents to communicate with each other.

The process of assigning tasks to agents in a team is known as task allocation. There are two groups of task allocation algorithms: centralized and decentralized. Centralized algorithms are based on a “master” agent that computes and assigns tasks for each agent. Decentralized algorithms do not have a master; all agents participate in computing and assigning tasks.

The performance of both groups of algorithms degrades under imperfect communication. It is known that centralized algorithms are susceptible to packet drops between master and agent. However, until the research described in this paper, little analysis has been done on the performance of decentralized task allocation algorithms under imperfect communication.

The paper compares five decentralized task allocation algorithms (CBAA, ACBBA, DHBA, HIPC, and PI) across many communication quality levels using three different communication models: Bernoulli, Gilbert-Elliot (G.E.), and Rayleigh Fading. The paper highlights differences in the performance of the decentralized algorithms across different communication conditions. The paper is the first systematic comparison of more than two decentralized algorithms.

The authors compare algorithms in two different scenarios, the second of which has not been studied extensively. First, in the “Collaborative visit scenario,” agents collaboratively visit known stationary targets. Second, in the “Collaborative search and visit scenario,” agents collaboratively search for unknown stationary targets and then visit them.

The authors consider two performance measures: the maximum (max) distance traveled by any agent and the max number of messages sent by any agent. All 30 combinations of algorithm, communication model, and scenario are evaluated with respect to both performance measures. Assuming constant velocity, the max distance traveled measure is proportional to the mission completion time, i.e., time taken by agents to complete all tasks.

The results of the experiments suggest that for the collaborative visit scenario, ACBBA generally performs better than other algorithms at high communication levels, given either Bernoulli or Rayleigh models. However, there is a trade-off with PI (less messages) when using the Gilbert-Elliot model. For the Rayleigh model with low communication, ACBBA performs the best. For the Bernoulli and Gilbert-Elliot models, ACBBA (less distance) shows a trade-off with HIPC and PI (less messages).

For the collaborative search and visit scenario, the authors found a trade-off exists between ACBBA (less distance) and CBAA (less messages) at high communication levels. At low communication levels, CBAA is generally more desirable, although there is a trade-off with HIPC (in general, if the Gilbert-Elliot model is used; and for the Ps = −35 dB level of Rayleigh model).

In the future the authors plan to expand their research using different parameter sets, objective functions, and new scenarios such as moving and dynamically added targets.

Published January 22, 2020