On the power of bounded asynchrony: convergence by autonomous robots with limited visibility

The main theoretical questions in all these environments are the same: what are the minimal operational 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 systems of autonomous mobile entities, which we refer to as robots, within the standard \(\mathcal {OBLOT}\) model (see, e.g. [2] and references therein). We focus on one fundamental task, called convergence, that asks for robots to congregate in a region of arbitrarily small diameter.

In the \(\mathcal {OBLOT}\) model, identical robots are free to move in a featureless spatial universe, typically the two dimensional Euclidean space. Very few papers deal with higher dimensions like the three dimensional space approached in [3‐6].

Robots operate under restrictions designed to elucidate what is essential in solving certain robot coordination objectives. Specifically, robots are viewed as points, and communicate only indirectly through their position which is visible to other robots within some, possibly bounded and unknown, visibility range. Robot motion is determined locally by a resident algorithm that depends only on current perceptions of the location of other robots, relative to some private coordinate framework. The activation of robots and realization of intended motions is governed by an adversarial, but fair, scheduler.

Computations in the \(\mathcal {OBLOT}\) model are very different from those in other distributed systems (e.g., message-passing networks): they are just continuous re-positionings of robots, realized by loosely coordinated activity of the individual robots. Computations start from some (typically unconstrained) initial configuration, and move towards some goal configuration. Permissible goal and intermediate configurations are expressed in terms of temporal geometric predicates.

A computational task simply specifies a subset of computations that fulfill the task, and an algorithm is said to solve the task if, under its control, starting from any permissible initial configuration, the robots produce a computation that fulfills the task 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, the primary distinction is between synchronous and asynchronous scheduling models.

In the semi-synchronous model (SSync), time is divided into discrete intervals, called rounds; in each round, the scheduler specifies a subset of the robots that perform some elementary activity in perfect synchronization. (The only constraint is activation fairness: every robot is activated within finite time and infinitely often.) When all robots are activated in every round, the model is said to be fully-synchronous.

In contrast, in the asynchronous model (Async), robots are activated at arbitrary times (constrained again by activation fairness), independently of the other robots, and the duration of individual activities, though finite, is unpredictable.

There are many studies on the feasibility of tasks and the complexity of algorithms in both the synchronous and asynchronous settings; Sect. 2 provides an overview of the most relevant related work. In spite of long and intensive research efforts, a fundamental question has remained unsettled: Is there any difference in computational scope between algorithms working within the scheduling models SSync and Async ? More precisely: Does the assumption of synchronous scheduling of activity make possible the solution of some task that is not solvable in the asynchronous setting?

In this paper, we provide an affirmative answer to the question. In fact, our results, which apply to realistic robots that operate with imprecise sensing, demonstrate an even stronger separation: between scheduling models with unbounded asynchrony (Async) and bounded asynchrony (what we call k-Async). In the latter the degree of asynchrony is bounded by an arbitrarily large but fixed k, that is, while any one robot is active, any other robot can be activated at most k times.

Most of the research concerning the limits of computation within the \(\mathcal {OBLOT}\) model (see Sect. 2 for a more comprehensive overview) has concentrated on specific tasks that fit under the general framework of pattern formation [5, 7‐11].¹ Among these, the task of point formation, where all robots are required to congregate (and remain) at the same point (not fixed in advance), has attracted particular attention due to its correspondence with the basic coordination task in swarm robotics called Gathering (or Rendezvous) [4, 12‐20]. The less stringent version of this task, called Point Convergence (hereafter simply Convergence) [21‐30], requires the 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 \) is eventually reached and maintained.

Previous investigations have examined Gathering and Convergence, taking into account a variety of different factors (e.g., synchronicity, shared knowledge of the environment, and inaccuracies in measurement and motion) assuming unlimited visibility. In brief, existing algorithms have been shown to solve Gathering assuming one or more of the following: (i) fully synchronous (FSync) scheduling, (ii) shared knowledge of a reference coordinate system, (iii)  absence of co-located robots in the initial configuration, or (iv) the use of non-computable geometric predicates. Under even slightly relaxed (SSync) scheduling assumptions, Gathering is known to be impossible in general, whereas Convergence is known to be solvable, provided multiplicities (i.e. the co-location of robots) can be detected, even with fully asynchronous (Async) scheduling.

