---
abstract: |
    The design of distributed gathering and convergence algorithms for tiny robots has recently received much attention. In particular, it has been shown that convergence problems can even be solved for very weak, *oblivious* robots: robots which cannot maintain state from one round to the next. The oblivious robot model is hence attractive from a self-stabilization perspective, where state is subject to adversarial manipulation. However, to the best of our knowledge, all existing robot convergence protocols rely on the assumption that robots, despite being “weak”, can measure distances.

    We in this paper initiate the study of convergence protocols for even simpler robots, called *monoculus robots*: robots which cannot measure distances. In particular, we introduce two natural models which relax the assumptions on the robots’ cognitive capabilities: (1) a Locality Detection ($\mathcal{LD}$) model in which a robot can only detect whether another robot is closer than a given constant distance or not, (2) an Orthogonal Line Agreement ($\mathcal{OLA}$) model in which robots only agree on a pair of orthogonal lines (say North-South and West-East, but without knowing which is which).

    The problem turns out to be non-trivial, and simple median and angle bisection strategies can easily increase the distances among robots (e.g., the area of the enclosing convex hull) over time. Our main contribution are deterministic self-stabilizing convergence algorithms for these two models, together with a complexity analysis. We also show that in some sense, the assumptions made in our models are minimal: by relaxing the assumptions on the *monoculus robots* further, we run into impossibility results.\
    \
    **Key words:** Convergence, Weak Robots, Oblivious Mobile Robots, Asynchronous, Distributed Algorithm.\
author:
- |
    Debasish Pattanayak$^1$ Kaushik Mondal$^1$\
    Partha Sarathi Mandal$^1$ Stefan Schmid$^{2,3}$[^1]
bibliography:
- 'bib.bib'
title:
- 'Self-Stabilizing Robots without Location Information'
- |
    Convergence of Even Simpler Robots\
    without Location Information
---

Introduction
============

The Context: Tiny Robots
------------------------

In the recent years, there has been a wide interest in the cooperative behavior of tiny robots. In particular, many distributed coordination protocols have been devised for a wide range of models and for a wide range of problems, like convergence, gathering, pattern formation, flocking, etc. At the same time, researchers have also started characterizing the scenarios in which such problems cannot be solved, deriving impossibility results.

Our Motivation: Even Simpler Robots
-----------------------------------

An interesting question regards the minimal cognitive capabilities that such tiny robots need to have for completing a particular task. In particular, researchers have initiated the study of “weak robots”[@FlocchiniPSW99]. Weak robots are *anonymous* (they do not have any identifier), *autonomous* (they work independently), *homogeneous* (they behave the same in the same situation), and *silent* (they also do not communicate with each other).

Weak robots are usually assumed to have their own local view, represented as a Cartesian coordinate system with origin and unit length and axes. The orientation of axes, or the *chirality* (relative order of the orientation of axes or handedness), is not common among the robots. The robots move in a sequence of three consecutive actions, *Look-Compute-Move*: they observe the positions of other robots in their local coordinate system and the observation step returns a set of points to the observing robot. The robots cannot distinguish if there are multiple robots at the same position, i.e., they do not have the capability of *multiplicity detection*. Importantly, the robots are *oblivious* and cannot maintain state between rounds (essentially moving steps). The computation they perform are always based on the data they have collected in the *current* observation step; in the next round they again collect the data. Such weak robots are therefore interesting from a self-stabilizing perspective: as robots do not rely on memory, an adversary cannot manipulate the memory either. Indeed, researchers have demonstrated that weak robots are sufficient to solve a wide range of problems.

We in this paper aim to relax the assumptions on the tiny robots further. In particular, to the best of our knowledge, all prior literature assumes that robots can observe the positions of other robots in their local view. This enables them to calculate the distance between any pair of robots. This seems to be a very strong assumption, and accordingly, we in this paper initiate the study of even weaker robots which cannot locate other robots positions in their local view, preventing them from measuring distances. We define these kind of robots as *monoculus robots*.

In particular, we initiate to explore two naturally weaker models for monoculus robots with less cognitive capabilities

1.  *Locality Detection* ($\mathcal{LD}$): The robots can distinguish whether a neighbor robot is at a distance more than a predefined value $c$ or not.

