A condensed version of this paper appears in [26]. [300]Theory of computation
Distributed computing models [300]Theory of computation Computational geometry
[500]Computer systems organization Robotics Dept. of Computer Science,
University of British Columbia, Vancouver, Canada<EMAIL_ADDRESS>Dept. of
Mathematics and Computer Science, TU Eindhoven, Eindhoven, the
<EMAIL_ADDRESS>Dept. of Mathematics and Computer Science,
University of Perugia, Perugia<EMAIL_ADDRESS>Dipartimento di
Informatica, University of Pisa, Pisa<EMAIL_ADDRESS>School
of Computer Science, Carleton University, Ottawa,
<EMAIL_ADDRESS>
# Separating Bounded and Unbounded Asynchrony for Autonomous Robots: Point
Convergence with Limited Visibility

David Kirkpatrick  Irina Kostitsyna  Alfredo Navarra  Giuseppe Prencipe
Nicola Santoro

###### Abstract

Among fundamental problems in the context of distributed computing by
autonomous mobile entities, one of the most representative and well studied is
Point Convergence: given an arbitrary initial configuration of identical
entities, disposed in the Euclidean plane, move in such a way that, for all
$\varepsilon>0$, a configuration in which the separation between all entities
is at most $\varepsilon$ is eventually reached and maintained.

The problem has been previously studied in a variety of settings, including
full visibility, exact measurements (like distances and angles), and
synchronous activation of entities. Our study concerns the minimal assumptions
under which entities, moving asynchronously with limited and unknown
visibility range and subject to limited imprecision in measurements, can be
guaranteed to converge in this way. We present an algorithm that solves Point
Convergence, for entities in the plane, in such a setting, provided the degree
of asynchrony is bounded: while any one entity is active, any other entity can
be activated at most $k$ times, for some arbitrarily large but fixed $k$. This
provides a strong positive answer to a decade old open question posed by
Katreniak.

We also prove that in a comparable setting that permits unbounded asynchrony,
Point Convergence in the plane is impossible, contingent on the natural
assumption that algorithms maintain the (visible) connectivity among entities
present in the initial configuration. This variant, that we call Cohesive
Convergence, serves to distinguish the power of bounded and unbounded
asynchrony in the control of autonomous mobile entities, settling at the same
time a long-standing question whether in the Euclidean plane synchronously
scheduled entities are more powerful than asynchronously scheduled entities.

###### keywords:

Mobile robots, Distributed geometric algorithms, Asynchronous computation

D. Kirkpatrick, I. Kostitsyna, A. Navarra, G. Prencipe, N. Santoro

##  1 Introduction

###  1.1 Framework and background

The notion of distributed computational system, initially restricted to
systems of processing units interacting by exchanging messages through a fixed
communication network, over time has been broadened to include not only other
forms of communication (e.g., via shared memory), but also very different
types of computational entities and operational environments, from mobile
agents to programmable particles, from mobile wireless ad-hoc networks to
robot swarms.

The main theoretical questions in all these environments are the same: what
are the minimal conditions that allow the entities to solve certain
fundamental problems? What is the computational relationship between different
conditions? In this paper, we address these questions for the standard
${\mathcal{O}BLOT}$ model of systems of autonomous mobile entities.

In this model, an arbitrarily large collection of identical computational
entities, called robots, operate in one or higher dimensional Euclidean space
within which they can move without constraint. Robots have no memory of past
configurations or actions, no global knowledge about the system beyond what
they are able to sense within some fixed but possibly unknown visibility
range, and no means of direct communication with other robots. In a single
active cycle, a robot plans, following a fixed built-in algorithm informed by
what it currently senses alone, and then initiates a change of position, that
may stop short of being fully realized.

Since the only input available to and the only output produced by individual
active cycles are geometric positions, computations in this model are very
different from those in other distributed universes (e.g., message-passing
networks). Informally then, computations in this model are just movements of
the robots from their initial configuration toward other goal configurations,
and (computational) problems are typically expressed as temporal geometric
predicates on goal and intermediate configurations.

For example, simple pattern formation problems require the robots to reach,
through a sequence of intermediate configurations that maintain some geometric
invariant (such as collision avoidance or the preservation of visibility), a
configuration where their positions satisfy the geometric predicate (the
pattern) of that problem and remain stationary thereafter. In contrast, for
simple pattern convergence problems, the robots are required to form the
pattern in the limit.

An algorithm solves a problem if, under its control, starting from any valid
initial configuration, the robots reach configurations that satisfy its
temporal geometric predicate in all valid activation sequences. The validity
of activation sequences is determined by the level of synchronization of the
system; as in other distributed environments (e.g., message-passing networks),
the primary distinction is between synchronous and asynchronous scheduling
models.

In synchronous systems (SSync), activity is divided into discrete intervals,
called rounds; in each round, activated robots perform their activity cycle in
perfect synchronization. The only constraint is activation fairness: every
robot is activated infinitely often. This very general model, first studied in
[32], is also sometimes called semi-synchronous to distinguish it from the
fully-synchronous model (FSync), the special case where all robots are active
in every round.

In contrast, in asynchronous systems (Async), first studied in [23], robots
are activated at arbitrary times (constrained again by activation fairness),
independently of the other robots, and the duration of individual active
cycles, though finite, is unpredictable.

There are many studies on the feasibility of problems and the complexity of
algorithms in both the synchronous and asynchronous settings, e.g., see [2, 8,
9, 12, 13, 14, 19, 21, 22, 24, 11, 31, 32, 34]. In spite of the long and
intensive research efforts, a fundamental question is still outstanding: Is
there any difference in computational scope between algorithms working within
the SSync and Async scheduling models? More precisely: Does the assumption of
synchronous scheduling of activity make possible the solution of some problem
that is not solvable in the asynchronous setting?

Any problem providing a positive answer would computationally separate the two
settings. The quest for a separator has motivated a large number of studies,
but so far no computational difference between SSync and Async has been
determined. In this paper, we provide an affirmative answer to the question.
In fact, our results demonstrate an even stronger separation: between
scheduling models with unbounded asynchrony (Async) and bounded asynchrony
(what we call $k$-Async).

###  1.2 Related work

Previous work on the computational power of collections of autonomous mobile
robots has concentrated on the study of pattern formation and pattern
convergence problems.111Many other problems can be reduced to pattern
formation ones (e.g., leader election, gathering) or require pattern formation
as an integral step (e.g. flocking). The vast majority of works assume that
the visibility range of the robots is unlimited.

####  1.2.1 Pattern formation

The first question studied has been what patterns can be formed from a given
initial configuration [32]. Assuming that robots share a common handedness
(also called chirality), a sequence of results has shown that the set of
formable patterns is determined solely by the symmetry of the initial
configurations, [11, 32, 34]. In other words, with chirality, there is no
distinction between the patterns formable from an initial configuration in the
SSync and Async models. No similar general results are known without
chirality.

Two specific pattern formation problems exhibit the level of symmetry
necessary for their solution starting from all initial configurations, namely
Point Formation and Uniform Circle Formation. Point Formation corresponds to a
basic coordination task in swarm robotics, called Gathering or Rendezvous,
where all robots are required to meet at a common point (not fixed in
advance).

Remarkably, these two pattern formation problems have been solved in the most
general Async without chirality in [13] and [21], respectively; hence they
cannot serve to separate the Async and SSync models. This, in part, stimulated
the study of the less stringent, but still well-motivated, pattern convergence
variant of Point Formation, namely Point Convergence. The Point Convergence
problem requires robots to move in such a way that, for all $\varepsilon>0$, a
configuration in which the separation between all robots is at most
$\varepsilon$. Point Convergence is discussed in more detail below.

The converse question of determining from which initial configurations it is
possible to form any possible pattern, called Arbitrary Pattern Formation, was
posed and studied in [22] for Async robots without chirality; the answer to
this question has been provided in [9], where it has been shown that the set
of possible initial configurations coincides with those from which it is
possible to solve another basic problem, namely Leader Election.

Related investigations include the Embedded Pattern Formation problem, where
the pattern is given to the robots as visible points in the plain, solved by
Async robots without chirality [10]; and the problem Pattern Sequence of
forming a sequence of patterns in spite of obliviousness, solved by SSync
robots with chirality [18].

When the visibility range of the robots is limited, the setting considered in
this paper, relatively little is known. It has been recently shown that
limited visibility drastically reduces the set of formable patterns by Async
robots [36].

####  1.2.2 Point Convergence under unlimited visibility

Without further restrictions to the capabilities of the robots, Point
Convergence has been solved, in [14], by means of the so-called
Go_To_The_Centre_Of_Gravity (CoG), algorithm. In this algorithm robots move
toward the center of gravity of the configuration, the unique point where the
weighted position vectors of all the robots’ locations sum up to zero. Note
that the center of gravity may change as robots move. The convergence rate of
this algorithm is $O(n^{2})$, measured in terms of the number of rounds
requited to halve the diameter of the convex-hull of the $n$ robots’ positions
(where a round corresponds to the minimal time during which all robots have
completed at least one activation cycle). A lower bound of $\Omega(n)$ on the
convergence required to solve Convergence was also provided.

In [16], a new algorithm was demonstrated that solves Point Convergence in an
asymptotically optimal $\Theta(n)$ number of rounds. It applies the
Go_To_The_Center_Of_Minbox (GCM) strategy, where the _minbox_ is the minimal
axes aligned box containing all current robots’ positions. In fact, when
robots share the notion about the orientation of the coordinate system axes,
the algorithm requires constant time for halving the diameter of the convex
hull.

In [29, 30], two algorithms were developed, taking into consideration further
relaxations of the underlying model. First, occlusion is taken into account,
that is, a robot $\mathbb{X}$ looking at a robot $\mathbb{Y}$ cannot see
anything behind $\mathbb{Y}$ (along the ray from $\mathbb{X}$ that passes
through $\mathbb{Y}$). Second, the proposed algorithms do not depend on the
actual distances of the robots but two main variants are considered: (1) a
robot can only deduce whether another robot is closer than a given constant
distance $\delta$ or not; (2) an orthogonal line agreement model is assumed in
which robots only agree on a pair of orthogonal lines. For (1) the proposed
algorithm makes a robot moving toward other robots that are at distance
greater than $\delta$ from itself. In (2), instead, still an algorithm based
on the minbox strategy is applied.

Other interesting works on Point Convergence concern the possible inaccuracy
of the measurements (in terms of distances or angles) of the robots. The first
investigation taking this kind of error into account can be found in [15]. In
particular, the authors show that still the CoG algorithm can solve
Convergence but in the FSync setting, whereas it fails in the Async setting.
The problem remains open for the SSync setting. Furthermore, they introduce a
modification of the algorithm (called Restricted_CoG) that ensures convergence
in the SSync setting and in the 1-dimensional Async setting. The problem was
left open for the 2-dimensional case of Async robots.

An extension of [15] in terms of solvability under imprecise measurements can
be found in [33]. The considered errors are restricted to uniform behaviours,
that is, the same percentage of error with respect to the measurements is
assumed for all the distances and angles perceived during an observation by a
robot. In such a uniform case, it is shown that the convergence problem can be
solved in a significantly wider set of cases.

####  1.2.3 Point Convergence under limited visibility

Very few investigations have focused on the limited visibility setting, and
among these none considers measurement errors (see [4], for a recent survey).

A central issue that arises when dealing with limited visibility concerns
_connectivity_. When two robots are within distance $V$, the visibility range
which may or may not be known to the robots, they are assumed to be visible to
each other. Any instantaneous configuration of robots induces a _visibility
graph_ that is usually (and naturally) assumed to be connected. In that case
the configuration itself is said to be connected.

In [24] it has been shown that Point Formation is solvable in Async if the
robots are endowed with global consistency of the local coordinate system. A
variant of Point Convergence is the Collisionless Convergence problem, which
requires the robots to converge without two (or more) robots ever occupying
the same point at the same time. This has been studied in [28], showing it can
be solved in Async when all the robots are assumed to have a compass (hence
they agree on the “North” direction), but they do not necessarily have the
same handedness (hence they may disagree on the “West”).

The pioneering work on Point Convergence under limited visibility is by Ando
et al. [2], in the SSync scheduling model. The authors propose and analyze an
algorithm that leads to convergence, by means of _cautious_ moves, starting
from any connected configuration of robots. In their
Go_To_The_Centre_Of_The_SEC algorithm, each active robot takes a snapshot of
its surrounding (up to a known limited visibility range $V$), computes the
center of the _Smallest Enclosing Circle_ (SEC) of the perceived robots,222The
smallest circle that encloses all the robots perceived during the Look phase
at distance not greater than $V$. and then makes a move toward the center of
the SEC for a distance that guarantees to preserve the visibility of these
perceived robots, regardless of the movements of other robots following the
same protocol. (Quite recently, Braun et al. [6] considered an extension of
the Go_To_The_Centre_Of_The_SEC algorithm applied in the three dimensional
Euclidean space, assuming a FSync and continuous time scheduling model.)

In subsequent work [25], Katreniak introduced the more powerful $k$-Async
scheduling model, that permits robot activations with bounded asynchrony, and
presents a solution algorithm for Point Convergence in the 1-Async model (a
solution under a more restricted version of the 1-Async scheduler was
presented earlier in [27]). The resolution of Convergence in the $k$-Async
model, for $k>1$, was left as an open problem.

The algorithms of Ando et al. and Katreniak, are reviewed in more detail in
Section 3. It is worth pointing out here that these, like all known algorithms
that deal with limited visibility, have the property that if two robots are
initially within visibility range of each other, they remain so at all times.
Thus they solve a more restricted variant of Point Convergence, that we call
Cohesive Convergence, that includes this property as a invariant. It follows
that, when solving Cohesive Convergence, an initially connected robot
configuration will remain connected indefinitely.

###  1.3 Main contributions

The focus of this paper, as in those of Ando et al. [2] and Katreniak [25],
concerns the Cohesive Convergence problem for identical autonomous robots with
bounded visibility. This requires any collection of such robots, starting from
an arbitrary connected configuration, to move, under the control of a possibly
adversarial scheduler, in such a way that, for all $\varepsilon>0$, the robots
are guaranteed to reach and maintain a configuration in which all robots lie
within a circle of radius at most $\varepsilon$. Our primary contributions are
threefold: (i) a novel moderately error-tolerant algorithm that succeeds in
the $k$-Async scheduling model for any fixed $k$, an environment that permits
scheduling of robot activity with an arbitrarily large but bounded degree of
asynchrony, (ii) an analysis that allows us to go well beyond what is possible
with previous techniques that depend on the assumption of a significantly more
restricted scheduling environment (SSync or $1$-Async), shedding new light on
the power of bounded asynchrony, and (iii) a family of robot configurations
that demonstrates the impossibility of solving Cohesive Convergence in Async,
the fully asynchronous scheduling environment, provided algorithms are
required to tolerate a modest amount of imprecision in perception
(significantly less than what can be tolerated by our $k$-Async algorithm).

Even in the same scheduling environment, our algorithm (described in its basic
form in Section 3, with extensions, including error-tolerance, and higher-
dimensional generalizations, outlined in Section 6) is slightly simpler in
formulation and provides a more general solution than its predecessors
developed in [2, 25, 27]. In particular, the motion function of a robot
depends only on the directions to the pair of visible neighbours, among those
that are relatively distant, that define the maximum angular range.
Furthermore, distance and angle measurements to visible neighbours are assumed
to be accurate only to within some limited imprecision, and robot motion is
subject to some limited error in both distance and angle. Finally, our
algorithm exhibits a degree of uniformity not evident in its predecessors:
specifically, (a) dependence on the visibility range $V$ is not built into the
algorithm, and (b) our algorithm is simply formulated to work in an
environment with a base level of asynchrony; to function in an environment
that permits a higher degree of asynchrony, captured by a parameter $k$, one
can simply scale the motion function used by our algorithm in its base
formulation by a factor of $1/k$.