Comparatively few investigations have focused on the limited visibility [1, 21, 27, 31‐34]. It is typically assumed that the visibility graph associated with the initial robot configuration is connected, and that the number of robots is not known, even approximately, obviously not an issue in the full visibility setting.

The design of successful algorithms for robots with limited visibility in the Async scheduling model, has come with the assumption of additional robot capabilities. For instance Gathering has been shown to be solvable if the local coordinate systems of all robots agree on the direction of the axes.

In the SSync scheduling model, the pioneering work of Ando et al. [21] (described in detail in Sect. 4.1) established the feasibility of Convergence, under limited visibility.

In subsequent work [27], Katreniak introduced the k-Async scheduling model.², that permits bounded asynchrony in robots’ activation, and presented a solution algorithm for Convergence in the 1-Async model (a solution under a more restricted version of the 1-Async scheduler was presented earlier in [19]). The existence of an algorithm to solve Convergence in the k-Async model, for \(k>1\), was left as an open question.

It is worth pointing out that, like all known algorithms that deal with limited visibility, the algorithms of Ando et al. and Katreniak have the property that, if two robots are initially within visibility range of each other, they remain mutually visible thereafter. Thus they solve an apparently more restricted variant of Convergence, that we call Cohesive Convergence.

The focus of this paper, as in those of Ando et al. [21] and Katreniak [27], concerns the Cohesive Convergence task for identical autonomous robots with bounded visibility (where the visibility radius is possibly unknown to the robots). 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 \). Furthermore, all robot pairs that are mutually visible in the initial configuration remain so thereafter.

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 [27]. However, even under slightly weaker assumptions, the same task 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.

In particular, our primary contributions are threefold: (i) a novel moderately error-tolerant algorithm that succeeds in the scheduling model k-Async, 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 the fully asynchronous scheduling environment Async, provided algorithms are required to tolerate a modest amount of imprecision in perception (yet significantly less than what can be tolerated by our k-Async algorithm). Furthermore, our construction shows the impossibility of even weaker forms of Cohesive Convergence, where visibility edges are allowed to be broken as long as the whole robot configuration remains connected. Our algorithm is described in its basic form in Sect. 4, with extensions, including error-tolerance, and three-dimensional generalization, outlined in Sect. 7. Even in the same scheduling environment, our algorithm is slightly simpler in formulation and provides a more general solution than its predecessors developed in [19, 21, 27]. In particular, the intended destination point for a robot in each step depends only on the directions to the pair of neighbours, among those that are relatively distant, that define the maximum angular range. Furthermore, distance and angle measurements to 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 \(\alpha \) that is at most 1/k.

As with the analysis of algorithms in [19, 21, 27], our proof of cohesive convergence involves (i) an argument that the edges of the initial visibility graph are preserved, and (ii) an argument that congregation, i.e., convergence to an arbitrarily small region, eventually takes place. Our analysis, presented in Sect. 5, 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, neighbour \(\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. (The reader might find a glance at Fig. 2 helpful in distinguishing between these models.) 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.

Our congregation argument is presented in Sect. 6. We start by observing, as was the case in [19, 21, 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 of that neighbourhood.

Demonstrating the impossibility of solving Cohesive Convergence in any environment that assumes exact measurement and control seems daunting, since, assuming motion is rigid, such assumptions might open up the possibility of encoding information, perhaps history, in the locations of robots. However, in Sect. 8, we show that algorithms that control more realistic robots (operating with even a very modest amount of imprecision in measurements) cannot solve Cohesive Convergence in a scheduling environment with no bound on asynchrony (other than a fairness condition that ensures that no robot is permanently locked out of activity). 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).

Our work raises several interesting questions, suitable for future research. Several of these are highlighted in our concluding section (Sect. 9).

The paper is organized as follows. In the next section, we review some relevant literature on Point Convergence. Section 3 specifies the model under which we approach the problem. Section 4 contains the description of our new algorithm. Section 5 is devoted to the analysis of the proposed algorithm concerning visibility properties. Section 6, instead, is devoted to prove the congregation property of the algorithm. Section 7 discusses some possible generalizations of the proposed algorithm in terms of error-tolerance and three-dimensional environment. Section 8 is devoted to prove the impossibility result for asynchronous robots. Finally, Sect. 9 provides conclusive remarks and challenging research directions for future work.

Almost all studies on pattern formation have assumed unlimited visibility, and that measurements and computations are free of error. The first question studied has been what patterns can be formed from a given initial configuration [35]. Assuming that robots share a common handedness (also called chirality), a sequence of results has shown that the set of formable patterns depends solely on the degree of symmetry (a parameter called symmetricity) of the initial configuration ([9, 35, 36]; see also [37]). In other words, with chirality, there is no distinction between the patterns formable from an initial configuration in SSync and Async. No similar general results are known without chirality.

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

For the converse question of which patterns can be formed from every initial configuration, there are only two possible candidate geometric patterns: point and uniform circle, and the latter only if the robots initially occupy distinct locations. The two tasks, Point Formation and Uniform Circle Formation, have been intensively studied assuming that the robots initially occupy distinct locations. Remarkably, both tasks have been shown to be solvable in Async even without chirality and with non-rigid movements³ [15, 38], assuming multiplicity detection⁴ in the case of Point Formation.

Observe that 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). It is known that this task, without agreement on the coordinate system, is unsolvable for \(n=2\) robots even in SSync [35]; expanding on this result, it has been shown that, without any additional capability of the robots (e.g., global coordinate system, multiplicity detection), it is unsolvable in SSync also for \(n>2\) [20]. Indeed Point Formation had been conjectured to be unsolvable in Async even with multiplicity detection and initially scattered robots (i.e., at distinct initial locations).

