search

UMD    AML





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
Diving Deeper into Competition, and Recruitment
Yu Named Elkins Professor
Miao Yu receives NSF funding to develop ice-measuring sensors
Modi Briefed on UMD-led Aquaculture Research
Michael Bonthron Wins NDSEG Fellowship
UMD’s Tubaldi Wins NSF CAREER Award

January 22, 2020


«Previous Story  

 

 

Current Headlines

Agents of Positive Change: Highlighting Women Maryland Engineers

Balachandran, Cameron, Yu Receive 2024 MURI Award

A Special Ceremony Honoring Bala Balachandran

Alumni Spotlight: José Cyrano Ruiz Cabarrús

3D and Beyond: UMD Researchers Explore Synthetic Dimensions

Celebrating Black Engineers: Philip Lovell

Fitzgerald Walker Honored By MCAMW

Clark School's Online Master of Engineering Soars to No. 6 National Rank

Celebrating the Impact of Black Maryland Engineers and Leaders

A Wider Lens

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