As with the analysis of algorithms in [2, 25, 27], our proof of convergence
involves (i) an argument that the connectivity of the initial configuration is
preserved, and (ii) an argument that congregation, i.e. convergence to an
arbitrarily small region, eventually takes place. Our connectivity
preservation analysis (presented in Section 4) is complicated by the fact
that, harnessed by an adversarial scheduler, even the most basic level of
asynchrony makes it impossible for a robot $\mathbb{X}$ to accurately discern
the influence of its own location on the motion of an active neighbour
$\mathbb{Y}$. This is further compounded by the fact that in environments with
a higher degree of asynchrony $\mathbb{Y}$ might have seen $\mathbb{X}$ many
times during its current motion. In order to help isolate the most salient
features of our analysis in asynchronous environments, we first introduce a
restriction on the $k$-Async environment, requiring intersecting activity
intervals to nest (one entirely within the other). By staging our analysis in
this way, we provide a clearer picture of the extent to which the difficulties
associated with asynchrony in our setting arise from (possibly lengthy)
chained, as opposed to nested, activations. To demonstrate the preservation of
visibility under arbitrarily long chains of activations we introduce a novel
backward reachability analysis that fully exploits the relative simplicity of
our algorithm’s motion function. For our congregation argument (presented in
Section 5), we start by observing, as was the case in [2, 25, 27], that
convergence to a convex configuration with bounded diameter follows directly
from the fact that the convex hull of successive configurations are properly
nested. Our argument that the limiting diameter is zero differs from, and is
arguably simpler than, that used in these earlier works. The argument exploits
a kind of hereditary property that ensures that, after some point in time,
robot locations become relatively stable in the sense that once a robot has
vacated a small neighbourhood of an extreme point of the configuration it must
remain outside.

Demonstrating the impossibility of solving Cohesive Convergence in any
environment that assumes exact measurement and control seems daunting, since
such assumptions open up the possibility of encoding information, perhaps
history, in the location of robots. However, we show (in Section 7) that
algorithms that control more realistic robots that operate with even a very
modest amount of imprecision in measurements in a scheduling environment with
no bound on asynchrony (other that a fairness condition that ensures that no
robot is permanently locked out of activity), cannot solve Cohesive
Convergence. This is demonstrated by a family of configurations with the
property that for any algorithm there is a configuration in the family that
can be forced to become disconnected into two linearly separable components.
Interestingly, the adversarial scheduler that achieves this uses only nested
activations (of necessarily unbounded depth).

In summary, we prove that, considering algorithms that tolerate a very modest
amount of measurement imprecision, Cohesive Convergence is solvable in the
$k$-Async scheduling model, for any fixed $k$, providing a strong positive
answer to a question left open in [25]. However, under even slightly weaker
assumptions, the same problem is shown to be unsolvable in the Async
scheduling model. In this sense, Cohesive Convergence provides a separation
between scheduling models with bounded and unbounded asynchrony, and ipso
facto between the SSync and Async scheduling models. Our work raises several
interesting questions, suitable for future research. Several of these are
highlighted in our concluding section (Section 8).

##  2 Model

We consider the standard ${\mathcal{O}BLOT}$ model of distributed systems of
mobile entities (e.g., see [20]). The system is composed of a set
$\mathcal{R}=\\{\mathbb{X}^{1},\ldots,\mathbb{X}^{n}\\}$ of $n\geq 1$
oblivious computational entities, called robots, that reside in
$d$-dimensional Euclidean space ${\mathbb{R}}^{d}$, $d\geq 1$, in which they
can move, and operate in Look-Compute-Move activity cycles.333If $P$ and $Q$
are points in $\mathbb{R}^{d}$, we denote by $\overline{PQ}$ the line segment
joining $P$ and $Q$, by $|PQ|$ the length of this segment, and by
$\overrightarrow{PQ}$ the ray from $P$ to $Q$.

###  2.1 Robots

We treat robots as dimensionless entities in , with $\mathbb{R}^{2}$; a
discussion of extensions to higher dimensional spaces is left to Section 6. We
use $X$ to denote the generic location of robot $\mathbb{X}$; when needed
$X(t)$ is used to denote the location of $\mathbb{X}$ at a specific time $t$.
The multiset ${\mathcal{C}}(t)=\\{X(t):X\in{\mathcal{R}}\\}$ specifying the
locations of the robots at time $t$ is called the configuration of the system
at time $t$.

Robots are equipped with sensorial devices that allow them to observe the
positions of the other robots within a fixed, but possibly unknown range $V$.
More precisely, the visible region of robot $\mathbb{X}$ at time $t$ is the
closed point set Vis$(\mathbb{X},t)=\\{Y:|X(t)Y|\leq V\\}$. We say that a
robot $\mathbb{Y}$ is a _neighbour_ of robot $\mathbb{X}$ at time $t$ if
$Y(t)$ belongs to Vis$(\mathbb{X},t)$. The associated visibility graph at time
$t$ is the undirected graph $G(t)=({\mathcal{R}},E(t))$, where
$(\mathbb{X},\mathbb{Y})\in E(t)$ if and only if $|X(t)Y(t)|\leq V$. A
configuration of robots is said to be connected when its associated visibility
graph is connected.

Robots are provided with a persistent read-only memory containing a control
algorithm as well as a local volatile memory for its computations, that could
involve exact real arithmetic. Robots are endowed with unrestricted motorial
capabilities; that is, they are free to move in any direction.

Robots are (i) autonomous: that is, they operate without a central control or
external supervision, (ii) identical: that is, they are indistinguishable by
their appearance, they do not have distinct identities that can be used during
the computation, and they all have and execute the same algorithm; and (iii)
silent: they have no means of direct communication of information to other
robots, so any communication occurs in a totally implicit manner, by moving
and by observing the positions of the robots within visibility range.

###  2.2 Activity cycles and obliviousness

The behaviour of each robot can be described as the alternation of finite
length _activity_ intervals with finite length _inactivity_ intervals. Each
active interval consists of a sequence of three phases: Look, Compute, and
Move, called a Look-Compute-Move (LCM) activity cycle. The operations
performed by each robot $\mathbb{X}$ in each phase are as follows.

  1. 1.

Look. At the start of an activity interval, the robot observes the world
within its visibility range. The result is an instantaneous snapshot of the
positions444If the robots are endowed with multiplicity detection, the
snapshot indicates also whether there are two or more robots co-located at a
point; otherwise such multiplicities are perceived as a single robot. occupied
by visible robots at that time; these positions are expressed within a local
(i.e., private) coordinate system. The private coordinate systems of different
robots at the same time, or the same robot at different times, need not be
consistent; hence from a global point of view, the robots are disoriented.

  2. 2.

Compute. Using the snapshot as an input, the robot executes its built-in
algorithm ${\mathcal{A}}$, the same for all robots, which determines an
intended destination point.

  3. 3.

Move. If the destination point coincides with its current location,
$\mathbb{X}$ is said to perform the _nil_ movement; otherwise it moves toward
the computed destination along a straight trajectory. The Move phase (and with
it, the activity cycle) of a robot might end before it reaches its
destination.

The duration of each Compute and Move phase is assumed to be finite,555Note
that also the Compute phase could be assumed to be instantaneous, without any
loss of generality. while the Look phase is assumed to be instantaneous.
During a Move phase a robot is said to be motile (not necessarily moving, but
capable of moving), otherwise it is immotile.

The local memory of the robots is volatile: at the end of a cycle, all
contents are erased. In other words, the robots are oblivious: at the
beginning of each activity cycle, a robot has no memory of past actions and
computations, and the computation is based solely on what determined in the
current cycle.

###  2.3 Adversarial control and conditions

In the environment in which the robots operate, there are several factors and
conditions, in addition to the initial configuration, that are beyond the
control of their algorithm but nevertheless impact their actions and,
ultimately, their worst-case behaviour. These factors, which are assumed to be
under adversarial control, are discussed in the following.

####  2.3.1 Activation and Synchronization

The mapping of robot activities to time, including activation/deactivation
times, as well as the duration of Compute and Move phases within each activity
cycle, and the rate of motion within each Move phase, is determined by a
scheduler that is constrained only by the understood level (or model) of
system synchronization. In all models, the scheduler must respect activation
fairness: for each robot $\mathbb{X}$ and each time $t$, there exists a time
$t^{\prime}>t$ where $\mathbb{X}$ will be active.

The main models are the synchronous and the asynchronous ones:

  * •

In the synchronous (also called semi-synchronous) model (SSync) time is
logically divided into a sequence of _rounds_. In each round, a subset of the
robots is activated, and they perform each phase of their LCM cycle
simultaneously, terminating their activity interval by the end of the round.
The choice of which robots are activated in a round is made by the scheduler.
A special case of SSync is the fully-synchronous model (FSync) where all
robots are activated in every round.

  * •

In the asynchronous model (Async), each robot is activated at arbitrary times,
independently of the others; in each activation interval, the duration of each
Compute and Move phase is finite but unpredictable, and might be different in
different cycles. The duration of the Compute and Move phases of each cycle as
well as the decision of when to activate a robot is controlled by the
scheduler.

An illustration of the difference between the activations and durations in
FSync, SSync, and Async is shown in Figure 1.

Figure 1:  The execution model of active intervals for each of FSync, SSync,
and Async robots. Inactive intervals are implicitly represented by empty time
periods. Figure 2: The execution model of active intervals for $1$-NestA and
$1$-Async robots.

The asynchronous model licenses an adversarial scheduler to depart from the
synchronous model in two ways: (i) activation intervals of different robots
can overlap arbitrarily; and (ii) one robot can be activated arbitrarily many
times during a single activation of another robot. With this in mind, we first
define the nested-activation model (NestA) that restricts the activity
intervals of all pairs of robots to be either disjoint or nested (no active
interval contains exactly one endpoint of another active interval). We will
focus more precisely on two natural restrictions of the NestA and Async
models, that lie between the SSync and Async models (see Figure 2):

  * •

_$k$ -Nested-Activations_ ($k$-NestA): Activity intervals of any pair of
robots are either disjoint or nested, and in addition, at most $k$ activity
intervals of one robot can be nested within a single activity interval of
another.

  * •

_$k$ -Asynchronous_ ($k$-Async): As in Async, robots are activated
independently and the duration of each activity interval is arbitrary (but
finite). However, at most $k$ activations of one robot can occur within a
single active interval of another.

####  2.3.2 Rigidity of motion

In the Move phase, there is a constant $\xi\in(0,1]$ (unknown to the robots,
and possibly related to the visibility range $V$) such that robots are
guaranteed to move at least fraction $\xi$ of the way toward their intended
destination. The associated motion is said to be $\xi$-rigid. (If $\xi=1$,
motion is simply said to be rigid).666In the literature, non-rigid motion is
usually qualified by an assumption that at least some non-trivial distance is
traversed. In our setting, where it makes no sense for an algorithm to specify
a motion of length that significantly exceeds the visibility range, this
assumption can be subsumed by the $\xi$-rigid assumption, for suitable $\xi$.

####  2.3.3 Measurement imprecision and coordinate system distortion

In error-tolerant settings, the accuracy of the measurements (distances and
angles) made by a robot during its Compute phase, as well as that of a robot’s
ability to realize its intended trajectory during its Move phase, are
considered to be subject to adversarial control.

One natural way in which relative error in angle measurements could arise is
from a small symmetric distortion of a robot’s local coordinate system: a
continuous bijection $\mu:[0,2\pi])\rightarrow[0,2\pi)$ with
$\mu(\theta+\pi)=\mu(\theta)+\pi$, for all $\theta\in[0,\pi)$. Such a
distortion would result in a robot’s local coordinate system deviating
slightly from any rigid transformation of an unknown global coordinate system,
yet still permit consistent orientation with respect to neighbours.

###  2.4 Problems and solutions

Since robots can only observe the positions of others and move, in the
${\mathcal{O}BLOT}$ model a problem to be solved (or, a task to be performed)
is expressed in terms of a temporal geometric predicate, which the
configurations formed by the robots’ positions from some time on must satisfy.

The Point Convergence problem requires the robots, starting from an arbitrary
connected configuration 777It is possible to define Convergence in a
meaningful way that applies to unconnected initial configurations as well. We
will discuss this further in Section 6. where they are all inactive, to become
arbitrarily close. More precisely, Point Convergence is the problem defined by
the temporal geometric predicate:

${\tt Convergence}\equiv\forall\varepsilon\in{\mathbb{R}}^{+},\exists
t:\forall t^{\prime}\geq
t,\forall\mathbb{X},\mathbb{Y}\in\mathcal{R},|X(t^{\prime})Y(t^{\prime})|\leq\varepsilon\,.$

A more constrained version is the the Cohesive Convergence problem that
additionally requires that, if two robots initially are within the visibility
region of each other, they remain so at all times; i.e. it is defined by the
temporal geometric predicate:

${\tt CohesiveConvergence}\equiv{\tt Convergence}\wedge(\forall t\geq
0,E(0)\subseteq E(t))\,.$

Note that even though Cohesive Convergence is strictly more constrained than
Point Convergence: all known algorithms for Point Convergence also solve
Cohesive Convergence.

An algorithm ${\mathcal{A}}$ is said to solve the Point Convergence (or
Cohesive Convergence) problem if it satisfies the corresponding predicate,
starting from _any_ valid initial configuration of robots, under _any_
(possibly adversarial) scheduler that respects the associated synchronization
model. If every Move is chosen in such a way that it cannot transform a static
connected configuration into a disconnected configuration, the algorithm is
said to be _coherent_.

##  3 A new algorithm for convergence

We begin this section with a review of the algorithms of [2] and [25],
emphasizing the features common to our algorithm, and features on which our
algorithm differs. This is followed by a detailed overview of our new
approach.

###  3.1 The convergence algorithms of Ando et al. and Katreniak.

The algorithm of Ando et al. [2] is the following: upon activation, each robot
$\mathbb{X}$

  * •

locates, within its local coordinate system, all of the other robots within
its visibility range;

  * •

computes a _safe region_ for motion with respect to each of its neighbours,
and

  * •

computes the center of a minimum enclosing ball of all the robots within its
visibility range, and moves as far as possible towards this center while
remaining inside all of the individual safe regions.

The algorithm of Ando et al. is formulated in the SSync scheduling model. It
assumes:

  * •

robots are points that execute their full planned motions instantaneously,
i.e. rigid collision-free motion;888The assumption of rigid motion, though
standard at the time of [2], could be relaxed without impacting the
correctness of the algorithm.

  * •

knowledge of the common visibility radius $V$ is built into the
algorithm;999Again, this assumption is stronger than necessary: it would
suffice to replace $V$ by the distance to the furthest visible neighbour.

  * •

there is no error in perception or in the realization of planned motion.

The algorithm of Katreniak [25] has many similarities to that of [2]: upon
activation, each robot $\mathbb{X}$

  * •

locates, within its local coordinate system, all of the other robots within
its visibility range,

  * •

computes a _safe region_ for motion with respect to each of its neighbours,
and

  * •

moves as far as possible while remaining inside a composite safe region that
respects all of the individual safe regions.

Katreniak’s algorithm is formulated in the $1$-Async model. It assumes:

  * •

knowledge of a common visibility radius $V$ is not assumed; instead each robot
$\mathbb{Z}$ works with a (changing) lower bound $V_{\mathbb{Z}}$ determined
by the distance to its furthest visible neighbour;

  * •

there is no error in perception;

  * •

the planned motion might not be fully realized, subject to a natural progress
condition, that ensures eventual convergence.

The most apparent difference between the algorithms of Ando et al. and
Katreniak lies in the specification of their safe regions. For a robot
$\mathbb{Y}$ located at $Y_{0}$ viewing a robot $\mathbb{X}$ located at
$X_{0}$, Ando et al. specify a safe region as a disk with radius $V/2$ centred
at the midpoint between $X_{0}$ and $Y_{0}$. Katreniak’s safe region is formed
by the union of two disks, one with radius $|X_{0}Y_{0}|/4$ centred at the
point $(X_{0}+3Y_{0})/4$, and the other with radius
$(V_{\mathbb{Y}}-|X_{0}Y_{0}|)/4$ centred at $Y_{0}$ (see Figure 3).