These basic impossibilities have further motivated the investigation of a weaker version of Point Formation, called Point Convergence (or simply Convergence) discussed in the next section, which requires the 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 \) is eventually reached and maintained.

The presence of even limited inaccuracy of the measurement of both distances and angles of the robots renders Point Formation impossible in SSync even with a global coordinate system and strong multiplicity detection [26]. On the other hand, Point Formation has been shown to be solvable with chirality in SSync even in presence of a limited tilt (less than \(\pi / 4\)) of the local compasses [18]. Further, with agreement on one axis, Point Formation is solvable in Async even in presence of occlusions (a robot \(\mathbb {X} \) looking at a robot \(\mathbb {Y} \) cannot see anything beyond \(\mathbb {Y} \) along the ray from \(\mathbb {X} \) that passes through \(\mathbb {Y} \)) and crash faults [39].

Related investigations on pattern formation with unlimited visibility include the study of: the impact of crash and Byzantine faults among the robots (e.g., [12, 13, 26, 39, 40]); the Embedded Pattern Formation task, where the pattern is given to the robots as visible points in the plane, solved in Async by robots without chirality [41]; and the Pattern Sequence task, where robots are required to form an ordered sequence of patterns, shown to be solvable in SSync by robots with chirality [42].

Very few investigations have focused on pattern formation in the limited visibility setting. In this setting, it is assumed that the visibility graph associated with the initial robot configuration is connected. It is has been shown that limited visibility drastically reduces the set of patterns that can be formed by robots in Async [34]. On the other hand, Point Formation is solvable in Async from any initial configurations if the robots are endowed with global consistency of the local coordinate system [32]. We are not aware of any investigation on pattern formation in the limited visibility setting that considers measurement inaccuracies.

The basic impossibilities of Point Formation have further motivated the investigation of a weaker version of the task called Point Convergence (or simply Convergence), which requires the 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 \) is eventually reached and maintained. Observe that, by definition, any solution to Point Formation under some assumptions automatically solves Point Convergence under the same assumptions.

We treat robots as dimensionless entities (points), free to move in any direction within \(\mathbb {R}^2\); a discussion of extensions of our results to motion in \(\mathbb {R}^3\) is left to Sect. 7. We use X, sometimes subscripted, 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 sensors 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)=\{P: |X(t) P| \le 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)| \le 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 are assumed to be error-free.

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.

The behaviour of each robot can be described as the alternation of finite length activity intervals with finite length inactivity intervals. Each activity 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. The duration of each Compute and Move phase is assumed to be finite,⁹ 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.

Since the local memory of robots is volatile, it cannot be assumed that memory contents persist between activity cycles. Accordingly, the control algorithm is oblivious: the Compute step is independent of past actions and computations.

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.

