Gathering Asynchronous Robots in the Presence of Obstacles

Abstract

This work addresses the problem of Gathering a swarm of point robots when the plane of deployment has non-intersecting transparent convex polygonal obstacles. While multiplicity detection is enough for gathering three or more asynchronous robots without obstacles, it is shown that in the presence of obstacles, gathering may not be possible even in the FSYNC model with all of multiplicity detection, memory, chirality and direction-only axis agreement. Initial configurations for which gathering is impossible are characterized. For other configurations, a distributed algorithm for the gathering problem is proposed without any extra assumption on the capabilities of the robots. The algorithm works even if the configuration contains points of multiplicities.

1 Introduction

A Robot Swarm is a distributed system of autonomous, memoryless, homogeneous mobile robots which can move freely on the infinite two-dimensional plane. The robots are anonymous, i.e., they cannot be distinguished by a unique identity or by their appearances. They do not communicate with each other directly. The communication is done implicitly by sensing the positions of other robots. The robots are memoryless or oblivious in the sense that they do not remember any information from the previous computational cycles. Each robot has its own local coordinate system. The robots follow the same execution cycle Look-Compute-Move [10].

We consider the ASYNC [8] model, where robots are activated asynchronously and independently from other robots. The time taken to complete an action is unpredictable but finite. Chirality or orientation of axes may be different for different robots. The primary objective of research in this field is to find strategies for cooperation, control and interaction to solve fundamental classes of problems like geometric pattern formation, gathering, convergence, flocking etc. Researchers have also identified sets of conditions under which certain problems are unsolvable.

The Gathering problem (also known as Homing/Rendezvous/Point Formation) is defined as bringing multiple autonomous mobile robots into a point which is not fixed in advance. The existing works have considered the plane of motion to be free of obstacles. We consider a model in which the region of deployment has a finite number of non-interesting convex polygonal obstacles. The robots can see through the obstacles but they can not pass through them. An instance of this model is the case when the obstacles are holes in the plane which hinder movements but cause no visual obstruction.

1.1 Related Works

The problem of gathering has received extensive attention in the field of swarm robotics [10]. In FSYNC model, the gathering problem is solvable without any extra assumption [10]. Suzuki and Yamashita proved that in the SSYNC model, gathering problem is not solvable for two robots without any agreement on the local coordinate systems even with strong multiplicity detection [14]. Prencipe proved that for $n>2$ robots, there does not exists any deterministic algorithm for the gathering problem in absence of multiplicity detection and any form of agreement on the local coordinate systems [13]. Flocchini et al. solved the gathering problem in the ASYNC model with oblivious robots having limited visibility and knowledge of a common direction [9]. Cieliebak et al. proposed an algorithm for gathering in the ASYNC model with multiplicity detection for $n\ge 5$ robots [4]. All of these works have considered robots to be dimensionless i.e., point robots. The gathering problem for fat robots (represented as unit discs) have also been investigated by the researchers [1, 5, 11]. The gathering problem under different fault models have been addressed by many researchers [2, 3, 6].

To the best of our knowledge, this paper is the first attempt to study the problem of gathering in the ASYNC model with the assumptions that the plane of motion has non-intersecting convex polygonal obstacles.

1.2 Our Contribution

This paper proposes a distributed algorithm for gathering if the initial configuration, consisting of the obstacles as well as the robots, does not have any rotational symmetry. The algorithm does not assume any extra capability for the robots. The obstacles provide some fixed reference points. However, the gathering problem is not solvable in general, if the configuration of the obstacles and the robots has rotational symmetry, even if robots have multiplicity detection capability, memory, chirality and direction-only axis agreement [7] and robots are fully synchronous.

2 Robot Model and Terminology

This work adopts the basic the ASYNC model (CORDA model). The robots are represented as points in the two dimensional Euclidean plane. The visibility range of a robot is assumed to be unlimited. We consider non-rigid motion of the robots i.e., a robot may stop before reaching its destination. However, to ensure finite time reachability to the destination point, there exists a fixed value $\delta > 0$ such that in each movement, where the robot does not reach its destination, it moves a distance not less than $\delta$ towards its destination [10]. The value of $\delta$ is not known to the robots.

Initially the robots are stationary and in arbitrary positions. Multiple robots may share same position on the plane. However, the robots do not have multiplicity detection capabilities i.e., they can not identify multiple robots at a point. The total number of robots in the system is not known to the robots. The region of deployment of the robots has finite non-zero number of non-intersecting convex polygonal obstacles. The robots have full visibility through the polygons but they can not pass through them. No robot can lie inside or on the boundary of a polygon.

