Computability of Perpetual Exploration in Highly Dynamic Rings
Computability of Perpetual Exploration in Highly Dynamic Rings
复制标题
高动态环中永续探索的可计算性
DOI：
10.1109/icdcs.2017.80
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
F. Petit
中科院分区：
文献类型：
--
作者：
Marjorie Bournat;S. Dubois;F. Petit
我们考虑由自主移动机器人组成的系统在高度动态的离散环境中进化，即，图中边缘可能不可预测地出现和消失，没有任何递归性，稳定性，也没有周期性假设。机器人是统一的（它们执行相同的算法），它们是匿名的（它们没有任何可观察到的ID），它们无法让它们一起通信，它们没有共同的方向感，它们没有与环境大小相关的全局知识。然而，它们中的每一个都被赋予了持久的记忆，并且能够检测到它是否单独站在当前位置。一个高度动态的环境是通过一个图来建模的，这样它的拓扑结构就会随着时间不断变化。在本文中，我们只考虑动态图，其中节点是匿名的，每个节点都可以无限频繁地从任何其他节点到达，并且其底层图（即由相同的节点集组成的静态图，其中包括至少出现一次的所有边）形成任意大小的环。在这种情况下，我们考虑永久探索的基本问题：每个节点需要被机器人无限次地访问。本文分析了该问题在（完全）同步条件下的可计算性，即研究了该问题关于机器人数量的确定性可解性。我们提供了三种算法和两种不可能结果，对于任何环尺寸，必要和足够数量的机器人来执行高动态环的永久探索。
We consider systems made of autonomous mobile robots evolving in highly dynamic discrete environment i.e., graphs where edges may appear and disappear unpredictably without any recurrence, stability, nor periodicity assumption. Robots are uniform (they execute the same algorithm), they are anonymous (they are devoid of any observable ID), they have no means allowing them to communicate together, they share no common sense of direction, and they have no global knowledge related to the size of the environment. However, each of them is endowed with persistent memory and is able to detect whether it stands alone at its current location. A highly dynamic environment is modeled by a graph such that its topology keeps continuously changing over time. In this paper, we consider only dynamic graphs in which nodes are anonymous, each of them is infinitely often reachable from any other one, and such that its underlying graph (i.e., the static graph made of the same set of nodes and that includes all edges that are present at least once over time) forms a ring of arbitrary size. In this context, we consider the fundamental problem of perpetual exploration: each node is required to be infinitely often visited by a robot. This paper analyzes the computability of this problem in (fully) synchronous settings, i.e., we study the deterministic solvability of the problem with respect to the number of robots. We provide three algorithms and two impossibility results that characterize, for any ring size, the necessary and sufficient number of robots to perform perpetual exploration of highly dynamic rings.
发现和评估机器人网络协议中的细粒度指标
DOI：
10.1109/srdsw.2014.34
发表时间：
2014
期刊：
Proceedings of the 33rd IEEE International Symposium on Reliable Distributed Systems Workshops
影响因子：
--
作者：
Francois Bonnet;Xavier Defago;Franck Petit;Maria Potop-Butucaru;Sebastien Tixeuil
通讯作者：
Sebastien Tixeuil