Since robots in the \(\mathcal {OBLOT}\) model can only observe the positions of others and then move, a task to be performed is expressed in terms of a temporal geometric predicate. From some point in time onward, the configurations formed by the robots’ positions must satisfy this predicate.

Let \({\mathcal {R}}\) be an arbitrary collection of robots. The Point Convergence task requires the robots in \({\mathcal {R}}\), starting in an arbitrary connected configuration¹¹ where they are all inactive, to become arbitrarily close. More precisely, Point Convergence is the task defined by the temporal geometric predicate:A more constrained version is the Cohesive Convergence task that additionally requires that, at all times, the visibility graph is a supergraph of the initial visibility graph. In fact, it is defined by the temporal geometric predicate:An algorithm \({{\mathcal {A}}}\) is said to solve the Point Convergence (or Cohesive Convergence) task if it satisfies the corresponding predicate, starting from any valid initial configuration of robots (of arbitrary size), under any (possibly adversarial) scheduler that respects the associated synchronization model. As previously observed, even though Cohesive Convergence is strictly more constrained than Point Convergence, all known algorithms for Point Convergence also solve Cohesive Convergence.

The algorithm of Ando et al. [21] proceeds as follows: upon activation, each robot \(\mathbb {X} \)

The algorithm of Ando et al. is formulated in the SSync scheduling model. It assumes:The algorithm of Katreniak [27] has many similarities to that of [21]: upon activation, each robot \(\mathbb {X} \)Katreniak’s algorithm is formulated in the 1-Async model. It assumes:The most apparent difference between the algorithms of Ando et al. and Katreniak lies in the specification of their safe regions (see Fig. 3). For a robot \(\mathbb {Y} \) located at point Y viewing a robot \(\mathbb {X} \) located at point X, Ando et al. specify a safe region as a disk with radius V/2 centred at the midpoint between X and Y. Katreniak’s safe region is formed by the union of two disks, one with radius |XY|/4 centred at the point \((X + 3 Y)/4\), and the other with radius \((V_{\mathbb {Y}}-|X Y|)/4\) centred at Y.

The correctness of the algorithms for Point Convergence in both [21, 27] rest on two observations: (i) visibility preservation the choice of safe region guarantees that all robot pairs that start or become mutually visible 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.

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

The Look, Compute, and Move phases of the KKNPS algorithm take the following form:

Look In the KKNPS algorithm, as in earlier schemes, each robot \(\mathbb {Y} \) starts an activity 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, as in [27], in each activity 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}}/4\) are referred to as distant neighbours of \(\mathbb {Y} \); others are close neighbours. Note that the notions of close and distant are robot-specific and configuration-dependent. In particular (i) \(\mathbb {Y} \), by definition, always has at least one distant neighbour; (ii) \(\mathbb {X} \) could be a close neighbour of \(\mathbb {Y} \) while \(\mathbb {Y} \) is a distant neighbour of \(\mathbb {X} \); and (iii) a distant neighbour of \(\mathbb {Y} \) could, without changing its actual distance, become a close neighbour of \(\mathbb {Y} \) (and vice versa).

Compute 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)| \le 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 [21, 27], 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/2. 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 Sect. 5.

Move 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 details are set out in Sect. 4.2.2. The target destination in turn is designed to ensure that the convex hull of the robot locations shrinks monotonically, and converges to a point.

Algorithm KKNPS Summarizing, Algorithm KKNPS is sketched in Algorithm 1 from the point of view of a robot \(\mathbb {Y} \). It is worth noting that the input is represented by the information acquired during the Look phase; the body of the algorithm represents the Compute phase; whereas the Move phase is simply realized by the movement toward the computed target c.

Though superficially similar, there is an important difference between the SSync and 1-NestA models: in the latter, if an activity interval of robot \(\mathbb {Y} \) is nested within an activity 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 during repeated activations of \(\mathbb {Y} \), nested within one activation of \(\mathbb {X} \), \(\mathbb {Y} \) may observe \(\mathbb {X} \) at many different positions on its determined trajectory. Furthermore, even if \(\mathbb {X} \) is stationary at some location X, \(\mathbb {Y} \) may view it from up to k different locations (cf. Fig. 13). 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 safe regions scaled by something slightly larger than 1/k could lead to a break in visibility.

