Taking Advantage of Symmetries: Gathering of Asynchronous Oblivious Robots on a Ring
Taking Advantage of Symmetries: Gathering of Asynchronous Oblivious Robots on a Ring
复制标题
利用对称性：异步遗忘机器人聚集在环上
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
A. Navarra
中科院分区：
文献类型：
--
作者：
R. Klasing;A. Kosowski;A. Navarra
最近考虑的一个基于机器人的计算模型利用相同的，无记忆的移动的单元放置在一个匿名图的节点。机器人在Look-Compute-Move循环中运行;在一个循环中，机器人获取当前配置的快照（Look），决定是否保持空闲或移动到与其当前位置相邻的节点之一（Compute），并在后一种情况下立即移动到该邻居（Move）。每个机器人异步执行循环。
在这样一个受限制的情况下，我们研究的机器人配置的对称性的影响，某些计算任务的可行性。更准确地说，我们处理的问题，收集所有机器人在一个节点的图形，并提出了一个解决方案的基础上，保序策略。当所考虑的图是一个无向环和机器人的数量足够大（超过18），这样的方法被证明是解决问题的所有开始的情况下，只要收集是可行的。这样，我们也关闭了公开的问题，特征对称的情况下，允许一个聚集环[R。Klasing，E. Markou，A.把异步的无意识移动的机器人聚集在一个环里，西奥。比较科学390（1），27-39，2008]。
所提出的保留冗余的方法，这是互补的冗余破坏技术在相关工作中发现，似乎是新的，并可能有进一步的应用在基于机器人的计算。
One of the recently considered models of robot-based computing makes use of identical, memoryless mobile units placed in nodes of an anonymous graph. The robots operate in Look-Compute-Move cycles; in one cycle, a robot takes a snapshot of the current configuration (Look), takes a decision whether to stay idle or to move to one of the nodes adjacent to its current position (Compute), and in the latter case makes an instantaneous move to this neighbor (Move). Cycles are performed asynchronously for each robot.
In such a restricted scenario, we study the influence of symmetries of the robot configuration on the feasibility of certain computational tasks. More precisely, we deal with the problem of gathering all robots at one node of the graph, and propose a solution based on a symmetry-preserving strategy. When the considered graph is an undirected ring and the number of robots is sufficiently large (more than 18), such an approach is proved to solve the problem for all starting situations, as long as gathering is feasible. In this way we also close the open problem of characterizing symmetric situations on the ring which admit a gathering [R. Klasing, E. Markou, A. Pelc: Gathering asynchronous oblivious mobile robots in a ring, Theor. Comp. Sci. 390(1), 27-39, 2008].
The proposed symmetry-preserving approach, which is complementary to symmetry-breaking techniques found in related work, appears to be new and may have further applications in robot-based computing.