Gathering over Meeting Nodes in Infinite Grid

• Autorzy: Bhagat, Subhash , Chakraborty, Abhinav , Das, Bibhuti , Mukhopadhyaya, Krishnendu
• Języki publikacji: EN

Abstrakty

EN

The gathering over meeting nodes problem asks the robots to gather at one of the pre-defined meeting nodes. The robots are deployed on the nodes of an anonymous two-dimensional infinite grid which has a subset of nodes marked as meeting nodes. Robots are identical, autonomous, anonymous and oblivious. They operate under an asynchronous scheduler. They do not have any agreement on a global coordinate system. All the initial configurations for which the problem is deterministically unsolvable have been characterized. A deterministic distributed algorithm has been proposed to solve the problem for the remaining configurations. The efficiency of the proposed algorithm is studied in terms of the number of moves required for gathering. A lower bound concerning the total number of moves required to solve the gathering problem has been derived.

Słowa kluczowe

EN

swarm robotics; gathering; meeting Nodes; asynchronous,; Look-Compute-Move Cycle

• Czasopismo: Fundamenta Informaticae
• Rocznik: 2022
• Tom: Vol. 187 nr 1
• Strony: 1--30
• Opis fizyczny: Bibliogr. 28 poz., rys., tab.

Twórcy

autor

Bhagat, Subhash

• Deepartement d’informatique Universit´e du Qu´ebec en Outaouais, Canada ,

autor

Chakraborty, Abhinav

• Advanced Computing and Microelectronics Unit Indian Statistical Institute, Kolkata, India

autor

Das, Bibhuti

• Advanced Computing and Microelectronics Unit Indian Statistical Institute, Kolkata, India

autor

Mukhopadhyaya, Krishnendu

• Advanced Computing and Microelectronics Unit Indian Statistical Institute, Kolkata, India

Bibliografia

