World Scientific
  • Search
Skip main navigation

Cookies Notification

We use cookies on this site to enhance your user experience. By continuing to browse the site, you consent to the use of our cookies. Learn More
×
Our website is made possible by displaying certain online content using javascript.
In order to view the full content, please disable your ad blocker or whitelist our website www.worldscientific.com.

System Upgrade on Tue, Oct 25th, 2022 at 2am (EDT)

Existing users will be able to log into the site and access content. However, E-commerce and registration of new users may not be available for up to 12 hours.
For online purchase, please visit us again. Contact us at [email protected] for any enquiries.

SCATTER OF ROBOTS

    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

    • H. Andoet al., IEEE Transaction on Robotics and Automation 15(5), 818 (1999), DOI: 10.1109/70.795787. CrossrefGoogle Scholar
    • F. Aurenhammer, ACM Comput Surv. 23(3), 345 (1991), DOI: 10.1145/116873.116880. Crossref, ISIGoogle 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 Scholar
    • M. Cieliebaket al., Solving the robots gathering problem, Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP 2003) (2003) pp. 1181–1196. Google Scholar
    • M. 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
    • R. Cohen and D. Peleg, Theor. Comput. Sci. 399(2), 71 (2008), DOI: 10.1016/j.tcs.2008.02.007. Crossref, ISIGoogle 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 Scholar
    • Y. 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
    • Y. Dieudonné and F. Petit, 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 Scholar
    • Y. 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 Scholar
    • Yoann 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 ) . CrossrefGoogle Scholar
    • P. Flocchiniet al., 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 Scholar
    • P. Flocchiniet al., Gathering of autonomous mobile robots with limited visibility, STACS 2001 (2001) pp. 247–258. Google Scholar
    • P. Flocchiniet al., Pattern formation by autonomous robots without chirality, VIII International Colloquium on Structural Information and Communication Complexity (SIROCCO 2001) (2001) pp. 147–162. Google Scholar
    • B. Katreniak, Biangular circle formation by asynchronous mobile robots, 12th International Colloquium, on Structural Information and Communication Complexity (SIROCCO 2005) (2005) pp. 185–199. Google Scholar
    • B. 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 Scholar
    • G. 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
    • I. Suzuki and M. Yamashita, Intelligent Robots: Sensing, Modeling and Planning 305 (1996). Google Scholar
    • I. Suzuki and M. Yamashita, SIAM Journal of Computing 28(4), 1347 (1999), DOI: 10.1137/S009753979628292X. Crossref, ISIGoogle Scholar