Gathering Asynchronous and Oblivious Robots on Basic Graph Topologies Under the Look-Compute-Move Model - Search Theory: A Game Theoretic Perspective - page 209

c 2 in order to end the gathering. If the number of nodes occupied in T 1 is equal to
that in T 2 , it is always possible to determine which subtree is less than the other
with respect to a natural ordering on labeled trees (see [ 1 , 7 ]). To define the smaller
tree as the one with the robots closer to the root, we associate label 1 to empty
nodes, and label 0 to nodes occupied by robots. Then the algorithm would exploit
this ordering in order to detect the robots to move from one subtree towards the
root of the other one. If a robot moves over a node already occupied, the number
of occupied nodes in the original subtree decreases. As soon as one robot moves
towards the other subtree, the number of robots in the two subtrees is no longer
equal and the previous strategy can be applied. Similarly to what happened in the
case of even odd grids of Sect. 13.3.2 , the occurrence of multiplicities does not

affect the proposed algorithm.

×

13.5 Conclusion

In this chapter, we surveyed recent results about the gathering problem under the
Look-Compute-Move model in various graph topologies.
For most of the cases under investigation, it turned out that the problem has been
fully characterized. For trees and grids, the multiplicity detection capability does not
strengthen the model, that is, all the cases which admit gathering are still solvable
without such a capability. The only exception is provided by the very specific case
of three robots on a 2 2 grid. However, the multiplicity detection capability can

strengthen the model in the case of ring topologies. In the literature, the case that
assumes global-weak multiplicity detection has been fully characterized while that
assuming local-weak multiplicity detection still lacks of a unified algorithm, and
there are some open cases that deserve further investigations.
The study of different topologies has required very different and sometimes op-
posite approaches that stimulate main advances in robot-based computing systems.
On the other hand, some of the techniques described for different topologies share
common ideas that can be, therefore, used in other topologies. Infinite grids, tori,
and hypercubes might represent just a sampling set.
Another challenging direction would be that of investigating the minimum num-
ber of steps required by the robots to accomplish the gathering task. So far, the
research has mainly focused on the feasibility of the gathering, while few results
concern the minimization of the robots' movements. Similarly, low effort has been
spent in order to increase the opportunity to parallelize movements. As we have
seen for ring networks, at most two robots are allowed to move concurrently un-
less robots composing multiplicities must move. Whereas, on grids and trees, less
restrictions are imposed on the robots' movements.
It would be interesting to investigate how the proposed techniques may affect the
resolution of different tasks, as well as how different assumptions on the capability
of the robots may change the required strategies.

×