Continuous Protocols for Swarm Robotics

Abstract

We consider simple models of swarms of identical, anonymous robots: they are points in the plane and “see” only their neighbors (robots within distance one). We will deal with distributed local protocols of such swarms that result in formations like “gathering at one point”. The focus will be on protocols assuming a continuous time model. We present upper and lower bounds on their run time and energy consumption, and compare different protocols both theoretically and experimentally.

1 Introduction

Envision a scenario where n mobile robots, each having a limited viewing range, are placed in the Euclidean plane and are supposed to establish a certain formation. To reach this formation, each robot has to plan and perform its movement based solely on the positions of the other robots within its viewing range, which we normalize to 1. In particular, the robots are not provided with global view, communication, or long term memory.

This chapter considers one of the most basic formation problems: the Gathering problem. Here, the n robots must move such that, eventually, they gather at a single, not predetermined point. While performing their protocols, it is crucial that the visibility graph spanned by the robots stays connected; if a robot loses sight of all other robots, no deterministic, local protocol can be guaranteed to reconnect the lost robot to the remaining formation.

Most protocols for such formation problems are based on some kind of discrete round model. For example, Ando et al. [1] and Degener et al. [4] show that gathering can be achieved with a simple protocol by robots with a limited visibility in a synchronous, discrete time model in ${\text {O}\left( n^2\right) }$ rounds. For the same problem with an unlimited viewing range, Cohen and Peleg [3] analyze a simple algorithm in several asynchronous time models. Further publications consider the Gathering problem in similar time models, see for example [2, 6, 9,10,11, 16, 17].

All of the above models have in common that they are based on the so-called Look-Compute-Move (LCM) model. That is, the robots act in rounds, where each round consists of a Look operation, a Compute operation, and a Move operation. During the Look operation, a robot determines the positions of all visible robots in its vicinity. During the Compute operation, the observed information is used to determine a target point. Finally, during the Move operation, the robot moves towards the previously computed target point. The specific models differ in whether these operations are executed synchronously or asynchronously (or something in between).

A different approach is to use a continuous time model. This was first done by Gordon et al. [8] for the Gathering problem. In such a continuous time model, all robots perpetually and at the same time measure and adjust their movement paths. This causes the trajectories of the robots, who are assumed to have some constant maximum moving speed, to become (continuous) curves. While this continuous motion model is somewhat idealized and might seem unrealistic – given that we assume there is no delay between the robots’ sensors and actors – it is comparatively close to real applications [14].

This chapter presents some of the more recent results that introduced general techniques to analyze the time required by such distributed robot formation protocols in the continuous time model to reach their goal and discusses other aspects specific to this model.

Chapter Outline. We continue with a formal model description and with the introduction of continuous robot formation protocols in Sect. 2. Afterward, we collect some auxiliary results in Sect. 3 that will be used throughout the chapter. In Sect. 4 we introduce a general class of (not necessarily distributed) robot formation protocols, so-called contracting protocols, and study their gathering time. Section 5 introduces a specific protocol of this class and sketches the proof that this protocol solves the gathering problem in asymptotical optimal time. We conclude this chapter in Sect. 6, where we discuss the issue of collisions and how to avoid them.

2 Model Description and Continuous Protocols

Consider a set of n autonomous, mobile robots in the Euclidean plane $\mathbb {R}^2$. The robots have no spatial dimension and each of them has its own, local coordinate system. In particular, there is no common “origin” notion and no common directional notions like “left” or “right”. All robots have a visual range of 1, allowing them to perceive other robots that are within this distance and to determine the relative position of such robots. However, neither can robots distinguish other robots from one another nor is there any form of multiplicity detection: a robot can only distinguish whether there is either no robot or at least one robot at a given position. There is a continuous notion of time and we assume robots move with a maximum speed of 1. We assume an idealized sensor-actor mechanism, allowing a robot to act instantly on any data perceived from within its visual range.

In order to convey the basics and characteristics of continuous robot formation problems (in contrast to their more standard discrete time pendants), we concentrate on the probably most basic formation problem: gathering.

Definition 1

( Problem). Consider n autonomous, mobile robots in the Euclidean plane. In the Gathering problem, we seek to gather all robots at a single point.

