search

UMD     This Site





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:
Aerodynamic interaction model improves quadrotor flight stability in gusty winds
Workshop focuses on needs of autonomous agent networks
Hybrid compositional planning for UAV rescue missions
How to steer a fish-inspired robot
New model predictive control framework improves reactive navigation for autonomous robots
A cooperative control algorithm for robotic search and rescue
Port-Hamiltonian modeling formalism framework proposed for swarms
Alum Evandro Valente testifies on two economic development bills
Discoveries from NASA's Parker Solar Probe published in Nature
Alum Hyun Jung takes first place in two Pathology AI Platform Challenge tasks

January 22, 2020


«Previous Story  

 

 

Current Headlines

In Race With Virus, Researchers Speed Development of Medical Equipment

GAMMA Group's Research on Emotional Modeling and Social Robotics Featured in Forbes

Srivastava wins NSF funding for integrated circuit fabrication security

Protection Collections Abound for Local Health Care Workers

New U.S. Patent: Integrated Onboard Chargers for Plug-In Vehicles

Public health planners: Free resources for emergency health clinics

Planning and learning algorithms developed for refinement acting engine

Clark School Engineers Create Solutions for a Crisis

COVID-19 Decision Making Gets a Big Data Boost

Researchers from Poland report results aided by UMD's AIM Lab

 
 
Back to top  
Home Clark School Home UMD Home