Figure 3: Basic safe region for motion of robot $\mathbb{Y}$ at location
$Y_{0}$ (with respect to visible robot $\mathbb{X}$ at location $X_{0}$), as
specified by Ando et al. (grey), by Katreniak (blue), when $\mathbb{X}$ is a
distant neighbour of $\mathbb{Y}$ (left) and when it is a close neighbour
(center); basic safe region in our scheme (green), assuming $\mathbb{X}$ is a
distant neighbour of $\mathbb{Y}$ (right).

The correctness of the convergence algorithms in both [2] and [25] rest on two
observations: (i)  _(initial) visibility preservation_ : the choice of safe
region guarantees that all robot pairs that are mutually visible in the
initial configuration will remain mutually visible thereafter, and (ii)
_incremental congregation_ : the trajectories of robots following the
algorithm exhibit a notion of “progress” towards convergence (measured in
terms of the shrinking of the convex hull of the robot locations). In both
cases, the argument is complicated by the need to demonstrate that the limit
of convergence is a single point.

Figure 4: An example where the (unmodified) Ando algorithm leads to separation
in the (a) 1-Async model and (b) 2-NestA model. The example consists of five
robots: $\mathbb{A}$, $\mathbb{B}$, and $\mathbb{C}$ being stationary through
the example (the scheduler does not activate these robots); and $\mathbb{X}$
and $\mathbb{Y}$ being activated according to the two activation timelines on
the bottom. Horizontal axis represents the time, grey arrows designate the
snapshots, and the corresponding positions of the robots $\mathbb{X}$ and
$\mathbb{Y}$ are also shown in grey. The red circle, centered at $X_{2}$, is
the smallest enclosing circle of the points $X_{0}$, $Y_{0}$, $B$, and $C$.
The black circle is centered at $X_{2}$ and has radius $V$. In both cases,
robot $\mathbb{X}$ moves from location $X_{0}$ to location $X_{2}$, and robot
$\mathbb{Y}$ moves from $Y_{0}$ to $Y_{1}$, leading to the distance between
the two robots being strictly greater than $V$.

Note that, even when $k=1$, both the $k$-NestA and the $k$-Async models
provide modest generalizations of the SSync model. Specifically, by
definition, any algorithm that guarantees convergence in the $1$-NestA (or
$1$-Async) model will do the same in the SSync model. However,

  1. (i)

In general, Ando’s algorithm (unmodified) does not succeed in the $1$-Async
model, even if it is able to assume that moves are rigid and instantaneous (so
the scheduler cannot pause or stop robots at intermediate points in their
planned trajectory);101010Note that Katreniak makes a similar observation,
using an example that exploits non-rigid motion. see Figure 4 (a);

  2. (ii)

The same construction, with a slightly modified timeline (Figure 4 (b)), shows
that Ando’s algorithm (unmodified) does not succeed in the $2$-NestA model;

  3. (iii)

It is also not difficult to show that Katreniak’s algorithm (unmodified) does
not succeed in the $k$-Async scheduling model, when $k$ is sufficiently large.

###  3.2 Overview of our algorithm.

In our algorithm, as in earlier schemes, each robot $\mathbb{Y}$ starts an
active interval by locating, within its local coordinate system, all of the
other robots within its visibility range, referred to as _neighbours_. It is
not assumed that the visibility radius $V$ is known. Instead, in each active
interval, robot $\mathbb{Y}$ computes a (tentative) lower bound
$V_{\mathbb{Y}}$ on $V$, provided by the distance to its current furthest
neighbour. Neighbours whose distance is greater than $V_{\mathbb{Y}}/2$ are
referred to as _distant_ neighbours of $\mathbb{Y}$; others are _close_
neighbours. Note that close and distant are relative and robot-specific
notions; in particular, $\mathbb{Y}$, by definition, always has at least one
distant neighbour. Furthermore, $\mathbb{X}$ could be a close neighbour of
$\mathbb{Y}$ while $\mathbb{Y}$ is a distant neighbour of $\mathbb{X}$.

Robot $\mathbb{Y}$ continues by determining a safe region for motion with
respect to each of its neighbours $\mathbb{X}$. Safe regions are designed to
ensure that, despite the fact that $V$ is unknown, the connectivity of the
initial robot configuration will not be lost; in particular, if robots
$\mathbb{X}$ and $\mathbb{Y}$ are mutually visible in their initial
configuration (i.e. $|X(0)Y(0)|\leq V$), when both are assumed to be immotile
then, provided both robots continue to confine their movement to the safe
regions for motion with respect to the other, their mutual visibility will be
maintained thereafter. Even though acquired visibility might be subsequently
lost, unlike the schemes of [2] and [25], a form of acquired visibility
preservation can be shown to hold, which suffices to ensure that there is a
point in time after which if robots $\mathbb{X}$ and $\mathbb{Y}$ are even
momentarily not mutually visible, then $\mathbb{X}$ and $\mathbb{Y}$ remain
separated by distance at least $V/4$. The specification of safe regions,
together with their properties that are exploited in subsequent visibility
preservation and congregation arguments, is provided in the next subsection;
the details of our visibility preservation arguments in models with bounded
asynchrony, are developed in Section 4.

Finally, $\mathbb{Y}$ plans a motion to a target destination contained within
the intersection of the safe regions associated with all of its neighbours.
The target destination in turn is designed to ensure that the convex hull of
the robot locations shrinks monotonically, and converges to a point. The
specification of the target destination, together with details of this
congregation argument, are presented in Section 5.

####  3.2.1 Safe regions: specification and properties.

The _basic safe region_ for motion of robot $\mathbb{Y}$, located at $Y_{0}$,
with respect to a distant neighbour $\mathbb{X}$ at location $X_{0}$, denoted
$S^{V_{\mathbb{Y}}/8}_{Y_{0}}(X_{0})$, is a disk, with radius
$V_{\mathbb{Y}}/8$, centered at the point at distance $V_{\mathbb{Y}}/8$ from
$Y_{0}$ in the direction of $X_{0}$ (cf. Figure 3).

Note that (i) in order to respect the basic safe region of any distant
neighbour, of which there must be at least one, a robot can plan a motion of
length at most $V_{\mathbb{Y}}/4$. (In fact, as will become clear, when the
actual destination point, respecting the safe regions of all visible
neighbours, is specified, a robot will never plan a motion of length greater
than $V/8$.) Hence, the planned motions of close neighbours cannot possibly
lead directly to a separation exceeding $V$, (ii) unlike the algorithms in [2]
and [25], our basic safe regions, defined for distant neighbours only, depend
only on the direction of that neighbour, and (iii) if a robot $\mathbb{X}$ is
located in the convex hull of its distant neighbours then the intersection of
the safe regions with respect to the distant neighbours contains its current
location only, so to respect all of these safe regions it must remain
stationary.111111It is worth noting that the choice of $V_{\mathbb{Y}}/2$ as
the definition of “close” is somewhat arbitrary. Similarly, the size of the
safe region associated with distant neighbours has been chosen to have radius
$V_{\mathbb{Y}}/8$ mostly for convenience. Anything less than this would
certainly work as long as it is at least some positive constant. (Furthermore,
choosing a smaller radius would allow us to choose a larger radius for
“close”). In the $1$-NestA and $1$-Async models robots are constrained to
choose a target location that lies within the basic safe region with respect
to each of their neighbours. In the $k$-NestA and $k$-Async models, with
$k>1$, the only change is to simply scale the basic safe regions by a factor
of $\alpha=1/k$. Thus for all $k$, robot $\mathbb{Y}$ is constrained to choose
a target location that lies within the $\alpha$-scaled safe region with
respect to each distant neighbour robot $\mathbb{X}$, denoted
$S_{Y_{0}}^{\alpha V_{\mathbb{Y}}/8}(X_{0})$, which is the disk, with radius
$\alpha V_{\mathbb{Y}}/8$, centered at the point at distance $\alpha
V_{\mathbb{Y}}/8$ from $Y_{0}$ in the direction of $X_{0}$. It is
straightforward to confirm that if point $P$ lies within the basic safe region
$S^{V_{\mathbb{Y}}/8}_{Y_{0}}(X_{0})$, then the point $P^{\alpha}$ at distance
$\alpha|PY_{0}|$ from $Y_{0}$ in the direction of $P$, lies in
$S_{Y_{0}}^{\alpha V_{\mathbb{Y}}/8}(X_{0})$.

The prospect of one robot, $\mathbb{Y}$, at location $Y_{0}$, making up to $k$
successive moves while another distant neighbour, $\mathbb{X}$, is in the
process of moving from location $X_{0}$ to location $X_{1}$, invites the
question: how can we characterize the set of points that can be reached by
robot $\mathbb{Y}$ in this situation, provided that each of its moves is
confined to the current $1/k$-scaled safe region with respect to the current
location of $\mathbb{X}$? As it happens the exact description of this set is
somewhat complicated, but a more simply described superset suffices for our
purposes.

Figure 5: Region $R^{r}_{Y_{0}}(X_{0},X_{1})$ consisting core (blue) and bulge
(green) subregions.

We define the region $R^{r}_{Y_{0}}(X_{0},X_{1})$ (see Figure 5) as the union
of

  1. (i)

its _core_ : the set of disks of radius $r$ whose centers lie at distance $r$
from $Y_{0}$ in the direction of some point on the line segment
$\overline{X_{0}X_{1}}$; and

  2. (ii)

its _bulge_ : the intersection of (a) the set of points at distance at most
$|X_{1}Y_{0}^{+}|$ from $X_{1}$, and at most $|Y_{0}Y_{0}^{+}|$ from $Y_{0}$,
where $Y_{0}^{+}$ is the point on the disk centered at distance $r$ from
$Y_{0}$ in the direction of $X_{0}$ that has maximum distance from $X_{1}$;
and (b) the set of points at distance at most $|X_{0}Y_{0}^{-}|$ from $X_{0}$,
and at most $|Y_{0}Y_{0}^{-}|$ from $Y_{0}$, where $Y_{0}^{-}$ is the point on
the disk centered at distance $r$ from $Y_{0}$ in the direction of $X_{1}$
that has maximum distance from $X_{0}$.

We begin by making the following observations that follow directly from the
definitions above:

######  Observation 1.

  1. (i)

$R^{V_{\mathbb{Y}}/8}_{Y_{0}}(X_{0},X_{0})$ coincides with
$S^{V_{\mathbb{Y}}/8}_{Y_{0}}(X_{0})$ and, more generally, for any
$\alpha\in(0,1]$,
$R^{\alpha V_{\mathbb{Y}}/8}_{Y_{0}}(X_{0},X_{0})$ coincides with $S^{\alpha
V_{\mathbb{Y}}/8}_{Y_{0}}(X_{0})$; and

  2. (ii)

the core of $R^{V_{\mathbb{Y}}/8}_{Y_{0}}(X_{0},X_{1})$ coincides with the
union of $S^{V_{\mathbb{Y}}/8}_{Y_{0}}(X_{*})$, over all
$X_{*}\in\overline{X_{0}X_{1}}$, and, more generally, for any
$\alpha\in(0,1]$, the core of $R^{\alpha
V_{\mathbb{Y}}/8}_{Y_{0}}(X_{0},X_{1})$ coincides with the union of $S^{\alpha
V_{\mathbb{Y}}/8}_{Y_{0}}(X_{*})$, over all $X_{*}\in\overline{X_{0}X_{1}}$.

Observation _(i)_ establishes the basis of a proof, by induction on $j$, of
the following:

######  Lemma 3.1.

$R^{jV_{\mathbb{Y}}/(8k)}_{Y_{0}}(X_{0},X_{0})$ contains the set of all points
that can be reached by robot $\mathbb{Y}$ at location $Y_{0}$, making $j\leq
k$ successive moves while another distant neighbour, $\mathbb{X}$, remains
stationary at location $X_{0}$, provided that each move of $\mathbb{Y}$ is
confined to the current $1/k$-scaled safe region with respect to the location
of $\mathbb{X}$.

######  Proof 3.2.

For the inductive step, we note that if $|X_{0}Y_{0}|\geq 2r_{1}$ and
$r_{1}\geq r_{2}$, then $R^{r_{1}+r_{2}}_{Y_{0}}(X_{0},X_{0})$ contains the
union of $S^{r_{2}}_{Y_{*}}(X_{0})$ over all $Y_{*}\in
R^{r_{1}}_{Y_{0}}(X_{0},X_{0})$. This follows from a simple geometric
observation captured in Figure 6. Suppose that point $P$ lies in
$R^{r_{1}}_{B}(A,A)$. Then the safe region $S^{r_{2}}_{P}(A)$ coincides with
the safe region $S^{r_{2}}_{\widehat{P}}(A_{\infty})$, where $\widehat{P}$
denotes the point on $S^{r_{2}}_{P}(A)$ that is extreme in the direction
$\overrightarrow{AB}$, and $A_{\infty}$ denotes the point at infinity in the
direction $\overrightarrow{BA}$ (see Figure 6.left). Assuming $|AB|\geq
2r_{1}$, $\angle(A,P,B^{\prime})<\angle(A,P,\widehat{P})<\angle(A,P,B)$. It
follows that $\widehat{P}\in R^{r_{1}}_{A}(B,B)$. But the union of
$S^{r_{2}}_{\widehat{P}}(A_{\infty})$, over all points $\widehat{P}\in
R^{r_{1}}_{A}(B,B)$ is exactly $R^{r_{1}+r_{2}}_{B}(A,A)$ (see Figure
6.right).

Figure 6: Circle expansion lemma.

Observation _(ii)_ establishes the basis of a proof, by induction on $j$, of
the following more general lemma:

######  Lemma 3.3 (Base region extension).

$R^{jV_{\mathbb{Y}}/(8k)}_{Y_{0}}(X_{0},X_{1})$ contains the set of all points
that can be reached by robot $\mathbb{Y}$ at location $Y_{0}$, making $j\leq
k$ successive moves while another distant neighbour, $\mathbb{X}$, is in the
process of moving from location $X_{0}$ to location $X_{1}$, provided that
each move of $\mathbb{Y}$ is confined to the current $1/k$-scaled safe region
with respect to the current location of $\mathbb{X}$.

######  Proof 3.4.