A (gathering) protocol is an algorithmic description that takes the current robot positions and determines how each robot moves. We are mostly interested in distributed protocols, where each robot determines its movement by the same algorithm that uses only information available to the respective robot (basically the relative positions of other robots within its visual range). The quality of a protocol is measured by its gathering time, the worst-case time (over the set of all possible initial robot positions) required by the protocol to gather all robots.

General Notation. Before we dive deeper into the specifics of continuous robot formation protocols, we introduce some general notation. For an integer $m \in \mathbb {N}$ define . For $x \in \mathbb {R}^2$ we use ${||}x{||}_2$ to denote the Euclidean norm (vector length) of x. For $S_1, S_2 \subseteq \mathbb {R}$ and $c_1, c_2 \in \mathbb {R}$ define . For $x, y \in \mathbb {R}^2$ let denote the signed¹ angle formed by the vectors x and y.

Fix an arbitrary ordering of the n robots. A configuration $c = {(c_i)}_{i=1}^n$ is a vector whose i-th element $c_i \in \mathbb {R}^2$ specifies the positions of the i-th robot. Define the polygon $\text {CH}_c \subseteq \mathbb {R}^2$ as the convex hull of all robot positions in configuration c. Furthermore, let be the set of robots that are at the boundary of the configuration’s convex hull. Similarly, let $\text {Corn}_c \subseteq \text {Bord}_c$ be the set of robots that are at a vertex of the polygon $\text {CH}_c$. A robot from $\text {Bord}_c$ is called border robot and a robot from $\text {Corn}_c$ is called corner robot. The diameter of configuration c is the maximum distance between any two robots.

The visibility graph $G_c = (V_c, E_c)$ of configuration c is the Euclidean graph whose vertices are the robots’ positions and in which two vertices are connected by an edge if and only if the two corresponding robots are within viewing range of each other. More formally, and . A configuration is called connected if $G_c$ is connected. We use $\mathcal {C}_n$ to denote the set of all connected configurations of n robots.

Continuous Protocols. A continuous robot formation protocol $\mathcal {P}$ specifies how, at any time $t \ge 0$, each robot calculates its velocity vector, which dictates the robot’s current speed and its movement direction. Given a continuous robot formation protocol $\mathcal {P}$, let $c(t) = {\bigl (c_i(t)\bigr )}_{i=1}^n$ be the configuration at time t, such that the function $c_i:\mathbb {R}_{\ge 0} \rightarrow \mathbb {R}^2$ is the trajectory of the i-th robot. For $i \in {[}n{]}$ and $t \ge 0$ let $v_i(t)$ denote the velocity vector of the i-th robot at time t. That is, at time t robot i moves with speed ${||}v_i(t){||}_2$ in direction $v_i(t)$. We use as a shorthand for the speed of robot i at time t.

The trajectories $c_i$ are continuous but not necessarily differentiable. Indeed, robots can change their speed and movement direction non-continuously, resulting in a non-differentiable trajectory. However, natural protocols have right-differentiable trajectories, and we restrict our study to such protocols. In particular, this allows us to see robot i’s velocity vector $v_i:\mathbb {R}_{\ge 0} \rightarrow \mathbb {R}^2$ as the (right) derivative of $c_i$ and we can write $v_i = {\dot{c}}_i$, where the differentiation is understood to be a right derivative whenever necessary.

It will be useful to consider how robots move relative to each other. For this purpose, we define the angles . That is, $\beta _{i, j}(t)$ is the signed angle between the velocity vector of robot i and the line segment connecting robot i and robot j.

Figure 1 illustrates the notions introduced above.

Fig. 1.

(a) An example configuration c for $n = 13$ robots with the corresponding visibility graph $G_c$ and the convex hull $\text {CH}_c$. The convex hull has 7 border robots, 6 of which are also corner robots. (b) The current movement vector $v_i(t)$ of a robot i, its current relative positional angle $\beta _{i, j}(t)$ with respect to robot j and example trajectories (in blue). (Color figure online)

3 Auxiliary Results

This section collects some basic results that turn out to be useful in the analysis of continuous robot formation protocols. We start with some simple trigonometric inequalities.

Lemma 2

• (a) For $\alpha \in {[}0, \pi /2{]}$ we have $\cos \alpha \ge 1 - 2\alpha /\pi$.

• (b) For $\alpha \ge 0$ we have $\cos \alpha \ge 1 - {\alpha }^2/2$.

