A unified approach for different tasks on rings in robot-based computing systems

摘要

A set of autonomous robots have to collaborate in order to accomplish a common task in a ring-topology where neither nodes nor edges are labeled. We present a unified approach to solve three important problems: the exclusive perpetual exploration, the exclusive perpetual search and the gathering problems. In the first problem, each robot aims at visiting each node infinitely often; in perpetual graph searching, the team of robots aims at clearing the whole network infinitely often; and in the gathering problem, all robots must eventually occupy the same node. We investigate these tasks in the Look-Compute-Move distributed computing model where the robots cannot communicate but can perceive the positions of other robots. Each robot is equipped with visibility sensors and motion actuators, and it operates in asynchronous cycles. In each cycle, a robot takes a snapshot of the current global configuration (Look), then, based on the perceived configuration, takes a decision to stay idle or to move to one of its adjacent nodes (Compute), and in the latter case it eventually moves to this neighbor (Move). Moreover, robots are endowed with very weak capabilities. Namely, they are anonymous, oblivious, uniform (execute the same algorithm) and have no common sense of orientation. In this setting, we devise algorithms that, starting from an exclusive rigid (i.e. a periodic and asymmetric) configuration, solve the three above problems in anonymous ring-topologies.