The Geodesic Mutual Visibility Problem for Oblivious Robots: the case of Trees

The Mutual Visibility is a well-known problem in the context of mobile robots. For a set of n robots disposed in the Euclidean plane, it asks for moving the robots without collisions so as to achieve a placement ensuring that no three robots are collinear. Here we introduce the Geodesic Mutual Visibility problem, a possible counterpart for robots moving in a discrete environment. For a set of robots disposed on the vertices of a graph, it asks for moving the robots so that they are pairwise geodesic mutually visible, that is there is a shortest path (i.e., a "geodesic") between each pair of robots along which no other robots reside. It is known that, for tree topologies, the maximum number of robots that can be disposed by respecting the geodesic mutual visibility equals the number of leaves. Given a tree T with (T) leaves, we consider n ≤ (T) identical, mobile and semi-synchronous robots disposed on n different vertices of T, and we study the problem to make the robots move so as to reach a configuration where the geodesic mutual visibility is achieved. We propose a distributed algorithm, along with its correctness, for configurations not admitting critical vertices. Intuitively, a vertex v is critical if two or more equivalent robots must pass through v in order to reach a leaf, hence potentially collide in v. Furthermore, we provide an extensive discussion about the implications as well as complications arising when admitting critical vertices and/or the synchronous or the asynchronous settings, along with impossibility results or possible strategies of resolution to investigate.