• (c) For $\phi \in {[}0, 1{]}$ and $\alpha \in {[}0, \pi {]}$ we have $\cos (\phi \cdot \alpha ) + \cos \bigl ((1 - \phi ) \cdot \alpha \bigr ) \ge 2 \cdot {(1 - \alpha /\pi )}^2$.

Proof

• (a) The statement follows from basic calculus by realizing that the graph of $f(x) = 1 - 2x/\pi$ is a secant line that intersects the graph of $\cos (x)$ at $x = 0$ and $x = \pi /2$.

• (b) The statement follows by realizing that $\cos \alpha$ and $1 - {\alpha }^2/2$ are equal for $\alpha = 0$ and that the first term’s derivative ($-\sin \alpha$) is as least as large as the second term’s derivative ($-\alpha$) for any $\alpha \ge 0$.

• (c) For $x, y \in \mathbb {R}$ we have the trigonometric identity $\cos x + \cos y = 2 \cdot \cos \bigl ((x + y)/2 \bigr ) \cdot \cos \bigl ((x - y)/2 \bigr )$ (see [15, Identity 4.21.8]). We apply this to the left-hand side of the desired inequality and calculate

  

  (1)

  The first inequality uses . Thus, the cosine in the expression is minimized when $(2\phi - 1)/2 \cdot \alpha = \alpha /2$. The second inequality uses the lemma’s first statement.    $\square$

The next lemma is central for analyzing the gathering time of protocols. Our general progress measure is based on how the robots’ convex hull changes over time. We quantify this change by studying how the distance between neighboring corner robots changes. To this end, the following lemma expresses the change in the distance between two robots i and j in terms of their current speeds $s_i(t)$ and $s_j(t)$ and their direction of movement relative to each other (the angles $\beta _{i, j}(t)$ and $\beta _{j, i}(t)$ between their velocity vectors and their connecting line). See Fig. 2 for an illustration.

Lemma 3

Consider a robot formation protocol $\mathcal {P}$ and fix two robots i and j. The distance between i and j at time t changes with speed

$$\begin{aligned} {\dot{d}}(t) = -s_i(t) \cdot \cos \beta _{i, j}(t) - s_j(t) \cdot \cos \beta _{j, i}(t). \end{aligned}$$

(2)

Proof

Define $D:\mathbb {R}_{\ge 0} \rightarrow \mathbb {R}^2, t \mapsto c_j(t) - c_i(t)$, such that $d(t) = {||}D(t){||}_2$. We use $D_x(t)$ to refer to the x-component of D(t) and, similarly, $D_y(t)$ to refer to the y-component of D(t). Fix a time $t \ge 0$. Without loss of generality, we can translate and rotate the coordinate system such that $D(t) = \bigl (d(t), 0\bigr )$. This immediately yields

(3)

Note that ${\dot{D}}_x(t)$ is the x-component of ${\dot{D}}(t)$, which can be written as

(4)

Together, Eqs. (3) and (4) imply the lemma’s statement.   $\square$

Fig. 2.

Illustration of Lemma 3

4 Contracting Robot Formation Protocols

A natural property of protocols that solve the Gathering problem is that robots move “towards each other”, causing the convex hull of all robot positions to contract over time. In the following we define the class of contracting robot formation protocols – which formalizes this intuitive property – and prove general upper and lower bounds for this class.

Define as the number of vertices of the polygon $\text {CH}_{c(t)}$. Let $m_1(t), m_2(t), \dots , m_{p(t)}(t)$ denote the vertices ordered counterclockwise along the boundary of $\text {CH}_{c(t)}$ (starting at an arbitrary vertex). For convenience, define and .

Definition 4

(Length). The length $\mathfrak {l}(t)$ of the configuration at time t is

(5)

We use the shorthand to denote the length of the initial configuration.

Note that the robots have solved the Gathering problem at time t if and only if $\mathfrak {l}(t) = 0$. This property (and the fact that most reasonable protocols do not increase a configuration’s length) make the length a good way to measure the progress of a gathering protocol. Next we define a quite general class of (not necessarily distributed) robot formation protocols. The definition, which is originally from [13], simply requires that corner robots move with maximum speed in some direction within the robots’ convex hull.

Definition 5