In asynchronous settings, it is certainly possible that a pair of robots under the control of the KKNPS algorithm could become mutually visible, only to have this visibility be 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)| \le 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:

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

In certain settings, the parameter k (the bound on potential asynchrony) may not be known precisely. One such scenario is where the duration of all activity intervals is bounded from above and (away from zero) below. Nevertheless, the KKNPS algorithm works correctly with any conservative upper bound on k at the cost of slowing down convergence in a proportional way.

We have already observed that, in the absence of any global information on the initial configuration, even an arbitrarily small amount of absolute error in distance or angle measurements, or in the actual destination relative to the trajectory to the intended destination, cannot be tolerated by algorithms that solve Point Convergence, even in fully synchronous scheduling environments. Nevertheless, the KKNPS algorithm can be modified to tolerate a modest amount of relative error.

The KKNPS algorithm 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.

Recall that the visibility region of robots was defined to be a closed set. However, the KKNPS 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, we can modify the notion of visibility region to accommodate a more realistic soft visibility threshold. With this modification, there are two thresholds V and \(V^+\); robots at distance less than or equal to V are guaranteed to be visible, those at distance greater than \(V^+\) are guaranteed to be invisible, and those whose distance is between V and \(V^+\) may or may not be visible. Since the KKNPS algorithm works correctly using any lower bound on the threshold V, and the distance to a robot’s current furthest neighbour provides a lower bound on \(V^+\), it suffices to use that distance scaled by \(V/V^+\) as a conservative bound on V.

Finally, we note that in the event that the visibility threshold 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.

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{A P_{i-1}}\) and the segment \(\overline{P_{i-1} P_i}\), taking \(P_0 = B\), is fixed at \(\psi \), for all \(i \ge 1\). (Fig. 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{A P_0}\) and \(\overline{A P_{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{A P_{i-1}}\) and \(\overline{A P_i}\) decreases with i, the sum \(\sum _i \gamma _i\) diverges. To see this, let \(d_i\) denote the length of the chord \(\overline{A P_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\),Since \(d_0 =1\), and \(d_i - d_{i-1} \le 1\) (by the triangle inequality), it follows by induction on i that \(1 + i(1 - \psi ^2/2) < d_i \le 1 + i\), for \(0 \le i \le n-3\). Since the scheduler maintains the distance from point A to the location of robot \(\mathbb {X} _i\) close to \(d_i\), choosing \(\psi \) small enough guarantees that the separation between successive robots remains close to 1. Hence each robot on the chain remains visible only to its initial neighbours.

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 \ge \sin \gamma _i = \frac{\sin \psi }{d_i} \ge \frac{\sin \psi }{i+1}\). It follows that \(\sum _{i=1}^{n-3} \gamma _i \ge \sin \psi \ln \frac{n-3}{e}\). Thus it will suffice to choose n large enough that \(\sin \psi \ln \frac{n-3}{e} \ge 3 \pi /8\), i.e., \(n \ge 3+ e^{\frac{3 \pi }{8 \sin \psi }+1}\).

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'\) some non-zero distance \(\zeta \) away from A into the sector CAB. By the symmetry of the local configuration, we can assume that \(|A'C| \le |A'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 \le i \le n-3\), in succession, all of the robots \(\mathbb {X} _0, \mathbb {X} _1, \ldots , \mathbb {X} _{i-1}\) onto (or close to) 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 Fig. 19 (center) and (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 chords \(AP_{i-1}\) and \(AP_{i}\) defines what we call the ith sliver (see Fig. 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 - \varphi _0, \pi ]\), where angle \(\varphi _0\) is chosen to be sufficiently small (relative to \(\psi \) and \(1/n^2\)). This slight slack permits termination of each flattening step and ensures that when the flattening of the ith sliver is complete the sum of all turn angles on the chain formed by \(\mathbb {X} _0, \ldots , \mathbb {X} _{i}\) is at most \(i \varphi _0\) and hence all of the robots lie within distance \(i^2 \varphi _0/2\) of the chord \(A P_{i}\). Hence, when all slivers have been flattened, robot \(\mathbb {X} _B\) lies within distance \(n^2 \varphi _0/2\) of the chord \(AP_{n-3}\).