2.  *Orthogonal Line Agreement* ($\mathcal{OLA}$): The robots agree on a pair of orthogonal lines (but not necessarily the orientation of the lines).

The Challenge: Convergence
--------------------------

We focus on the fundamental convergence problem for monoculus robots and show that the problem is already non-trivial in this setting.

In particular, many naive strategies lead to non-monotonic behaviors. For example, strategies where boundary robots (robots located on the convex hull) move toward the “median” robot they see, may actually *increase* the area of the convex hull in the next round, counteracting convergence as shown in Fig. \[fig:anglebisector\]$(a)$. A similar counterexample exists for a strategy where robots move in the direction of the angle bisector as shown in Fig. \[fig:anglebisector\] ($b$).

![ The 4 boundary robots are moving $(a)$ towards the median robot $(b)$ along the angle bisector. The discs are the old positions and circles are the new positions. The old convex hull is drawn in solid line, the new convex hull is dashed. The arrows denote the direction of moving. []{data-label="fig:anglebisector"}](figanglebisector.pdf){width="\linewidth"}

But not only enforcing convex hull invariants is challenging, also the fact that visibility is restricted and we cannot detect multiplicity: We in this paper assume that robots are not transparent, and accordingly, a robot does not see whether and how many robots may be hidden behind a visible robot. As robots are also not able to perform multiplicity detection (i.e., determine how many robots are collocated at a certain point), strategies such as “move toward the center of gravity” (the direction in which most robots are located), are not possible.

Our Contributions
-----------------

This paper studies distributed convergence problems for anonymous, autonomous, oblivious, non-transparent, monoculus, point robots under a most general asynchronous scheduling model and makes the following contributions.

1.  We initiate the study of a new kind of robot, the *monoculus robot* which cannot measure distances. The robot comes in two natural flavors, and we introduce the Locality Detection ($\mathcal{LD}$) and the Orthogonal Line Agreement ($\mathcal{OLA}$) model accordingly.

2.  We present and formally analyze deterministic and self-stabilizing distributed convergence algorithms for both $\mathcal{LD}$ and $\mathcal{OLA}$.

3.  We show our assumptions in $\mathcal{LD}$ and $\mathcal{OLA}$ are minimal in the sense that robot convergence is not possible for monoculus robots without any additional capability.

4.  We report on the performance of our algorithms through simulation.

5.  We show that our approach can be generalized to higher dimensions and, with a small extension, supports termination.

Paper Organization
------------------

The remainder of this paper is organized as follows. Section \[sec:preli\] introduces the necessary background and preliminaries. Section \[sec:algo\] introduces two algorithms for convergence. Section \[sec:impossibilty\] presents an impossibility result which shows the minimality of our assumptions. We report on simulation results in Section \[sec:simul\] and discuss extensions in Section \[sec:discussion\]. In Section \[sec:relwork\], we review related work, before we conclude in Section \[sec:conclusion\].