(Contracting [13]). Consider a continuous robot formation protocol $\mathcal {P}$. We say $\mathcal {P}$ is contracting if for any time $t \ge 0$ with $\mathfrak {l}(t) > 0$ each corner robot $i \in \text {Corn}_{c(t)}$ moves with speed $s_i(t) = 1$ along the velocity vector $v_i(t) \in (m_{\iota - 1}(t) - m_{\iota }(t)) \cdot \mathbb {R}_{\ge 0} + (m_{\iota + 1}(t) - m_{\iota }(t)) \cdot \mathbb {R}_{\ge 0}$.

See Fig. 3 for an illustration.

Fig. 3.

Possible movement vectors for a contracting protocol. Note that the velocity vectors of corner robots have all the same length (1), while the border robot may move at a slower speed. The movement of robots within the convex hull is completely unrestricted.

Even though Definition 5 does not specify the movement of general border robots, it has an interesting implication for their movement. Consider a border robot $j \in \text {Bord}_{c(t)} \setminus \text {Corn}_{c(t)}$ between two corner robots $i_1, i_2 \in \text {Corn}_{c(t)}$ at time t of a contracting robot formation protocol $\mathcal {P}$. Assume that j “falls behind” at time t, such that for any small enough $\epsilon > 0$ j is a corner robot (at a position different from $i_1$ and $i_2$) in configuration $c(t+\epsilon )$. Definition 5 requires that j moves with speed 1 towards the line connecting $i_1$ and $i_2$ for any such $\epsilon$. In the worst case this line moves with a speed of at most 1 away from j (if both $i_1$ and $i_2$ move accordingly). Thus, the distance between j and the line connecting $i_1$ and $i_2$ cannot increase at time $t + \epsilon$. But if that holds for any $\epsilon > 0$, j cannot leave the line in the first place. In other words, contracting protocols will not create new corners along the robots’ convex hull.

The above phenomenon illustrates an important aspect of continuous strategies and is also known as Zenoness (see [8]). The continuous nature of the system – which allows for an instant and continuous course correction – makes it possible that collinear robots (like corner robots and any border robots between them) remain collinear.

4.1 Gathering Time of Contracting Protocols

With the above notions we can formulate a general result that bounds the gathering time of any contracting robot formation protocol.

Theorem 6

([13]). Consider a continuous robot formation protocol $\mathcal {P}$ started in a configuration of n robots and of diameter $\Delta$. If $\mathcal {P}$ is contracting, then it has gathering time at most $\pi \cdot n \cdot \Delta /8$.

Proof

Fix a time t and consider the convex hull $\text {CH}_{c(t)}$ formed by the robots’ positions at time t. The robots have gathered at time t if and only if the length $\mathfrak {l}(t)$ of the robots’ convex hull equals zero. We show that at any time t with $\mathfrak {l}(t) > 0$, the configuration’s length decreases with a speed of at least 8/n. Since the initial length is at most $2\pi \cdot \Delta /2$, this implies the theorem’s statement.

So fix a time $t \ge 0$ with $\mathfrak {l}(t) > 0$. Recall the definition of the vertices $m_1(t), m_2(t), \dots , m_{p(t)}(t)$ of the robots’ convex hull and of the configuration’s length $\mathfrak {l}(t) = \sum _{\iota = 1}^{p(t)} {||}m_{\iota }(t) - m_{\iota - 1}(t){||}_2$. To avoid double indices, we make a slight abuse of notation and identify $\iota$ with one of the robots positioned on $m_{\iota }(t)$. In particular, we write $v_{\iota }(t)$ for the velocity vector of the robots positioned at $m_{\iota }(t)$. Similarly we write $\beta _{\iota ,\iota -1}(t)$ and $\beta _{\iota -1,\iota }(t)$ for the corresponding angles between robots positioned at $m_{\iota }(t)$ and $m_{\iota -1}(t)$. Note that, since the robot formation protocol $\mathcal {P}$ is contracting, these vertices move with speed $s_{\iota }(t) = 1$. Define as the distance between the corner robots at $m_{\iota }(t)$ and $m_{\iota - 1}(t)$. By Lemma 3

$$\begin{aligned} {\dot{d}}_{\iota }(t) = -\cos \beta _{\iota , \iota -1}(t) -\cos \beta _{\iota -1, \iota }(t). \end{aligned}$$

(6)

