New algorithms for multi-robot systems in low communication situations

A new paper by Clark School faculty, alumni and students explores the problem of task allocation among networked multi-robot systems when communication conditions are poor. It was recently published online in IEEE Access.

Distributed Task Allocation Algorithms for Multi-Agent Systems With Very Low Communication presents two new algorithms designed for situations when robot “agents” choose not to communicate. This may be for reasons of stealth, when there is considerable loss in communication signal over long distances, when hardware malfunctions, or when communication is actively jammed by an adversary. In such cases, agents may need to divide up tasks without knowing the status of other agents.

Giving robots algorithms that can handle these conditions is useful. Assuming that networked agents know the total number of agents in the workspace, the authors developed solutions that ensure all tasks are eventually completed—even if some agents in the network are destroyed. Their two new task allocation algorithms assume communication may not happen, but beneﬁt the robotic agents and their missions whenever communication is successful.

The work was conducted by ISR alumnus Akshay Bapat (MSSE 2020), now a robotics perception engineer with Magna International in Troy, Mich.; current M.Eng. in Robotics student Bharath Reddy Bora; Professor Jeffrey Herrmann (ME/ISR), Professor Shapour Azarm (ME), Assistant Professor Huan Mumu Xu (AE/ISR), and ISR-affiliated Assistant Professor Michael Otte (AE).

The first algorithm, the “Spatial Division Playbook Algorithm,” (SDPbA), divides tasks among agents based on an area decomposition. The second algorithm, the “Traveling Salesman Playbook Algorithm” (TSPbA), considers mission travel distance by leveraging an existing algorithm, Christoﬁdes’ 3/2 approximation algorithm. Both algorithms are designed to perform better than existing decentralized task allocation algorithms in scenarios with very low communication availability.

In the paper, the authors use simulations to compare the new SDPbA and TSPbA algorithms to four existing state-of-the-art task allocation algorithms (ACBBA, DHBA, PIA and GA) across multiple communication levels and multiple numbers of targets, and using three different communication models. In particular, they consider task allocation scenarios that involve visiting stationary targets, and study how performance changes across a variety of communication quality levels and target numbers, while keeping number of agents constant.

They find that both SDPbA and TSPbA offer trade-offs between using a simple and computationally efﬁcient approach and using a more sophisticated but more expensive approach. If the number of targets is small, TSPbA is only slightly computationally more expensive than SDPbA. If there are a large number of targets, TSPbA may generate a better solution but is signiﬁcantly more computationally expensive than SDPbA. Overall, the new algorithms perform favorably, in terms of the time required to ensure all targets are visited, in the special case when communication is very low.

The authors’ experimental results show that SDPbA and TSPbA perform better on average than current algorithms ACBBA, DHBA, PIA and GA at lower communication levels and at number of targets greater than 30, especially with respect to average mission completion time. TSPbA performs better than SDPbA in all cases except for when the number of targets are 10.

The playbook algorithms performed well in scenarios with very low communication and many targets regardless of communication model. This suggests that the playbook algorithms, and especially TSPbA, may have useful applications in a variety of low-communication settings.

Published January 19, 2023