Résumé | In this paper, we consider the problem of formation of a series of geometric patterns by a network of oblivious mobile robots that communicate only through vision.
So far, the problem has been studied in models where robots are either assumed to have distinct identifiers or to be completely anonymous.
To generalize these results and to better understand how anonymity affects the computational power of robots, we study the problem in a new model, introduced recently in cite{Delporte2011}, in which n robots may share up to 1 <= l <= n different identifiers.
We present necessary and sufficient conditions, relating symmetricity and homonymy, that makes the problem solvable.
To present our algorithms, we use a function that computes the Weber point for many regular and symmetric configurations. This function is interesting in its own right, since the problem of finding Weber points has been solved up to now for only few other patterns.
Das2010:
S. Das, P. Flocchini, N. Santoro and M. Yamashita. On the computational power of oblivious robots: forming a series of geometric patterns. In PODC 2010.
Delporte2011:
C. Delporte-Gallet, H. Fauconnier, R. Guerraoui, T. Hung, A. Kermarrec, and E. Ruppert. Byzantine agreement with homonyms. In PODC 2011.
****
Zohir Bouzid is doing his PhD with Sébastien Tixeuil in Paris. |