Gathering over Meeting Nodes in Infinite Grid^*

Article type: Research Article

Authors: Bhagat, Subhash^a | Chakraborty, Abhinav^{b; †} | Das, Bibhuti^b | Mukhopadhyaya, Krishnendu^b

Affiliations: [a] Département d’informatique, Université du Québec en Outaouais, Canada. subhash.bhagat.math@gmail.com | [b] Advanced Computing and Microelectronics Unit, Indian Statistical Institute, Kolkata, India. abhinav.chakraborty06@gmail.com, dasbibhuti905@gmail.com, krishnendu.mukhopadhyaya@gmail.com

Correspondence: [†] Address for correspondence: Advanced Computing and Microelectronics Unit, Indian Statistical Institute, Kolkata, India.

Note: [*] A preliminary version of this paper appeared in the 6th International Conference, CALDAM 2020, Hyderabad, India, February 13-15, 2020,

Abstract: 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.

Keywords: Swarm Robotics, Gathering, Meeting Nodes, Asynchronous, Look-Compute-Move Cycle

DOI: 10.3233/FI-222128

Journal: Fundamenta Informaticae, vol. 187, no. 1, pp. 1-30, 2022