• [1] Cieliebak M, Flocchini P, Prencipe G, Santoro N. Solving the Robots Gathering Problem. In: Baeten JCM, Lenstra JK, Parrow J, Woeginger GJ (eds.), Automata, Languages and Programming, 30th International Colloquium, ICALP 2003, Eindhoven, The Netherlands, June 30 - July 4, 2003. Proceedings, volume 2719 of Lecture Notes in Computer Science. Springer, 2003 pp. 1181-1196. doi:10.1007/3-540-45061-0\ 90.URL https://doi.org/10.1007/3-540-45061-0_90.
• [2] Agmon N, Peleg D. Fault-tolerant gathering algorithms for autonomous mobile robots. In: Munro JI (ed.), Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11-14, 2004. SIAM, 2004 pp. 1070-1078. URL http://dl.acm. org/citation.cfm?id=982792.982951.
• [3] Bhagat S, Chaudhuri SG, Mukhopadhyaya K. Fault-tolerant gathering of asynchronous oblivious mobile robots under one-axis agreement. J. Discrete Algorithms, 2016. 36:50-62. doi:10.1016/j.jda.2015.10.005. URL https://doi.org/10.1016/j.jda.2015.10.005.
• [4] Klasing R, Markou E, Pelc A. Gathering asynchronous oblivious mobile robots in a ring. Theor. Comput. Sci., 2008. 390(1):27-39. doi:10.1016/j.tcs.2007.09.032. URL https://doi.org/10.1016/j.tcs.2007.09.032.
• [5] Klasing R, Kosowski A, Navarra A. Taking advantage of symmetries: Gathering of many asynchronous oblivious robots on a ring. Theor. Comput. Sci., 2010. 411(34-36):3235-3246. doi:10.1016/j.tcs.2010.05.020 URL https://doi.org/10.1016/j.tcs.2010.05.020.
• [6] D’Angelo G, Stefano GD, Klasing R, Navarra A. Gathering of robots on anonymous grids and trees without multiplicity detection. Theor. Comput. Sci., 2016. 610:158-168. doi:10.1016/j.tcs.2014.06.045. URL https://doi.org/10.1016/j.tcs.2014.06.045.
• [7] Stefano GD, Navarra A. Gathering of oblivious robots on infinite grids with minimum traveled distance. Inf. Comput., 2017. 254:377-391. doi:10.1016/j.ic.2016.09.004. URL https://doi.org/10.1016/j.ic.2016.09.004.
• [8] Cicerone S, Stefano GD, Navarra A. Gathering of robots on meeting-points: feasibility and optimal resolution algorithms. Distributed Computing, 2018. 31(1):1-50. doi:10.1007/s00446-017-0293-3. URL https://doi.org/10.1007/s00446-017-0293-3.
• [9] Pattanayak D, Mondal K, Ramesh H, Mandal PS. Gathering of mobile robots with weak multiplicity detection in presence of crash-faults. J. Parallel Distributed Comput., 2019. 123:145-155. doi:10.1016/j.jpdc.2018.09.015. URL https://doi.org/10.1016/j.jpdc.2018.09.015.
• [10] Cicerone S, Stefano GD, Navarra A. Asynchronous Arbitrary Pattern Formation: the effects of a rigorous approach. Distributed Comput., 2019. 32(2):91-132. doi:10.1007/s00446-018-0325-7. URL https: //doi.org/10.1007/s00446-018-0325-7.
• [11] Barber´a HM, Qui˜nonero JPC, Zamora-Izquierdo MA, G´omez-Skarmeta AF. i-Fork: a flexible AGV system using topological and grid maps. In: Proceedings of the 2003 IEEE International Conference on Robotics and Automation, ICRA 2003, September 14-19, 2003, Taipei, Taiwan. IEEE, 2003 pp. 2147-2152. doi:10.1109/ROBOT.2003.1241911. URL https://doi.org/10.1109/ROBOT.2003.1241911.
• [12] Sharma G, Dutta A, Kim J. Optimal Online Coverage Path Planning with Energy Constraints. In: Elkind E, Veloso M, Agmon N, Taylor ME (eds.), Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, AAMAS ’19, Montreal, QC, Canada, May 13-17, 2019. International Foundation for Autonomous Agents and Multiagent Systems, 2019 pp. 1189-1197. URL http://dl.acm.org/citation.cfm?id=3331820S.Bhagat et al. / Gathering over Meeting Nodes in Infinite Grid 29
• [13] Flocchini P. Gathering. In: Flocchini P, Prencipe G, Santoro N (eds.), Distributed Computing by Mobile Entities, Current Research in Moving and Computing, volume 11340 of Lecture Notes in Computer Science, pp. 63-82. Springer, 2019. doi:10.1007/978-3-030-11072-7\ 4. URL https://doi.org/10.1007/978-3-030-11072-7_4.
• [14] Flocchini P, Prencipe G, Santoro N. Distributed Computing by Oblivious Mobile Robots. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers, 2012. doi:10.2200/S00440ED1V01Y201208DCT010. URL https://doi.org/10.2200/S00440ED1V01Y201208DCT010.
• [15] D’Angelo G, Stefano GD, Navarra A. Gathering six oblivious robots on anonymous symmetric rings. J. Discrete Algorithms, 2014. 26:16-27. doi:10.1016/j.jda.2013.09.006. URL https://doi.org/10.1016/j.jda.2013.09.006.
• [16] D’Angelo G, Stefano GD, Navarra A. Gathering on rings under the Look-Compute-Move model. Distributed Comput., 2014. 27(4):255-285. doi:10.1007/s00446-014-0212-9. URL https://doi.org/10.1007/s00446-014-0212-9.
• [17] Izumi T, Izumi T, Kamei S, Ooshita F. Mobile Robots Gathering Algorithm with Local Weak Multiplicity in Rings. In: Patt-Shamir B, Ekim T (eds.), Structural Information and Communication Complexity Springer Berlin Heidelberg, Berlin, Heidelberg. ISBN 978-3-642-13284-1, 2010 pp. 101-113.
• [18] Kamei S, Lamani A, Ooshita F, Tixeuil S. Gathering an Even Number of Robots in an Odd Ring without Global Multiplicity Detection. In: Rovan B, Sassone V, Widmayer P (eds.), Mathematical Foundations of Computer Science 2012. Springer Berlin Heidelberg, Berlin, Heidelberg. ISBN 978-3-642-32589-2, 2012 pp. 542-553.
• [19] Cicerone S, Stefano GD, Navarra A. Gathering robots in graphs: The central role of synchronicity. Theor. Comput. Sci., 2021. 849:99-120. doi:10.1016/j.tcs.2020.10.011. URL https://doi.org/10.1016/j.tcs.2020.10.011.
• [20] Cicerone S, Stefano GD, Navarra A. Gathering Synchronous Robots in Graphs: From General Properties to Dense and Symmetric Topologies. In: Censor-Hillel K, Flammini M (eds.), Structural Information and Communication Complexity - 26th International Colloquium, SIROCCO 2019, L’Aquila, Italy, July 1-4, 2019, Proceedings, volume 11639 of Lecture Notes in Computer Science. Springer, 2019 pp. 170-184. doi:10.1007/978-3-030-24922-9\ 12. URL https://doi.org/10.1007/978-3-030-24922-9_12.
• [21] Cicerone S, Stefano GD, Navarra A. On Gathering of Semi-synchronous Robots in Graphs. In: Ghaffari M, Nesterenko M, Tixeuil S, Tucci S, Yamauchi Y (eds.), Stabilization, Safety, and Security of Distributed Systems - 21st International Symposium, SSS 2019, Pisa, Italy, October 22-25, 2019, Proceedings, volume 11914 of Lecture Notes in Computer Science. Springer, 2019 pp. 84-98. doi:10.1007/978-3-030-34992-9\7. URL https://doi.org/10.1007/978-3-030-34992-9_7.
• [22] Bhagat S, Chakraborty A, Das B, Mukhopadhyaya K. Gathering over Meeting Nodes in Infinite Grid. In: Changat M, Das S (eds.), Algorithms and Discrete Applied Mathematics - 6th International Conference, CALDAM 2020, Hyderabad, India, February 13-15, 2020, Proceedings, volume 12016 of Lecture Notes in Computer Science. Springer, 2020 pp. 318-330. doi:10.1007/978-3-030-39219-2\26. URL https://doi.org/10.1007/978-3-030-39219-2_26.
• [23] Bose K, Kundu MK, Adhikary R, Sau B. Optimal Gathering by Asynchronous Oblivious Robots in Hypercubes. In: Gilbert S, Hughes D, Krishnamachari B (eds.), Algorithms for Sensor Systems. Springer International Publishing, Cham. ISBN 978-3-030-14094-6, 2019 pp. 102-117.30 S.Bhagat et al. / Gathering over Meeting Nodes in Infinite Grid
• [24] Stefano GD, Navarra A. Optimal gathering of oblivious robots in anonymous graphs and its application on trees and rings. Distributed Computing, 2017. 30(2):75-86. doi:10.1007/s00446-016-0278-7. URL https://doi.org/10.1007/s00446-016-0278-7.
• [25] Fujinaga N, Ono H, Kijima S, Yamashita M. Pattern Formation through Optimum Matching by Oblivious CORDA Robots. In: Lu C, Masuzawa T, Mosbah M (eds.), Principles of Distributed Systems. Springer Berlin Heidelberg, Berlin, Heidelberg. ISBN 978-3-642-17653-1, 2010 pp. 1-15.
• [26] Cicerone S, Di Stefano G, Navarra A. Embedded pattern formation by asynchronous robots without chirality. Distributed Computing, 2019. 32(4):291-315. doi:10.1007/s00446-018-0333-7. URL https://doi.org/10.1007/s00446-018-0333-7.
• [27] Bhagat S, Das B, Chakraborty A, Mukhopadhyaya K. k-Circle Formation and k-epf by Asynchronous Robots. Algorithms, 2021. 14(2):62. doi:10.3390/a14020062. URL https://doi.org/10.3390/a14020062.
• [28] Das B, Chakraborty A, Bhagat S, Mukhopadhyaya K. k-Circle formation by disoriented asynchronous robots. Theor. Comput. Sci., 2022. 916:40-61. doi:10.1016/j.tcs.2022.03.003. URL https://doi.org/10.1016/j.tcs.2022.03.003.

Identyfikatory

DOI

10.3233/FI-222128