For $\iota \in {[}p(t){]}$ let $\alpha _{\iota }(t) \in {[}0, \pi {]}$ denote the inner angle of the polygon $\text {CH}_{c(t)}$ at vertex $m_{\iota }(t)$. Since the robot formation protocol $\mathcal {P}$ is contracting, the velocity vector $v_{\iota }(t)$ points towards the inside of the robots’ convex hull, such that $\alpha _{\iota }(t) = \beta _{\iota , \iota -1}(t) + \beta _{\iota , \iota +1}(t)$. Since $\mathfrak {l}(t) = \sum _{\iota = 1}^{p(t)} d_{\iota }(t)$, we can take the derivative of $\mathfrak {l}(t)$ and apply Eq. (6) to get

(7)

Applying Lemma 2(c) to the last expression yields

(8)

Now we first use the Cauchy-Schwarz inequality and then that the sum of internal angles of a polygon with p vertices equals $(p-2) \cdot \pi$ to get

(9)

As argued at the beginning of the proof, this yields the desired statement.   $\square$

In Theorem 6 we did not restrict the configuration to be connected. As long as the protocol (which could be executed by an omniscient observer that knows where to move the robots) is contracting, the stated bound holds. If we start in a connected configuration, as required for any truly distributed protocol restricted by the robots’ visual range, we see that the initial diameter is at most $n-1$, yielding a bound of $\pi /8 \cdot n^2$. In fact, if instead of bounding the initial configuration’s length by $2\pi \cdot \Delta /2$ in the proof of Theorem 6 we use the bound $\mathfrak {l}(0) \le 2(n-1)$ (which can easily be shown, see [12]), we get the following corollary:

Corollary 7

([13]). Consider a continuous robot formation protocol $\mathcal {P}$ started in a connected configuration of n robots. If $\mathcal {P}$ is contracting, then it has gathering time at most $n^2/4$.

4.2 Worst-Case Contracting Protocols

It is not difficult to see, that the upper bound of ${\text {O}\left( n^2\right) }$ from Corollary 7 is tight in the sense that there are contracting protocols and corresponding initial configurations for which the gathering time is at least ${\Omega }\left( n^2\right)$. In fact, if we assume that all robots are positioned at corners of a regular polygon and move towards their counterclockwise neighbor, we get a situation that resembles the so-called n-bugs problem [18], which is known to have a quadratic convergence speed. The next lemma provides this result and a simple proof using our terminology.

Lemma 8

There is a contracting robot formation protocol $\mathcal {P}$ and a connected initial configuration $c \in \mathcal {C}_n$ such that the gathering time is at least $n^2/(2\pi ^2)$.

Proof

Assume the initial configuration is such that the robots’ convex hull is an n-sided regular polygon with edge length 1 (the robots’ visual range) and assume that each robot moves with speed 1 towards its counterclockwise neighbor. Since all robots move symmetrically, the configuration will stay an n-sided regular polygon (which eventually degenerates to a point) at any time $t \ge 0$. Now fix a time $t \ge 0$ with $\mathfrak {l}(t) > 0$. Consider Eq. (7) from the proof of Theorem 6, which gives the speed at which the configuration’s length changes. Since the current convex hull is an n-sided regular polygon, we have for each that $\beta _{\iota , \iota + 1}= 0$ and $\beta _{\iota , \iota - 1}= (n-2) \cdot \pi /n= \pi - 2\pi /n$. With this, Eq. (7) simplifies to

(10)

where the inequality uses Lemma 2(b). Since the initial configuration has length n, this yields the lemma’s claim.    $\square$

See Fig. 4 for an illustration of Lemma 8. When introducing the Move-on-Bisector protocol in the next section, we will also encounter a “best-case” contracting protocol (global Move-on-Bisector).

Fig. 4.

Configuration, velocity vectors, and trajectories of the n-bug problem from Lemma 8.

5 Near-Optimal Continuous Protocols for Gathering

Section 4 showed that any contracting robot formation protocol has at most quadratic gathering time and that this bound is tight in the sense that there are contracting protocols (and corresponding initial configurations) that have at least quadratic gathering time. However, there is still hope that a specific contracting protocol can have a much better – maybe even linear – gathering time. This is indeed true and has been proved for the so-called Move-on-Bisector protocol in [5]. This section provides a sketch of this result; see [5] for the full proof (and further related results).

5.1 The Move-on-Bisector Protocol

At each time t, each robot i observes all positions of its neighbors (i.e., other robots within its visual range). It then computes the local convex hull $\text {CH}_i(t)$ of its own and any observed positions. Given this local convex hull, robot i performs the following actions:

• (a) If i is on a vertex of $\text {CH}_i(t)$, it moves with speed 1 along the angle bisector of this vertex.

