On the mutual visibility of fat mobile robots.

摘要

Given a set of n ≥ 1 autonomous, anonymous, history-oblivious, silent, and possibly disoriented mobile robots operating following Look-Compute-Move cycles in the Euclidean plane, we consider the fundamental problem of providing mutual visibility for them, i.e., the robots must reposition themselves to reach a configuration in finite time without collisions where they all see each other. This problem arises under obstructed visibility where a robot can not see another robot if there lies a third robot on the line segment connecting their positions. This problem is important since it provides a basis to solve many other problems under obstructed visibility, and it has applications in many scenarios including coverage, intruder detection, etc. The literature on this problem assumed that the robots are dimensionless points, i.e., they occupy no space. However, this assumption can be easily refuted. For example, in reality, robots are not dimensionless, but they have a physical extent.;Therefore, in this thesis, we initiate the study of the mutual visibility problem for the robots with extents. We address this problem in the recently proposed robots with lights model, where each robot is equipped with an externally visible persistent light that can assume colors from a fixed set of colors. This model corresponds to the classical oblivious robots model when the number of colors in the set is 1. In particular, we first develop a deterministic algorithm that provides mutual visibility for robots with extents of unit disc size avoiding collisions using only 4 colors in the color set. Note that this algorithm works for fat robots under the fully synchronous and semi-synchronous settings. We then present a faster algorithm that solves this problem in O(n) rounds in the fully synchronous setting.