Time-Optimal Geodesic Mutual Visibility of Robots on Grids Within Minimum Area

For a set of robots disposed on the Euclidean plane, Mutual Visibility is often desirable. The requirement is to move robots without collisions so as to achieve a placement where no three robots are collinear. For robots moving on graphs, we consider the Geodesic Mutual Visibility (GMV) problem. Robots move along the edges of the graph, without collisions, so as to occupy some vertices that guarantee they become pairwise geodesic mutually visible. This means that there is a shortest path (i.e., a “geodesic”) between each pair of robots along which no other robots reside. We study this problem in the context of square grids for robots operating under the standard Look-Compute-Move model. We add the further requirement to obtain a placement of the robots so as that the final bounding rectangle enclosing all the robots is of minimum area. This leads to the GMV_area version of the problem. We show that GMVarea can be solved by a time-optimal distributed algorithm for synchronous robots sharing chirality.