Mutual Visibility by Robots with Persistent Memory

This paper addresses one of the fundamental geometric formation problems, namely the mutual visibility problem, for a set of semi-synchronous, opaque robots occupying distinct positions in the Euclidean plane. Since robots are opaque, if three robots lie on a line, the middle robot obstructs the visions of the two other robots. The mutual visibility problem requires the robots to coordinate their movements to form a configuration, within finite time and without collision, in which no three robots are collinear. We assume that robots are endowed with constant bits of persistent memory. We consider the computational model [4] in which the persistent memory is used by the robots only to remember their previous internal states. This piece of information is not communicated or visible to the other robots. Except from this persistent memory, robots are oblivious i.e., they do not carry forward any other information from their previous computational cycles. The paper presents a distributed algorithm to solve the mutual visibility problem for a set of semi-synchronous robots using only 1 bit of persistent memory. The proposed algorithm also provides a self-stabilizing solution to the problem. The algorithm does not impose any other restriction on the capability of the robots and guarantees collision-free movements for the robots.