• (b) If i is not on a vertex but on the boundary of the local convex hull, it moves with the corresponding line such that it stays on it and maintains the ratio of distances between its two neighbors on the boundary.

• (c) If i is strictly inside $\text {CH}_i(t)$, it does not move.

This protocol was originally suggested by Gordon et al. [8] (using a slightly different description and not under this name). See Fig. 5a for an illustration.

Fig. 5.

(Local) Move-on-Bisector vs. global Move-on-Bisector. Note that the lengths of the velocity vectors is not accurate. (Color figure online)

Global – A Best-Case Contracting Protocol. Before we analyze the Move-on-Bisector protocol, let us give an intuition why it should be fast. Remember that our definition of contracting robot formation protocols is not restricted to distributed protocols. So, consider a global variant of Move-on-Bisector, where the only difference in the protocol description is that robots use the global convex hull $\text {CH}_{c(t)}$ instead of their respective local convex hull $\text {CH}_i(t)$. This is obviously not a distributed protocol, as robots do not have, in general, knowledge of the global convex hull. However, it is a contracting protocol (see also Fig. 5b). In fact, in a sense this is an “optimal” contracting gathering protocol: Using an analysis similar to Sect. 4.1, one can see that, as long as the robots have not yet gathered, the length of the configuration at time t decreases at a constant rate, yielding a gathering time that is linear in the diameter $\Delta$ of the initial configuration. Since robots move at unit speed, this is asymptotically optimal.

Unfortunately, we cannot analyze the actual Move-on-Bisector protocol in the same way as its global counterpart. Since robots move not along the vertices of the global convex hull, the length of the configuration does not necessarily decrease at a constant speed. However, the next section introduces a “local” variant of a configuration’s length, which we call stretch. With some additional work, we can show (Sect. 5.3) that not only does this stretch decrease at a constant rate but it is also linear in the configuration’s diameter. This yields the same asymptotical optimal guarantee as the global Move-on-Bisector protocol.

5.2 Preliminaries

Instead of using the robots’ convex hull and its circumference as a progress measure, our progress measure for the Move-on-Bisector protocol is based on the simple polygon spanned by the robots (the configuration polygon) and its circumference (its stretch).

Definition 9

(Configuration Polygon). Consider a configuration c with its visibility graph $G_c$. This graph defines a simple polygon $\mathrm{Pol}_c$. We call this polygon the configuration polygon of configuration c.

Note that the configuration polygon or parts of it might be degenerated (e.g., to a line), as can be seen in the example from Fig. 6.

Define q(t) as the number of vertices of the configuration polygon $\text {Pol}_{c(t)}$. Let $w_1(t), w_2(t), \dots , w_{q(t)}(t)$ denote the vertices ordered counterclockwise long the boundary of $\text {Pol}_{c(t)}$ (starting at an arbitrary vertex). For convenience, define and . Similar to the length of the configuration we can define the stretch of a configuration as follows:

Definition 10

(Stretch). The stretch of the configuration at time t is

(11)

We use the shorthand to denote the stretch of the initial configuration.

For a vertex $w_{\iota }(t)$ of the configuration polygon at time t we define $\alpha _{\iota }(t) \in {[}0, 2\pi {)}$ as the inner angle of the configuration polygon at that vertex. We use to characterize the set of all convex angles of the polygon and for the remaining (concave) angles. See Fig. 6 for an illustration of the notions defined above.

Fig. 6.

The configuration polygon and its vertices of a configuration c and two examples for the inner angles $\alpha _{\iota }(t)$ (the image omits the time parameter to improve readability). Note that it is degenerated at several places, causing a single robot position to represent possibly multiple vertices (at most 6 by Lemma 14). The stretch is the length of the red boundary (where degenerated parts are counted twice).

An important observation is, that a robot at the vertex $w_{\iota }$ of the configuration polygon at time t is not necessarily on the vertex of its local convex hull. Indeed, if the inner angle at that vertex is concave (${>}\pi$), it may be inside its local convex hull and may, thus, not move. However, any robot at a vertex that forms a convex inner angle is guaranteed to move, as they must be on a vertex of their local convex hull. These are exactly the vertices $w_{\iota }$ with $\iota \in \mathcal {W}$.

