This work deals with the problem of gathering of $n$ oblivious mobile entities, called robots, with limited visibility, at a point (not known beforehand) placed on an infinite triangular grid. Earlier works of gathering mostly considered the robots either on a plane or on a circle or on a rectangular grid under both full and limited visibility. In the triangular grid, there are two works to the best of our knowledge. The first one is arbitrary pattern formation where full visibility is considered (\cite{C21}). The other one considers seven robots with 2- hop visibility that form a hexagon with one robot in the center of the hexagon in a collision-less environment under a fully synchronous scheduler (\cite{ShibataOS00K21}). In this work, we first show that gathering on a triangular grid with 1-hop vision of robots is not possible even under a fully synchronous scheduler if the robots do not agree on any axis. So one axis agreement has been considered in this work (i.e., the robots agree on a direction and its orientation). We have also showed that the lower bound for time is $\Omega(n)$ epochs when $n$ number of robots are gathering on an infinite triangular grid. An algorithm is then presented where a swarm of $n$ number of robots with 1-hop visibility can gather within $O(n)$ epochs under a semi-synchronous scheduler. So the algorithm presented here is time optimal.
翻译:这项工作涉及在无限三角网格上( 事先不为人知) 某个点( 无法预知) 收集美元隐蔽的移动实体( 叫做机器人) 的问题。 早期的收集工作大多将机器人视为在飞机上、 圆圈上或矩形网格上的机器人, 在完全和有限的可见度下进行。 在三角网格中, 我们最了解的是两种方法。 第一个是任意模式的形成, 考虑完全可见性 (\ cite{C21}) 。 另一个则考虑7个具有2升可见度的机器人, 在完全同步的定时器(\ cite{ ShibataOS00K21}) 下, 在无碰撞的三角网格环境中与一个机器人形成一个机器人的六边形( 机器人同意方向及其方向 ) 。 在这项工作中, 我们第一次显示, 以1HO- hop 视野的三角网格, 即使机器人在任何轴上无法达成一致, 也不可能在完全同步的定式中进行。 因此, 一个半轴协议在这项工作中( 机器人在一个方向及其方向上 美元 ), 。 我们还数 显示, 当一个O- x 时间在 的 的 的 节值 中, 一个机器人 的 的 的 的 的 时间 正在 以 。