论文标题
在三个维度上的本地聚会移动机器人
Local Gathering of Mobile Robots in Three Dimensions
论文作者
论文摘要
在这项工作中，我们启动有关三维欧几里得空间中观看范围有限的机器人收集问题的研究。在收集问题中，需要一组最初分散的机器人才能在同一位置收集。机器人的功能非常有限 - 它们在任何坐标系统或指南针上都不同意，观看范围有限，对过去没有记忆，也无法交流。我们在FSONC（完全同步的离散回合）和连续的时间模型中研究了两个不同时间模型的问题。对于Fsync，我们介绍了3D-Go-to-to-Center-Strategy，并证明了$θ（n^2）$的运行时间，该运行时间与欧几里得平面中同一型号的当前最佳运行时限制了[SPAA'11]。我们的主要结果是从[algosensors'17]到三个维度的合同策略（连续时间）的概括。在承包策略中，所有机器人位置的全球凸面上的每个机器人都以全速移动到凸船体的内部。对于任何三维签约策略，我们证明了$ o（δ\ cdot n^{3/2}）$的运行时限制，其中$Δ$表示初始配置的直径。这是$ \ sqrt {n} $接近$ω（δ\ cdot n）$的$ \ sqrt {n} $的因子，这在二维中已经是正确的。总的来说，观看范围有限的机器人可能很难确定它们是否位于全球凸船体上，并且哪个运动保持群的连通性，从而使混凝土合约策略的设计成为一个具有挑战性的任务。我们证明，3D-Go-to-the Center的连续变体正在收缩并保持群体连接。此外，我们为三维合同策略提供了一个简单的设计标准，该策略维持了群的连通性，并根据此标准引入了典型的策略。
In this work, we initiate the research about the Gathering problem for robots with limited viewing range in the three-dimensional Euclidean space. In the Gathering problem, a set of initially scattered robots is required to gather at the same position. The robots' capabilities are very restricted -- they do not agree on any coordinate system or compass, have a limited viewing range, have no memory of the past and cannot communicate. We study the problem in two different time models, in FSYNC (fully synchronized discrete rounds) and the continuous time model. For FSYNC, we introduce the 3D-Go-To-The-Center-strategy and prove a runtime of $Θ(n^2)$ that matches the currently best runtime bound for the same model in the Euclidean plane [SPAA'11]. Our main result is the generalization of contracting strategies (continuous time) from [Algosensors'17] to three dimensions. In contracting strategies, every robot that is located on the global convex hull of all robots' positions moves with full speed towards the inside of the convex hull. We prove a runtime bound of $O(Δ\cdot n^{3/2})$ for any three-dimensional contracting strategy, where $Δ$ denotes the diameter of the initial configuration. This comes up to a factor of $\sqrt{n}$ close to the lower bound of $Ω(Δ\cdot n)$ which is already true in two dimensions. In general, it might be hard for robots with limited viewing range to decide whether they are located on the global convex hull and which movement maintains the connectivity of the swarm, rendering the design of concrete contracting strategies a challenging task. We prove that the continuous variant of 3D-Go-To-The-Center is contracting and keeps the swarm connected. Moreover, we give a simple design criterion for three-dimensional contracting strategies that maintains the connectivity of the swarm and introduce an exemplary strategy based on this criterion.
