English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In this paper we explore the problem of task allocation when communication is very low, e.g., when the probability of a successful message between agents is <inline-formula> <tex-math notation="LaTeX">$\ll 0.01$ </tex-math></inline-formula>. Such situations may occur when agents choose not to communicate for reasons of stealth or when agent-to-agent communication is actively jammed by an adversary. In such cases, agents may need to divide tasks without knowing the locations of each other. Given the assumption that agents know the total number of agents in the workspace, we investigate solutions that ensure all tasks are eventually completed&#x2014;even if some of the agents are destroyed. We present two task allocation algorithms that assume communication may not happen, but that benefit whenever communications are successful. (1) The Spatial Division Playbook Algorithm divides task among agents based on an area decomposition. (2) The Traveling Salesman Playbook Algorithm considers mission travel distance by leveraging Christofides&#x2019; 3/2 approximation algorithm. These algorithms have task completion runtime complexity of <inline-formula> <tex-math notation="LaTeX">$O(m \log m)$ </tex-math></inline-formula> and <inline-formula> <tex-math notation="LaTeX">$O(m^{3})$ </tex-math></inline-formula>, respectively, where <inline-formula> <tex-math notation="LaTeX">$m$ </tex-math></inline-formula> refers to the total number of tasks. We compare both algorithms to four state-of-the-art task allocation algorithms &#x2014; ACBBA, DHBA, PIA and GA &#x2014; across multiple communication levels and multiple numbers of targets, and using three different communication models. 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.

Distributed Task Allocation Algorithms for Multi-Agent Systems With Very Low Communication