Local Gathering of Mobile Robots in Three Dimensions

摘要: In this work, we initiate the research about Gathering problem for robots with limited viewing range in three-dimensional Euclidean space. problem, a set of initially scattered is required to gather at same position. The robots' capabilities are very restricted -- they do not agree on any coordinate system or compass, have range, no memory past and cannot communicate. We study two different time models, FSYNC (fully synchronized discrete rounds) continuous model. For FSYNC, introduce 3D-Go-To-The-Center-strategy prove runtime $\Theta(n^2)$ that matches currently best bound model plane [SPAA'11]. Our main result generalization contracting strategies (continuous time) from [Algosensors'17] three dimensions. strategies, every robot located global convex hull all positions moves full speed towards inside hull. $O(\Delta \cdot n^{3/2})$ strategy, where $\Delta$ denotes diameter initial configuration. This comes up factor $\sqrt{n}$ close lower $\Omega (\Delta n)$ which already true general, it might be hard decide whether movement maintains connectivity swarm, rendering design concrete challenging task. variant 3D-Go-To-The-Center keeps swarm connected. Moreover, give simple criterion an exemplary strategy based criterion.