论文标题
在无限三角网格上近视机器人的时间最佳收集
Time Optimal Gathering of Myopic Robots on an Infinite Triangular Grid
论文作者
论文摘要
这项工作涉及在一个无限三角网格上收集$ n $ oblevious移动实体（未知）的问题。机器人被认为是近视的，即机器人的可见度有限。早期收集的作品主要考虑在平面上，圆或矩形网格上的机器人。在三角形网格中，据我们所知，有两种作品。第一个是Cicerone等人的作者。在考虑全面可见性的任意模式形成下。 Shibata等人的另一个。它认为在完全同步的调度程序下，在无碰撞环境中，在六角形的中心形成六角形的七个机器人。 在这项工作中，我们首先表明，即使在机器人在任何轴上不同意的情况下，在完全同步的调度程序下，也无法在具有1跳的机器人视觉的三角形网格上进行聚集。因此，在这项工作中考虑了一项轴协议（即机器人就方向及其方向达成共识）。我们还表明，当$ n $机器人数量在无限三角网格上聚集时，时间的下限为$ω（n）$时期。然后，提出了一种算法，其中有$ n $ n $数量的具有1个跳投可见性的机器人可以在半同步调度程序下聚集在$ o（n）$时期内。因此，此处介绍的算法是时间最佳。
This work deals with the problem of gathering $n$ oblivious mobile entities, called robots, at a point (not known beforehand) placed on an infinite triangular grid. The robots are considered to be myopic, i.e., robots have limited visibility. 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 by Cicerone et al. on arbitrary pattern formation where full visibility is considered. The other one by Shibata et al. which 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 . 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 shown that the lower bound for time is $Ω(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.
