2022/06/15 by Castenow, Jannik, Harbig, Jonas, Jung, Daniel +3
#Distributed #FOS: Computer and information sciences #Parallel #and Cluster Computing (cs.DC)
paper · doi:10.48550/arxiv.2206.07567
We consider a swarm of n robots in ℝ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 task gathering requires that all robots reach the same, not predefined position. In the related near-gathering task, they must reach distinct positions such that every robot sees the entire swarm. In the considered setting, gathering can be solved in O(n + Δ2) synchronous rounds both in two and three dimensions, where Δ denotes the initial maximal distance of two robots. In this work, we formalize a key property of efficient gathering protocols and use it to define λ-contracting protocols. Any such protocol gathers n robots in the d-dimensional space in O(Δ2) synchronous rounds. Moreover, we prove a corresponding lower bound stating that any protocol in which robots move to target points inside of the local convex hulls of their neighborhoods -- λ-contracting protocols have this property -- requires Ω(Δ2) rounds to gather all robots. Among others, we prove that the d-dimensional generalization of the GtC-protocol is λ-contracting. Remarkably, our improved and generalized runtime bound is independent of n and d. The independence of d answers an open research question. We also introduce an approach to make any λ-contracting protocol collisionfree to solve near-gathering. The resulting protocols maintain the runtime of Θ(Δ2) and work even in the semi-synchronous model.