Note that while the trajectory of the robots is continuous, the direction in which a robot moves may change in a non-continuous way. This may happen if the visibility graph changes. Moreover, a change in the visibility graph may also influence the length of the current configuration in a non-continuous way. However, it is not hard to see (and it has been proved in [8]) that once two robots are within visual range, they will not lose visibility. Thus, there can be only a finite amount of these discontinuities. Moreover, by the definition of the visibility graph, the number of the configuration polygon’s vertices cannot increase at such a discontinuity. This leads to the following observation.

Observation 11

A change in the visibility graph cannot increase the current configuration’s stretch.

5.3 Analysis of the Move-on-Bisector Protocol

We are now ready to sketch the analysis of the Move-on-Bisector protocol. The interested reader will find the full analysis in [5]. First we show, similar to the proof of Theorem 6 a lower bound on the rate at which the current configuration’s stretch decreases as long as the robots have not yet gathered (Lemmas 12 and 13). Afterward, we argue that a configuration’s stretch is linear in its diameter. Combining these easily yields the desired bound on the gathering time of Move-on-Bisector (Theorem 15).

Lemma 12

The stretch of a configuration at time t changes at a rate of

(12)

Proof

Fix a time $t \ge 0$ and $\iota \in {[}q(t){]}$. We consider how the distance changes. Let $s_{\iota }(t)$ denote the speeds of vertex $\iota$ at time t.² Set if $\iota \in \mathcal {W}(t)$ and if $\iota \not \in \mathcal {W}(t)$. By Lemma 3, the distance changes at a rate of

$$\begin{aligned} {\dot{d}}(t) = -s_{\iota }(t) \cdot \cos (\beta _\iota (t)/2) - s_{\iota -1}(t) \cdot \cos (\beta _{\iota -1}(t)/2). \end{aligned}$$

(13)

Note that the speed of any vertex $w_{\iota }(t)$ with $\iota \in \mathcal {W}(t)$ equals 1. Summing over all we get that the current configuration’s stretch changes at a rate of .   $\square$

Lemma 13

The stretch of a configuration at time t decreases at a rate of at least 4.

Proof

Since the configuration polygon is a (possibly degenerated) simple polygon, the sum of its inner angles $\alpha _{\iota }(t)$ is exactly $(q(t) - 2) \cdot \pi$. Define the angles if $\iota \in \mathcal {W}(t)$ and if $i \not \in \mathcal {W}(t)$. Together with Lemmas 12 and 2(a) we get that the current configuration’s stretch decreases at a rate of at least

(14)

finishing the proof.    $\square$

Together, Observation 11 and Lemma 13 yield a bound of on the gathering time. To get our desired bound of ${\text {O}\left( n\right) }$, we use a result from [5] showing that $\mathfrak {s}\le 6n$. This might seem trivial at first glance: After all, the stretch $\mathfrak {s}$ corresponds to the length of a chain of actual robots that forms the configuration polygon. However, note that while the configuration polygon is simple, it might be degenerated, such that, for example, parts of it may form a line. Thus, the robots along the above-mentioned chain are not necessarily unique. However, using the basic geometry of the underlying visibility graph, one can show that no node appears more than 6 times in this chain.

Lemma 14

([5, Lemma 5.7]). For any configuration of n robots and stretch $\mathfrak {s}$, we have $\mathfrak {s}\le 6n$.

Combining Observation 11 and Lemmas 13 and 14, we immediately get the following result.

Theorem 15

Consider an initial configuration of n robots and stretch $\mathfrak {s}$. In the worst-case, the Move-on-Bisector protocol gathers the robots in time at most . This is asymptotically optimal for the gathering problem.

6 Avoiding Collisions

The final section of this chapter gives a brief outlook of how one can avoid (early) collisions when gathering multiple point robots. Here, by collision we mean situations where two or more robots share the same position in the Euclidean plane. A configuration is called collision-free if no two robots share the same position. When the robots are gathered, we have a collision between all robots. We call this the final collision, which is not avoidable if we want to gather. Any collision between two or more robots before all robots are gathered is called an early collision. The question we study in this section is:

Such a gathering protocol is called collision-free.

Many natural gathering protocols, including the Move-on-Bisector protocol, are prone to early collisions. In fact, in the analysis of both discrete and continuous setting, collisions are often seen as a success, as robots that collided behave identical (in synchronous and deterministic robot formation protocols). Thus, there can be at most $n-1$ collisions, allowing us to use the number of collisions as a progress measure. However, from a practical standpoint and, collisions should be avoided as much as possible.

