SCATTER OF ROBOTS
Abstract
In this paper, we investigate the scatter problem, which is defined as follows: Given a set of n robots, regardless of the initial position of the robots on the plane, eventually, no two robots are located at the same position forever. We show that this problem cannot be deterministically solved. Next, we propose a randomized algorithm. The proposed solution is trivially self-stabilizing. We then show how to design a self-stabilizing version of any deterministic solution for the Pattern Formation and the Gathering problems for any number n ≥ 2 of robots.
A preliminary version of this work appeared in [12].
References
- IEEE Transaction on Robotics and Automation 15(5), 818 (1999), DOI: 10.1109/70.795787. Crossref, Google Scholar
- ACM Comput Surv. 23(3), 345 (1991), DOI: 10.1145/116873.116880. Crossref, ISI, Google Scholar
D. Canepa and M. Gradinariu Potop-Butucaru , Flocking via leader election in robot networks, 9th International Symposium, on Stabilization, Safety, and Security of Distributed Systems (SSS 2007)4838,Lecture Notes in Computer Science (Springer, 2007) pp. 52–66. Google ScholarM. Cieliebak , Solving the robots gathering problem, Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP 2003) (2003) pp. 1181–1196. Google ScholarM. Cieliebak and G. Prencipe , Gathering autonomous mobile robots, 9th International Colloquium on Structural Information and Communication Complexity (SIROCCO 9) (2002) pp. 57–72. Google Scholar- Theor. Comput. Sci. 399(2), 71 (2008), DOI: 10.1016/j.tcs.2008.02.007. Crossref, ISI, Google Scholar
X. Defago and A. Konagaya , Circle formation for oblivious anonymous mobile robots with no common sense of orientation, 2nd ACM International Annual Workshop on Principles of Mobile Computing (POMC 2002) (2002) pp. 97–104. Google ScholarY. Dieudonné , O. Labbani-Igbida and F. Petit , Circle formation of weak mobile robots, 8th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS 2006)4280,Lecture Notes in Computer Science (Springer, 2006) pp. 262–275. Google Scholar- Information Processing Letters 104(4), 156 (2007). Google Scholar
Y. Dieudonné and F. Petit , Deterministic leader election in anonymous sensor networks without common coodinated system, 11th International Conference On Principles of Distributed Systems (OPODIS 2007)4878,Lecture Notes in Computer Science (Springer, 2007) pp. 132–142. Google ScholarY. Dieudonné and F. Petit , Swing words to make circle formation quiescent, 14th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2007)4474,Lecture Notes in Computer Science (Springer, 2007) pp. 166–179. Google ScholarYoann Dieudonné and Franck Petit , Robots and demons (the code of the origins), Fun with Algorithms, 4th International Conference (FUN 2007)4475,Lecture Notes in Computer Science (Springer, 2007) pp. 108–119. Google Scholar-
S. Dolev , Self-Stabilization ( The MIT Press , 2000 ) . Crossref, Google Scholar P. Flocchini , Hard tasks for weak robots: The role of common knowledge in pattern formation by autonomous mobile robots, 10th Annual International Symposium on Algorithms and Computation (ISAAC 99) (1999) pp. 93–102. Google ScholarP. Flocchini , Gathering of autonomous mobile robots with limited visibility, STACS 2001 (2001) pp. 247–258. Google ScholarP. Flocchini , Pattern formation by autonomous robots without chirality, VIII International Colloquium on Structural Information and Communication Complexity (SIROCCO 2001) (2001) pp. 147–162. Google ScholarB. Katreniak , Biangular circle formation by asynchronous mobile robots, 12th International Colloquium, on Structural Information and Communication Complexity (SIROCCO 2005) (2005) pp. 185–199. Google ScholarB. Katreniak and Jana Katreniaková , On the inability of gathering by asynchronous mobile robots with initial movements, ECAI 2006, 17th European Conference on Artificial Intelligence (2006) pp. 255–259. Google ScholarG. Prencipe , Instantaneous actions vs. full asynchronicity: Controlling and coordinating a set of autonomous mobile robots, ICTCS 2001 (2001) pp. 185–190. Google Scholar- G Prencipe. Distributed Coordination of a Set of Autonomous Mobile Robots. PhD thesis, Dipartimento di Informatica, University of Pisa, 2002 . Google Scholar
- Intelligent Robots: Sensing, Modeling and Planning 305 (1996). Google Scholar
- SIAM Journal of Computing 28(4), 1347 (1999), DOI: 10.1137/S009753979628292X. Crossref, ISI, Google Scholar


