Arbitrary Pattern Formation on a Continuous Circle by Oblivious Robot Swarm
Pages 94 - 103
Abstract
In the field of distributed system, Arbitrary Pattern Formation (APF) problem is an extensively studied problem. The purpose of APF is to design an algorithm to move a swarm of robots to a particular position on an environment (discrete or continuous) such that the swarm can form a specific but arbitrary pattern given previously to every robot as an input. In this paper the solvability of the APF problem on a continuous circle is discussed for a swarm of oblivious and silent robots without chirality under a semi synchronous scheduler. Firstly a class of configurations (the initial placements of the robots on the circle) called Formable Configuration (FC) has been provided which is necessary to solve the APF problem on a continuous circle. Then considering the initial configuration to be an FC, an deterministic and distributed algorithm has been provided that solves the APF problem for n robots on a continuous circle of fixed radius within O(n) epochs without collision, where an epoch is considered to be a time interval in which all robots are activated at least once.
References
[1]
Kaustav Bose, Ranendu Adhikary, Manash Kumar Kundu, and Buddhadeb Sau. 2020. Arbitrary pattern formation on infinite grid by asynchronous oblivious robots. Theor. Comput. Sci. 815 (2020), 213–227. https://doi.org/10.1016/j.tcs.2020.02.016
[2]
Kaustav Bose, Archak Das, and Buddhadeb Sau. 2022. Pattern Formation by Robots with Inaccurate Movements. In 25th International Conference on Principles of Distributed Systems (OPODIS 2021)(Leibniz International Proceedings in Informatics (LIPIcs), Vol. 217), Quentin Bramas, Vincent Gramoli, and Alessia Milani (Eds.). Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl, Germany, 10:1–10:20. https://doi.org/10.4230/LIPIcs.OPODIS.2021.10
[3]
Kaustav Bose, Manash Kumar Kundu, Ranendu Adhikary, and Buddhadeb Sau. 2021. Arbitrary pattern formation by asynchronous opaque robots with lights. Theoretical Computer Science 849 (2021), 138–158. https://doi.org/10.1016/j.tcs.2020.10.015
[4]
Quentin Bramas and Sébastien Tixeuil. 2016. Probabilistic Asynchronous Arbitrary Pattern Formation (Short Paper). In Stabilization, Safety, and Security of Distributed Systems - 18th International Symposium, SSS 2016, Lyon, France, November 7-10, 2016, Proceedings(Lecture Notes in Computer Science, Vol. 10083), Borzoo Bonakdarpour and Franck Petit (Eds.). 88–93. https://doi.org/10.1007/978-3-319-49259-9_7
[5]
Quentin Bramas and Sébastien Tixeuil. 2018. Arbitrary Pattern Formation with Four Robots. In Stabilization, Safety, and Security of Distributed Systems - 20th International Symposium, SSS 2018, Tokyo, Japan, November 4-7, 2018, Proceedings(Lecture Notes in Computer Science, Vol. 11201), Taisuke Izumi and Petr Kuznetsov (Eds.). Springer, 333–348. https://doi.org/10.1007/978-3-030-03232-6_22
[6]
Serafino Cicerone, Alessia Di Fonso, Gabriele Di Stefano, and Alfredo Navarra. 2020. Arbitrary Pattern Formation on Infinite Regular Tessellation Graphs. CoRR abs/2010.14152 (2020). arXiv:2010.14152https://arxiv.org/abs/2010.14152
[7]
Serafino Cicerone, Alessia Di Fonso, Gabriele Di Stefano, and Alfredo Navarra. 2023. Arbitrary pattern formation on infinite regular tessellation graphs. Theor. Comput. Sci. 942 (2023), 1–20. https://doi.org/10.1016/j.tcs.2022.11.021
[8]
Serafino Cicerone, Gabriele Di Stefano, and Alfredo Navarra. 2019. Embedded pattern formation by asynchronous robots without chirality. Distributed Comput. 32, 4 (2019), 291–315. https://doi.org/10.1007/s00446-018-0333-7
[9]
Jurek Czyzowicz, Leszek Gasieniec, Adrian Kosowski, and Evangelos Kranakis. 2011. Boundary Patrolling by Mobile Agents with Distinct Maximal Speeds. In Algorithms - ESA 2011 - 19th Annual European Symposium, Saarbrücken, Germany, September 5-9, 2011. Proceedings(Lecture Notes in Computer Science, Vol. 6942), Camil Demetrescu and Magnús M. Halldórsson (Eds.). Springer, 701–712. https://doi.org/10.1007/978-3-642-23719-5_59
[10]
Yoann Dieudonné, Franck Petit, and Vincent Villain. 2010. Leader Election Problem versus Pattern Formation Problem. In Distributed Computing, 24th International Symposium, DISC 2010, Cambridge, MA, USA, September 13-15, 2010. Proceedings(Lecture Notes in Computer Science, Vol. 6343), Nancy A. Lynch and Alexander A. Shvartsman (Eds.). Springer, 267–281. https://doi.org/10.1007/978-3-642-15763-9_26
[11]
Ofer Feinerman, Amos Korman, Shay Kutten, and Yoav Rodeh. 2017. Fast rendezvous on a cycle by agents with different speeds. Theor. Comput. Sci. 688 (2017), 77–85. https://doi.org/10.1016/j.tcs.2015.12.035
[12]
Paola Flocchini, Ryan Killick, Evangelos Kranakis, Nicola Santoro, and Masafumi Yamashita. 2019. Gathering and Election by Mobile Robots in a Continuous Cycle. In 30th International Symposium on Algorithms and Computation, ISAAC 2019, December 8-11, 2019, Shanghai University of Finance and Economics, Shanghai, China(LIPIcs, Vol. 149), Pinyan Lu and Guochuan Zhang (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 8:1–8:19. https://doi.org/10.4230/LIPIcs.ISAAC.2019.8
[13]
Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Peter Widmayer. 2008. Arbitrary pattern formation by asynchronous, anonymous, oblivious robots. Theoretical Computer Science 407, 1 (2008), 412–447. https://doi.org/10.1016/j.tcs.2008.07.026
[14]
Satakshi Ghosh, Avisek Sharma, Pritam Goswami, and Buddhadeb Sau. 2023. Brief Announcement: Asynchronous Gathering of Finite Memory Robots on a Circle Under Limited Visibility. In Stabilization, Safety, and Security of Distributed Systems - 25th International Symposium, SSS 2023, Jersey City, NJ, USA, October 2-4, 2023, Proceedings(Lecture Notes in Computer Science, Vol. 14310), Shlomi Dolev and Baruch Schieber (Eds.). Springer, 430–434. https://doi.org/10.1007/978-3-031-44274-2_32
[15]
Manash Kumar Kundu, Pritam Goswami, Satakshi Ghosh, and Buddhadeb Sau. 2022. Arbitrary pattern formation by opaque fat robots on infinite grid. Int. J. Parallel Emergent Distributed Syst. 37, 5 (2022), 542–570. https://doi.org/10.1080/17445760.2022.2088750
[16]
Giuseppe Antonio Di Luna, Ryuhei Uehara, Giovanni Viglietta, and Yukiko Yamauchi. 2020. Gathering on a Circle with Limited Visibility by Anonymous Oblivious Robots. In 34th International Symposium on Distributed Computing, DISC 2020, October 12-16, 2020, Virtual Conference(LIPIcs, Vol. 179), Hagit Attiya (Ed.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 12:1–12:17. https://doi.org/10.4230/LIPIcs.DISC.2020.12
[17]
Brati Mondal, Pritam Goswami, Avisek Sharma, and Buddhadeb Sau. 2023. Arbitrary Pattern Formation on a Continuous Circle by Oblivious Robot Swarm. CoRR abs/2303.10366 (2023). https://doi.org/10.48550/arXiv.2303.10366 arXiv:2303.10366
[18]
Ichiro Suzuki and Masafumi Yamashita. 1996. Distributed Anonymous Mobile Robots. In SIROCCO’96, The 3rd International Colloquium on Structural Information & Communication Complexity, Siena, Italy, June 6-8, 1996, Nicola Santoro and Paul G. Spirakis (Eds.). Carleton Scientific, 313–330.
[19]
Masafumi Yamashita and Ichiro Suzuki. 2010. Characterizing geometric patterns formable by oblivious anonymous mobile robots. Theoretical Computer Science 411, 26 (2010), 2433–2453. https://doi.org/10.1016/j.tcs.2010.01.037
Index Terms
- Arbitrary Pattern Formation on a Continuous Circle by Oblivious Robot Swarm
Recommendations
Arbitrary pattern formation by asynchronous, anonymous, oblivious robots
From an engineering point of view, the problem of coordinating a set of autonomous, mobile robots for the purpose of cooperatively performing a task has been studied extensively over the past decade. In contrast, in this paper we aim to understand the ...
k-Circle Formation by Oblivious Mobile Robots
ICDCN '22: Proceedings of the 23rd International Conference on Distributed Computing and NetworkingA solution to the k-circle formation problem requires the formation of disjoint circles by a swarm of mobile robots. The circles are restricted to be centered at one of the pre-fixed points. Each circle must contain exactly k robots at distinct ...
Non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformity
This paper presents a distributed algorithm whereby a group of mobile robots self-organize and position themselves into forming a circle in a loosely synchronized environment. In spite of its apparent simplicity, the difficulty of the problem comes from ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
January 2024
423 pages
ISBN:9798400716737
DOI:10.1145/3631461
Copyright © 2024 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 22 January 2024
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Funding Sources
Conference
ICDCN '24
ICDCN '24: International Conference on Distributed Computing and Networking
January 4 - 7, 2024
Chennai, India
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 23Total Downloads
- Downloads (Last 12 months)23
- Downloads (Last 6 weeks)3
Reflects downloads up to 24 Nov 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format