作者： Jannik Castenow , Thorsten Götte
DOI:
关键词:
摘要: We consider n robots with limited visibility: each robot can observe other robots only up to a constant distance denoted as the viewing range. The robots operate in discrete rounds that are either fully synchronous (FSYNC) or semi-synchronized (SSYNC). Most previously studied formation problems in this setting seek to bring the robots closer together (eg, GATHERING or CHAIN-FORMATION). In this work, we introduce the MAX-LINE-FORMATION problem, which has a contrary goal: to arrange the robots on a straight line of maximal length. First, we prove that the problem is impossible to solve by robots with a constant sized circular viewing range. The impossibility holds under comparably strong assumptions: robots that agree on both axes of their local coordinate systems in FSYNC. On the positive side, we show that the problem is solvable by robots with a constant square viewing range, ie, the robots can observe other robots that lie within a constant-sized square centered at their position. In this case, the robots need to agree on only one axis of their local coordinate systems. We derive two algorithms: the first algorithm considers oblivious robots (OBLOT) and converges to the optimal configuration in time O (n²· log (n/ɛ)) under the SSYNC scheduler (ε is a convergence parameter). The other algorithm makes use of locally visible lights (LUMI). It is designed for the FSYNC scheduler and can solve the problem exactly in optimal time O (n). Afterward, we show that both the algorithmic and the analysis techniques can also be applied to the GATHERING and CHAIN-FORMATION problem: we introduce an algorithm with a reduced viewing range for …