Circle formation by asynchronous opaque robots on infinite grid

• Autorzy: Adhikary Ranendu , Kundu Manash Kumar , Sau Buddhadeb

Identyfikatory

DOI

10.7494/csci.2021.22.1.3840

• Języki publikacji: EN

Abstrakty

EN

This paper presents a distributed algorithm for the Circle Formation problem under the infinite grid environment by asynchronous mobile opaque robots. Initially, all of the robots acquire distinct positions, and they must form a circle over the grid. The movements of the robots are only restricted along the grid lines; they do not share any global coordinate system. The robots are controlled by an asynchronous adversarial scheduler that operates in Look-Compute-Move cycles. The robots are indistinguishable by their nature, and they do not have any memory of their past configurations nor previous actions. We consider the problem under a luminous model, where robots communicate via lights; other than that, they do not have any external communication systems. Our protocol solves the Circle Formation problem using seven colors. A subroutine of our algorithm also solves the Line Formation problem using three colors.

Słowa kluczowe

EN

distributed computing; autonomous robots; circle formation; line formation; robots with lights; asynchronous; Look-Compute-Move cycle; grid

• Wydawca: Wydawnictwa AGH
• Czasopismo: Computer Science
• Rocznik: 2021
• Tom: T. 22 (1)
• Strony: 81--100
• Opis fizyczny: Bibliogr. 30 poz., rys.

Twórcy

autor

Adhikary Ranendu

• Jadavpur University, Department of Mathematics, Kolkata, West Bengal – 700032, India

autor

Kundu Manash Kumar

• Gayeshpur Government Polytechnic, Department of Science and Humanities, Kalyani, West Bengal - 741234, India

autor

Sau Buddhadeb

• Jadavpur University, Department of Mathematics, Kolkata, West Bengal – 700032, India

Bibliografia

