Gathering of Unit Disk Robots
Abstract
The gathering problem in distributed robotics involves coordinating autonomous mobile robots to converge at a single location, a task complicated by physical constraints and limited sensing. Prior research predominantly utilizes point robots or assumes full visibility, which neglects real-world conditions where robots have physical dimensions and obstruct each other's vision. No existing algorithm in the classical model addresses gathering of unit-disk robots under obstructed visibility using small, constant memory. This study proposes a novel algorithm for collision-free gathering of opaque unit-disk robots with limited memory, operating under a fully synchronous scheduler. The algorithm proceeds in two phases: a visibility phase to reposition robots into a convex hull ensuring mutual visibility, and a gathering phase to move all robots toward the centroid. It achieves collision-free convergence in O(n) rounds using only O(1) memory per robot, without knowledge of the total number of robots. Unlike prior models that rely on lights, transparency, or global knowledge, this work uniquely solves the gathering problem using opaque robots with geometric reasoning and no communication. This result advances the feasibility of memory-efficient, scalable coordination strategies for real-world swarm robotics where physical and visibility limitations are critical.
References
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), pages 250–259, 2013.
Chrysovalandis Agathangelou, Chryssis Georgiou, and Marios Mavronicolas. A distributed algorithm for gathering many fat mobile robots in the plane. In Proceedings of the 2013 ACM symposium on Principles of distributed computing, pages 250–259, 2013.
Rusul J Alsaedi, Joachim Gudmundsson, and Andr´e van Renssen. The mutual visibility problem for fat robots. In Algorithms and Data Structures Symposium, pages 15–28. Springer, 2023.
Rusul J. Alsaedi, Joachim Gudmundsson, and Andr´e van Renssen. The mutual visibility problem for fat robots. In Proceedings of the 18th Algorithms and Data Structures Symposium (WADS 2023), volume 14079 of Lecture Notes in Computer Science, pages 15–28, 2023.
Rusul J Alsaedi, Joachim Gudmundsson, and Andr´e van Renssen. Pattern formation for fat robots with lights. arXiv preprint arXiv:2306.14440, 2023.
Rusul J Alsaedi, Joachim Gudmundsson, and Andr´e van Renssen. Pattern formation for fat robots with memory. arXiv preprint arXiv:2309.14649, 2023.
Rusul J Alsaedi, Joachim Gudmundsson, and Andr´e van Renssen. Shortest paths of mutually visible robots. arXiv preprint arXiv:2309.16901, 2023.
K´alm´an Bolla, Zsolt Csaba Johany´ak, Tam´as Kov´acs, and G´abor Fazekas. Local center of gravity based gathering algorithm for fat robots. Issues and Challenges of Intelligent Systems and Computational Intelligence, pages 175–183, 2014.
K´alm´an Bolla, Tam´as Kovacs, and G´abor Fazekas. Gathering of fat robots with limited visibility and without global navigation. In International Conference on Swarm and Evolutionary Computation (SIDE), volume 7269 of Lecture Notes in Computer Science, pages 30–38, 2012.
K´alm´an Bolla, Tam´as Kovacs, and G´abor Fazekas. Gathering of fat robots with limited visibility and without global navigation. In International Symposium on Evolutionary Computation, pages 30–38. Springer, 2012.
K´alm´an Bolla, Tam´as Kov´acs, and G´abor Fazekas. Investigating the rate of failure of asynchronous gathering in a swarm of fat robots with limited visibility. In Artificial Intelligence and Soft Computing: 13th International Conference, ICAISC 2014, Zakopane, Poland, June 1-5, 2014, Proceedings, Part II 13, pages 249–256. Springer, 2014.
Kaustav Bose, Ranendu Adhikary, Manash Kumar Kundu, Archak Das, and Buddhadeb Sau. Dis-tributed pattern formation by autonomous robot swarm. In 23rd International Conference on Dis-tributed Computing and Networking (ICDCN), pages 242–243, 2022.
Kaustav Bose, Ranendu Adhikary, Manash Kumar Kundu, and Buddhadeb Sau. Arbitrary pattern for-mation by opaque fat robots with lights. In Conference on Algorithms and Discrete Applied Mathematics (CALDAM), volume 12016 of Lecture Notes in Computer Science, pages 347–359, 2020.
Kaustav Bose, Archak Das, and Buddhadeb Sau. Pattern formation by robots with inaccurate move-ments. In 25th International Conference on Principles of Distributed Systems (OPODIS), volume 217 of Leibniz International Proceedings in Informatics (LIPIcs), pages 10:1–10:20, 2021.
Kaustav Bose, Manash Kumar Kundu, Ranendu Adhikary, and Buddhadeb Sau. Arbitrary pattern formation by asynchronous opaque robots with lights. Theoretical Computer Science, 849:138–158, 2021.
Sruti Gan Chaudhuri, Swapnil Ghike, Shrainik Jain, and Krishnendu Mukhopadhyaya. Pattern forma-tion for asynchronous robots without agreement in chirality. arXiv preprint arXiv:1403.2625, 2014.
Sruti Gan Chaudhuri and Krishnendu Mukhopadhyaya. Leader election and gathering for asynchronous fat robots without common chirality. Journal of Discrete Algorithms, 33:171–192, 2015.
Sruti Gan Chaudhuri and Krishnendu Mukhopadhyaya. Leader election and gathering for asynchronous fat robots without common chirality. Journal of Discrete Algorithms, 33:171–192, 2015.
Serafino Cicerone, Gabriele Di Stefano, and Alfredo Navarra. Gathering of robots on meeting-points: feasibility and optimal resolution algorithms. Distributed Computing, 31(1):1–50, 2018.
Mark Cieliebak, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Distributed computing by mobile robots: Gathering. SIAM Journal on Computing, 41(4):829–879, 2012.
Reuven Cohen and David Peleg. Local spreading algorithms for autonomous robot systems. Theoretical Computer Science, 399(1-2):71–82, 2008.
Andreas Cord-Landwehr, Bastian Degener, Matthias Fischer, Martina H¨ullmann, Barbara Kempkes, Alexander Klaas, Peter Kling, Sven Kurras, Marcus M¨artens, Friedhelm Meyer auf der Heide, Christoph Raupach, Kamil Swierkot, Daniel Warner, Christoph Weddemann, and Daniel Wonisch. Collisionless gathering of robots with an extent. In 37th Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), volume 6543 of Lecture Notes in Computer Science, pages 178–189, 2011.
Jurek Czyzowicz, Leszek Gasieniec, and Andrzej Pelc. Gathering few fat mobile robots in the plane. Theoretical Computer Science, 410(6-7):481–499, 2009.
Jurek Czyzowicz, Leszek Gasieniec, and Andrzej Pelc. Gathering few fat mobile robots in the plane. Theoretical Computer Science, 410(6-7):481–499, 2009.
Shantanu Das, Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Masafumi Yamashita. Au-tonomous mobile robots with lights. Theoretical Computer Science, 609:171–184, 2016.
Giuseppe Antonio Di Luna, Paola Flocchini, S Gan Chaudhuri, Federico Poloni, Nicola Santoro, and Giovanni Viglietta. Mutual visibility by luminous robots without collisions. Information and Compu-tation, 254:392–418, 2017.
Ayan Dutta, Sruti Gan Chaudhuri, Suparno Datta, and Krishnendu Mukhopadhyaya. Circle formation by asynchronous fat robots with limited visibility. In Distributed Computing and Internet Technology (ICDCIT), volume 7154 of Lecture Notes in Computer Science, pages 83–93, 2012.
Paola Flocchini. Computations by luminous robots. In 14th International Conference on Ad Hoc Networks and Wireless (ADHOC-NOW), volume 9143 of Lecture Notes in Computer Science, pages 238–252, 2015.
Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Distributed Computing by Oblivious Mobile Robots. Synthesis Lectures on Distributed Computing Theory (SLDCT). Springer Cham, 2012.
Nao Fujinaga, Yukiko Yamauchi, Hirotaka Ono, Shuji Kijima, and Masafumi Yamashita. Pattern formation by oblivious asynchronous mobile robots. SIAM Journal on Computing, 44(3):740–785, 2015.
Sruti Gan Chaudhuri and Krishnendu Mukhopadhyaya. Gathering asynchronous transparent fat robots. In Distributed Computing and Internet Technology: 6th International Conference, ICDCIT 2010, Bhubaneswar, India, February 15-17, 2010. Proceedings 6, pages 170–175. Springer, 2010.
Satakshi Ghosh, Pritam Goswami, Avisek Sharma, and Buddhadeb Sau. Move and time optimal arbitrary pattern formation by asynchronous robots on infinite grid. International Journal of Parallel, Emergent and Distributed Systems, 38(1), 2023.
Anthony Honorat, Maria Potop-Butucaru, and S´ebastien Tixeuil. Gathering fat mobile robots with slim omnidirectional cameras. Theoretical Computer Science, 557:1–27, 2014.
Manash Kumar Kundu, Pritam Goswami, Satakshi Ghosh, and Buddhadeb Sau. Arbitrary pattern for-mation by opaque fat robots on infinite grid. International Journal of Parallel, Emergent and Distributed Systems, 37(5):542–570, 2022.
Giuseppe Antonio Di Luna, Paola Flocchini, Sruti Gan Chaudhuri, Nicola Santoro, and Giovanni Vigli-etta. Robots with lights: Overcoming obstructed visibility without colliding. In 16th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), volume 8756 of Lecture Notes in Computer Science, pages 150–164, 2014.
Giuseppe Antonio Di Luna, Paola Flocchini, Federico Poloni, Nicola Santoro, and Giovanni Viglietta. The mutual visibility problem for oblivious robots. In 26th Canadian Conference on Computational Geometry (CCCG), 2014.
Debasish Pattanayak, Klaus-Tycho Foerster, Partha Sarathi Mandal, and Stefan Schmid. Conic for-mation in presence of faulty robots. In 16th International Symposium on Algorithms and Experiments for Wireless Sensor Networks (ALGOSENSORS), volume 12503 of Lecture Notes in Computer Science, pages 170–185, 2020.
David Peleg. Distributed coordination algorithms for mobile robot swarms: New directions and chal-lenges. In 7th International Workshop on Distributed Computing (IWDC), volume 3741 of Lecture Notes in Computer Science, pages 1–12, 2005
Gokarna Sharma, Rusul Alsaedi, Costas Busch, and Supratik Mukhopadhyay. The complete visibility problem for fat robots with lights. In Proceedings of the 19th International Conference on Distributed Computing and Networking, pages 1–4, 2018.
Gokarna Sharma, Costas Busch, and Supratik Mukhopadhyay. Bounds on mutual visibility algorithms. In 27th Canadian Conference on Computational Geometry (CCCG), pages 268–274, 2015.