Preliminaries {#sec:preli}
=============

Model
-----

We consider anonymous, autonomous, homogeneous, oblivious, non-transparent robots with unlimited visibility, unless the view is obstructed by another robot: Since the robots are non-transparent, any robot can see at most one robot in any direction. As usual, the robots in each round execute a sequence of *Look-Compute-Move* steps: First, the robot observes other robots (*Look* step); second, on the basis of the observed information, it executes an algorithm which computes a direction which the robot must move towards (*Compute* step); the robot then moves in this direction (*Move* step), for a fixed distance $b$ (the step size). The robots are silent, cannot detect multiplicity points, and can pass over each other (no collision occurs).

In this paper, we introduce monoculus robots:

(Monoculus Robot) A robot is called *monoculus* if it is anonymous, autonomous, oblivious, homogeneous, and silent. We assume the robot is a non-transparent point robot, has unlimited visibility, and can neither determine the position of other robots nor detect multiplicty.

We consider the most general CORDA or ASYNC scheduling model known from weak robots [@FlocchiniPSW99] as well as the ATOM or Semi-Synchronous (SSYNC) model [@suzu]. These models define the activation schedule of the robots: the SSYNC model considers instantaneous computation and movement, i.e., the robots cannot observe other robots in motion, while in the ASYNC model any robot can look at any time. In SSYNC the time is divided into global rounds and a subset of the robots are activated in each round which finish their *Look-Compute-Move* within that round. In case of ASYNC, there is no global notion of time. The Fully-synchronous (FSYNC) is a special case of SSYNC, in which all the robots are activated in each round. The algorithms presented in this paper work in both the ASYNC and the SSYNC setting. For the sake of generality, we present our proofs in terms of the ASYNC model.

Notation and Terminology
------------------------

A configuration $C$ is a multiset containing all the robot positions in 2D. At any time $t$ the configuration (the mapping of robots in the plane) is denoted by $C_t$. The convex hull of configuration $C_t$ is denoted as $CH_t$. *Convergence* is achieved when the distance between any pair of robots is less than a predefined value $c$ (and subsequently does not violate this anymore). Our multi-robot system is vulnerable to adversarial manipulation, however the algorithms presented in this paper are self-stabilizing [@dolev2000self] and robust to state manipulations. Since the robots are oblivious, they only depend on the *current state*: if the state is perturbed, the algorithms are still able to converge in a self-stabilizing manner [@Gilbert2009].

Convergence Algorithms {#sec:algo}
======================

We now present distributed robot convergence algorithms for both our models, $\mathcal{LD}$ and $\mathcal{OLA}$.

Convergence for $\mathcal{LD}$
------------------------------

In this section we consider the convergence problem for the monoculus robots in the $\mathcal{LD}$ model. Our claims hold for any $c\geq 2b$. Algorithm \[algo:convergelocality\] distinguishes between two cases: (1) If the robot only sees one other robot, it infers that the current configuration must be a line (of 2 or more robots), and that this robot must be on the border of this line; in this case, the boundary robots always move inside (usual step size $b$). (2) Otherwise, a robot moves towards any visible, non-local robot (distance at least $c$), for a $b$ distance (the step size).

Our proof unfolds in a number of lemmas followed by a theorem. First, Lemma \[lem:4bdistance\] shows that it is impossible to have a pair of robots with distance larger than $2c$ in the converged situation. Lemma \[lem:chsubset\] shows that our algorithm ensures a monotonically decreasing convex hull size. Lemma \[lem:finitedecrement\] then proves that the decrement in perimeter for each movement is greater than a constant (the convex hull decrement is strictly monotonic). Combining all the three lemmas, we obtain the correctness proof of the algorithm. In the following, we call two robots *neighboring* if they see each other (line of sight is not obstructed by another robot).

\[lem:4bdistance\] If there exists a pair of robots at distance more than $2c$ in a non-linear configuration, then there exists a pair of neighboring robots at distance more than $c$.

Proof by contradiction. If there is a pair of robots with distance more than $2c$, then for them not to move, there are at least two robots on the line joining them positioned such that each pair has a distance less than $c$. Since the robots are non-transparent, the end robots cannot look beyond their neighbors to know that there is a robot at a distance more than $c$. In Fig. \[fig:4bdistance\], $r_1$ and $r_4$ are $2c$ apart. So $r_2$ and $r_3$ block the view. Since it is a non-linear configuration, say robot $r_5$ is not on the line joining $r_1$ and $r_4$. $l$ is the perpendicular bisector of $\overline{r_1r_4}$. If $r_5$ is on the left side, then it is more than $c$ distance away from $r_4$ and vice versa. If there is another robot on $\overline{r_4r_5}$, then consider that as the new robot in a non-linear position, and we can argue similarly. Hence there would at least be a single robot similar to $r_5$ in a non-linear configuration for which the distance is more than $c$.

![A non-linear configuration with a pair of robots at a distance $2c$[]{data-label="fig:4bdistance"}](fig4bdistance.pdf){height="0.2\linewidth"}

\[lem:chsubset\] For any time $t' > t$ before convergence, $CH_{t'}\subseteq CH_{t}$.

The proof follows from a simple observation. Consider any robot $r_i$. If $r_i$ decides to move towards some robot, say $r_j$, then it is at least $c$ distance away. Even if $r_j$ is on the boundary, $r_i$ cannot cross the boundary. If $r_i$ is already on the boundary, then it always moves on the perimeter or inside the convex hull. Hence the convex hull gradually decreases.

If all the robots are on a straight line, then the boundary robots move monotonically closer in each step. The distance between the end robots is a monotonically decreasing sequence until it reaches $c$.

\[lem:finitedecrement\] In finite time the decrement in the perimeter of the convex hull is at least $ b \left(1- \sqrt{\frac{1}{2}\left(1+\cos\left(\frac{2\pi}{n}\right)\right)}\right)$.

The sum of internal angles of a $k$-sided convex polygon is $(k-2)\pi$. So there exists a robot $r$ at a corner $A$ (ref. Fig. \[fig:decrement\]) of the convex hull such that the internal angle is less than $(1-\frac{2}{n})\pi$, where $n$ is the total number of robots. Let $B$ and $C$ be the points where the circle centered at $A$ with radius $b/2$ intersects the convex hull. Any robot lying outside the circle will not move inside the circle according to Algorithm \[algo:convergelocality\]. All the robots inside the circle will eventually move out once they are activated. After all the robots are activated at least once, the decrement in perimeter is at least $AB + AC - BC$. From cosine rule, $$AB + AC - BC = \frac{b}{2}+\frac{b}{2} -\sqrt{\left(\frac{b}{2}\right)^2+\left(\frac{b}{2}\right)^2-  2\frac{b}{2}\frac{b}{2}\cos\left(\pi -\frac{2\pi}{n}\right)}$$ $$= b \left(1- \sqrt{\frac{1}{2}\left(1+\cos\left(\frac{2\pi}{n}\right)\right)}\right)$$

![Once activated the robots $r$ and $r'$ will move outside the solid circle with radius $b/2$. The robot $r''$ moves a distance $b$ towards $r'$ because distance between them is more than $2b$ and stops at $D$.[]{data-label="fig:decrement"}](exampleforfinitedecrement.pdf){height="0.3\linewidth"}

(Correctness) Algorithm \[algo:convergelocality\] terminates when all the robots are within a $c$ radius disc.

From Lemmas \[lem:chsubset\] and \[lem:finitedecrement\] we know that the convex hull never increases, and eventually a robot will be activated which strictly decreases the hull. According to Lemma \[lem:4bdistance\], eventually there will not be a pair of robots with more than $2c$ distance. Note that the distance between any two points in a disc of radius $c$ is less than or equal to $2c$. Hence the robots will converge within a disc of radius $c$.

Convergence for $\mathcal{OLA}$
-------------------------------

In this section we consider monoculus robots in the $\mathcal{OLA}$ model. Our algorithm will distinguish between *boundary-*, *corner-* and *inner-robots*, defined in the canonical way. We note that robots can determine their type: From the Fig. \[fig:orthogonalline\], we can observe that for $r_2$, all the robots lie below the horizontal line. That means, one side of the horizontal line is empty and therefore $r_2$ can figure out that it is a boundary robot. Similarly all $r_i$, $i\in \{3,4,5,6,7,8\}$ are boundary robots. Whereas, for $r_1$, both horizontal and vertical lines have one of the sides empty, hence $r_1$ is a corner robot. Other robots are all inner robots. Consequently, we define *boundary robots* to be those, which have exactly one side of one of the orthogonal lines empty.

Algorithm \[algo:convergequadrant\] (<span style="font-variant:small-caps;">ConvergeQuadrant</span>) can be described as follows. A rectangle can be constructed with lines parallel to the orthogonal lines passing through boundary robots such that, all the robots are inside this rectangle. In Fig. \[fig:orthogonalline\], each boundary robot always moves inside the rectangle perpendicular to the boundary and the inside robots do not move. Note that the corner robot $r_1$ has two possible directions to move. So it moves toward any robot in that common quadrant. Gradually the distance between opposite boundaries becomes smaller and smaller and the robots converge. In case all the robots are on a line which is parallel to either of the orthogonal lines, then the robots will find that both sides of the line are empty. In that case they should not move. But the robots on either end of the line would only see one robot. So they would move along the line towards that robot.

![Movement direction of the boundary robots[]{data-label="fig:orthogonalline"}](figdirectionlesscompass.pdf){height="0.4\linewidth"}

(Correctness) Algorithm \[algo:convergequadrant\] moves all the robots inside some $2b$-sided square in finite time.

Consider the distance between the robots on the left and right boundary. The horizontal distance between them decreases each time either of them gets activated. The rightmost robot will move towards the left and the leftmost will move towards the right. The internal robots do not move. So in at most $n$ activation rounds of the boundary robot, the distance between two of the boundary nodes will decrease by at least $b$. Hence the distance is monotonically decreasing until $2b$. Afterwards, the total distance will never exceed $2b$ anymore.

Given there is a corner robot present in the configuration, that robot will move towards any robot in the non-empty quadrant. So, the movement of the corner robot contributes to the decrement in distance in both directions. Consider robots inside the quadrant are presently very close to one of the boundaries and the corner robot moves towards that robot, then the decrement in one of the dimensions can be small (an $\epsilon > 0$). Consider for example the configuration of a strip of width $b$, then the corner robot becomes the adjacent corner in the next round; this can happen only finitely many times. Each dimension converges within a distance $2b$, so in the converged state the shape of the converged area would be $2b$-sided square.

If the robots have some sense of angular knowledge, the corner robots can always move in a $\pi/4$ angle, so the decrement in both dimension is significant, hence convergence time is less on average.

Impossibility and Optimality {#sec:impossibilty}
============================

Given these positive results, we now show that we cannot make the monoculus robots much weaker, otherwise we lose convergeability.

There is no deterministic convergence algorithm for monoculus robots without any additional capability.

We prove the theorem using a symmetry argument. Consider the two configurations $C_1$ and $C_2$ in Fig. \[fig:indistinguishableconfig\]. In $C_1$, all the robots are equidistant from robot $r$, while in $C_2$, the robots are at different distances, however the relative angle of the robots is the same at $r$. Now considering the local view of robot $r$, it cannot distinguish between $C_1$ and $C_2$. Say a deterministic algorithm $\phi$ decides a direction of movement for robot $r$ in configuration $C_1$. Since both $C_1$ and $C_2$ are the same from robot $r$’s perspective, the deterministic algorithm outputs the same direction of movement for both cases.

![Locally indistinguishable configurations with respect to $r$[]{data-label="fig:indistinguishableconfig"}](figindistinguishableconfig.pdf){height="0.3\linewidth"}

Now consider the convex hull $CH_1$ and $CH_2$ of $C_1$ and $C_2$ respectively. The robot $r$ moves a distance $b$ in one round. The distance from any point inside $CH_1$ is more than $b$ but we can skew the convex hull in the direction of movement, so to make it like $CH_2$, where if the robot $r$ moves a distance $b$ it exits $CH_2$. Therefore there always exists a situation for any algorithm $\phi$ such that the area of the convex hull increases. Hence it is impossible for the robots to converge.

Simulation {#sec:simul}
==========

We now complement our formal analysis with simulations, studying the average case. We assume that robots are distributed uniformly at random in a square initially, that $b=1$ and $c=2$, and we consider FSYNC scheduling. As a baseline to evaluate performance, we consider the optimal convergence distance and time if the robots had capability to observe positions, i.e., they are *not* monoculus. Moreover, as a lower bound, we compare to an algorithm which converges all robots to the centroid, defined as follows: $$\{\bar{x}, \bar{y}\} = \left\{\cfrac{\sum_{i=1}^nx_i}{n},\cfrac{\sum_{i=1}^ny_i}{n}\right\}$$ where $\{x_i,y_i\} \forall i \in \{1,2,\cdots,n\}$ are the robots’ coordinates.

We calculate distance $d_i$ from each robot to the centroid in the initial configuration. The optimal distance we have used as convergence distance is the sum of distances from each robot to the unit disc centered at the centroid. So the sum of the optimal convergence distances $d_{opt}$ is given by $$d_{opt} = \sum_{i=1}^n (d_i -1), \quad if \, d_i>1$$ In the simulation of Algorithm \[algo:convergelocality\], we define $d_{CL}$ as the cumulative number of steps taken by all the robots to converge (sometimes also known as the *work*). Now we define the performance ratio, $\rho_{CL}$ as $$\rho_{CL} = \cfrac{d_{CL}}{d_{opt}}$$ Similarly for Algorithm \[algo:convergequadrant\] we define $d_{CQ}$ and $\rho_{CQ}$.\
In Fig. \[fig:varrobot\], we plot the distribution of 100 iterations of simulation of Algorithm \[algo:convergelocality\], varying the number of robots for a fixed region of deployment. The median increases if we increase the number of robots deployed in the same region.

In Fig. \[fig:varrobotCQ\], we plot the distribution of 100 iterations of simulation of Algorithm \[algo:convergequadrant\] varying the number of robots for a fixed region of deployment. The median increases if we increase the number of robots deployed in the same region. In Fig. \[fig:varregionCQ\], we plot the distribution of 100 iterations of simulation of Algorithm \[algo:convergequadrant\] for a fixed number of robots deployed in different regions. Here we can observe that the distribution does not vary much even if we change the region of deployment.

![Different number of robots in same region in $\mathcal{LD}$[]{data-label="fig:varrobot"}](VarRobotFixRange100.pdf){width="\linewidth"}

![Fixed number of robots deployed in different region in $\mathcal{LD}$[]{data-label="fig:varrange"}](VarRangeFixRobot40.pdf){width="\linewidth"}

![Different number of robots in same region in $\mathcal{OLA}$[]{data-label="fig:varrobotCQ"}](CQVarRobotFixRange100.pdf){width="\linewidth"}

![Fixed number of robots deployed in different region in $\mathcal{OLA}$[]{data-label="fig:varregionCQ"}](CQVarRangeFixRobot40.pdf){width="\linewidth"}

In Fig. \[fig:varrange\], we plot the distribution of 100 iterations of simulation of Algorithm  \[algo:convergelocality\] for a fixed number of robots deployed in different regions. Here we can observe that the distribution does not vary much even if we change the region of deployment.

![ $\rho_{CL}$ VS $\rho_{CQ}$ for the same number of robots[]{data-label="fig:compareCLCQrobotdistance"}](CLvsCQdistance40robot.pdf){height="0.37\linewidth"}

![ $\rho_{CL}$ VS $\rho_{CQ}$ for the same size of region[]{data-label="fig:compareCLCQregiondistance"}](CLvsCQdistance100region.pdf){height="0.37\linewidth"}

![ $\tau_{CL}$ VS $\tau_{CQ}$ for the same number of robots[]{data-label="fig:compareCLCQrobot"}](CLvsCQtime40robot.pdf){height="0.37\linewidth"}

![$\tau_{CL}$ VS $\tau_{CQ}$ for the same size of region[]{data-label="fig:compareCLCQregion"}](CLvsCQtime100region.pdf){height="0.37\linewidth"}

Fig. \[fig:compareCLCQrobotdistance\], and  \[fig:compareCLCQregiondistance\] show the comparison between the performance ratio (PR) for distance. We can observe that Algorithm \[algo:convergequadrant\] performs better. This is due to the fact that, in Algorithm \[algo:convergequadrant\] only boundary robots move.

Let $d_{max}$ be the distance of farthest robot from the centroid and $t_{CL} $ be the number of synchronous rounds taken by Algorithm \[algo:convergelocality\] for convergence. We define $\tau_{CL}$ as follows $$\tau_{CL} =\cfrac{t_{CL}}{d_{max}}$$ Similarly for Algorithm \[algo:convergequadrant\], we define $t_{CQ}$ and $\tau_{CQ}$. $\tau_{CL}$ and $\tau_{CQ}$ show performance ratio for convergence time of Algorithm \[algo:convergelocality\] and  \[algo:convergequadrant\] respectively. In Fig. \[fig:compareCLCQrobot\] and  \[fig:compareCLCQregion\], we can observe that $\tau_{CL}$ is very close to 1, so Algorithm \[algo:convergelocality\] converges in almost the same number of synchronous rounds (proportional to distance covered, since step size $b=1$) as the maximum distance. We can observer that Algorithm \[algo:convergequadrant\] takes more time as the number of robots and the side length of square region increases.

Discussion {#sec:discussion}
==========

This section shows that our approach supports some interesting extensions.

Termination for $\mathcal{OLA}$ Model
-------------------------------------

While we only focused on convergence and not termination so far, we can show that with a small amount of memory, termination is also possible in the $\mathcal{OLA}$ model. To see this, assume that each robot has a 2-bit persistent memory in the $\mathcal{OLA}$ model for each dimension, total 4-bits for two dimensions. Algorithm \[algo:convergequadrant\] has been modified to Algorithm \[algo:convergequadranttermination\] such that it can accommodate termination. All the bits are initially set to 0. Each robot has its local coordinate system, which remains consistent over the execution of the algorithm. The four bits correspond to four boundaries in two dimensions, i.e., left, right, top and bottom. If a robot finds itself on one of the boundaries according to its local coordinate system, then it sets the corresponding bit of that boundary to 1. Once both bits corresponding to a dimension become 1, the robot stops moving in that dimension. Consider a robot $r$. Initially it was on the left boundary in its local coordinate system. Then it sets the first bit of the pair of bits corresponding to $x$-axis. It moves towards right. Once it reaches the right boundary, then it sets the second bit corresponding to $x$-axis to 1. Once both the bits are set to 1, it stops moving along the $x$-axis. Similar movement termination happens on the $y$-axis also. Once all the 4-bits are set to 1, the robot stops moving.

Extension to $d$-Dimensions
---------------------------

Both our algorithms can easily be extended to $d$-dimensions. For the $\mathcal{LD}$ model, the algorithm remains exactly the same. For the proof of convergence, similar arguments as Lemma \[lem:finitedecrement\] can be used in $d$ dimensions. We can consider the convex hull in $d$-dimensions and the boundary robots of the convex hull always move inside. The size of convex hull reduces gradually and the robots converge.

Analogously for the $\mathcal{OLA}$ model, the distance between two robots in the boundary of any dimension gradually decreases and the corner robots always move inside the $d$-dimensional cuboid. Hence it converges. Here the robot would require $2d$ number of bits for termination.

Related Work {#sec:relwork}
============

The problems of gathering [@suzuki1999distributed], where all the robots gather at a single point, convergence [@cohen2006convergence], where robots come very close to each other and Pattern formation [@flochini1; @suzuki1999distributed] have been studied intensively in the literature.

Flocchini et al. [@FlocchiniPSW99] introduced the CORDA or Asynchronous (ASYNC) scheduling model for weak robots. Suzuki et al. [@suzu] have introduced the ATOM or Semi-synchronous (SSYNC) model. In [@suzuki1999distributed], impossibility of gathering for $n=2$ without assumptions on local coordinate system agreement for *SSYNC* and *ASYNC* is proved. Also, for $n>2$ it is impossible to solve gathering without assumptions on either coordinate system agreement or multiplicity detection [@Prencipe2007]. Cohen and Peleg [@CohenP04] have proposed a center of gravity algorithm for convergence of two robots in ASYNC and any number of robots in SSYNC.

To the best of our knowledge in all the previous works, the mathematical models always assume that the robots can find out the location of other robots in their local coordinate system in the Look step. This in turn implies that the robots can measure the distance between any pair of robots albeit in their local coordinates. All the algorithms exploit this location information to create an invariant point or a robot where all the other robots gather. But in this paper we deprive the robots of the capability to determine the location of other robots. This leads to robots incapable of finding any kind of distance or angles. Any kind of pattern formation requires these robots to move to a particular point of the pattern. Since the monoculus robots cannot figure out locations, they cannot stop at a particular point. Hence any kind of pattern formation algorithm described in the previous works which requires location information as input are obsolete. Gathering problem is nothing but the point formation problem [@suzuki1999distributed]. Hence gathering is also not possible for the monoculus robots.

Conclusion {#sec:conclusion}
==========

This paper introduced the notion of *monoculus robots* which cannot measure distance: a practically relevant generalization of existing robot models. We have proved that the two basic models still allow for convergence (and with a small memory, even termination), but with less capabilities, this becomes impossible.

The $\mathcal{LD}$ model converges in an almost optimal number of rounds, while the $\mathcal{OLA}$ model takes more time. But the cumulative number of steps is less for the $\mathcal{OLA}$ model compared to the $\mathcal{LD}$ model since only boundary robots move. Although we found in our simulations that the median and angle bisector strategies successfully converge, finding a proof accordingly remains an open question. We see our work as a first step, and believe that the study of weaker robots opens an interesting field for future research.

[^1]: Trip to IIT Guwahati and Research were funded by Global Initiative of Academic Networks (GIAN), an initiative by Govt. of India for Higher Education.
