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 Tools annual

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 Tools monthly

Global: Zendy Plus monthly

Presents the access of premium content as premium feature

Premium Content

Global: Zendy Plus annual

Global: Zendy Free Plan

We consider a swarm of $n$ robots in \mathbb{R}^d. The robots are oblivious,disoriented (no common coordinate system/compass), and have limited visibility(observe other robots up to a constant distance). The basic formation taskgathering requires that all robots reach the same, not predefined position. Inthe related near-gathering task, they must reach distinct positions such thatevery robot sees the entire swarm. In the considered setting, gathering can besolved in $\mathcal{O}(n + \Delta^2)$ synchronous rounds both in two and threedimensions, where $\Delta$ denotes the initial maximal distance of two robots.In this work, we formalize a key property of efficient gathering protocols anduse it to define $\lambda$-contracting protocols. Any such protocol gathers $n$robots in the $d$-dimensional space in $\mathcal{O}(\Delta^2)$ synchronousrounds. Moreover, we prove a corresponding lower bound stating that anyprotocol in which robots move to target points inside of the local convex hullsof their neighborhoods -- $\lambda$-contracting protocols have this property --requires $\Omega(\Delta^2)$ rounds to gather all robots. Among others, we provethat the $d$-dimensional generalization of the GtC-protocol is$\lambda$-contracting. Remarkably, our improved and generalized runtime boundis independent of $n$ and $d$. The independence of $d$ answers an open researchquestion. We also introduce an approach to make any $\lambda$-contractingprotocol collisionfree to solve near-gathering. The resulting protocolsmaintain the runtime of $\Theta (\Delta^2)$ and work even in thesemi-synchronous model.

A Unifying Approach to Efficient (Near)-Gathering of Disoriented Robots with Limited Visibility