In this paper, we consider the gathering problem of seven autonomous mobile robots on triangular grids. The gathering problem requires that, starting from any connected initial configuration where a subgraph induced by all robot nodes (nodes where a robot exists) constitutes one connected graph, robots reach a configuration such that the maximum distance between two robots is minimized. For the case of seven robots, gathering is achieved when one robot has six adjacent robot nodes (they form a shape like a hexagon). In this paper, we aim to clarify the relationship between the capability of robots and the solvability of gathering on a triangular grid. In particular, we focus on visibility range of robots. To discuss the solvability of the problem in terms of the visibility range, we consider strong assumptions except for visibility range. Concretely, we assume that robots are fully synchronous and they agree on the direction and orientation of the x-axis, and chirality in the triangular grid. In this setting, we first consider the weakest assumption about visibility range, i.e., robots with visibility range 1. In this case, we show that there exists no collision-free algorithm to solve the gathering problem. Next, we extend the visibility range to 2. In this case, we show that our algorithm can solve the problem from any connected initial configuration. Thus, the proposed algorithm is optimal in terms of visibility range.
翻译:在本文中, 我们考虑在三角网格上7个自主移动机器人的集合问题。 聚集问题要求, 从所有机器人节点( 机器人所在的节点) 所引出的一个子谱构成一个连接图的任何连接初始配置开始, 机器人达到一个配置, 使两个机器人之间的最大距离最小化。 就7个机器人而言, 当一个机器人有6个相邻的机器人节点( 它们形成像六边形的形状 ) 时, 聚集就可以实现。 在本文中, 我们首先要澄清机器人的能力和三角网格上集合的可溶性之间的关系。 特别是, 我们关注机器人的可见度范围。 要讨论问题的可溶性, 我们考虑除可见度范围外的强度假设。 具体地说, 我们假设机器人是完全同步的, 他们同意X轴和三角网格的动向方向和方向。 在本文中, 我们首先考虑对可见度范围最弱的假设, 即机器人与可见度范围 1 。 在本案中, 我们展示的是, 我们从可见度范围 存在任何不相联的可视性 的算法 。