The rest of this section surveys recent results [12, 13] that made progress towards answering the above question.

6.1 A Candidate for an Almost Collision-Free Gathering Protocol

The Go-to-the-Center protocol is another simple and natural gathering protocol. Here, each robot moves with speed 1 towards the center of the minimum enclosing circle of all robot positions it currently sees.

In the discrete setting, this algorithm was introduced by Ando et al. [1] who showed that it indeed gathers all robots, but the authors provided no bound on the gathering time. A quadratic upper bound in this discrete setting was later shown by Degener et al. [4]. In the continuous setting, we can simply use our framework from Sect. 4: Indeed, it is easy to verify that Go-to-the-Center is a contracting protocol [13]. This allows us to apply Corollary 7 to get a quadratic bound on its gathering time.

Unfortunately, Go-to-the-Center is also prone to collisions. In fact, the analysis of its discrete variant [4] is partly based on collisions. However, as noted by Li et al. [12], one can slightly change the definition of Go-to-the-Center to get a promising candidate for an collision-free, continuous gathering protocol (or almost collision-free; see below).

We can rephrase Go-to-the-Center as follows: each robot moves with speed 1 towards the center of the minimum enclosing circle of its (inclusive) neighborhood in the visibility graph. A variant of Go-to-the-Center – called Go-to-the-Gabriel-Center and due to Li et al. [12] – is defined using the same phrasing but uses the so-called Gabriel graph [7] instead of the visibility graph:

Definition 16

(Gabriel Graph). The Gabriel graph $GG_c = (VG_c, EG_c)$ of configuration c is a subgraph of the visibility graph. It has the same vertex set . The edge set $EG_c \subseteq E_c$ consists of all edges such that the interior of the smallest enclosing circle of u and v does not contain another robot’s position.

See Fig. 7 for an example of how the Gabriel graph differs from the visibility graph.

Fig. 7.

Visibility graph vs. Gabriel graph.

With this definition, we can now formally define the Go-to-the-Gabriel-Center protocol. Here, at each time t each robot i performs the following actions:

• (a) Robot i computes the minimum enclosing circle $\mathfrak {C}_i(t)$ of all robots in its neighborhood (including i itself) of the Gabriel graph $GG_{c(t)}$. Let $T_i(t)$ denote the center of $\mathfrak {C}_i(t)$ (robot i’ s target point).

• (b) If $c_i(t)$ equals $T_i(t)$, robot i moves with $T_i(t)$.

• (c) If $c_i(t)$ is different from $T_i(t)$, robot i moves with speed 1 towards $T_i(t)$.

As with the Go-to-the-Center protocol, it is easy to see (and has been proved in [13]) that the Go-to-the-Gabriel-Center protocol is contracting and, thus, gathers in quadratic time.

6.2 Collisions in the Go-to-the-Gabriel-Center Protocol

Experimental results indicate that for “typical” initial configurations, the Go-to-the-Gabriel-Center protocol causes no early collisions. In fact, in the one dimensional case (where all robots start on a line) this can be easily proved [12]. However, in the two dimensional case there are, in fact, some (quite symmetric) situations that exhibit early collisions. See Fig. 8 for an example. One of the central open questions left in [12] is whether the following conjecture is true.

Conjecture 17

The set of initial configurations that lead to early collisions of the Go-to-the-Gabriel-Center has Lebesgue measure 0.

A less formal variant of this conjecture states that independent small random perturbations of the robots’ initial positions ensure that, with probability 1, there will be no early collisions. Note that even for the special case of $n = 4$ robots, a proof of Conjecture 17 seems challenging.

Fig. 8.

Early collisions in the Go-to-the-Gabriel-Center protocol.

Even if Conjecture 17 is true, it remains open whether a distributed continuous gathering protocol can achieve truly collisionless gathering. There is currently only one continuous gathering protocol [13] that completely avoids early collisions, but it requires a considerably more complex robot model. Namely, robots must be non-oblivious (they have one memory bit), chiral (they share a common left/right orientation), and luminous (the contents of a robot’s memory bit is visible to other robots). Additionally, this protocol requires quadratic time to gather all robots, so it is much slower than the Move-on-Bisector protocol from Sect. 5. So even using a more complex robot model like the one above, it would be interesting to find a collision-free continuous gathering protocol that has linear gathering time.