Document Open Access Logo

Brief Announcement: Line Formation in Silent Programmable Matter

Authors Alfredo Navarra , Francesco Piselli

PDF
Thumbnail PDF

File

LIPIcs.DISC.2023.45.pdf
  • Filesize: 0.83 MB
  • 8 pages

Document Identifiers

Author Details

Alfredo Navarra
  • Department of Mathematics and Computer Science, University of Perugia, Perugia, Italy
Francesco Piselli
  • Department of Mathematics and Computer Science, University of Perugia, Perugia, Italy

Cite As Get BibTex

Alfredo Navarra and Francesco Piselli. Brief Announcement: Line Formation in Silent Programmable Matter. In 37th International Symposium on Distributed Computing (DISC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 281, pp. 45:1-45:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023) https://doi.org/10.4230/LIPIcs.DISC.2023.45

Abstract

Programmable Matter (PM) has been widely investigated in recent years. One reference model is certainly Amoebot, with its recent canonical version (DISC 2021). Along this line, with the aim of simplification and to address concurrency, the SILBOT model has been introduced (AAMAS 2020). Within SILBOT, we consider the Line formation primitive in which particles are required to end up in a configuration where they are all aligned and connected. We propose a simple and elegant distributed algorithm, optimal in terms of number of movements.

Subject Classification

ACM Subject Classification
  • Theory of computation → Distributed algorithms
  • Theory of computation → Concurrency
  • Theory of computation → Self-organization
Keywords
  • Programmable Matter
  • Line formation
  • Asynchrony
  • Stigmergy

Metrics

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

Related Versions

  • An extended version appears in the Proceedings of the 25th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), 2023.
  • Full Version https://arxiv.org/abs/2307.16731

References

  1. He Cai, Shuping Guo, and Huanli Gao. A dynamic leader–follower approach for line marching of swarm robots. Unmanned Systems, 11(01):67-82, 2023. Google Scholar
  2. Jannik Castenow, Thorsten Götte, Till Knollmann, and Friedhelm Meyer auf der Heide. The max-line-formation problem - and new insights for gathering and chain-formation. In Proc. 23rd Int.'l Symp. on Stabilization, Safety, and Security of Distributed Systems (SSS), volume 13046 of LNCS, pages 289-304. Springer, 2021. Google Scholar
  3. Serafino Cicerone, Gabriele Di Stefano, and Alfredo Navarra. A structured methodology for designing distributed algorithms for mobile entities. Information Sciences, 574:111-132, 2021. URL: https://doi.org/10.1016/j.ins.2021.05.043.
  4. Gianlorenzo D'Angelo, Mattia D'Emidio, Shantanu Das, Alfredo Navarra, and Giuseppe Prencipe. Asynchronous silent programmable matter achieves leader election and compaction. IEEE Access, 8:207619-207634, 2020. Google Scholar
  5. Gianlorenzo D'Angelo, Gabriele Di Stefano, Alfredo Navarra, Nicolas Nisse, and Karol Suchan. Computing on rings by oblivious robots: A unified approach for different tasks. Algorithmica, 72(4):1055-1096, 2015. Google Scholar
  6. Joshua J. Daymude, Andréa W. Richa, and Christian Scheideler. The canonical amoebot model: Algorithms and concurrency control. In Proc. 35th Int.'l Symp. on Distributed Computing (DISC), volume 209 of LIPIcs, pages 20:1-20:19, 2021. Google Scholar
  7. Zahra Derakhshandeh, Shlomi Dolev, Robert Gmyr, Andréa W. Richa, Christian Scheideler, and Thim Strothmann. Brief announcement: amoebot - a new model for programmable matter. In Proc. 26th ACM Symp. on Parallelism in Algorithms and Architectures, (SPAA), pages 220-222. ACM, 2014. Google Scholar
  8. Zahra Derakhshandeh, Robert Gmyr, Thim Strothmann, Rida A. Bazzi, Andréa W. Richa, and Christian Scheideler. Leader election and shape formation with self-organizing programmable matter. In Andrew Phillips and Peng Yin, editors, Proc. 21st Int.'l Conf. on Computing and Molecular Programming (DNA), volume 9211 of LNCS, pages 117-132. Springer, 2015. Google Scholar
  9. Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro, editors. Distributed Computing by Mobile Entities, Current Research in Moving and Computing, volume 11340 of Lecture Notes in Computer Science. Springer, 2019. URL: https://doi.org/10.1007/978-3-030-11072-7.
  10. Dominik Gall, Riko Jacob, Andréa W. Richa, Christian Scheideler, Stefan Schmid, and Hanjo Täubig. A note on the parallel runtime of self-stabilizing graph linearization. Theory Comput. Syst., 55(1):110-135, 2014. Google Scholar
  11. Donghwa Jeong and Kiju Lee. Dispersion and line formation in artificial swarm intelligence. In Proc. 20th Int.'l Conf. on Collective Intelligence), 2014. Google Scholar
  12. Zhiying Jiang, Xin Wang, and Jian Yang. Distributed line formation control in swarm robots. In IEEE Int.'l Conf. on Information and Automation (ICIA), pages 636-641. IEEE, 2018. Google Scholar
  13. Yonghwan Kim, Yoshiaki Katayama, and Koichi Wada. Pairbot: A novel model for autonomous mobile robot systems consisting of paired robots, 2020. URL: https://arxiv.org/abs/2009.14426.
  14. Alfredo Navarra, Giuseppe Prencipe, Samuele Bonini, and Mirco Tracolli. Scattering with programmable matter. In Proc. 37th Int.'l Conf. on Advanced Information Networking and Applications (AINA), Lecture Notes in Networks and Systems. Springer, 2023. Google Scholar
  15. Francesco Piselli. Silent programmable matter: Coating. Master’s thesis, University of Perugia, Italy, 2022. Google Scholar
  16. Arijit Sil and Sruti Gan Chaudhuri. Formation of straight line by swarm robots. In Proc. 7th Int.'l Conf. on Advanced Computing, Networking, and Informatics (ICACNI), pages 99-111. Springer, 2020. Google Scholar
  17. Thomas Sousselier, Johann Dréo, and Marc Sevaux. Line formation algorithm in a swarm of reactive robots constrained by underwater environment. Expert Syst. Appl., 42(12):5117-5127, 2015. Google Scholar
  18. Yukiko Yamauchi, Taichi Uehara, Shuji Kijima, and Masafumi Yamashita. Plane formation by synchronous mobile robots in the three-dimensional euclidean space. J. ACM, 64(3):16:1-16:43, 2017. Google Scholar
  19. Jian Yang, Xin Wang, and Peter Bauer. Line and v-shape formation based distributed processing for robotic swarms. Sensors, 18(8):2543, 2018. Google Scholar
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