Let $\mathcal {R}=\{r_1,r_2,\ldots ,r_n\}$ be the set of n homogeneous robots. The position occupied by a robot $r_i\in \mathcal {R}$ at time t is denoted by $r_i(t)$. Let $\mathcal {R}(t)$ be the collection of all such positions occupied by the robots in $\mathcal {R}$ at time t. Let $\mathcal {P}=\{P_1, P_2,\ldots ,P_m\}$ denote the set of mutually non-intersecting convex polygonal obstacles where $m\ge 1$. For a polygon $P_i\in \mathcal {P}$, let $P_{iv}$ denote the set of vertices of $P_i$. Let $\mathcal {P}_v=\{P_{1v},P_{2v},\ldots ,P_{mv}\}$ be the collection of all such sets of vertices for the polygons in $\mathcal {P}$. Note that in our model, $P_{iv}\cap P_{jv}=\emptyset$ for $i\ne j$. The set of all vertices of all the polygons in $\mathcal {P}$ is denoted by $\hat{\mathcal {P}_v}$. The center of gravity of a point set A is denoted by CoG(A). We use $\mathcal {O}$ to denote $CoG(\hat{\mathcal {P}_v})$. If $\mathcal {O}$ lies inside a polygon, the polygon containing $\mathcal {O}$ is called the central polygon and is denoted by $P_c$. By a configuration $\mathcal {C}(t)$ at time t, we mean the set $\mathcal {P}\cup \mathcal {R}(t)$.

The distance of point x from a polygon $P_i$ is the minimum euclidean distance between x and a point y in $P_i$ and it is denoted by $dist(x,P_i)$. The distance between two polygons $P_i, P_j\in \mathcal {P}$, is the minimum distance between two points in $P_i$ and $P_j$ and it is denoted by $dist(P_i, P_j)$. The minimum of all the distances of the robot positions in $\mathcal {R}(t)$ from a polygon $P_i \in \mathcal {P}$ at time t is denoted by $\sigma _i(t)$ i.e., $\sigma _i(t)=min\{dist(r_j(t), P_i): \forall r_j(t)\in \mathcal {R}(t)\}$. Let $\varSigma (t)=min\{\sigma _i(t):\forall P_i\in \mathcal {P}\}$.

Let

