Two scenarios used to compare decentralized algorithms in imperfect communication conditions.

Two scenarios used to compare decentralized algorithms in imperfect communication conditions.


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.

Related Articles:
Alum Rick Stamper appointed Provost and VP for Academic Affairs at Rose-Hulman
Do Good Robotics Symposium to explore technologies that benefit society and the planet
Alum Sagar Chowdhury wins ASME CIE Best Dissertation Award
Student autonomous drone racing team takes 2nd place at IROS
Advancing Healthcare through Robotics and Machine Learning
Special Delivery
Helping robots remember
Machine Learning's Translational Medicine
Student autonomous robotics competition slated for June 2019
It takes a swarm: These robots talk to each other, make decisions as a group

January 22, 2020

«Previous Story  



Current Headlines

Public health planners: Free resources for emergency health clinics

Clark School Engineers Create Solutions for a Crisis

UMD Researchers to Publish Study on Polyelectrolyte Brushes

UMD Mechanical Engineering Among Top 20 Nationwide: US News

Brand Savior

Pride of Maryland Solar Car Returns to Roots at Maryland

Poppler James Named Chair Elect for ASEE’s Continuing Professional Development Division

Giving Spotlight: A Commitment to the American Dream

Srebric to Receive 2020 USM Board of Regents Faculty Award for Excellence in Innovation

Robert Briber Named Interim Dean of Clark School

Back to top  
AML Home Clark School Home UMD Home ENME Home