Computability of Perpetual Exploration in Highly Dynamic Rings

摘要

We consider systems made of autonomous mobile robots evolving in highly\ndynamic discrete environment i.e., graphs where edges may appear and disappear\nunpredictably without any recurrence, stability, nor periodicity assumption.\nRobots are uniform (they execute the same algorithm), they are anonymous (they\nare devoid of any observable ID), they have no means allowing them to\ncommunicate together, they share no common sense of direction, and they have no\nglobal knowledge related to the size of the environment. However, each of them\nis endowed with persistent memory and is able to detect whether it stands alone\nat its current location. A highly dynamic environment is modeled by a graph\nsuch that its topology keeps continuously changing over time. In this paper, we\nconsider only dynamic graphs in which nodes are anonymous, each of them is\ninfinitely often reachable from any other one, and such that its underlying\ngraph (i.e., the static graph made of the same set of nodes and that includes\nall edges that are present at least once over time) forms a ring of arbitrary\nsize. In this context, we consider the fundamental problem of perpetual\nexploration: each node is required to be infinitely often visited by a robot.\nThis paper analyzes the computability of this problem in (fully) synchronous\nsettings, i.e., we study the deterministic solvability of the problem with\nrespect to the number of robots. We provide three algorithms and two\nimpossibility results that characterize, for any ring size, the necessary and\nsufficient number of robots to perform perpetual exploration of highly dynamic\nrings.\n