$$\begin{aligned} D_p = {\left\{ \begin{array}{ll} min\{dist(P_i,P_j), \forall P_i, P_j \in \mathcal {P}\} &{}\text {if } |\mathcal {P}|>1\\ l &{}\text {if } |\mathcal {P}|=1 \end{array}\right. } \end{aligned}$$

where l is the length of the smallest side of the polygon in $\mathcal {P}$,

$$\begin{aligned} \varDelta (t) = {\left\{ \begin{array}{ll} min\{\sigma _c(t), D_p/4\} &{}\text {if } \mathcal {O} \text { lies inside }P_c\\ D_p/4 &{}\text {otherwise} \end{array}\right. } \end{aligned}$$

and

$$\begin{aligned} \zeta (t) = {\left\{ \begin{array}{ll} min\{\varSigma (t), D_p/4\} &{}\text {if }\mathcal {O} \text { lies inside }P_c\\ D_p/4 &{}\text {otherwise} \end{array}\right. } \end{aligned}$$

For every polygon, we define an extended version of it by expanding the boundaries. A polygon in $\mathcal {P}\backslash \{P_c\}$ is extended by an amount $\zeta (t)$. The polygon $P_c$ is extended by an amount $\varDelta (t)$. Note that these extended polygons are also convex and non-overlapping. Let $P_{ai}$ be the extended version of $P_i$. The polygon $P_{ai}$ is called the auxiliary polygon of $P_i$. The auxiliary polygons are used in the path computations for the robots. Let $\overline{ab}$ denote the line segment joining two points a and b (including the end points a and b).

3 Preliminaries

This section describes some basic results which are used to develop the gathering algorithm.

Definition 1

A straight line $\mathcal{L}$ is called a line of symmetry for $\mathcal {P}$, if (i) for every polygon ${P_i} \in \mathcal{P}$, such that $\mathcal{L}$ passes through the interior of $P_i$, $\mathcal{L}$ is a line of symmetry for $P_{i}$ (ii) for every polygon ${P_i} \in \mathcal{P}$, such that $\mathcal{L}$ does not pass through the interior of $P_i$, there exists a $P_j \in \mathcal{P}$, such that $P_{j}$ is the mirror image of $P_{i}$ about $\mathcal{L}$.

Definition 2

A point O is called the center of rotational symmetry for $\mathcal {P}$ with an angle of symmetry $0<\theta \le \pi$, if (i) for every polygon ${P_i} \in \mathcal{P}$, such that O lies in the interior of $P_i$, O is the center of rotational symmetry for $P_{i}$ with $\theta$ as an angle of symmetry (ii) for every polygon ${P_i} \in \mathcal{P}$, such that O does not lie in the interior of $P_i$, there exists a $P_j \in \mathcal{P}$, such that $P_{j}$ can be obtained by rotating $P_{i}$ by an angle $\theta$ about O.

Definition 3

A straight line $\mathcal {L}$ is a line of symmetry for $\mathcal {P} \cup \mathcal {R}(t)$, if $\mathcal {L}$ is a line of symmetry for $\mathcal {P}$ as well as for $\mathcal {R}(t)$. Similarly, a point O is the center of rotational symmetry for $\mathcal {P} \cup \mathcal {R}(t)$, if O is the center of rotational symmetry for $\mathcal {P}$ as well as for $\mathcal {R}(t)$ with the same angle of symmetry.

Note that if a set of points $\mathcal{A}$ (polygons $\mathcal {P}$) has more than one line of symmetry, then $\mathcal{A}$ ($\mathcal {P}$) has rotational symmetry with center of gravity of $\mathcal{A}$ ($\mathcal {P}$) as the center of rotational symmetry. A set of points $\mathcal{A}$ (polygons $\mathcal {P}$) is asymmetric if it has neither a line of symmetry nor rotational symmetry. We use the notion of ordering as defined in [11]. A set of points $\mathcal {A}$ (polygons $\mathcal {P}$) is orderable, if a deterministic algorithm can produce a unique sequencing of the points in $\mathcal {A}$ (polygons in $\mathcal {P}$) such that the sequencing does not depend on the local coordinate systems.

Result 1 [11]. If a set of points $\mathcal{A}$ (polygons $\mathcal {P}$) does not have any line of symmetry or rotational symmetry, then the points in $\mathcal{A}$ (polygons in $\mathcal {P}$) are orderable.

Observation 1

If a set of points $\mathcal{A}$ has only one line of symmetry $\mathcal {L}$, then positive and negative directions can be defined along $\mathcal {L}$.

Observation 2

If a set of points $\mathcal{A}$ has both a line of symmetry and rotational symmetry, then A has multiple lines of symmetry.

4 Algorithm GatheringObstacles()

Our objective is to compute a unique point which remains intact under the motion of robots and all robots can agree on that point. If such a point exists in the initial configuration $\mathcal {P} \cup \mathcal {R}(t_0)$, then we are done. Otherwise, we convert the initial configuration into one where such a point can be defined. The point $\mathcal {O}$ is fixed and invariant under orthogonal coordinate transformations. If $\mathcal {O}$ lies outside the obstacles, then $\mathcal {O}$ serves our purpose. If $\mathcal {O}$ lies inside an obstacle, we adopt different strategies to have such a point. If the set $\mathcal {P}$ does not have rotational symmetry, a gathering point is defined in terms of the points in $\hat{\mathcal {P}_v}$. Since the obstacles are stationary, this point is also fixed. When $\mathcal {P}$ has rotational symmetry, the positions of the robots along with the polygons are considered to compute a unique gathering point. If $\mathcal {P}\cup \mathcal {R}(t)$ has no rotational symmetry, a unique robot position is created on the boundary of $P_{ac}$ which serves the purpose. During the creation of such unique point, the movements of the robots are coordinated in such a way that they do not create any rotational symmetry of $\mathcal {P}\cup \mathcal {R}(t)$. If the initial configuration $\mathcal {P}\cup \mathcal {R}(t_0)$ has rotational symmetry, then gathering is not possible. When $\mathcal {O}$ lies inside or on the boundary of the obstacle $P_c$ and $\mathcal {P}\cup \mathcal {R}(t)$ has no rotational symmetry, there are following possible scenarios:

(A) $\varvec{\mathcal {P}}$ has no rotational symmetry: In this case, $\mathcal {P}$ has at most one line of symmetry. If $\mathcal {P}$ is asymmetric, we fix an ordering of the vertices of the polygons in $\mathcal {P}$. Let p be the first vertex of $P_c$ in that ordering such that $p\ne \mathcal {O}$. Draw the straight line $\mathcal {L}$ through p and $\mathcal {O}$. The direction from $\mathcal {O}$ along $\mathcal {L}$ on which p lies is defined as the positive direction of $\mathcal {L}$ and denoted by $\mathcal {L}^+$. This definition remains invariant since it involves only fixed points. If $\mathcal {P}$ has exactly one line of symmetry $\mathcal {L}$, by Observation 1, we can define the positive direction $\mathcal {L}^+$ along $\mathcal {L}$. In both the cases, we consider the point r on $\mathcal {L}^+$ which is $D_p/4$ distance apart from $P_c$. Since this point is defined in terms of polygons in $\mathcal {P}$, it is a fixed point and we take this point as our desired gathering point. Robots move towards r.

(B) $\mathcal {P}$ has rotational symmetry: The Observation 2 implies that either (i) $\mathcal {P}$ has more than one line of symmetry or (ii) $\mathcal {P}$ has no line of symmetry. In scenario (ii), $\mathcal {P} \cup \mathcal {R}(t)$ is asymmetric. When $\mathcal {P}$ has multiple lines of symmetry, these lines of symmetry define different wedges w.r.t. $\mathcal {O}$. When $\mathcal {P}$ has rotational symmetry but no line of symmetry, the wedges are defined in the following way: consider the robot positions having minimum Euclidean distance from $\mathcal {O}$. Let S(t) be the set of these robot positions. Since $\mathcal {P}\cup \mathcal {R}(t)$ is orderable, consider the robot position $r_i(t)\in S(t)$, which has highest ordering among the robot positions in S(t). Let $\mathcal {L}_i(t)$ be the line joining $r_i(t)$ and $\mathcal {O}$. The line $\mathcal {L}_i(t)$ divides the plane into two non-overlapping wedges.

The set $\mathcal {P} \cup \mathcal {R}(t)$ has at most one line of symmetry. Our approach focuses on the number of robot positions on $P_{ac}$ and performs actions accordingly.

(B.1) $\varvec{P_{ac}}$ contains no robot position on its boundary: If in the initial configuration, there is no robot on $P_{ac}$, we create at least one robot position on $P_{ac}$. In the following discussion, we shall be talking about paths from robot positions to the auxiliary polygons. Any path computation will serve our purpose as long as: (i) the computation is done with auxiliary polygons (ii) if the robot stops in the middle, the newly computed path would again be the remaining portion of the original path and (iii) each path is completely contained inside one of the wedges as defined above. Since polygons are non-interesting and no polygon disconnects a wedge, it is possible to find such paths. In particular one may consider the piece-wise linear voronoi diagram for convex sites [12] with the extended polygons. The path may be obtained by projecting a perpendicular on a voronoi edge and then following voronoi edges to the destination, with the final segment being a perpendicular from the destination point. When $\mathcal {P}$ has multiple lines of symmetry, for each wedge, we compute the intersection point between its bisector and $P_{ac}$. On the other hand, when $\mathcal {P}$ has rotational symmetry but no line of symmetry, the intersection point between $\mathcal {L}_i(t)$ and $P_{ac}$ is considered. These intersection points are called wedge points. The shortest paths are computed from each robot position to the wedge point of the wedge it belongs to. If a robot position lies on a line of symmetry, both the adjacent wedge points are equidistant. Any one of them may be considered for path computation.

(a) $\mathcal {P}$ has no line of symmetry: If the line segment $\overline{r_i(t)\mathcal {O}}$ intersects $P_{ac}$ only, then the robots at $r_i(t)$ move towards the intersection point of $\overline{r_i(t)\mathcal {O}}$ and $P_{ac}$ along the line segment $\overline{r_i(t)\mathcal {O}}$. Other robots in the system waits until $P_{ac}$ has one robot position on its boundary. Now suppose, the line segment $\overline{r_i(t)\mathcal {O}}$ intersects at least one obstacle other than $P_{c}$. Let $P_m$ be the nearest obstacle to $r_i(t)$ among such obstacles. The robots at $r_i(t)$ computes a point $\hat{r}$ on the line segment $\overline{r_i(t)\mathcal {O}}$ such that distance of $\hat{r}$ from $P_m$ is $\frac{1}{2}\varSigma (t)$ (any distance less than $\varSigma (t)$ will work). The robots at $r_i(t)$ move towards $\hat{r}$ along the line segment $\overline{r_i(t)\mathcal {O}}$. Other robots wait until, at least one of these robots reaches a point on $\overline{r_i(t)\mathcal {O}}$, which realizes $\varSigma (t')$ for some $t'>t$. Let w be the unique point on $\overline{r_i(t)\mathcal {O}}$ which realizes $\varSigma (t')$. The movements of the robots at $r_i(t)$ towards $\hat{r}$ do not change the asymmetry of $\mathcal {P}\cup \mathcal {R}(t)$. Once such a point w is created, the robots compute the set $F(t')$ of robot positions over $\mathcal {R}(t')\backslash \{w\}$, having shortest paths to the wedge point (the shortest paths should completely lie within one of the wedges defined by $\mathcal {L}_i(t)$). The robot position in $F(t')$, which appears first in an ordering of $\mathcal {P}\cup \mathcal {R}(t')$, is selected. The robots at this point move towards the wedge point along the corresponding shortest path(s). Rest of the robots wait until at least one robot reaches $P_{ac}$. During this whole process, $\mathcal {P}\cup \mathcal {R}(t)$ remains asymmetric.

(b) $\mathcal {P}$ has multiple lines of symmetry: Let T(t) be the set of all robot positions, which have the shortest paths to the corresponding wedge points. The following are the different possibilities:

b.1. $\varvec{|T(t)|=1:}$ Let $r_i(t)$ be the corresponding robot position. If the point $r_i(t)$ does not lie on any wedge boundary, then the robots at this point move to the corresponding wedge point along the shortest path(s). Otherwise, the robots at $r_i(t)$ choose any of one of the wedge points corresponding to the neighbouring wedges of $r_i(t)$ and move towards it. Since multiple robots may be located at $r_i(t)$, it may happen that two robots at $r_i(t)$ choose two different wedge points as their destinations. The other robots do not move till at least one robot reaches $P_{ac}$.

b.2. $\varvec{|T(t)|> 1:}$ Since $\mathcal {P} \cup \mathcal {R}(t)$ has at most one line of symmetry, we have following cases only:

     b.2.1. $\varvec{\mathcal {P} \cup \mathcal {R}(t)}$ is asymmetric: The set $\mathcal {P} \cup \mathcal {R}(t)$ is orderable [11]. We fix any ordering. Let $r_i(t)$ be the point in T(t), which appears first in this ordering. If the point $r_i(t)$ does not lie on the boundary of the wedges, the robots at this point move to the corresponding wedge point along the shortest path. Otherwise, the robots at $r_i(t)$ choose any one of the wedge points in the neighbouring wedges and move towards it. If $r_i(t)$ contains multiple robots, the robots at this points may move to both of the wedge points.

     b.2.2. $\varvec{\mathcal {P} \cup \mathcal {R}(t)}$ has exactly one line of symmetry: Let $\mathcal {L}$ be the line of symmetry of $\mathcal {P} \cup \mathcal {R}(t)$. We define positive and negative directions along $\mathcal {L}$ as stated in Observation 1. Let $\mathcal {L^+}$ and $\mathcal {L^-}$ denote the positive and negative sides of $\mathcal {L}$ respectively, with $\mathcal {O}$ as the origin.

• (i) $\mathcal {L}$ passes through at least one member of T(t): If $\mathcal {L}$ passes through robot positions in T(t), consider the robot position in T(t) which lies on $\mathcal {L^+}$ and has smallest Euclidean distance from $\mathcal {O}$. Let $r_i(t)$ be this robot position. The robots at $r_i(t)$ arbitrarily choose any one of the wedge points in the neighbouring wedges and move towards wedge point(s) along the shortest path(s).

• (ii) $\mathcal {L}$ does not pass through any member of T(t): In this case, we move the robots in such a way that even if symmetry occurs, $\mathcal {L}$ remains as the unique line of symmetry for the whole configuration. We consider the pair of points in T(t) which are closest to $\mathcal {L^+}$. If there is more than one such pair, we choose the one having smallest euclidean distance from $\mathcal {O}$. Let these points be $r_l(t)$ and $r_k(t)$. If these two points do not lie on the wedge boundaries, the active robots at these two points move towards the corresponding wedge points. Otherwise, the robots at each point has two options. For each of the points, the robots select the wedge point which makes smaller angle with $\mathcal {L^+}$.

(B.2) $\varvec{P_{ac}}$ contains exactly one robot position on its boundary: The robots which observe this point on $P_{ac}$, move towards it along paths not crossing $P_{ac}$.

(B.3) $\varvec{P_{ac}}$ contains more than one robot position on its boundary: If at any time there are more than one robot position on $P_{ac}$, we create a unique fixed robot position on $P_{ac}$.

If possible, we divide the perimeter of $P_{ac}$ into two polygonal chains such that (i) one of them contains all the robot positions (the robot positions at the joint belong to both the chains) and (ii) the chain containing the robots is not longer than the other chain.

Let both the chains have same length and $v_i$ and $v_j$ be the two joints of the chains. The robots do one of the followings to change the lengths of the chains:

(1) if $\mathcal {P} \cup \mathcal {R}(t)$ is asymmetric, the robot positions are orderable. Without loss of generality, suppose that $v_i$ has higher order than $v_j$. The robots at $v_i$ move along the boundary of $P_{ac}$ towards the next nearest vertex of $P_{ac}$ on the chain satisfying any one of the followings: (a) if $P_{ac}$ contains more than two robot positions, the chain contains the other robot positions (b) if $P_{ac}$ contains exactly two robot positions, the chain contains the vertex of $P_{ac}$, having highest order among the vertices of $P_{ac}$ (2) if $\mathcal {P} \cup \mathcal {R}(t)$ has one line of symmetry $\mathcal {L}$, the positive and the negative directions are defined along $\mathcal {L}$. The robots at $v_i$ and $v_j$ move towards the corresponding next nearest vertices of $P_{ac}$ on the chain intersected by $\mathcal {L^+}$. The robots move along the boundary of $P_{ac}$.

Once we have a polygonal chain having length less than half of the perimeter of $P_{ac}$ and containing all the robots, we move the robots towards the middle vertex of the corresponding chain. If the middle vertex is not unique, the robots move to the nearest one. In each movement, a robot tries to reach the next vertex on its path. This process continues till all robots lie on a single edge or reach at a single vertex of $P_{ac}$. If the robots lie on a single edge, they gather at the mid point of the edge.

If such a division is not possible, we update $P_{ac}$ with a newer version which is obtained by expanding the boundaries of $P_c$ by an amount $\varDelta (t)/2$. It may be noted that the expansion can be made by any amount less than $\varDelta (t)$. Now we have a new $P_{ac}$ with no robot position on its boundary. We follow the same strategies as described in (B.1). According to the strategies in (B.1), the new $P_{ac}$ would contain at most two robots on its boundary. Since robots on old $P_{ac}$ move to the boundary of new $P_{ac}$ along the straight lines and these straight lines completely lie in the corresponding wedges in which robots lie, the updated configuration $\mathcal {P} \cup \mathcal {R}(t')$ can have at most one line of symmetry. Suppose, there are two robot positions on the updated $P_{ac}$. If these two robot positions define two polygonal chains of the updated $P_{ac}$ with unequal lengths, then we are done. Otherwise, the two polygonal chains would have same length and the robots follow the same strategy as described above to reduce the length of one of the chains. This implies that the process of creating new polygonal chains with unequal lengths will terminate in finite time. Note that none of our strategies, described above, creates this scenario. This scenario is possible only in one of the initial configurations. Also this is the only case in which $P_{ac}$, initially defined, is changed. In all other cases $P_{ac}$ remains intact.

4.1 Correctness of GatheringObstacles()

In this section we prove that if the initial configuration does not have rotational symmetry, the robots gather in finite time by executing GatheringObstacles(). To prove the correctness of our approach, we show that in possible cases, our approach provides, within finite time, a unique gathering point which remains intact under the motion of the robots.

Lemma 1

Suppose $\mathcal {P}\cup \mathcal {R}(t_0)$ has no rotational symmetry. During the whole execution of algorithm GatheringObstacles(), $\mathcal {P}\cup \mathcal {R}(t)$ does not become rotationally symmetric.

Proof

The obstacles are static. If $\mathcal {P}$ has no rotational symmetry, then the lemma is true. If $\mathcal {P}$ has rotational symmetry, during the execution of algorithm GatheringObstacles(), following are the possible scenarios:

• $P_{ac}$ contains exactly one robot position on its boundary: The robots on $P_{ac}$ do not move. Whenever other robots move to this point, they move along the shortest paths having no intersections with $P_{ac}$. Hence, the lemma is true.

• $P_{ac}$ contains no robot position on its boundary: In this scenario, $\mathcal {P}$ has either multiple lines of symmetry or no line of symmetry. First consider the case when $\mathcal {P}$ has multiple lines of symmetry. The set $\mathcal {P}\cup \mathcal {R}(t)$ has at most one line of symmetry. Robots having positions in T(t) move towards at most two wedge points. All the shortest paths to these wedge points lie in the corresponding wedges in which the wedge points lie. If the robots move towards a single wedge point, the lemma follows immediately. If the robots move towards two wedge points, the angle made by these two wedge points at $\mathcal {O}$ is less than $\pi$. This implies the lemma. Next, consider the case when $\mathcal {P}$ has no line of symmetry. In this case, $\mathcal {P}\cup \mathcal {R}(t)$ is asymmetric. A robot position $r_i(t)$ is selected. The robots at $r_i(t)$ move straight either to the boundary of $P_{ac}$ or move to a point which would be a unique robot position in the system realizing the quantity $min\{\varSigma (t'),\frac{D_p}{4}\}$, $t'>t$. The robots move along the straight line to the corresponding destination point. Until, at least one robot reaches the destination point, other robots do not move. Thus, these movements of the robots do not make $\mathcal {P}\cup \mathcal {R}(t)$ rotationally symmetric.

• $P_{ac}$ contains more than one robot position on its boundary: Suppose, it is possible to define two polygonal chains, one with all robot positions. Since the robots move along the chain which contains them, to create a unique robot position on the chain and the length of this chain is at most half of the perimeter of $P_{ac}$, the movements of these robots do not make $\mathcal {P}\cup \mathcal {R}(t)$ rotationally symmetric. If it is not possible to define such polygonal chains, the robots move to the updated version of $P_{ac}$. At most two robot positions are selected and the robots at these positions are asked to move to the boundary of the new $P_{ac}$. The robots follow same strategies as in the case of (B.1) when initial $P_{ac}$ contains no robot positions. Thus, in this case, lemma follows from the same arguments as in the case when $P_{ac}$ contains no robot positions.   $\square$

Lemma 2

Let $\mathcal {P}\cup \mathcal {R}(t_0)$ have no rotational symmetry. If $\mathcal {P}$ has rotational symmetry and initially $P_{ac}$ does not contain any robot position on its boundary, during the execution of algorithm GatheringObstacles(), $P_{ac}$ will have at least one robot position on its boundary in finite time.

Proof

Since $P_{ac}$ does not contain any robot position, by definition, the polygon $P_{ac}$ is defined by the obstacles. This implies that $P_{ac}$ is independent of the movements of the robots. By Lemma 1, $\mathcal {P}\cup \mathcal {R}(t)$ does not become rotationally symmetric during the whole execution of the algorithm. This implies that at least one robot reaches the boundary of $P_{ac}$ in finite time.   $\square$

Lemma 3

Let $\mathcal {P}$ have rotational symmetry and $\mathcal {P}\cup \mathcal {R}(t_0)$ have no rotational symmetry. Suppose, $P_{ac}$ contains more than one robot position on its boundary and it cannot be decomposed into two polygonal chains as described in (B.3) of Sect. 4. During the execution of algorithm GatheringObstacles(), there exits a time $t>t_0$ such that $\varDelta (t')$ does not change, $\forall t'\ge t$. Furthermore, $P_{ac}$ at time t can be decomposed into two desired polygonal chains.

Proof

According to algorithm GatheringObstacles(), at most two robot positions are selected and the robots at these positions are asked to move towards at most two points on the boundary of the updated $P_{ac}$ which is defined by the quantity $\frac{\varDelta (t_0)}{2}$. The robots move along straight lines towards their respective destination points. Once at least a robot starts moving towards the updated $P_{ac}$, the value of $\varDelta ()$ is dependent solely on the robots positions. There are two possibilities: (i) at least one robot reaches the boundary of the computed $P_{ac}$ at time t or (ii) at least one robot position is created by some static robot (in between old and the computed $P_{ac}$) such that this robot position realizes the value $\varDelta (t)$ and all other robots agree on this value. These imply that $\varDelta (t')$ does not change for $t'\ge t$. The polygon $P_{ac}$ at time $t'$ depends only on the robot positions and it contains at most two robot positions. By Lemma 1, $\mathcal {P}\ cup\mathcal {R}(t)$ has at most one line of symmetry. Hence, $P_{ac}$ can be decomposed into two desired polygonal chains.   $\square$

During the whole execution of algorithm GatheringObstacles(), none of the strategies creates a configuration in which $P_{ac}$ contains more than one robot position such that it cannot be decomposed into two polygonal chains. Only an initial configuration can have such scenario. The above lemma implies that the process of updating $P_{ac}$ in (B.3) of Sect. 4, when $P_{ac}$ contains more than one robot position on its boundary and it cannot be decomposed into two polygonal chains, terminates in finite time.

Lemma 4

Let $\mathcal {P}\cup \mathcal {R}(t_0)$ have no rotational symmetry. Suppose $\mathcal {P}$ has rotational symmetry and $P_{ac}$ contains more than one robot position on its boundary. During the execution of algorithm GatheringObstacles(), there is a time $t\ge t_0$ such that $P_{ac}$ does not change after time t and $P_{ac}$ has exactly one robot position on its boundary, $\forall t'\ge t$.

Proof

First consider the initial configuration $\mathcal {P}\cup \mathcal {R}(t_0)$. Suppose the circumference of $P_{ac}$ can be decomposed into two polygonal chains, one containing all the robots. Our approach asks the robots to move along the corresponding polygonal chain of $P_{ac}$ to merge the robot positions on $P_{ac}$ into one point. Since $\mathcal {P}\cup \mathcal {R}(t)$ has at most one line of symmetry, the robots can agree on the corresponding polygonal chain to move along. The polygonal chain is of finite length. In each movement, robots move towards the nearest vertex of the chain in the direction of its destination. Hence after a finite time, we are left with either one robot position or two robot positions, sharing same edge, on the polygonal chain. In the later case robots move to the mid point of the corresponding edge. This creates exactly one robot position on $P_{ac}$ within finite time. In this process, $P_{ac}$ remains same. If the circumference of $P_{ac}$ cannot be decomposed into two desired polygonal chains, then by Lemma 3, there exits t such that $P_{ac}$ becomes static and it can be decomposed into two desired polygonal chains. Hence, the lemma follows from the same foregoing arguments.   $\square$

Lemma 5

Algorithm GatheringObstacles() deterministically solves the gathering problem within finite time provided the initial configuration $\mathcal {P} \cup \mathcal {R}(t_0)$ does not have rotational symmetry,

Proof: When $CoG(\mathcal {P})$ i.e., $\mathcal {O}$ lies outside the obstacles, then we are done. The point $\mathcal {O}$ is static and serves as the point of gathering. Otherwise, according to our algorithm:

• When $\mathcal {P}$ is asymmetric or has one line of symmetry, our algorithm chooses a point r based on the vertices of the polygons.Thus, r is a fixed point and is not affected by the movements of the robots.

• When $\mathcal {P}$ has more than one line of symmetry, our approach involves the robot positions in $\mathcal {R}(t)$. If $\mathcal {P}\cup \mathcal {R}(t)$ does not have rotational symmetry, according to our algorithm we have the following: (i) if $P_{ac}$ does not change and contains exactly one robot position on its boundary, this unique robot position on $P_{ac}$ serves as the gathering point. Since the robots move towards this point along paths not crossing $P_{ac}$ (such paths exists because polygons are non-overlapping), the robot position on $P_{ac}$ remains fixed under the movements of the robots (ii) otherwise, by Lemmas 2 and 4, $P_{ac}$ becomes static and contains exactly one robot position in finite time, which implies the corresponding of the lemma.

Therefore, algorithm GatheringObstacles() deterministically solves the gathering problem in finite time.   $\square$

Combining the above results, we have the following theorem.

Theorem 1

The gathering problem is solvable in finite time, without any extra assumption on the capabilities of the robots, in the presence of non-intersecting convex polygonal obstacles, when the initial configuration of the polygons and the robot positions does not have rotational symmetry.

Theorem 2

If $\mathcal {P} \cup \mathcal {R}(t)$ has rotational symmetry around $\mathcal {O}$ which lies inside an obstacle in $\mathcal {P}$, there does not exist any deterministic algorithm that solves the gathering problem starting from $\mathcal {P} \cup \mathcal {R}(t)$. The problem remains unsolvable even if we arm the robots strong multiplicity detection, memory, chirality and direction-only axis agreement and have them move in FSYNC model.

5 Conclusion

This paper studies the gathering problem in the presence of transparent polygonal obstacles. Obstacles are fixed objects. They help us by providing fixed reference points. One may identify certain fixed points (i.e., independent of axes and robot positions) based on these reference points. However if all these points fall within the obstacles and hence are unreachable, the advantage is lost. On the other hand obstacles also create problems in finding paths. A distributed algorithm has been proposed which solves the gathering problem without any extra assumption on the capabilities of the robots if the initial configuration does not have any rotational symmetry. The gathering is impossible if the initial configuration has rotational symmetry. The problem remains unsolvable even if robots have multiplicity detection, memory, chirality and direction-only axis agreement in the FSYNC model. While it would be interesting to consider opaque obstacles, it is not sure whether much can be expected from that model.