Subhash Bhagat

Prakhar Shukla, Seshunadh Tanuj Peddinti, Subhash Bhagat

This paper studies the gathering problem for a set of $N \ge 2$ autonomous mobile robots operating in the Euclidean plane under the distributed Look-Compute-Move model. We consider oblivious robots executing under the adversarial defected view model, in which an activated robot may observe only a restricted subset of robots due to adversarial visibility faults. Consequently, the information obtained during each Look phase may be incomplete and dynamically altered. The objective is to guarantee deterministic finite-time gathering at a location not known a priori despite such sensing restrictions. We present two distributed algorithms under distinct scheduling assumptions. In the fully synchronous (FSYNC) model, we prove finite-time gathering in the adversarial (4, 2) defected view setting, resolving a previously open case without requiring additional capabilities or coordinate agreement. In the asynchronous (ASYNC) model, we establish finite-time gathering under the general adversarial (N, K) defected view model, where an activated robot observes at most K of the other $N - 1$ robots for any $1 \le K < N - 1$. Both results hold under non-rigid motion. The proposed algorithm for the ASYNC model assumes agreement in the direction and orientation of one coordinate axis.

Animesh Maiti, Abhinav Chakraborty, Subhash Bhagat

In this paper, we introduce the \emph{Surplus Parking Gathering Problem} ($\mathcal{SPG}$), a new coordination problem for robots deployed on an infinite grid. The input consists of a set of designated parking nodes, each associated with a prescribed capacity, while the total number of robots exceeds the total parking capacity. The objective is to saturate every parking node exactly according to its capacity while gathering all remaining surplus robots at a common grid node that is not specified a priori. The robots are assumed to be autonomous, anonymous, oblivious, identical, disoriented, and homogeneous. We consider the asynchronous (\textsc{async}) model with global visibility and global strong multiplicity detection. We first establish necessary conditions for the solvability of $\mathcal{SPG}$ by characterizing the initial configurations that admit no deterministic distributed algorithm. For all the remaining solvable configurations, we present a deterministic distributed algorithm that correctly solves the problem. The proposed algorithm proceeds in several phases and avoids collisions throughout its execution. We prove that the algorithm terminates in finite time and, upon termination, every parking node is saturated according to its prescribed capacity while all surplus robots are gathered at a uniquely determined gathering node. We further analyze the move complexity of the proposed algorithm, obtaining an $O(n(a+b)+n^2)$ upper bound together with an $Ω(n(a+b))$ worst-case lower bound for the $\mathcal{SPG}$ problem.

Subhash Bhagat, Sruti Gan Chaudhuri, Krishnendu Mukhopadhyaya

This paper proposes a strategy for a group of deaf and dumb robots, carrying clocks from different countries, to meet at a geographical location which is not fixed in advanced. The robots act independently. They can observe others, compute some locations and walk towards those locations. They can only get a snapshot of the locations of other robots but can not detect whether they are static or in motion. The robots are forgetful; once they have completed their motion they forget their previous locations and observations. Again they decide new destinations to move to. Eventually all the robots compute the same destination and meet there. There exists no global positioning system. As they stand, they agree on up and down directions. However, as they do not have any compass, the other directions are not agreed upon. They also do not agree on the clockwise direction. For determining a strategy, we imagine the robots to be points on a three dimensional plane where all the robots are mutually visible to each other always. The strategy we propose has to be obeyed by all the robots independently with respect to their own clock and compass. Initially the robots start from distinct locations. Some dead robots may be present in the system or some may die any time before or after the get together. However, the live robots are not aware of the presence of these dead robots.

S. Bhagat, S. Gan Chaudhuri, K. Mukhopadhyaya

The traditional distributed model of autonomous, homogeneous, mobile point robots usually assumes that the robots do not create any visual obstruction for the other robots, i.e., the robots are see through. In this paper, we consider a slightly more realistic model, by incorporating the notion of obstructed visibility (i.e., robots are not see through) for other robots. Under the new model of visibility, a robot may not have the full view of its surroundings. Many of the existing algorithms demand that each robot should have the complete knowledge of the positions of other robots. Since, vision is the only mean of their communication, it is required that the robots are in general position (i.e., no three robots are collinear). We consider asynchronous robots. They also do not have common chirality (or any agreement on a global coordinate system). In this paper, we present a distributed algorithm for obtaining a general position for the robots in finite time from any arbitrary configuration. The algorithm also assures collision free motion for each robot. This algorithm may also be used as a preprocessing module for many other subsequent tasks performed by the robots.