Abstract We consider two finite and disjoint sets of homogeneous robots deployed at the nodes of an infinite grid graph. The grid graph also comprises two finite and disjoint sets of prefixed meeting nodes located over the nodes of the grid. The objective of our study is to design a distributed algorithm that gathers all the robots belonging to the first team at one of the meeting nodes belonging to the first type, and all the robots in the second team must gather at one of the meeting nodes belonging to the second type. The robots can distinguish between the two types of meeting nodes. However, a robot cannot identify its team members. This paper assumes the strongest adversarial model, namely the asynchronous scheduler. We have characterized all the initial configurations for which the gathering problem is unsolvable. For the remaining initial configurations, the paper proposes a distributed gathering algorithm. Assuming the robots are capable of global-weak multiplicity detection, the proposed algorithm solves the problem within a finite time period. The algorithm runs in $\Theta (dn)$ moves and $O(dn)$ epochs, where $d$ is the diameter of the minimum enclosing rectangle of all the robots and meeting nodes in the initial configuration, and $n$ is the total number of robots in the system.

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.

Gathering is one of the fundamental and well-studied problems in the context of autonomous and oblivious mobile robots. The gathering problem requires the robots, initially distributed on the Euclidean plane, to coordinate their movements to gather at a single point, not known to them a priori. We study a constrained version of the gathering problem, called the min-max gathering, which requires the robots to achieve gathering by minimizing the maximum distance traversed by any robot. A solution to the problem provides energy efficiency for the robots to achieve the goal. We present a deterministic algorithm for the min-max gathering problem in the Euclidean plane under two of the strongest adversarial models, namely, the asynchronous scheduler and the non-rigid movements of the robots. Moreover, we establish a minimal set of necessary and sufficient conditions to solve the problem.