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:
$100,000 investment from Amazon to power Clark School initiatives in diversity, robotics research and education
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
Maryland engineers receive $10M to transform shellfish farming
Sci-Fi Social Distancing?
New model can help decisionmakers planning to retrofit buildings for energy efficiency
Two Clark School teams take top spots in VFS micro air vehicle competition
Student autonomous drone racing team takes 2nd place at IROS
Advancing Healthcare through Robotics and Machine Learning

January 22, 2020

«Previous Story  



Current Headlines

A Tech Rx for COVID Recovery at Home

Bar-Cohen, Distinguished University Professor and Thermal Packaging Pioneer, Passes at 74

$100,000 investment from Amazon to power Clark School initiatives in diversity, robotics research and education

Xu Wins Best Student Paper Award at ASME Dynamic Systems and Control Conference

Paying It Forward

Calculating Uncertainties in Chaotic Turbulent Flow Models

Challenges and Opportunities: Student Internships During 2020

Mehr Gift Establishes Two Funds at UMD

Computer Algorithms Help Improve Emissions Control

Alumnus Charles Dickerson Named President of SUEZ North America's Utility Division

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