For the induction step, we prove that for any $\alpha\in(0,1]$, $R^{r+\alpha
V_{\mathbb{Y}}/8}_{Y_{0}}(X_{0},X_{1})$ contains the union of $S^{\alpha
V_{\bf Y}/8}_{Y_{*}}(X_{*})$ over all $X_{*}\in\overline{X_{0}X_{1}}$ and
$Y_{*}\in R^{r}_{Y_{0}}(X_{0},X_{1})$. The argument here is treated in five
cases (see Figures 9, 9, and 9, where $R^{r}_{Y_{0}}(X_{0},X_{1})$ is depicted
in blue, $R^{r+\alpha V_{\mathbb{Y}}/8}_{Y_{0}}(X_{0},X_{1})$ is depicted in
red, and the small red circle depicts an extremal safe region associated with
a point in $R^{r}_{Y_{0}}(X_{0},X_{1})$. It is essentially the same as the
argument used in Lemma 3.1 above; in all cases, a safe region $S^{\alpha
V_{\bf Y}/8}_{Y_{*}}(X_{*})$, where $X_{*}\in\overline{X_{0}X_{1}}$ and
$Y_{*}\in R^{r}_{Y_{0}}(X_{0},X_{1})$, coincides with a safe region $S^{\alpha
V_{\bf Y}/8}_{\widehat{Y}}(\widehat{X})$, in the extremal form illustrated,
where $\widehat{Y}\in R^{r}_{Y_{0}}(X_{0},X_{1})$. Since the safe regions in
the extreme form illustrated all lie inside $R^{r+\alpha
V_{\mathbb{Y}}/8}_{Y_{0}}(X_{0},X_{1})$, the result follows.

Figure 7: Base region extension Lemma (cases A and D).

Figure 8: Base region extension Lemma (cases B and E).

Figure 9: Base region extension Lemma (case C).

##  4 Visibility preservation by our algorithm, under bounded asynchrony

In this section we begin the analysis of our algorithm by demonstrating the
fact that it guarantees that the connectivity of the initial robot
configuration is preserved in both the $k$-NestA and $k$-Async scheduling
models. This is established by showing that all pairs of robots that are
mutually visible in the initial configuration remain so. In addition, we also
demonstrate a limited form of preservation of acquired visibility (mutual
visibility of robot pairs that arises in subsequent configurations), critical
to our congregation argument.

###  4.1 Visibility preservation in the _k_ -NestA model

Though superficially similar, there is an important difference between the
SSync and $1$-NestA models: in the latter, if an active interval of robot
$\mathbb{Y}$ is nested within an active interval of robot $\mathbb{X}$, it is
possible that the Look phase of $\mathbb{Y}$ takes place after the Move phase
of $\mathbb{X}$ has begun. In this situation, even if we assume that
$\mathbb{Y}$ was seen by $\mathbb{X}$ when it last looked, $\mathbb{X}$ could
be viewed by $\mathbb{Y}$ anywhere on its chosen trajectory.

For the $k$-NestA model, with $k>1$, demonstrating that mutual visibility of a
pair $\mathbb{X},\mathbb{Y}$ of robots is preserved, is further complicated by
the fact that repeated activations of $\mathbb{Y}$, nested within one
activation of $\mathbb{X}$, may view $\mathbb{X}$ at many different positions
on its determined trajectory, and even if $\mathbb{X}$ is stationary
$\mathbb{Y}$ may view it from up to $k$ different locations. In fact, (i) as
illustrated by the bulge region, $k$ nested activations of $\mathbb{Y}$, each
moving within its $1/k$-scaled safe region with respect to $\mathbb{X}$, while
preserving mutual visibility, can take $\mathbb{Y}$ outside of its basic
(unscaled) safe region, and (ii) $k$ nested activations of $\mathbb{Y}$, each
moving within even slightly larger safe regions could lead to a break in
visibility.

In asynchronous settings, it is certainly possible that a pair of robots under
the control of our algorithm could become temporarily mutually visible, and
then such a visibility may become subsequently lost. However, a critical
component of our congregation argument relies on the fact that, if the
separation of a robot pair becomes sufficiently small, visibility will be
preserved indefinitely. We say that robot $\mathbb{X}$ is _strongly visible_
from robot $\mathbb{Y}$ at time $t$ if $|X(t)Y(t)|\leq V/2$.

With this definition in hand we can state and prove what we need in terms of
visibility preservation for the $k$-NestA scheduling model:

######  Theorem 4.1.

Provided robots $\mathbb{X}$ and $\mathbb{Y}$ both continue to confine their
movement to the $1/k$-scaled safe regions for motion with respect to the
other, then if (i) $\mathbb{X}$ is visible from $\mathbb{Y}$ at time $t=0$
(i.e. $|X(0)Y(0)|\leq V$), or (ii) $\mathbb{X}$ becomes strongly visible from
$\mathbb{Y}$ at some subsequent time $t>0$, then their mutual visibility will
be maintained thereafter, under arbitrary $k$-NestA scheduling.

The proof of the two cases in this theorem is developed in the following two
subsections.

####  4.1.1 Preservation of initial visibilities

We begin with the preservation of initial visibilities. Specifically, in the
following we prove that any pair of robots $\mathbb{X}$ and $\mathbb{Y}$,
satisfying $|X(0)Y(0)|\leq V$, also satisfies $|X(t)Y(t)|\leq V$, for all
$t\geq 0$.

######  Proof 4.2.

Recall that, in the $k$-NestA model, the schedule of activations of any pair
of robots $\mathbb{X}$ and $\mathbb{Y}$ decomposes into a sequence activation
events which consist of a single activation interval of one of the two robots
within which are nested up to $k$ activation intervals of the other. Hence, it
will suffice to prove that (i) if $\mathbb{X}$ and $\mathbb{Y}$ are mutually
visible at the start of any such activation event then they remain mutually
visible throughout the event, and (ii) if one of the robots becomes strongly
visible from the other during the course of the activation event then they
will remain mutually visible thereafter. In fact, since the diameter of all
$1/k$-scaled safe regions is at most $V/(4k)$, the total length of moves of
$\mathbb{X}$ and $\mathbb{Y}$ in any activation event is at most $V/2$, and
thus one robot can become strongly visible from the other during the course of
the activation event only if they are mutually visible at both the start and
end. Hence, it suffices to prove property (i) alone, knowing that at no
intermediate point one of the robots becomes strongly visible from the other.

Suppose that an activation event begins with the pair of robots $\mathbb{X}$
and $\mathbb{Y}$ at locations $X_{0}$ and $Y_{0}$ respectively, with
separation at most $V$. Suppose further that this activation event consists of
a single active interval of robot $\mathbb{X}$ and some $j\leq k$ active
intervals of robot $\mathbb{Y}$ all of which are nested within the active
interval of $\mathbb{X}$ (in particular, at both the start and end of the
active interval of $\mathbb{X}$, both $\mathbb{X}$ and $\mathbb{Y}$ are
immotile). Finally, suppose that (i) the active interval of robot $\mathbb{X}$
determines a target destination $X_{1}$ that is confined to the $1/k$-scaled
safe region $S_{X_{0}}^{V_{\mathbb{X}}/(8k)}(Y_{0})$, and (ii) the $i$-th
active intervals of robot $\mathbb{Y}$ determines a target destination $Y_{i}$
that is confined to the $1/k$-scaled safe region
$S_{Y_{i-1}}^{V_{\mathbb{Y}}/(8k)}(X_{*})$ for some
$X_{*}\in\overline{X_{0}X_{1}}$ (recall that relocation to every point within
a safe region may not be realizable in practice, since moves are ultimately
dependent on the locations of one or more neighbouring robots).

Now suppose, leading to a contradiction, that at the end of the active
interval of robot $\mathbb{X}$, robots $\mathbb{X}$ and $\mathbb{Y}$ are no
longer mutually visible. In this case, we can assume that we are dealing with
a counterexample with minimum $j$. By definition, $\mathbb{Y}$, at location
$Y_{0}$, is visible from $\mathbb{X}$ at the start of its interval.
Furthermore, at the start of its first nested active interval, $\mathbb{Y}$,
still at location $Y_{0}$, must view $\mathbb{X}$ at some location $X_{*}$ on
its trajectory towards $X_{1}$. Since $S_{X_{0}}^{V_{\mathbb{X}}/(8k)}(Y_{0})$
is entirely contained in the disk of radius $V$ centered at $Y_{0}$, the point
$X_{*}$ is visible from robot $\mathbb{Y}$ at this point in time. To establish
the preservation of mutual visibility, we need to show that $\mathbb{X}$
remains visible to $\mathbb{Y}$ at the time $\mathbb{Y}$ ends each of its
successive nested active intervals. Of course, by the minimality of our
supposed counterexample, we can assume that $\mathbb{X}$ remains visible to
$\mathbb{Y}$ at the time $\mathbb{Y}$ ends each of its first $j-1$ nested
active intervals.

But we have already established, in Lemma 3.1, that the set of points
reachable by $\mathbb{Y}$ starting at $Y_{0}$ making $j$ successive moves each
of which is confined to an $1/k$-scaled safe region with respect to some
(possibly changing) location of $\mathbb{Y}$ within the segment
$\overline{X_{0}X_{1}}$, is contained in $R^{jV/(8k)}_{Y_{0}}(X_{0},X_{1})$.
Given this, it is straightforward to confirm that the distance from $X_{1}$ to
$Y_{j}$ is at most $|X_{1}Y_{0}^{+}|$, which is at most $|X_{0}Y_{0}|$. Hence
$\mathbb{X}$ remains visible to $\mathbb{Y}$ at the end of its $j$-th active
interval.

####  4.1.2 Preservation of acquired visibilities

To complete the proof of Theorem 4.1 it remains to argue that if robot
$\mathbb{X}$ becomes strongly visible from $\mathbb{Y}$ at some time $t>0$,
then their mutual visibility will be maintained thereafter, under arbitrary
$k$-NestA scheduling.

######  Proof 4.3.

We have already established that if a pair of robots $\mathbb{X}$ and
$\mathbb{Y}$ are mutually visible at the start of an active interval for
$\mathbb{X}$ that contains up to $k$ nested active intervals for $\mathbb{Y}$,
then they remain mutually visible up to the end of the active interval for
$\mathbb{X}$. So if $\mathbb{X}$ and $\mathbb{Y}$ have their visibility broken
at some point it must be that they had a separation greater than $V$ at the
start of the active interval for $\mathbb{X}$. But since both $\mathbb{X}$ and
$\mathbb{Y}$ move a distance at most $V/4$ over the duration of this active
interval, it follows that their separation never falls below $V/2$. Hence, if
the separation of $\mathbb{X}$ and $\mathbb{Y}$ ever falls below $V/2$ in this
interval it must be that $\mathbb{X}$ and $\mathbb{Y}$ are mutually visible at
the end, and thereafter.

###  4.2 Visibility preservation in the _k_ -Async model

Turning now to the more inclusive $k$-Async scheduling model, we establish the
following generalization of Theorem 4.1, exploiting the structure common to
the $k$-NestA and $k$-Async models.

######  Theorem 4.4.

Provided robots $\mathbb{X}$ and $\mathbb{Y}$ both continue to confine their
movement to the $1/k$-scaled safe regions for motion with respect to the
other, then if (i) $\mathbb{X}$ is visible from $\mathbb{Y}$ at time $t=0$
(i.e. $|X(0)Y(0)|\leq V$), or (ii) $\mathbb{X}$ becomes strongly visible from
$\mathbb{Y}$ at some subsequent time $t>0$, then their mutual visibility will
be maintained thereafter, under arbitrary $k$-Async scheduling.

As in our proof of Theorem 4.1, we treat the preservation of initial
visibilities and acquired visibilities separately. In each of these cases, we
begin by treating the case $k=1$, which captures many of the most important
features of the general argument. Treatment of the case where $k>1$, which
builds on this simpler case, and exploits many of the same ideas that arose in
Theorem 4.1, will follow.

####  4.2.1 Preservation of initial visibilities

Suppose that robots $\mathbb{X}$ and $\mathbb{Y}$ have separation at most $V$
in their initial configuration (when both are immotile). We need to show that,
from this point onward, provided $\mathbb{Y}$ moves to a point within the safe
region with respect to the observed position of $\mathbb{X}$, the visibility
of $\mathbb{X}$ will not be lost, no matter how $\mathbb{X}$ chose to move,
_based on its observed position of $\mathbb{Y}$_. Note, the argument here
seems to be intrinsically more difficult than that used in the $1$-NestA
model. In particular, it does not suffice, as it did in the $k$-NestA model,
to focus attention on just one active interval for one of the two robots whose
mutual visibility is being considered. In the $1$-Async model, the validity of
each step depends on the full history of transitions since the last time both
robots were simultaneously immotile.

1-Async Case.
We say that a pair of robots $\mathbb{X}$ and $\mathbb{Y}$ is engaged at time
$t$ if at least one of them is active. Suppose that $\mathbb{X}$ and
$\mathbb{Y}$ become engaged at time $t_{0}$, with $|X(t_{0})Y(t_{0})|\leq V$.
We proceed to show that while $\mathbb{X}$ and $\mathbb{Y}$ remain engaged
their separation remains at most $V$. Suppose, leading ultimately to a
contradiction, that

  1. 1.

at time $t_{0}$, $\mathbb{X}$ is starting an active interval and $\mathbb{Y}$
is immotile, i.e. either idle or starting an active interval,

  2. 2.

each subsequent move of $\mathbb{X}$ and $\mathbb{Y}$, the timing and extent
of which is determined by an adversarial scheduler, has a target destination
that respects the safe regions of $\mathbb{X}$ and $\mathbb{Y}$ alone (and
hence may form a strict superset of the realizable destinations when other
robots are taken into consideration); and

  3. 3.

at some subsequent time $t_{*}$, during the $i$-th active interval of
$\mathbb{X}$ and after the start of the $h$-th active interval, and before the
start of the $(h+1)$-th active interval, of $\mathbb{Y}$, and prior to which
$\mathbb{X}$ and $\mathbb{Y}$ remain engaged, $\mathbb{X}$ and $\mathbb{Y}$
reach positions $X(t_{*})$ and $Y(t_{*})$ whose separation is greater than
$V$.

If the schedules of $\mathbb{X}$ and $\mathbb{Y}$ are truncated at time
$t_{*}$, we refer to the interval $[t_{0},t_{*}]$ as a doomed engagement of
$\mathbb{X}$ and $\mathbb{Y}$. There is, of course, no loss of generality in
assuming that both $\mathbb{X}$ and $\mathbb{Y}$ are active just prior to time
$t_{*}$. We will assume that the doomed engagement under consideration
minimizes $i+h$. For $a\geq 1$, we define $X_{a}$ (respectively, $Y_{a}$) to
be the position of robot $\mathbb{X}$ (respectively $\mathbb{Y}$) at the end
of its $a$-th active interval starting at or after time $t_{0}$. For
convenience in subsequent definitions, we denote $X(t_{0})$ (respectively
$Y(t_{0})$) by $X_{0}$ (respectively $Y_{0}$), and imagine that $\mathbb{Y}$
has a $0$-th active interval intersecting $t_{0}$ during which it is
stationary (and accordingly define $Y_{-1}=Y_{0}$).

We first note that, by minimality,

  1. 1.

During the doomed engagement, the $\mathbb{X}$ and $\mathbb{Y}$ active
intervals interleave, i.e. (i) for all $1\leq j\leq i$, the $j$-th activation
interval of $\mathbb{Y}$ starts during the $j$-th active interval of
$\mathbb{X}$, and (ii) for all $1<j\leq i$, the $j$-th active interval of
$\mathbb{X}$ starts during the $(j-1)$-st active interval of $\mathbb{Y}$ (see
Figure 10). Minimality dictates that the active intervals overlap, and by our
$1$-NestA analysis they cannot nest.

Figure 10: Without loss of generality, active intervals for $\mathbb{X}$ and
$\mathbb{Y}$ interleave, up to disconnection.

  2. 2.

The doomed engagement ends at the end of the $i$-th activation of both
$\mathbb{X}$ and $\mathbb{Y}$); when $\mathbb{X}$ is at location $X_{i}$ and
$\mathbb{Y}$ is at location $Y_{i}$ (the case where the doomed engagement ends
at the end of the $i+1$-st activation of $\mathbb{X}$ and the $i$-th
activation of $\mathbb{Y}$ is handled identically, with only a trivial change
in indexing).

  3. 3.

For all $0\leq j\leq i$, the separation between $X_{j}$ and $Y_{j-1}$, as well
as that between $Y_{j-1}$ and $X_{j-1}$, is at most $V$.

  4. 4.

For all $1\leq j<i$, the point $Y_{j+1}$ lies in the basic safe region
$S^{V_{\mathbb{Y}}/8}_{Y_{j}}(X_{*})$ associated with $\mathbb{Y}$ at location
$Y_{j}$, viewing $\mathbb{X}$ at some location $X_{*}$ between $X_{j}$ and
$X_{j+1}$. Similarly, the point $X_{j+1}$ lies in the basic safe region
$S^{V_{\mathbb{X}}/8}_{X_{j}}(Y_{*})$ associated with $\mathbb{X}$ at location
$X_{j}$, viewing $\mathbb{Y}$ at some location $Y_{*}$ between $Y_{j-1}$ and
$Y_{j}$. We refer to these as the _safety constraints_ for points $Y_{j}$ and
$X_{j}$, respectively.

We will analyze the chain of edges

$\overline{Y_{i}X_{i}},\;\overline{X_{i}Y_{i-1}},\;\overline{Y_{i-1}X_{i-1}},\;\overline{X_{i-1}Y_{i-2}},\ldots,\overline{X_{2}Y_{1}},\;\overline{Y_{1}X_{1}},\;\overline{X_{1}Y_{0}},\;\overline{Y_{0}X_{0}},\;\overline{X_{0}Y_{-1}}$

associated with a minimal doomed engagement for $\mathbb{X}$ and $\mathbb{Y}$,
essentially a walk from their terminal configuration back to their initial
configuration, ultimately showing that no such chain exists that satisfies all
of the specified constraints, thereby demonstrating our contradiction.

