Optimum Algorithm for the Mutual Visibility Problem

We consider a distributed system of n >= 3 opaque robots deployed in the Euclidean plane. 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 form a configuration in which no three robots are collinear i.e., all the robots in the system are mutually visible. Robots work without any centralized control. We considers the FSTATE computational model in which each robot is endowed with an additional constant amount of persistent memory to retain some information of their previous states [3]. This information is not available to the other robots in the system. Except from this persistent memory, the robots are oblivious i.e., they do not carry forward any other information from their previous computational cycles. The robots do not have any explicit message passing capabilities. Under these weak settings, we present a deterministic distributed algorithm to solve the mutual visibility problem for a set of synchronous robots using only 1 bit of persistent memory. The proposed algorithm solves the mutual visibility problem in 2 rounds and guarantees collision-free movements for the robots. The algorithm is optimum in terms of round complexity, the amount of memory for the FSTATE computational model and number of movements for the robots.