Document Open Access Logo

Collision-Free Pattern Formation

Authors Rachid Guerraoui, Alexandre Maurer

PDF
Thumbnail PDF

File

LIPIcs.OPODIS.2016.16.pdf
  • Filesize: 459 kB
  • 13 pages

Document Identifiers

Author Details

Rachid Guerraoui
Alexandre Maurer

Cite As Get BibTex

Rachid Guerraoui and Alexandre Maurer. Collision-Free Pattern Formation. In 20th International Conference on Principles of Distributed Systems (OPODIS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 70, pp. 16:1-16:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017) https://doi.org/10.4230/LIPIcs.OPODIS.2016.16

Abstract

Shoals of small fishes can change their collective shape and form a specific pattern. They do so efficiently (in parallel) and without collision.

In this paper, we study the analog problem of distributed pattern formation. A set of processes needs to move from a set of initial positions to a set of final positions. The processes are oblivious (no internal memory) and must preserve, at any time, a minimal distance between them.

A naive solution would be to move the processes one by one, but this would take too long. The difficulty here is to move the processes simultaneously in clearly delimited phases, no matter how unfavorable the initial configuration may be. We solve this by treating the problem "dimension by dimension": the processes first form 1D trails, then gather into a 2D shape (this technique can be generalized to higher dimensions).

We present an optimal algorithm which time complexity depends linearly on the radius of the smallest circle containing both initial and final positions. The algorithm is self-stabilizing, as the processes are oblivious and the initial positions are arbitrary.

Subject Classification

Keywords
  • Pattern formation
  • Collision
  • Landmarks

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Chrysovalandis Agathangelou, Chryssis Georgiou, and Marios Mavronicolas. A distributed algorithm for gathering many fat mobile robots in the plane. In ACM Symposium on Principles of Distributed Computing, PODC'13, Montreal, QC, Canada, July 22-24, 2013, pages 250-259, 2013. URL: http://dx.doi.org/10.1145/2484239.2484266.
  2. Thomas Bäck. Evolutionary algorithms in theory and practice: evolution strategies, evolutionary programming, genetic algorithms. Oxford university press, 1996. Google Scholar
  3. Leoncio Briones, Paul Bustamante, and Miguel Serna. Wall-climbing robot for inspection in nuclear power plants. In Robotics and Automation, pages 1409-1414. IEEE, 1994. Google Scholar
  4. Sruti Gan Chaudhuri and Krishnendu Mukhopadhyaya. Gathering asynchronous transparent fat robots. In Distributed Computing and Internet Technology, pages 170-175. Springer, 2010. Google Scholar
  5. Jurek Czyzowicz, Leszek Gasieniec, and Andrzej Pelc. Gathering few fat mobile robots in the plane. Theoretical Computer Science, 410(6):481-499, 2009. Google Scholar
  6. Jurek Czyzowicz, Evangelos Kranakis, and Eduardo Pacheco. Localization for a system of colliding robots. In Automata, Languages, and Programming, pages 508-519. Springer, 2013. Google Scholar
  7. Suparno Datta, Ayan Dutta, Sruti Gan Chaudhuri, and Krishnendu Mukhopadhyaya. Circle formation by asynchronous transparent fat robots. In Distributed Computing and Internet Technology, 9th International Conference, ICDCIT 2013, Bhubaneswar, India, February 5-8, 2013. Proceedings, pages 195-207, 2013. URL: http://dx.doi.org/10.1007/978-3-642-36071-8_15.
  8. Xavier Défago and Samia Souissi. Non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformity. Theoretical Computer Science, 396(1):97-112, 2008. Google Scholar
  9. Zahra Derakhshandeh, Robert Gmyr, Andréa W. Richa, Christian Scheideler, Thim Strothmann, and Shimrit Tzur-David. Infinite object coating in the amoebot model. CoRR, abs/1411.2356, 2014. URL: http://arxiv.org/abs/1411.2356.
  10. Yoann Dieudonné and Franck Petit. Scatter of robots. Parallel Processing Letters, 19(01):175-184, 2009. Google Scholar
  11. Shlomi Dolev. Self-Stabilization. MIT Press, 2000. Google Scholar
  12. Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Distributed computing by oblivious mobile robots. Synthesis Lectures on Distributed Computing Theory, 3(2):1-185, 2012. Google Scholar
  13. Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Peter Widmayer. Arbitrary pattern formation by asynchronous, anonymous, oblivious robots. Theoretical Computer Science, 407(1):412-447, 2008. Google Scholar
  14. Nao Fujinaga, Hirotaka Ono, Shuji Kijima, and Masafumi Yamashita. Pattern formation through optimum matching by oblivious CORDA robots. In Principles of Distributed Systems - 14th International Conference, OPODIS 2010, Tozeur, Tunisia, December 14-17, 2010. Proceedings, pages 1-15, 2010. URL: http://dx.doi.org/10.1007/978-3-642-17653-1_1.
  15. Nao Fujinaga, Yukiko Yamauchi, Hirotaka Ono, Shuji Kijima, and Masafumi Yamashita. Pattern formation by oblivious asynchronous mobile robots. SIAM J. Comput., 44(3):740-785, 2015. URL: http://dx.doi.org/10.1137/140958682.
  16. Martin T. Hagan, Howard B. Demuth, Mark H. Beale, et al. Neural network design. Pws Pub. Boston, 1996. Google Scholar
  17. Anthony Honorat, Maria Potop-Butucaru, and Sébastien Tixeuil. Gathering fat mobile robots with slim omnidirectional cameras. Theoretical Computer Science, 557:1-27, 2014. Google Scholar
  18. Oussama Khatib. Real-time obstacle avoidance for manipulators and mobile robots. The international journal of robotics research, 5(1):90-98, 1986. Google Scholar
  19. Sylvain Martel, Mahmood Mohammadi, Ouajdi Felfoul, Zhao Lu, and Pierre Pouponneau. Flagellated magnetotactic bacteria as controlled mri-trackable propulsion and steering systems for medical nanorobots operating in the human microvasculature. The International journal of robotics research, 28(4):571-582, 2009. Google Scholar
  20. Michael S. Mooring and Benjamin L. Hart. Animal grouping for protection from parasites: selfish herd and encounter-dilution effects. Behaviour, 123(3):173-193, 1992. Google Scholar
  21. Ichiro Suzuki and Masafumi Yamashita. Distributed anonymous mobile robots: Formation of geometric patterns. SIAM Journal on Computing, 28(4):1347-1363, 1999. Google Scholar
  22. Stephen Wolfram et al. Theory and applications of cellular automata, volume 1. World Scientific Singapore, 1986. Google Scholar
  23. Yukiko Yamauchi, Taichi Uehara, Shuji Kijima, and Masafumi Yamashita. Plane formation by synchronous mobile robots in the three dimensional euclidean space. In Distributed Computing - 29th International Symposium, DISC 2015, Tokyo, Japan, October 7-9, 2015, Proceedings, pages 92-106, 2015. URL: http://dx.doi.org/10.1007/978-3-662-48653-5_7.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact