Gathering of robots on anonymous grids and trees without multiplicity detection

The paper studies the gathering problem on grid and tree networks. A team of robots placed at different nodes of the input graph, has to meet at some node and remain there. Robots operate in Look–Compute–Move cycles; in one cycle, a robot perceives the current configuration in terms of occupied nodes (Look), decides whether to move toward one of its neighbors (Compute), and in the positive case makes the computed move instantaneously (Move). Cycles are performed asynchronously for each robot. The problem has been deeply studied for the case of ring networks. However, the known techniques used on rings cannot be directly extended to grids and trees. Moreover, on rings, another assumption concerning the so-called multiplicity detection capability was required in order to accomplish the gathering task. That is, a robot is able to detect during its Look operation whether a node is empty, or occupied by one robot, or occupied by an undefined number of robots greater than one. In this paper, we provide a full characterization about gatherable configurations for grids and trees. In particular, we show that on these topologies, the multiplicity detection is not required. Very interestingly, sometimes the problem appears trivial, as it is for the case of grids with both odd sides, while sometimes the involved techniques require new insights with respect to the well-studied ring case. Moreover, our results reveal the importance of structures like grids and trees that allow to overcome the multiplicity detection with respect to the ring case.