• [1] Adhikary R., Bose K., Kundu M.K., Sau B.: Mutual Visibility by Asynchronous Robots on Infinite Grid. In: Algorithms for Sensor Systems – 14th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2018, Helsinki, Finland, August 23–24, 2018, Revised Selected Papers, Lecture Notes in Computer Science, vol. 11410, pp. 83–101, Springer, 2018.
• [2] Barbera H.M., Quinonero J.P.C., Zamora-Izquierdo M.A., Skarmeta A.G.: I-Fork: a flexible AGV system using topological and grid maps. In: Robotics and Automation, 2003. Proceedings. ICRA’03. IEEE International Conference on, vol. 2, pp. 2147–2152, IEEE, 2003.
• [3] Bhagat S., Mukhopadhyaya K.: Optimum circle formation by autonomous robots. In: Advanced Computing and Systems for Security, pp. 153–165, Springer, 2018.
• [4] Bose K., Adhikary R., Chaudhuri S.G., Sau B.: Crash tolerant gathering on grid by asynchronous oblivious robots. In: arXiv preprint arXiv:1709.00877, 2017.
• [5] Bose K., Adhikary R., Kundu M.K., Sau B.: Arbitrary pattern formation on infinite grid by asynchronous oblivious robots. In: WALCOM: Algorithms and Computation – 13th International Conference, WALCOM 2019, Guwahati, India, February 27 – March 2, 2019, Proceedings, Lecture Notes in Computer Science, vol. 11355, pp. 354–366, Springer, 2019.
• [6] Bose K., Adhikary R., Kundu M.K., Sau B.: Arbitrary pattern formation on infinite grid by asynchronous oblivious robots, Theoretical Computer Science, vol. 815, pp. 213–227, 2020.
• [7] D’Angelo G., Di Stefano G., Klasing R., Navarra A.: Gathering of robots on anonymous grids and trees without multiplicity detection, Theoretical Computer Science, vol. 610, pp. 158–168, 2016.
• [8] Defago X., Konagaya A.: Circle formation for oblivious anonymous mobile robots with no common sense of orientation. In: Proceedings of the second ACM international workshop on Principles of mobile computing, pp. 97–104. 2002.
• [9] Defago X., Souissi S.: Non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformity, Theoretical Computer Science, vol. 396(1–3), pp. 97–112, 2008.
• [10] Deshpande A.M., Kumar R., Radmanesh M., Veerabhadrappa N., Kumar M., Minai A.A.: Self-Organized Circle Formation around an Unknown Target by a Multi-Robot Swarm using a Local Communication Strategy. In: 2018 Annual American Control Conference (ACC), pp. 4409–4413, IEEE, 2018.
• [11] Di Stefano G., Navarra A.: Gathering of oblivious robots on infinite grids with minimum traveled distance, Information and Computation, vol. 254, pp. 377–391, 2017.
• [12] Dutta A., Chaudhuri S.G., Datta S., Mukhopadhyaya K.: Circle Formation by Asynchronous Fat Robots with Limited Visibility. In: Ramanujam R., Ramaswamy S. (eds.), Distributed Computing and Internet Technology – 8th International Conference, ICDCIT 2012, Bhubaneswar, India, February 2–4, 2012. Proceedings, Lecture Notes in Computer Science, vol. 7154, pp. 83–93, Springer, 2012.
• [13] Feletti C., Mereghetti C., Palano B.: Uniform circle formation for swarms of opaque robots with lights. In: International Symposium on Stabilizing, Safety, and Security of Distributed Systems, pp. 317–332, Springer, 2018.
• [14] Fischer M., Jung D., Meyer auf der Heide F.: Gathering Anonymous, Oblivious Robots on a Grid. In: Algorithms for Sensor Systems – 13th International Symposium on Algorithms and Experiments for Wireless Sensor Networks, ALGOSENSORS 2017, Vienna, Austria, September 7–8, 2017, Revised Selected Papers, pp. 168–181. 2017.
• [15] Flocchini P., Prencipe G., Santoro N.: Self-deployment Algorithms for Mobile Sensors on a Ring. In: International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, pp. 59–70, Springer, 2006.
• [16] Flocchini P., Prencipe G., Santoro N.: Distributed Computing by Oblivious Mobile Robots. Synthesis Lectures on Distributed Computing Theory, Morgan & Claypool Publishers, 2012.
• [17] Flocchini P., Prencipe G., Santoro N.: Distributed Computing by Mobile Entities, Current Research in Moving and Computing, vol. 11340, 2019.
• [18] Flocchini P., Prencipe G., Santoro N., Viglietta G.: Distributed Computing by Mobile Robots: Solving the Uniform Circle Formation Problem. In: International Conference on Principles of Distributed Systems, pp. 217–232, Springer, 2014.
• [19] Flocchini P., Prencipe G., Santoro N., Viglietta G.: Distributed computing by mobile robots: uniform circle formation, Distributed Computing, vol. 30(6), pp. 413–457, 2017.
• [20] Fujinaga N., Yamauchi Y., Kijima S., Yamashita M.: Asynchronous pattern formation by anonymous oblivious mobile robots. In: International Symposium on Distributed Computing, pp. 312–325, Springer, 2012.
• [21] Lukovszki T., Meyer auf der Heide F.: Fast Collisionless Pattern Formation by Anonymous, Position-Aware Robots. In: International Conference on Principles of Distributed Systems, pp. 248–262, Springer, 2014.
• [22] Mamino M., Viglietta G.: Square Formation by Asynchronous Oblivious Robots. In: arXiv preprint arXiv:1605.06093, 2016.
• [23] Mondal M., Chaudhuri S.G.: Uniform circle formation by mobile robots. In: Proceedings of the Workshop Program of the 19th International Conference on Distributed Computing and Networking, pp. 1–2, 2018.
• [24] Pamecha A., Ebert-Uphoff I., Chirikjian G.S.: Useful metrics for modular robot motion planning, IEEE Transactions on Robotics and Automation, vol. 13(4), pp. 531–545, 1997.
• [25] Peleg D.: Distributed Coordination Algorithms for Mobile Robot Swarms: New Directions and Challenges. In: International Workshop on Distributed Computing, pp. 1–12, Springer, 2005.
• [26] Poudel P., Sharma G.: Universally Optimal Gathering Under Limited Visibility. In: Stabilization, Safety, and Security of Distributed Systems – 19th International Symposium, SSS 2017, Boston, MA, USA, November 5–8, 2017, Proceedings, pp. 323–340, 2017.
• [27] Poudel P., Sharma G., Aljohani A.: Sublinear-time mutual visibility for fat oblivious robots. In: Proceedings of the 20th International Conference on Distributed Computing and Networking, ICDCN 2019, Bangalore, India, January 04–07, 2019, pp. 238–247, ACM, 2019.
• [28] Sugihara K., Suzuki I.: Distributed motion coordination of multiple mobile robots. In: Proceedings of 5th IEEE International Symposium on Intelligent Control 1990, pp. 138–143, IEEE, 1990.
• [29] Suzuki I., Yamashita M.: Distributed anonymous mobile robots: Formation of geometric patterns, SIAM Journal on Computing, vol. 28(4), pp. 1347–1363, 1999.
• [30] Tanaka O.: Forming a circle by distributed anonymous mobile robots, Bachelor thesis, Department of Electrical Engineering, Hiroshima University, Japan, 1992.

Uwagi

PL

„Opracowanie rekordu ze środków MNiSW, umowa Nr 461252 w ramach programu "Społeczna odpowiedzialność nauki" - moduł: Popularyzacja nauki i promocja sportu (2021).”