For $t\geq 0$, let $e_{t}$ denote the $t$-th edge on this chain; i.e.,
$e_{t}=\overline{Y_{i-t/2}X_{i-t/2}}$, for even $t$, and
$e_{t}=\overline{X_{i-(t-1)/2}Y_{i-1-(t-1)/2}}$, for odd $t$, and $\theta_{t}$
— the (clockwise) angle, in the range $(-\pi,\pi]$ between $e_{t+1}$ and
$e_{t}$. Note that $\theta_{2i}=0$ but, by our minimality assumption,
$\theta_{t}\neq 0$, for $0<t<2i$. The minimality assumption implies other
structural constraints as well:

  1. 1.

Observe that, in order for the distance between $Y_{i}$ and $X_{i}$ to be at
least $V$, it must be the case that $\theta_{0}\neq 0$ (otherwise, by
minimality of our example, $Y_{i}$ must lie on the line through $X_{i}$ and
$Y_{i-1}$ but outside the segment $\overline{X_{i}Y_{i-1}}$, and so outside of
the safe region $S^{V_{\mathbb{Y}}/8}_{Y_{i-1}}(X_{*})$ the safe region for
$\mathbb{Y}$ at location $Y_{i-1}$ viewing $\mathbb{X}$ at any location
$X_{*}$ on the segment $\overline{X_{i-1}X_{i}}$). Thus, in particular, $i$
must be greater than $1$;

  2. 2.

Next, note that, for all $0<j<i$, $Y_{j+1}$ is _not_ within the safe region
for $\mathbb{Y}$ at location $Y_{j}$ viewing $\mathbb{X}$ at location
$X_{j+1}$ (and $X_{j+1}$ is _not_ within the safe region for $\mathbb{X}$ at
location $X_{j}$ viewing $\mathbb{Y}$ at location $Y_{j}$) (otherwise, our
minimal separating sequence could be shortened, by starting instead at
$X_{j+1}$ and $Y_{j}$, or $X_{j}$ and $Y_{j}$, a contradiction).

Figure 11: Illustration for the case when $\theta_{t}>0$ and $\theta_{t+1}<0$.
Region $S^{V_{\mathbb{Y}}/8}_{Y_{i-1-t/2}}(X^{\prime}_{i-1-t/2})$ (in green)
is the safe region of $\mathbb{Y}$ at location $Y_{i-1-t/2}$ when it sees
$\mathbb{X}$ at some point
$X^{\prime}_{i-1-t/2}\in\overline{X_{i-1-t/2}X_{i-t/2}}$. Region
$S^{V_{\mathbb{Y}}/8}_{Y_{i-1-t/2}}(X_{i-t/2})$ (in yellow) is the safe region
of $\mathbb{Y}$ at location $Y_{i-1-t/2}$ when it sees $\mathbb{X}$ at
$X_{i-t/2}$. As the striped region is fully contained in
$S^{V_{\mathbb{Y}}/8}_{Y_{i-1-t/2}}(X_{i-t/2})$, any location $Y_{i-t/2}$ that
is in $S^{V_{\mathbb{Y}}/8}_{Y_{i-1-t/2}}(X^{\prime}_{i-1-t/2})$ is also in
$S^{V_{\mathbb{Y}}/8}_{Y_{i-1-t/2}}(X_{i-t/2})$.

  3. 3.

It follows that we can assume that $\theta_{t}>0$, for $0<t<2i$. Certainly
this holds without loss of generality for $\theta_{0}$ (by replacing clockwise
angles with counterclockwise, if necessary). Moreover, if it holds for
$\theta_{t}$ then it must hold for $\theta_{t+1}$. Suppose, to the contrary,
that $\theta_{t}>0$ and $\theta_{t+1}<0$, when $t$ is even (see Figure 11);
the argument when $t$ is odd is essentially the same. Then, since $Y_{i-t/2}$
belongs to the safe region for $\mathbb{Y}$ at location $Y_{i-1-t/2}$ when it
sees $\mathbb{X}$ at some location on the segment
$\overline{X_{i-1-t/2}X_{i-t/2}}$, $Y_{i-t/2}$ must also belong to the safe
region for $\mathbb{Y}$ at location $Y_{i-1-t/2}$ when it sees $\mathbb{X}$ at
location $X_{i-t/2}$. (This follows because, restricted to points $Z$ for
which $\angle(Y_{i-1-t/2},X_{i-t/2},Z)>0$, the safe region for $\mathbb{Y}$ at
location $Y_{i-1-t/2}$ viewing $\mathbb{X}$ at any location on
$\overline{X_{i-1-t/2}X_{i-t/2}}$ is contained in the safe region for
$\mathbb{Y}$ at location $Y_{i-1-t/2}$ viewing $\mathbb{X}$ at location
$X_{i-t/2}$; This, contradicts our minimality assumption, as noted previously.

It is not hard to see that, in order to satisfy local safety constraints,
there is a kind of tradeoff between $|e_{t}|$ and $\theta_{t}$: specifically,
if $|e_{t}|$ is increased then the safety constraint at the common endpoint of
$e_{t}$ and $e_{t+1}$ can be satisfied with a smaller angle $\theta_{t}$. We
make this tradeoff explicit in the following:

######  Lemma 4.5.

$|e_{t}|>V\cos\theta_{t}$ and $\cos\theta_{t}\geq\sqrt{(2+\sqrt{3})/4}\approx
0.9659$, for all $t\geq 0$.

Note that since the chain ends with $\theta_{2i}=0$ (because $\mathbb{Y}$ is
stationary in its $0$-th active interval), it follows that the edge
$e_{2i}=\overline{X_{0}Y_{0}}$ has length greater than $V$, a contradiction
that completes the proof of Theorem 4.4 in the case $k=1$.

######  Proof 4.6.

The proof of Lemma 4.5 proceeds by induction on $t$.

Since $|e_{0}|$, the length of edge $\overline{X_{i}Y_{i}}$, is at least $V$,
it follows immediately that $|e_{0}|\geq V\cos\theta_{t}$. To complete the
basis of our induction, observe that in order to satisfy the safety constraint
at $Y_{i-1}$ it must be the case that $Y_{i-1}$ is no further than $V/4$ from
$Y_{i}$, and hence no further than $V/4$ from $e_{0}$. It follows that
$|e_{0}|\sin\theta_{0}\leq V/4$, and thus $\sin\theta_{0}\leq 1/4$, which
holds exactly when $\cos\theta_{0}\geq\sqrt{15/16}>\sqrt{(2+\sqrt{3})/4}.$

Suppose now that $|e_{t}|>V\cos\theta_{t}$ and
$\cos\theta_{t}\geq\sqrt{(2+\sqrt{3})/4}$. We will show that
$|e_{t+1}|>V\cos\theta_{t+1}$ and $\cos\theta_{t+1}\geq\sqrt{(2+\sqrt{3})/4}$.
For this induction step, consider four successive points on the chain (renamed
$S$, $R$, $Q$, and $P$, for simplicity and to reflect the commonality of the
argument for even and odd $t$), their associated edges $\overline{SR}$,
$\overline{RQ}$ and $\overline{QP}$, and their intervening angles (renamed
$\beta$ and $\varphi$) (see Figure 12). We show that assuming
$|SR|>V\cos\beta$ and $\cos\beta\geq\sqrt{(2+\sqrt{3})/4}$, then
$|RQ|>V\cos\varphi$ and $\cos\varphi\geq\sqrt{(2+\sqrt{3})/4}$.

Figure 12:  The point $M$ is at distance $V/2$ from $R$, and is the center of
the circle $c_{V/2}$ (in red). The safe region $S^{V/8}_{Q}(P)$ is shown in
green. The two circles must intersect for the conditions on point $S$ to hold.

First observe that motion from $P$ to $R$ and from $Q$ to $S$ are the result
of single move steps of the corresponding robots. As we shall see in Section
5, where we specify a robot’s destination as a function of the locations of
its visible neighbours, this means that $|PQ|$ and $|QS|$ are both at most
$V/8$. It follows then that both $|PQ|\geq|RS|-V/4>V/2$ and
$|RQ|\geq|RS|-V/8>V/2$; since $|RS|\geq\sqrt{(2+\sqrt{3})/4}$. In particular,
the robot at location $Q$ sees the robot at position $P$ as a distant
neighbour when planning its motion to location $S$.

Consider a circle $c_{V/2}$ of radius $V/2$ centered at a point $M$ lying on
the segment $\overline{RQ}$ at distance $V/2$ from $R$ (see Figure 12). Point
$S$ must be outside of $c_{V/2}$, otherwise $|SR|\leq V\cos\beta$ (due to the
angle $\angle RSQ^{\prime}\geq\pi/2$ where $Q^{\prime}$ is an intersection of
the extension of $\overline{RQ}$ with $c_{V/2}$); hence $|MS|>V/2$. Let $I$ be
the center of $S^{V/8}_{Q}(P)$, i.e., $I$ lies on $\overline{QP}$ at distance
$V/8$ from $Q$. Since point $S$ lies in $S^{V/8}_{Q}(P)$, $|IS|\leq V/8$ and
hence $|MI|\geq|MS|-|IS|>3V/8$.

Consider the triangle $\triangle QIM$. From the cosine theorem it follows that

$|MI|^{2}=|MQ|^{2}+|IQ|^{2}-2|MQ||IQ|\cos\varphi\,.$

Then, after dividing by $V^{2}$ and replacing $|MQ|/V$ by $x$, the equation
above becomes

$x^{2}-2x\frac{|IQ|}{V}\cos\varphi+\left(\frac{|IQ|}{V}\right)^{2}-\left(\frac{|MI|}{V}\right)^{2}=0\,.$

Since $x>0$, it follows that
$x=\frac{|IQ|}{V}\cos\varphi+\sqrt{\left(\frac{|IQ|}{V}\right)^{2}\cos^{2}\varphi-\left(\frac{|IQ|}{V}\right)^{2}+\left(\frac{|MI|}{V}\right)^{2}}$.
But since $|IQ|=V/8$, $|MI|>3V/8$, and $\cos\varphi\leq 1$, we get

$x>\frac{\cos\varphi}{8}+\sqrt{\frac{\cos^{2}\varphi}{64}-\frac{1}{64}+\frac{9}{64}}\geq\frac{\cos\varphi}{8}+\sqrt{\frac{\cos^{2}\varphi}{64}-\frac{\cos^{2}\varphi}{8}}=\frac{\cos\varphi}{8}+\frac{3\cos\varphi}{8}=\frac{\cos\varphi}{2}\,.$

Thus,
$\frac{|RQ|}{V}=\frac{1}{2}+\frac{|MQ|}{V}>\frac{1}{2}+\frac{\cos\varphi}{2}\geq\cos\varphi$.

Now, as $|PR|\leq V/4$ and the length of the perpendicular dropped from $R$
onto the line supporting $\overline{PQ}$ is at most $|PR|$, we obtain that

$\sin\varphi\leq\frac{V}{4|QR|}\leq\frac{1}{4\cos\varphi}\,,$

or $\sin^{2}\varphi\cos^{2}\varphi\leq 1/16$ from which it follows that
$\cos^{2}\varphi\geq\frac{2+\sqrt{3}}{4}$ or
$\cos\varphi\geq\sqrt{\frac{2+\sqrt{3}}{4}}$.

$k$-Async Case, when ${k>1}$.
As we saw in the $k$-NestA model, we take advantage of the fact that up to $k$
motions within safe regions that have been scaled by a factor of $1/k$, are
largely equivalent to single unscaled motions. Accordingly, the proof of
Theorem 4.4 when $k>1$ is essentially a reduction to the case $k=1$: we argue
that if there is a separating sequence when $k>1$, there must also be one when
$k=1$ (which we have just shown is impossible). The proof proceeds as follows:

  1. 1.

As in the case where $k=1$, we first suppose that a separating sequence for
two robots $\mathbb{X}$ and $\mathbb{Y}$ exists, and define a minimal
separating sequence to be one that minimizes the total number of activations
of $\mathbb{X}$ and $\mathbb{Y}$. As before, it follows from minimality that
the activations of $\mathbb{X}$ and $\mathbb{Y}$ interleave, with up to $k$
activations of one, an _activation cluster_ , between activations of the
other.

  2. 2.

We denote by $X_{j,1},\ldots,X_{j,s_{j}}$, where $s_{j}\leq k$, the positions
of robot $\mathbb{X}$ at the start of the first activation in its $j$-th
activation cluster, which occurs as robot $\mathbb{Y}$ is executing the last
activation cycle of its $(j-1)$-st activation cluster. (Similarly, we denote
by $Y_{j,1},\ldots,Y_{j,t_{j}}$, where $t_{j}\leq k$, the positions of robot
$\mathbb{Y}$ at the start of the first activation in its $j$-th activation
cluster, which occurs as robot $\mathbb{X}$ is executing the last activation
cycle of its $j$-th activation cluster (see Figure 13).

Figure 13: Without loss of generality, active intervals for $\mathbb{X}$ and
$\mathbb{Y}$ interleave, up to disconnection, with at most $k$ activations of
one between activations of the other. Activation clusters are shown in green.

  3. 3.

We refer to the locations at the start of activation clusters as _activation
checkpoints_ , and observe that there is no loss of generality in assuming
that the first point at which a separation occurs is at the separation
checkpoint pair $(X_{i+1,1},Y_{i+1,1})$.

  4. 4.

The same _safety constraints_ that applied in the case where $k=1$ are
expressed more generally as follows. For all $j\leq i$,

    1. (i)

for $1\leq t<t_{j}$, the point $Y_{j,t+1}$ lies in the $1/k$-fraction safe
region associated with $\mathbb{Y}$ at location $Y_{j,t}$, viewing
$\mathbb{X}$ at some location between $X_{j,s_{j}}$ and $X_{j+1,1}$, and

    2. (ii)

the point $Y_{j+1,1}$ lies in the $1/k$-fraction safe region associated with
$\mathbb{Y}$ at location $Y_{j,t_{j}}$, viewing $\mathbb{X}$ at some location
between $X_{j,s_{j}}$ and $X_{j+1,1}$.

Similarly,

    1. resume*

for $1\leq s<s_{j}$, the point $X_{j,s+1}$ lies in the $1/k$-fraction safe
region associated with $\mathbb{X}$ at location $X_{j,s}$, viewing
$\mathbb{Y}$ at some location between $Y_{j-1,s_{j-1}}$ and $Y_{j,1}$, and

    2. resume*

the point $X_{j+1,1}$ lies in the $1/k$-fraction safe region associated with
$\mathbb{X}$ at location $X_{j,s_{j}}$, viewing $\mathbb{Y}$ at some location
between $Y_{j-1,s_{j-1}}$ and $Y_{j,1}$.

  5. 5.

If the sequence of points $X_{j,2},\ldots,X_{j,s_{j}}$ all lie on the segment
$X_{j,1}X_{j+1,1}$ we say that the $j$-th activation cluster of $\mathbb{X}$
is _linear_. Similarly, if the sequence of points $Y_{j,2},\ldots,Y_{j,t_{j}}$
all lie on the segment $Y_{j,1}Y_{j+1,1}$ we say that the $j$-th activation
cluster of $\mathbb{Y}$ is _linear_.

We can assume that in our hypothesized minimum separating sequence all
activation clusters are linear. This follows by induction on $j$ (the index of
the activation cluster) using the facts that (i) during the initial activation
cluster of $\mathbb{X}$, robot $\mathbb{Y}$ is fixed at location $Y_{1,1}$,
and (ii) assuming the other robot is following a linear trajectory between
activation checkpoints, there is no loss of generality in assuming that the
next activation cluster is linear. The latter exploits our characterization,
from our analysis in the $k$-NestA setting, of the locus of points reachable
by up to $k$ successive $1/k$-fraction moves of one robot seeing the other at
successive points on some linear trajectory, in particular the fact that (by
convexity of the regions involved) all reachable points are reachable by a
straight path.

  6. 6.

Given that all activation clusters in our separating sequence are linear, it
becomes evident that the sequence of transitions between successive activation
checkpoints corresponds closely to a valid separating sequence in the
$1$-Async model. We then can extend the proof of Lemma 4.5 to the case when
$k>1$. In it, our characterization of the full safe region (recall Lemma 3.3)
is slightly more complicated (and slightly larger) than assumed for the case
$k=1$. In fact, our analysis in Lemma 4.5 (in the case $k=1$) treats the
situation where point $S$ lies in the core of the safe region for the robot at
location $Q$.

We show that $|RQ|>V\cos\varphi$ in the second case as well, when $S$ lies in
the bulge (see Figure 14). Observe that still $|MI|>3V/8$ and that,
consequently, our earlier proof continues to hold, despite the fact that it is
no longer the case that $|IS|\leq V/8$. Indeed, let $H$ be the intersection
point of a ray emanating from $I$ along $\overrightarrow{RI}$ and circle
$S^{V/8}_{Q}(P)$. Note that $|IH|=V/8$ and $|MH|>V/2$ (otherwise point $H$
and, thus, point $S$ do not lie outside of circle $c_{V/2}$, contradicting our
assumption that $|SR|>V\cos\beta$). Thus $|MI|\geq|MH|-|IH|>3V/8$, and Lemma
4.5 holds for $k>1$.

Figure 14:  Region $R^{V/8}_{Q}(R,P)$ intersects $c_{V/2}$ only if
$S^{V/8}_{Q}(P)$ intersects $c_{V/2}$.

####  4.2.2 Preservation of acquired visibilities

Here it suffices to observe that if at some point $\mathbb{Y}$ is seen by
$\mathbb{X}$ at some distance less than $V/2$, then $\mathbb{X}$ and
$\mathbb{Y}$ must remain mutually visible thereafter. This follows because at
the next checkpoint robots $\mathbb{X}$ and $\mathbb{Y}$ each could not have
moved more than distance $V/8$, and hence their separation could not exceed
$3V/4$ at that point. Hence, by our inductive assertions established in the
preceding subsubsection that demonstrate that any configuration of
$\mathbb{X}$ and $\mathbb{Y}$ leading to a separation of at least $V$ must be
preceded by configurations of $\mathbb{X}$ and $\mathbb{Y}$ with separation at
least $0.96V$, we conclude that $\mathbb{X}$ and $\mathbb{Y}$ must remain
mutually visible.

##  5 Incremental congregation in the _k_ -NestA and _k_ -Async models

We have, to this point, not specified the details of the destination function
of an activated robot $\,\mathbb{Z}$, other than that it must be a point in
the intersection of the safe regions with respect to all of its distant
neighbours (those neighbours whose distance is in the range
$(V_{\mathbb{Z}}/2,V_{\mathbb{Z}}]$, where $V_{\mathbb{Z}}$ is the distance to
the furthest visible neighbour of $\,\mathbb{Z}$). We choose the center point
of this intersection as the target destination.

In the event that the distant neighbours are not properly contained in any
halfspace with $\,\mathbb{Z}$ on its boundary, the intersection of the
corresponding safe regions is just the current location of $\,\mathbb{Z}$, so
the target destination is just this current location (i.e. $\,\mathbb{Z}$ does
not move). Other events consist of two cases:

  1. (i)

$\mathbb{Z}$ has only one distant neighbour. In this case the target
destination is just the center point of the sole constraining safe region.

  2. (ii)

$\mathbb{Z}$ has two or more distant neighbours. In this case the target
destination is the center point of the intersection of the safe regions
associated with the two distant neighbours that define the largest sector
containing all of the distant neighbours of $\,\mathbb{Z}$ (see Figure 15).
Note that the center point is the middle point of the segment connecting the
centers of the safe regions corresponding to the two distant neighbours.

Figure 15: Visualization of the target destination $x$ for $\mathbb{Z}$ when
it admits two distant neighbours.

Note that, in all events, the distance to the target destination of an
activated robot is at most $V/8$.

As we have demonstrated, our algorithm has the property that it preserves all
initial visibilities as well as all visibilities that at some point fall below
the $V/2$ threshold. We say that a pair of robots are strong neighbours at
some point in time if one of these conditions holds. It follows that the graph
of the strong neighbour relation is both connected, because it includes all
initially visible pairs, and monotonic. In particular, at any moment in time
there is a path in this graph joining any pair of robots. Furthermore there is
a point in time after which the graph no longer changes: thereafter for any
pair of robots, (i) their separation is continuously less than or equal to $V$
(i.e., they are mutually visible), or (ii) their separation is continuously
greater than $V/2$. This, combined with the fact that our strategy is hull-
diminishing, suffices to show that the robots always converge to a point, from
any initial configuration.

We begin with an informal overview of the argument.

  * •

As with all hull-diminishing strategies, progress towards convergence to a
point can be measured in terms of the shrinkage of the convex hull of the full
set of robot locations. Let $CH_{t}$ denote the convex hull of the robot
locations, including their planned but as yet unrealized trajectories, at time
$t$. Then incremental progress towards convergence is captured by the
following observation (made previously in [25]):

$CH_{t^{+}}\subseteq CH_{t}$ for all $t^{+}>t$. This follows from the facts
that (i) when a motion is planned it is towards a point inside the current
convex hull, and (ii) when the motion completes, and the planned trajectory
(or some prefix) has been realized, replacing the trajectory by its endpoint
can only shrink the convex hull.

  * •

Since convex hulls form a nested sequence, they either converge to a single
point (which is what we are trying to establish), or not. Suppose that the
convex-hull sequence does not converge in this way for some initial
configuration of $n$ robots. Then both the convex hull perimeter and the hull
radius (the radius of the smallest ball enclosing the convex hull) must form
monotonically decreasing sequences that converge to some non-zero values,
$\Lambda$ and $\rho$ respectively. Thus, for any $\varepsilon>0$ there is a
time $t_{\varepsilon}$ after which the hull perimeter lies in the range
$[\Lambda,\Lambda+\varepsilon)$ and the hull radius lies in the range
$[\rho,\rho+\varepsilon)$.

  * •

Let $t$ be any time after which the hull radius lies in the range
$[\rho,3\rho/2)$ and consider the convex hull $H=CH_{t}$, with perimeter
$\Lambda_{t}$, and its smallest bounding circle $\,\Xi$, with center $O_{H}$
and radius $r_{H}$, at that time (see Figure 16). We will argue that there is
a $\lambda>0$, dependent on $\rho$, such that at some time $t^{\prime}>t$ the
perimeter of $CH_{t^{\prime}}$ becomes less than $\Lambda_{t}-\lambda$. This
leads to a contradiction, if we choose $\varepsilon<\lambda$ and $t\geq
t_{\varepsilon}$.

Figure 16: Smallest bounding circle $\,\Xi$.

We know that $\,\Xi$ is determined by three critical points (robot positions)
$A_{H}$, $B_{H}$ and $C_{H}$ (two of which might coincide), all of which are
at distance exactly $r_{H}$ from $O_{H}$, and in pairs bound sectors of
$\,\Xi$ with span no more than $\pi$. We will show that there is a $\delta>0$,
dependent on $\rho$, such that for at least one of these critical points, say
$A_{H}$, the $\delta$-neighbourhood of $A_{H}$ (the set of robots at distance
at most $\delta$ from $A_{H}$) is eventually empty.

The critical observation is captured in a lemma that states that that if some
robot $\,\mathbb{Z}$ has neighbours at distance that is some sufficiently
large fraction of $r_{H}$, then its motion cannot take it too close to
$A_{H}$. From this it follows immediately that if $\,\mathbb{Z}$ continues to
have at least one such distant neighbour then $\,\mathbb{Z}$ must become and
stay well removed from $A_{H}$.

######  Lemma 5.1.

If $\,V_{\mathbb{Z}}\geq\zeta\cdot r_{H}$ then any $\xi$-rigid motion of
$\,\mathbb{Z}$ takes it to a point at distance at least
$\left(\frac{\zeta}{80(1+1/\xi)^{1/2}}\right)^{4}r_{H}$ from $A_{H}$.

######  Proof 5.2.

Refer to Figure 17.left. Let
$d=\left(\frac{\zeta}{80(1+1/\xi)^{1/2}}\right)^{4}r_{H}$, consider a circle
$\Gamma_{d}(A_{H})$ of radius $d$ centered at $A_{H}$. Let $y_{d}$ be the
length of the chord $PP^{\prime}$ (shown in blue) tangent to
$\Gamma_{d}(A_{H})$ and normal to $A_{H}O_{H}$, and let $R_{d}$ denote the
portion of $\,\Xi$, containing point $A_{H}$, between the arc $PP^{\prime}$
and the chord $PP^{\prime}$. Note that
$y_{d}=2\sqrt{r_{H}^{2}-(r_{H}-d)^{2}}<2\sqrt{2r_{H}d}$.

First suppose that the motion of $\,\mathbb{Z}$ is $1$-rigid. If the target
destination $T$ satisfies $|A_{H}T|\leq d$ (red sector) then, since $T$ is the
midpoint of safe region centers of two (or one) distant neighbours of
$\,\mathbb{Z}$, the safe region center $C_{W}$ associated with at least one
extreme distant neighbour $\mathbb{W}$ of $\,\mathbb{Z}$ must lie in $R_{d}$.

As $C_{W}$ lies in $R_{d}$ and $C_{W}$ lies on $\overline{ZW}$, there can be
two cases: either (i) $Z$ lies in $R_{d}$, or (ii) $W$ lies in $R_{d}$. In the
first case, we have $|ZC_{W}|<y_{d}$, $|ZW|\leq 8|ZC_{W}|$, and thus
$V_{\mathbb{Z}}<2|ZW|<16y_{d}<32\sqrt{2r_{H}d}$. In the second case, if $W$
lies in $R_{d}$, then $|C_{W}W|<y_{d}$, and
$|ZW|=V_{\mathbb{Z}}/8+|C_{W}W|<V_{\mathbb{Z}}/8+y_{d}$. Thus, as $\mathbb{W}$
is a distant neighbour of $\mathbb{Z}$,
$V_{\mathbb{Z}}<2|ZW|<2(V_{\mathbb{Z}}/8+y_{d})$, and hence
$V_{\mathbb{Z}}<8/3y_{d}<16/3\sqrt{2r_{H}d}$.

If the motion of $\,\mathbb{Z}$ is $\xi$-rigid its actual destination
$T^{\prime}$ satisfies $|ZT^{\prime}|\geq\xi|ZT|$. Let $|A_{H}T^{\prime}|\leq
d$. Consider again the two cases: $Z$ lies in $R_{d}$, and $W$ lies in
$R_{d}$. In the second case, when $Z$ lies outside $R_{d}$, then $T$ must lie
in $R_{d}$ (as $T^{\prime}$ lies on $\overline{ZT}$). Hence $|A_{H}T|\leq
y_{d}$ and, by our earlier analysis (for $\xi=1$),
$V_{\mathbb{Z}}<32\sqrt{2r_{H}(2\sqrt{2r_{H}d})}$. On the other hand, if $Z$
lies in $R_{d}$ then $|ZT^{\prime}|\leq y_{d}$ and hence $|ZT|\leq y_{d}/\xi$.
Thus, $|A_{H}T|\leq|A_{H}Z|+|ZT|<y_{d}+y_{d}/\xi=y_{d}(1+1/\xi)$ and, by our
earlier analysis,

$\displaystyle V_{\mathbb{Z}}$
$\displaystyle<32\sqrt{2r_{H}y_{d}(1+1/\xi)}<32\sqrt{4r_{H}\sqrt{2r_{H}d}(1+1/\xi)}$
$\displaystyle<80(1+1/\xi)^{1/2}r_{H}^{3/4}d^{1/4}=80(1+1/\xi)^{1/2}(d/r_{H})^{1/4}r_{H}=\zeta
r_{H}\,.$

It follows directly from Lemma 5.1 that permanent separation from $A_{H}$ is
contagious:

######  Lemma 5.3.

If robot $\,\mathbb{Z}$ has a neighbour $\mathbb{X}$ whose distance from
$A_{H}$ remains at least $\mu r_{H}$ then $\,\mathbb{Z}$ must itself become
and remain at distance at least
$\left(\frac{\mu}{240(1+1/\xi)^{1/2}}\right)^{4}r_{H}$ from $A_{H}$.

######  Proof 5.4.

By Lemma 5.1, while $V_{\mathbb{Z}}\geq(\mu/3)r_{H}$, $\,\mathbb{Z}$ must
remain at distance at least
$\left(\frac{\mu}{240(1+1/\xi)^{1/2}}\right)^{4}r_{H}$ from $A_{H}$. On the
other hand, if $V_{\mathbb{Z}}<(\mu/3)r_{H}$ then, since $\mathbb{X}$ is a
neighbour of $\,\mathbb{Z}$, $\,\mathbb{Z}$ has distance at least
$(2\mu/3)r_{H}$ from $A_{H}$. But any movement of $\,\mathbb{Z}$ (taking it to
a position within the convex hull of its neighbours) must leave it no further
than $(\mu/3)r_{H}$ from its current position, and hence at least
$(\mu/3)r_{H}$ from $A_{H}$.

Figure 17: Left: the radius of the red circle is $d$, and the length of the
chord $\overline{PP^{\prime}}$ (in blue) is $y_{d}$. Right: The length of the
chord $\overline{QQ^{\prime}}$ (in green) is $2z_{d}$, and the distance from
$A_{H}$ to $\overline{QQ^{\prime}}$ is $x_{d}$.

Suppose now that we have chosen a time $t$ after which the strong neighbour
graph no longer changes and the hull radius lies in the range
$[\rho,3\rho/2)$. Consider robots in $\Gamma_{\delta}(A_{H})$, the
$\delta$-neighbourhood of vertex $A_{H}$. Consider some time $t^{\prime}>t$
after which all robots that will eventually lie and remain outside of
$\Gamma_{\delta}(A_{H})$ have done so. Further, imagine that at time
$t^{\prime}$ one or more robots, including $\,\mathbb{Z}$, lie inside
$\Gamma_{\delta}(A_{H})$. It will suffice to argue that, assuming motion is
$\xi$-rigid, $\,\mathbb{Z}$ must move and remain outside
$\Gamma_{\delta}(A_{H})$.

There are two cases to consider depending on the composition of the set of
neighbours of $\,\mathbb{Z}$.

  1. (i)

All other robots are neighbours of $\,\mathbb{Z}$. In this case, either (i) at
some subsequent point in time, either one of $\Gamma_{\delta}(A_{H})$,
$\Gamma_{\delta}(B_{H})$ or $\Gamma_{\delta}(C_{H})$ contains no robots (in
which case nothing remains to be proved), or (ii) $\,\mathbb{Z}$ must continue
to have a neighbour at distance at least $r_{H}-\delta$, that is
$V_{\mathbb{Z}}\geq r_{H}-\delta\geq r_{H}/2$, provided that $\delta\leq
r_{H}/2$. Hence, by Lemma 5.1, $\,\mathbb{Z}$ too must move to, and remain at,
a position at least $\left(\frac{1}{160(1+1/\xi)^{1/2}}\right)^{4}r_{H}$ from
$A_{H}$.

  2. (ii)

$\,\mathbb{Z}$ has at least one other robot that is not a strong neighbour. In
this case, since the strong neighbour graph is connected, there must be a
strong neighbour $\mathbb{X}$ of $\,\mathbb{Z}$ that has a strong neighbour
$\mathbb{Y}$ that is not a strong neighbour of $\,\mathbb{Z}$. Since
$\mathbb{Y}$ and $\,\mathbb{Z}$ are not strong neighbours their separation
must continue to exceed $V/4$, and hence the distance from at least one of
them to $\mathbb{X}$ must continue to be at least $V/8$ which, by the
connectivity of the strong neighbour graph, is at least $r_{H}/(8n)$. Thus, by
Lemma 5.1, $\mathbb{X}$ itself must move to, and remain at, a position at
least $\left(\frac{1}{640n(1+1/\xi)^{1/2}}\right)^{4}r_{H}$ from $A_{H}$. It
follows, by Lemma 5.3, that $\,\mathbb{Z}$ too must move to, and remain at, a
position at least
$\left(\frac{1}{640n(1+1/\xi)^{1/2}}\right)^{16}\left(\frac{1}{240(1+1/\xi)^{1/2}}\right)^{4}r_{H}$
from $A_{H}$.

Hence, if
$\delta<\left(\frac{1}{640n(1+1/\xi)^{1/2}}\right)^{16}\left(\frac{1}{240(1+1/\xi)^{1/2}}\right)^{4}r_{H}$,
$\,\mathbb{Z}$ must eventually, and permanently, vacate
$\Gamma_{\delta}(A_{H})$. This contradicts our assumption that at time
$t^{\prime}$ all robots that will permanently vacate $\Gamma_{\delta}(A_{H})$
have done so. Thus, we can assume that at time $t^{\prime}$, and thereafter,
$\Gamma_{\delta}(A_{H})$ contains no robots.

This means, of course, that $CH_{t^{\prime}}$, the convex hull of the robot
positions at time $t^{\prime}$, has no vertex closer than $\delta$ to $A_{H}$.
It follows from this that the perimeter of $CH_{t^{\prime}}$ is less than
$\Lambda_{t}$, the perimeter of $CH_{t}$, by an amount $\lambda$ that is
independent of $\varepsilon$.

######  Lemma 5.5.

If the robot positions at time $t^{\prime}$ are all outside of
$\,\Gamma_{d}(A_{H})$ then the perimeter of $\,CH_{t^{\prime}}$ is at most
$\Lambda_{t}-\frac{d^{3}}{4r_{H}^{2}}$.

######  Proof 5.6.

Since $A_{H}$ lies on the boundary of $CH_{t}$, and all robot positions at
time $t^{\prime}$ lie outside of $\Gamma_{d}(A_{H})$, it follows that the
perimeter of $CH_{t^{\prime}}$ is at least $2(d-z_{d})$ shorter than the
perimeter of $CH_{t}$, where $2z_{d}$ is the length of the chord $QQ^{\prime}$
(see Figure 17.right). Let $x_{d}$ be the distance from $A_{H}$ to
$\overline{QQ^{\prime}}$. It is straightforward to confirm that
$d-z_{d}=x_{d}^{2}/(d+z_{d})>x_{d}^{2}/(2d)$ and (by similar triangles)
$x_{d}=d^{2}/(2r_{H})$, and hence $2(d-z_{d})>d^{3}/(4r_{H}^{2})$.

As previously noted, this leads to a contradiction (of our assumption of non-
convergence) if we choose $\varepsilon<\frac{d^{3}}{4r_{H}^{2}}$ and
$t>t_{\varepsilon}$. Therefore the sequence of nested convex hulls converge to
a point, and our algorithm solves Point Convergence problem.

##  6 Extensions/Generalizations

###  6.1 Error tolerance

  * •

It is clear that any absolute error in distance measurements makes convergence
to a point impossible, even in a fully synchronous scheduling environment.
However our algorithm can be modified to tolerate a modest amount of relative
error in distance measurements The only concern with error in distance
measurements is that it might lead $V_{\mathbb{Z}}$, the perceived distance to
the closest neighbour of $\,\mathbb{Z}$, to become an overestimate of $V$. If
the error is bounded by some small fraction $\delta$ of the true distance,
then this can be avoided by simply scaling the perceived distance by a factor
of $1/(1+\delta)$.

  * •

In the absence of any global information on the initial configuration, even an
arbitrarily small amount of absolute error in angle measurements makes
convergence infeasible for any algorithm, even in fully synchronous scheduling
environment. This follows by observing that the presence of such error would
make it impossible to distinguish some non co-linear triple of points,
separated by distance $V$, with a co-linear such triple. Given this, any
algorithm would be forced to refrain from moving the midpoint of such a co-
linear triple (at the risk of a catastrophic separation). This in turn would
lead to completely frozen activity on a suitably collection of robots
configured as a regular polygon with vertex separation $V$.

However, our algorithm can be modified to tolerate a modest amount of a kind
of relative error in angle measurements (that preserves sidedness with respect
to lines through neighbouring points).

To make this concrete, consider the error in angle measurements that would
arise from a small perturbation of a robot’s local coordinate system: a
_symmetric distortion_ of some reference coordinate system is a continuous
bijection $\mu:[0,2\pi])\rightarrow[0,2\pi)$ with
$\mu(\theta+\pi)=\mu(\theta)+\pi$, for all $\theta\in[0,\pi)$. Such a
distortion has _skew_ bounded by $\lambda<1$ if
$(1-\lambda)\xi\leq\mu(\theta+\xi)-\mu(\theta)\leq(1+\lambda)\xi$, for all
$\xi\in(0,\pi)$.

Observe that a symmetric distortion with skew $0$ is just a rotation or
reflection of the local coordinate system. That a permissible distortion is a
continuous bijection seems natural; that it should also be symmetric is also
realistic in our context, since otherwise it is possible to construct (as
above) a configuration with robots located at the vertices of a regular
polygon with $V$ length edges, that fails to converge.

Our algorithm can be modified to tolerate a symmetric distortion of its local
coordinate system with small skew. The intuition here is to reduce the safe
region of robot $\mathbb{Y}$ with respect to a distant neighbour $\mathbb{X}$
by making it instead the intersection of the safe regions that would be
associated with all possible true locations of $\mathbb{X}$.

  * •

It should be clear that absolute error, measured as the deviation of the
actual destination from the trajectory to the intended destination, cannot be
tolerated by any convergence algorithm, even in the fully synchronous model.
In fact, even linear relative error (error that grows linearly with the
distance travelled) cannot be tolerated (see Figure 18).

Figure 18: If the relative motion error is greater than $\tan\varphi$ then $B$
can move to the left of the normal to $BC$ (red) and $C$ can move to the
right, resulting in separation if $|BC|=V$.

However, our algorithm can be modified to tolerate relative motion error that
grows quadratically (specifically error is $O(d^{2}/V)$, where $d$ is the
distance travelled). To see this, recall that our algorithm chooses as its
destination point the midpoint of the region formed by the intersection of the
safe regions of a robot’s extreme distant neighbours. If the angle formed by
these neighbours is bounded away from $\pi$ then there is fixed faction of the
intended trajectory that, even when followed with quadratic error, will remain
within the intersection of the safe regions.

  * •

Our algorithm can clearly tolerate premature stop failures, provided these do
not accumulate in a way that violates the activation fairness condition. In
fact, a single crash (or “fail-stop”) fault, where a robot crashes and remains
stationary thereafter, can also be tolerated. In this case the remaining
robots converge to the location of the crashed robot.

###  6.2 Visibility

Our algorithm works correctly even if the visibility region is open (i.e. to
be visible a neighbouring robot must be at distance strictly less than $V$).
To see this, it suffices to observe that in this case, $V_{\mathbb{Z}}$, the
perceived distance to the furthest neighbour, is always strictly smaller than
$V$.

Furthermore, can be modified without difficulty to work correctly even if the
visibility radius $V$ may differ for different robots, provided that (i) the
initial mutual visibility graph is connected, and (ii) individual (unknown)
visibility radii could differ by at most some small (known) constant factor.

In the event that the visibility radius $V$ exceeds the diameter of the
initial configuration, it follows from the hull-diminishing property that all
robots will remain mutually visible throughout the computation. Since our
congregation argument continues to hold even under an Async scheduler, we
conclude that our $1$-Async algorithm will guarantee convergence in this case,
without any need for multiplicity detection.

###  6.3 Further relaxations

####  6.3.1 General initial configuration.

It is worth noting that if the initial configuration is not connected our
algorithm guarantees that every connected subset of robots will converge to a
single point. Furthermore, noting that robots in any component embedded in an
interior face of the visibility graph associated with the initial
configuration must ultimately converge to the same point as the robots
defining that face, it is clear that connectivity of the initial configuration
is not a necessary condition for our algorithm to solve Point Convergence.

####  6.3.2 Three (and higher) dimensions.

Our algorithm admits a very natural generalization for robots configured in
three (and higher) dimensions (as in [6, 35]). Specifically, safe regions are
generalized to higher dimensional disks, with the same center and radius.
While it seems clear that both our visibility preservation and incremental
congregation arguments can be extended, the geometric details are more
intricate. We leave the full resolution of these details to future work.

##  7 Impossibility of visibility preservation in Async model, assuming modest
error in perception, but no error in motion

In this section, we will show how to associate with any modestly error-
tolerant control algorithm an initial connected configuration of robots,
together with an adversarial scheduler in the Async model (in fact, the NestA
model) that produces a robot configuration with two or more linearly separable
connected components in its associated visibility graph. Specifically, we
consider algorithms, like the one developed in preceding sections, and like
those that we might reasonably expect to be used in practice, for robots whose
perceptual apparatus is accurate up to (i) small relative error in distance
measurements (the perceived distance $\tilde{d}$ to any neighbour of a robot
is accurate only to within a constant $\delta>0$ times the true distance $d$),
and (ii) small relative errors in angle measurements of the kind that arise
from symmetric distortions of local coordinate systems, with bounded skew (the
perceived angle $\tilde{\theta}$ between any two neighbours is accurate only
to within some constant $0<\lambda<1$ times $\pi-\theta$, where $\theta$ is
the true angle). The control algorithm is free to assume a fixed visibility
threshold (assumed to be 1), and that motion is rigid and free of error.

The first assumption allows us to specify an initial configuration of robots
so that the true distance of neighbouring robots, in both this initial
configuration and all subsequent configurations, is sufficiently close to the
visibility threshold that neighbours could be perceived as always being
exactly at that threshold. The second assumption allows us to conclude that,
while the perceived sidedness of the observing robot with respect to the line
joining any pair of its neighbours agrees with reality, there is sufficient
uncertainty to guarantee that robots that are not yet co-linear with their
neighbours must move. (Otherwise, as we will show, it would be possible to
construct a local configuration that likewise has no associated forced move,
but which could be replicated into a global configuration that, for this
reason, fails to converge).

It follows that the Cohesive Convergence problem is not solvable in the Async
or NestA model. This in turn implies that the Point Convergence problem is not
solvable in the Async model, using any hull-diminishing algorithm. In fact,
even if an algorithm satisfies the weaker condition of being _coherent_ , in
the sense that it never prescribes a motion for a robot that will immediately
disconnect the visibility graph induced on its neighbours, then it must fail
to converge from the disconnected configuration forced by the adversary that
we describe.

We conclude that the Point Convergence problem illustrates a separation in the
power of bounded vs. unbounded asynchrony, for natural (hull-diminishing or
coherent), modestly error-tolerant algorithms. Note that, it seems unavoidable
to insist on some measure of error tolerance in framing this result. In fact,
a proof that something is impossible for error-free algorithms with rigid
motion seems well out of reach.

###  7.1 The initial configuration

We describe the initial configuration in terms of a parameter $\psi>0$ that we
will subsequently set to be sufficiently small. We take the visibility
threshold $V$ to be $1$.

The initial robot configuration consists of three robots $\mathbb{X}_{A}$,
$\mathbb{X}_{C}$ and $\mathbb{X}_{B}$, located at positions $A=(0,0)$,
$C=(-\frac{1}{\sqrt{2}},-\frac{1}{\sqrt{2}})$ and $B=(1,0)$ respectively, and
$n-3$ additional robots,
$\mathbb{X}_{1},\mathbb{X}_{2},\ldots\mathbb{X}_{n-3}$, positioned at points
$P_{1},P_{2},\ldots,P_{n-3}$ spaced at distance $1$, along a discrete spiral
tail starting with the edge $AB$. The turn angle between the chord
$\overline{AP_{i-1}}$ and the segment $\overline{P_{i-1}P_{i}}$, taking
$P_{0}=B$, is fixed at $\psi$, for all $i\geq 1$. (Figure 19.left illustrates
such a configuration).

The total number of robots, $n$, is chosen to be sufficiently large that the
angle between the chords $\overline{AP_{0}}$ and $\overline{AP_{n-3}}$ is
about $3\pi/8$ (so the line through $A$ and $P_{n}$ bisects the angle
$\angle(CAB)$). Of course, we need to argue that such an $n$ exists: for this
we observe that even though the angle $\gamma_{i}$ between successive chords
$\overline{AP_{i-1}}$ and $\overline{AP_{i}}$ decreases with $i$, the sum
$\sum_{i}\gamma_{i}$ diverges. To see this, let $d_{i}$ denote the length of
the chord $\overline{AP_{i}}$. We know, from the cosine law, that
$d_{i}^{2}=d_{i-1}^{2}+1-2d_{i-1}\cos(\pi-\psi)$. Hence, when $\psi>0$,

$\displaystyle d_{i}-d_{i-1}$
$\displaystyle=\frac{1+2d_{i-1}-2d_{i-1}(1-\cos\psi)}{d_{i}+d_{i-1}}>\frac{1+2d_{i-1}-2d_{i-1}(1-\cos\psi)}{1+2d_{i-1}}$
$\displaystyle=1-\frac{2d_{i-1}(1-\cos\psi)}{1+2d_{i-1}}\geq
1-\frac{2d_{i-1}(\psi^{2}/2)}{1+2d_{i-1}}>1-\psi^{2}/2.$

Since $d_{0}=1$, and $d_{i}-d_{i-1}\leq 1$ (by the triangle inequality), it
follows by induction on $i$ that $i(1-\psi^{2}/2)<d_{i}<i$, for $1\leq i\leq
n-3$.

It is easy to confirm that the perpendicular distance from $P_{i}$ to the line
through $A$ and $P_{i-1}$ equals both $\sin\psi$ and $d_{i}\sin\gamma_{i}$.
Hence
$\gamma_{i}\geq\sin\gamma_{i}=\frac{\sin\psi}{d_{i}}\geq\frac{\sin\psi}{i}$.
It follows that $\sum_{i=1}^{n-3}\gamma_{i}\geq\sin\psi\ln(n-3)$. Thus it will
suffice to choose $n$ large enough that $\sin\psi\ln(n-3)\geq 3\pi/8$, i.e.,
$n\geq 3+e^{\frac{3\pi}{8\sin\psi}}$.

Figure 19: Left: initial robot configuration; Center: approximate trajectories
to final configuration; Right: typical intermediate configuration

###  7.2 Adversarial scheduler strategy

The strategy of the adversarial scheduler is to first activate the robot
$\mathbb{X}_{A}$ forcing it (as we will argue) to plan a move to a point
$A^{\prime}$ some non-zero distance $\zeta$ away from $A$ into the sector
$CAB$ (by the symmetry of the local configuration, we can assume that
$|A^{\prime}C|\leq|A^{\prime}B|$; for ease of description, we will assume that
these distances are equal).

Next, and before the robot $\mathbb{X}_{A}$ actually begins its move, the
scheduler begins a long sequence of activations of the robots
$\mathbb{X}_{0},\ldots,\mathbb{X}_{n-3}$ (where
$\mathbb{X}_{0}=\mathbb{X}_{B}$), with the goal of moving, for each $i$,
$1\leq i\leq n-3$, in succession, all of the robots
$\mathbb{X}_{0},\mathbb{X}_{1},\ldots,\mathbb{X}_{i-1}$ onto the chord
$AP_{i}$, without changing their initial distance from $A$ by more than an
amount that is $\Theta(\psi^{2})$. If successful in this task then, by
choosing $\psi$ to be sufficiently small, all robots will follow trajectories
that approximate circular arcs, centered at $A$, from their initial position
to their final position on the chord $\overline{AP_{n}}$ (see Figure 19.center
and Figure 19.right). Furthermore, if $\psi$ is chosen to be sufficiently
small relative to $\zeta$, the scheduler will have succeeded in breaking the
visibility between the robots $\mathbb{X}_{A}$ and $\mathbb{X}_{B}$.

The argument that such an activation sequence exists involves two things: (i)
showing that specified robots must move, when activated, and (ii) showing that
the motion must keep their distance from $A$ the same, up to an additive
factor that accumulates to something that is $O(\psi^{2})$.

The space between successive chords defines what we call a sliver (see Figure
20). The transitions of robots from one chord to the next, flattening the
associated sliver, involves the (essential) collapse of a succession of thin
triangles, each of which involves the relocation of a robot to become
essentially co-linear with its neighbours at almost distance one. By
“essentially co-linear” we mean that the angle formed by the neighbours is in
$(\pi-\psi/2^{n},\pi]$. This slight slack permits termination of the collapse
process and ensures that when the entire relocation is complete the sum of all
turn angles on the chain is at most $n\psi/2^{n}$ and hence all of the robots
lie arbitrarily close to the chord $AP_{n-3}$.

Figure 20: Initial sliver.

####  7.2.1 Forced motion

Imagine that a triple of robots is in a local configuration like that
illustrated in Figure 21. Under what conditions can we assume that if
activated the robot at position $Q$ must move? Our assumption about error in
distance perception is such that if the distances between $Q$ and its two
neighbours are both in the range $(1-\delta,1]$, then they could both be
perceived as being $1$. Clearly, this would preclude the algorithm from
choosing not to move the robot at $Q$ (when activated) if in addition the
angle $\phi$ is of the form $2\pi/k$, for some integer $k$; otherwise the
algorithm would fail to converge if started from a configuration with robots
located at the vertices of a regular $k$-gon with unit length sides. Thus, if
the error in angle perception is such that the angle $\phi$ could be perceived
to have this special form, some motion of the robot at $Q$ is forced.

Our assumption about error in angle perception is such that the true turn
angle $\phi$ could be perceived as anything in the range
$[\phi(1-\lambda),\phi]$, for some positive constant $\lambda<1$. Since this
range might not contain a special angle when $\phi$ is very small, we need a
more versatile argument to see that motion can be forced. Fortunately, it
suffices to observe that, if integer $M$ is greater than
$\frac{4\pi}{\lambda\phi}$, then there must exist angles $\frac{2\pi i}{M}$
and $\frac{2\pi(i+1)}{M}$ both in the range $[\phi(1-\lambda),\phi]$. It must
be the case that if the algorithm chooses not to move the robot at point $Q$
(when activated) when the turn angle is perceived to be $\frac{2\pi i}{M}$
then it must move the robot at point $Q$ (when activated) when the turn angle
is perceived to be $\frac{2\pi(i+1)}{M}$. Otherwise, we could construct
another polygonal placement with $2M$ edges that alternate a
$\frac{2\pi(i+1)}{M}$ counter-clockwise turn with a $\frac{2\pi i}{M}$
clockwise turn, from which the algorithm would fail to move, and hence fail to
converge.

####  7.2.2 Collapsing thin triangles

Figure 21:

It is not enough to know that motion can be forced by an adversary. We also
need to demonstrate that (i) motion is productive, in the sense that it
eventually leads to essential co-linearity 121212To simplify the argument, we
treat ignore the fact that “essential co-linearity” is not exactly the same as
co-linearity. This is justified by the fact that, as we will demonstrate,
robots can be moved to become arbitrarily close to co-linear, and the extra
work involved in carrying insignificant error terms would not make the
argument stronger or more illuminating in any measurable way. with neighbours,
and (ii) motion preserves distance to point $A$, up to some small additive
error, proportional to angle $\phi$ and the distance moved.

Here again, it helps to consider a triple of robots is in a configuration like
that illustrated in Figure 21, where the distances $|RQ|$ and $|QP|$ are both
$1$, as perceived by the robot at $Q$. We know that the robot at location $Q$
(when activated) is forced to move, and its intended destination must lie
within the green lens; otherwise, such a move would separate this robot from
one of its neighbours, following which convergence would be impossible if this
were the full initial configuration.

Any motion only leads to a configuration with smaller turn angle $\phi$. (This
is true even if the motion takes $Q$ beyond the midpoint of the lens). Since
the new turn angle $\phi^{\prime}$ could continue to be perceived as being in
the range $[\phi(1-\lambda),\phi]$ as long as
$\phi^{\prime}>\phi/(1+\lambda)$, it follows that repeated activation of the
same robot will keep it inside the lens and eventually bring it to a position
$Q^{\prime}$ of essential co-linearity with its neighbours, provided that the
distances to the neighbouring robots continues to fall in the range
$(1-\delta,1]$.

Any point $Q^{\prime}$ of co-linearity within the lens has distance $\ell$ at
most $2\sin(\phi/4)$, which is at most $\phi/2$, from $Q$. Furthermore, the
distance from $Q^{\prime}$ to both of the normals $N_{RQ}$ and $N_{QP}$ is at
most $\ell\sin\phi$. From this it follows that the distance from $Q^{\prime}$
to any point at or beyond $R$ on the ray from $Q$ through $R$ (or any point at
or beyond $P$ on the ray from $Q$ through $P$) does not change by more than
$\ell\sin\phi$, which is at most $\phi^{2}/2$.

Thus, it suffices to assume that the distances to the neighbouring robots
starts in the range $(1-\delta+\phi^{2}/2,1]$. Furthermore, once the robot has
reached a position of essential co-linearity with its neighbours, its distance
from point $A$, the base point of our global configuration, has not changed by
more than $\phi^{2}/2$.

####  7.2.3 Flattening slivers

A sliver (see Figure 22.top_left, for a generic example) is iteratively
flattened by first (i) moving the endpoint $Q$ of the first chord until it is
(essentially) co-linear with its neighbours $R$ and $P$, collapsing the
associated triangle (see Figure 22.top_right), as described in the preceding
subsubsection, then (ii) recursively flattening the newly created sliver
$ARQ^{\prime}$ (see Figure 22.bottom_left), and finally (iii) continuing to
flatten the semi-flattened sliver $AQ^{\prime}P$ (see Figure 22.bottom_right).

Figure 22: Recursive collapse of a sliver.

It remains to argue that the change in the distance between the location of
robot $\mathbb{X}_{j}$ and $A$, even though it may accumulate through a long
sequence of triangle collapses, does not sum to more than $4\psi^{2}$. To see
this we observe that:

  1. (i)

all slivers formed by successive chords in the initial placement have turn
angle $\psi$;

  2. (ii)

the successively narrower slivers that arise in flattening any initial sliver
have progressively smaller turn angles;

  3. (iii)

the sliver that arises after the first triangle collapse (the blue sliver in
Figure 22.bottom_left) has a turn angle that is exactly one half of that its
parent sliver; and more generally the slivers that arise in the $t$-th level
of recursive sliver flattening have a turn angle that is a fraction $1/2^{t}$
of that of its parent sliver.

It follows that the change in distance from $A$ associated with the motion of
robot $\mathbb{X}_{j}$ in the course of moving it from its location on chord
$AP_{i-1}$ to its location on chord $AP_{i}$ is at most
$\gamma_{i}d_{j}\frac{\psi}{2^{i-j-1}}$. Hence the total deviation from its
initial distance $d_{j}$ is at most
$\sum_{i>j}\gamma_{i}d_{j}\frac{\psi}{2^{i-j-1}}<\gamma_{j}d_{j}\psi\sum_{i>j}\frac{i}{2^{i-j-1}}<2\gamma_{j}d_{j}\psi<4\sin\gamma_{j}d_{j}\psi=4\frac{\sin\psi}{j}d_{j}\psi<4\psi^{2}$.

##  8 Summary and Conclusion

We have studied the well-known Point Convergence problem for autonomous mobile
robots with bounded visibility. Connectivity, realized through visibility,
plays a fundamental role in all known algorithms for Point Convergence in this
setting: it is typically assumed that the visibility graph of the initial
robot configuration is connected, and a central algorithm design constraint is
the preservation of visibility between pairs of robots. Indeed all previous
algorithms solve the apparently more restricted problem, which we call
Cohesive Convergence, that requires the visibility between all initially
mutually visible robot pairs to be preserved indefinitely.

We propose a new algorithm for Cohesive Convergence designed for robots
operating within the $k$-Async scheduling model, for any constant $k$, a
significantly more inclusive scheduling environment than that assumed by its
predecessors. In addition, our algorithm makes comparatively weak assumptions,
including non-rigid movements and no knowledge of the visibility radius $V$,
about robot capabilities. Another significant distinguishing feature is our
algorithm’s tolerance for limited imprecision in the distances and angles
perceived by the robots, and limited relative error in the realization of
intended motions. Although formulated for robots moving in two dimensions, our
algorithm has a very natural extension to three (and even higher) dimensions,
with somewhat more involved correctness proofs. As it happens, our algorithm,
without modification, also solves Point Convergence in the fully asynchronous
(Async) scheduling model, when visibility is unbounded, without depending on
the ability to detect multiplicities in robot locations.

We also establish a complementary result that Cohesive Convergence cannot be
solved in the fully asynchronous (Async) scheduling environment, assuming that
robots are subject to very limited imprecision in measurements, even assuming
exact rigid motion and knowledge of $V$. Hence, Cohesive Convergence
demonstrates a separation between the power of autonomous robots operating in
a scheduling models with arbitrarily high but bounded asynchrony ($k$-Async),
and those operating in the presence of unbounded asynchrony (Async). As a
special case, this also provides a positive answer to a long-standing open
question: whether robots operating in a semi-synchronous (SSync) scheduling
environment are strictly more powerful than those operating in a fully
asynchronous (Async) scheduling environment.

Our results leave open several natural questions. Among these we note:

  1. 1.

Are there problems that serve to distinguish the power of robots operating in
the $k$-Async and SSync scheduling environments?

  2. 2.

Is (Cohesive) Point Convergence solvable in the fully asynchronous (Async)
scheduling environment if there is no error in perception or motion, or if
error is restricted to some arbitrarily small relative quantity arising from
motion alone?

  3. 3.

From our investigation and from the literature, it turns out to be natural to
consider Cohesive Convergence rather than simply Point Convergence. However,
it is not clear whether hull-diminishing or coherent algorithms, as natural as
they may be, can actually be avoided. In general, it remains open to
understand whether the resolution of Point Convergence necessarily solves
Cohesive Convergence as well.

As future work, it would be interesting to extend our results to consider
robots with non-zero extent, as in the _fat_ robots studied in [1, 7, 17].
Other natural constraints worth investigating include occlusion, as in [3, 5],
and collision avoidance, as in [28].

Acknowledgments. We would like to acknowledge the stimulating research
environment provided by the Bertinoro Workshop on Distributed Geometric
Algorithms, held in August 2019, where the seeds of this paper were planted.
In particular, we gratefully acknowledge the discussions with Pierre
Fraigniaud at the beginning of this work. This research project has been
supported in part by the Natural Sciences and Engineering Research Council
(Canada) under Discovery Grants A3583 and A2415, and by the Italian National
Group for Scientific Computation GNCS-INdAM.

## References

  * [1] Chrysovalandis Agathangelou, Chryssis Georgiou, and Marios Mavronicolas.  A distributed algorithm for gathering many fat mobile robots in the plane.  In Symposium on Principles of Distributed Computing (PODC), pages 250–259. ACM, 2013.
  * [2] Hideki Ando, Yoshinobu Oasa, Ichiro Suzuki, and Masafumi Yamashita.  Distributed memoryless point convergence algorithm for mobile robots with limited visibility.  IEEE Trans. Robotics Autom., 15(5):818–828, 1999.
  * [3] Subhash Bhagat, Sruti Gan Chaudhuri, and Krishnendu Mukhopadyaya.  Gathering of opaque robots in 3D space.  In 19th International Conference on Distributed Computing and Networking (ICDCN), pages 1–10. ACM, 2018.
  * [4] Subhash Bhagat and Krishnendu Mukhopadhyaya.  Computations Under Restricted Visibility.  Chapter 7 of Distributed Computing by Mobile Entities, pages 134–183, 2019.
  * [5] Kaustav Bose, Manash Kumar Kundu, Ranendu Adhikary, and Buddhadeb Sau.  Arbitrary pattern formation by asynchronous opaque robots with lights.  Theoretical Computer Science, 849:138–158, 2021.
  * [6] Michael Braun, Jannik Castenow, and Friedhelm Meyer auf der Heide.  Local gathering of mobile robots in three dimensions.  CoRR, abs/2005.07495, 2020.  URL: https://arxiv.org/abs/2005.07495.
  * [7] Sruti Gan Chaudhuri and Krishnendu Mukhopadhyaya.  Leader election and gathering for asynchronous fat robots without common chirality.  J. Discrete Algorithms, 33:171–192, 2015.
  * [8] Serafino Cicerone, Gabriele Di Stefano, and Alfredo Navarra.  Gathering of robots on meeting-points: feasibility and optimal resolution algorithms.  Distributed Computing, 31(1):1–50, 2018.
  * [9] Serafino Cicerone, Gabriele Di Stefano, and Alfredo Navarra.  Asynchronous arbitrary pattern formation: the effects of a rigorous approach.  Distributed Computing, 32(2):91–132, 2019.
  * [10] Serafino Cicerone, Gabriele Di Stefano, and Alfredo Navarra.  Embedded pattern formation by asynchronous robots without chirality.  Distributed Computing, 32(4):291–315, 2019.
  * [11] Serafino Cicerone, Gabriele Di Stefano, and Alfredo Navarra.  A methodology to design distributed algorithms for mobile entities: the pattern formation problem as case study.  CoRR, abs/2010.12463, 2020.  URL: https://arxiv.org/abs/2010.12463.
  * [12] Serafino Cicerone, Gabriele Di Stefano, and Alfredo Navarra.  “semi-asynchronous”: A new scheduler in distributed computing.  IEEE Access, 9:41540–41557, 2021.
  * [13] Mark Cieliebak, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro.  Distributed computing by mobile robots: Gathering.  SIAM J. Comput., 41(4):829–879, 2012.
  * [14] Reuven Cohen and David Peleg.  Convergence properties of the gravitational algorithm in asynchronous robot systems.  SIAM J. Comput., 34(6):1516–1528, 2005.
  * [15] Reuven Cohen and David Peleg.  Convergence of autonomous mobile robots with inaccurate sensors and movements.  SIAM J. Comput., 38(1):276–302, 2008.
  * [16] Andreas Cord-Landwehr, Bastian Degener, Matthias Fischer, Martina Hüllmann, Barbara Kempkes, Alexander Klaas, Peter Kling, Sven Kurras, Marcus Märtens, Friedhelm Meyer auf der Heide, Christoph Raupach, Kamil Swierkot, Daniel Warner, Christoph Weddemann, and Daniel Wonisch.  A new approach for analyzing convergence algorithms for mobile robots.  In Automata, Languages and Programming (ICALP), volume 6756 of Lecture Notes in Computer Science, pages 650–661. Springer, 2011.
  * [17] Jurek Czyzowicz, Leszek Gasieniec, and Andrzej Pelc.  Gathering few fat mobile robots in the plane.  Theoretical Computer Science, 410(6-7):481–499, 2009.
  * [18] Shantanu Das, Paola Flocchini, Nicola Santoro, and Masafumi Yamashita.  Forming sequence of geometric patterns with oblivious mobile robots.  Distributed Computing, 28:131–145, 2015.  doi:10.1007/s00446-014-0220-9.
  * [19] Mattia D’Emidio, Gabriele Di Stefano, Daniele Frigioni, and Alfredo Navarra.  Characterizing the computational power of mobile robots on graphs and implications for the euclidean plane.  Information and Computation, 263:57–74, 2018.
  * [20] Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro.  Distributed Computing by Oblivious Mobile Robots.  Morgan & Claypool, 2012.
  * [21] Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Giovanni Viglietta.  Distributed computing by mobile robots: Uniform circle formation.  Distributed Computing, 30(6):413–457, 2017.
  * [22] Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and P. Widmayer.  Arbitrary pattern formation by asynchronous oblivious robots.  Theoretical Computer Science, 407(1-3):412–447, 2008.
  * [23] Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Peter Widmayer.  Hard tasks for weak robots: the role of common knowledge in pattern formation by autonomous mobile robots.  In 10th International Symposium on Algorithms and Computation (ISAAC), volume 1741 of Lecture Notes in Computer Science, pages 93–102. Springer, 1999.
  * [24] Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Peter Widmayer.  Gathering of asynchronous robots with limited visibility.  Theoretical Computer Science, 337(1-3):147–168, 2005.
  * [25] Branislav Katreniak.  Convergence with limited visibility by asynchronous mobile robots.  In Structural Information and Communication Complexity (SIROCCO), volume 6796 of Lecture Notes in Computer Science, pages 125–137. Springer, 2011.
  * [26] David Kirkpatrick, Irina Kostitsyna, Alfredo Navarra, Giuseppe Prencipe, and Nicola Santoro.  Separating bounded and unbounded asynchrony for autonomous robots: Point convergence with limited visibility.  In 40th Symposium on Principles of Distributed Computing (PODC). ACM, 2021.