Enabling Ring Exploration with Myopic Oblivious Robots
Enabling Ring Exploration with Myopic Oblivious Robots
复制标题
使用近视遗忘机器人进行环形探索
DOI：
10.1109/ipdpsw.2015.137
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
F. Petit
中科院分区：
文献类型：
--
作者：
A. Datta;Anissa Lamani;L. Larmore;F. Petit
我们考虑了使用异步和不经意机器人的匿名、无定向环的确定性终止探索，我们解决了在所需机器人数量和视觉能力方面尽可能减少资源的问题。我们假设近视机器人，也就是说，他们的视力被限制在一定的距离f内，以跳数计算。众所周知，假设能见度无限大，至少需要四个相同的(概率或确定性)机器人来解决终止探测的问题。我们还知道，假设f=1，只有同步机器人才能确定地解决这个问题。换言之，假设f=1，则不存在异步解。通过对比，我们证明了仅使用少数近视机器人，终止探索仍然可以异步求解。假设f=3，我们首先证明了在异步环境下，确定性地解决终止探索问题需要5个机器人。接下来，我们提供了一个与此界限匹配的异步算法，但它要求机器人从连续的节点开始。然后，我们给出了一个算法，该算法可以从只使用7个异步机器人的任何可能的初始配置开始。最后，我们证明了当f=2时，这个问题也可以解决。我们给出了一个针对7个异步机器人的算法。
We consider the deterministic terminating exploration of an anonymous, unoriented ring using asynchronous and oblivious robots.We address the problem of reducing the resource as much as possible in terms of number of required robots and in terms of vision capacities. We assume myopic robots, i.e., their vision is limited within a certain distance f, computed in terms of hops. It is known that assuming an infinite visibility, at least four identical (probabilistic or deterministic) robots are necessary to solve terminating exploration. It is also known that assuming f = 1, the problem can be deterministically solved with synchronous robots only. In other words, no asynchronous solution exists assuming f = 1.By contrast, we show that the terminating exploration can still be solved asynchronously using a few number of myopic robots only. Assuming f = 3, we first show that 5 robots are necessary to solve the terminating exploration deterministically in asynchronous settings. Next, we provide an asynchronous algorithm that matches this bound, but it requires that the robots start on contiguous nodes. We then give an algorithm that can start from any possible initial configuration that uses 7 asynchronous robots only. Finally, we show that the problem can also be solved assuming f = 2. We present an algorithm for 7 asynchronous robots.