--- abstract: | We study the <span>*Gathering*</span> problem for $n$ autonomous mobile robots in semi-synchronous settings with persistent memory called <span>*light*</span>. It is well known that Gathering is impossible in a basic model when robots have no lights, if the system is semi-synchronous or even centralized (only one robot is active in each time) @SY [@DGCMR]. On the other hand, Rendezvous (Gathering when $n=2$) is possible if robots have lights of various types with a constant number of colors @FSVY [@V]. If robots can observe not only their own lights but also other robots' lights, their lights are called <span>*full-light*</span>. If robots can only observe the state of other robots' lights, their lights are called <span>*external-light*</span>. If robots can only observe their own lights, their lights are called <span>*internal-light*</span>. In this paper, we extend the model of robots with lights so that Gathering algorithms can be discussed properly. Then we show Gathering algorithms with three types of lights in the semi-synchronous settings and reveal relationship between the power of lights and other additional assumptions. The most algorithms shown here are optimal in the number of colors they use. author: - 'Satoshi Terai[^1], Koichi Wada[^2], Yoshiaki Katayama[^3]' title: Gathering Problems for Autonomous Mobile Robots with Lights --- Introduction ============ <span>**Background and Motivation**</span> The computational issues of autonomous mobile robots have been research object in distributed computing fields. In particular, a large amount of work has been dedicated to the research of theoretical models of autonomous mobile robots @AP [@BDT; @CFPS; @DKLMPW; @IBTW; @KLOT; @SDY; @SY]. In the basic common setting, a robot is modeled as a point in a two dimensional plane and its capability is quite weak. We usually assume that robots are <span>*oblivious*</span> (no memory to record past history), <span>*anonymous*</span> and <span>*uniform*</span> (robots have no IDs and run identical algorithms)@FPS. Robots operate in Look-Compute-Move (LCM) cycles in the model. In the Look operation, robots obtain a snapshot of the environment and they execute the same algorithm with the snapshot as an input in Compute operation, and move towards the computed destination in Move operation. Repeating these cycles, all robots perform a given task. It is difficult for these too weak robot systems to accomplish the task to be completed. Revealing the weakest capability of robots to attain a given task is one of the most interesting challenges in the theoretical research of autonomous mobile robots. In this paper, we also explore such weakest capabilities. In particular, we reveal the weakest additional assumptions for the task which cannot be solved in the basic common models. The problem considered in this paper is <span>*Gathering*</span>, which is one of the most fundamental tasks of autonomous mobile robots. Gathering is the process of $n$ mobile robots, initially located on arbitrary positions, meeting within finite time at a location, not known a priori. When there are two robots in this setting, this task is called <span>*Rendezvous*</span>. Since Gathering and Rendezvous are simple but essential problems, they have intensively studied and a number of possibility and/or impossibility results have been shown under the different assumptions@AP [@BDT; @CFPS; @DGCMR; @DKLMPW; @DP; @FPSW; @IKIW; @ISKIDWY; @KLOT; @LMA; @P; @SDY]. The solvability of Gathering and Rendezvous depends on the activation schedule and the synchronization level. Usually three basic types of schedulers are identified, the fully synchronous (FSYNC), the semi-synchronous (SSYNC) and the asynchronous (ASYNC). In the FSYNC model, there is a common round and in each round all robots are activated simultaneously and Compute and Move are done instantaneously. The SSYNC is the same as FSYNC except that in each round only a subset of robots are activated. In the ASYNC scheduler, there is no restriction about notion of time, Compute and Move in each cycle can take an unpredictable amount of time, and the time interval between successive activations is also unpredictable (but these times must be finite). Gathering and Rendezvous are trivially solvable in FSYNC and the basic model. However, these problems can not be solved in SSYNC without any additional assumptions @FPS. In particular, Gathering can not be solvable even in a restricted subclass of SSYNC scheduler, where exactly one robot is activated in each round (called CENT) @DGCMR. If all robots are initially located on different positions (called distinct Gathering), this Gathering can not be solved even in the ROUND-ROBIN scheduler, in which exactly one robot is activated in each round and always in the same order @DGCMR. In @DFPSY, persistent memory called <span>*light*</span> has been introduced to reveal relationship between the solvability of Gathering and the synchrony of schedulers and they show asynchronous robots with lights equipped with a constant number of colors, are strictly more powerful than semi-synchronous robots without lights. Robots with lights have been also introduced in order to solve Rendezvous without any other additional assumptions. @FSVY [@DFPSY; @V]. Table \[tab:Table-Rendezvous\] shows results to solve Rendezvous by robots with lights in each scheduler, where the circle ($\bigcirc$) and the cross ($\times$) mean Rendezvous is solvable and unsolvable, respectively, the hyphen ($-$) indicates that this part has been solved under weaker conditions or unsolved under the stronger ones, and the question mark ($?$) means that this part has not been solved. In the table, <span>*full-light*</span> means that robots can see not only lights of other robots but also their own light, and <span>*external-light*</span> and <span>*internal-light*</span>[^4] mean that they can see only lights of other robots and only own light, respectively. Full-light is not a weaker assumption than external-light and internal-light, and internal-light seems to be weaker than external-light. Although this relationship is not proved, the results indicate the relationship. For example, Rendezvous is solved by robots with $3$ colors of external-light in SSYNC and non-rigid. On the other hand, it is solved by robots with $6$ colors of internal-light in SSYNC and rigid, where robots can reach the computed destination in <span>*rigid*</span> and they may be stopped before reaching it in <span>*non-rigid*</span>. The number of colors used in the external-light algorithm is less than that in the internal-light one, and the former uses non-rigid assumption but the latter uses the stronger one, rigidness. When robots know the value $\delta$ of a minimum distance movement in non-rigid (denoted by $+\delta$ in the table), the number of colors can be reduced into only $3$ in SSYNC and internal-light. Thus, the assumption robots know $\delta$ in non-rigid seems to be stronger than that in rigid. The power of lights to solve other problems are discussed in @LFCPSV [@DFN]. scheduler movement full-light external-light internal-light no-light ----------- ----------- ------------ ------------------- ------------------- ---------------- FSYNC $-$ $-$ $-$ $-$ $\bigcirc$@FPS rigid $-$ ? 6@FSVY non-rigid $-$ 3@FSVY 3(+$\delta$)@FSVY rigid $-$ 12@FSVY ? non-rigid 2@HDT 3(+$\delta$)@FSVY ? : Rendezvous algorithms by robots with lights.<span data-label="tab:Table-Rendezvous"></span> <span>**Our Contribution**</span> In this paper, we discuss Gathering algorithms by robots with lights and reveal relationship about the solvability between kinds of lights and other additional assumptions. First, we extend the model of robots with lights in which Gathering algorithms can be discussed properly. Unlike Rendezvous, the multiplicity detection affects the solvability of Gathering and in fact, Gathering can be solvable by robots without lights if robots detect the exact number of robots on the same points (strong multiplicity detection) @FPS. When several robots with lights occupy a same location, if we assume that robots can recognize all colors of the robots on the location, the strong multiplicity detection is possible and robots without lights can solve the Gathering problem. Thus, we define the model so that robots can not detect the exact number of robots on the same location provided that robots use only one color. We consider two types of models according to views robots observe. One is called <span>*set-view*</span>, where robots can recognize sets of colors robots have on the same locations[^5]. Another is called <span>*arbitrary-view*</span>, where robots can recognize arbitrary color robots have on the same locations. We usually use the set view assumption in this paper. We also consider the case that several robots occupy a same location and how these robots observe one another. We call <span>*local-aware*</span> if any robot can recognize other robots located on the same position and <span>*local-unaware*</span>, otherwise. If we assume the local-awareness, the view of robots obeys the model (set-view or arbitrary-view) we assume. We usually assume the local-unawareness but we show the local-awareness reduces the number of colors for some Gathering algorithm. In the extended model, we show the following six Gathering algorithms with lights (Table \[tab:Table-Gathering\]). 1. <span>**Algorithm 1**</span>:(2, full, SSYNC, non-rigid), 2. <span>**Algorithm 2**</span>:(3, external, SSYNC, rigid), 3. <span>**Algorithm 3**</span>:(2, external, SSYNC, rigid; local-awareness), 4. <span>**Algorithm 4**</span>+<span>**5**</span>+<span>**6**</span>:(2, internal, SSYNC, non-rigid; D-distant), 5. <span>**Algorithm 7**</span>:(2, external, CENT, non-rigid), and 6. <span>**Algorithm 8**</span>:(2, internal, ROUND-ROBIN, rigid), where Algorithm i:($\alpha, \beta, \gamma, \delta ; \eta$) means Algorithm i uses $\beta$-light with $\alpha$ colors and works in $\gamma$ scheduler and movement restriction $\delta$ with additional assumption $\eta$ (if any). Table \[tab:Table-Gathering\] also shows the unsolvability of Gathering and every algorithm using two colors is optimal with respect to the number of colors, since Gathering is not solvable without lights in every case. We show four algorithms in SSYNC. In the full-light model, we construct an algorithm with the weakest assumptions, non-rigid and the least number of colors ($2$ colors). In the external-light model, we construct an algorithm with $3$ colors of lights and rigid assumption and we reduce the number of colors used in the algorithm into $2$ colors if the local-awareness is assumed. In the internal-light model, with a little bit more assumption we construct an algorithm with lights of $2$ colors if robots know the minimum distance $\delta$ of movement in non-rigid and if initial configurations of robots satisfy some condition called $2\delta$-distant, where arbitrary two robots not occupying the same locations are separated by at least $2\delta$. We reveal some relationship between view of lights (full, external and internal) and the other assumptions (movement, local-awareness) in our algorithms. We also construct Gathering algorithms in CENT and ROUND-ROBIN schedulers. Since Gathering and distinct Gathering can not be solved without lights in CENT and ROUND-ROBIN, respectively @DGCMR, our algorithms use $2$ colors but fairly weak assumptions. We give algorithms in external-light of $2$ colors, non-rigid and CENT, and in internal-light of $2$ colors, rigid and ROUND-ROBIN, respectively. scheduler movement full-light external-light internal-light no-light ------------- ----------- ------------ ------------------ ------------------------- --------------------- FSYNC $-$ $-$ $-$ $-$ $\bigcirc$ ROUND-ROBIN rigid $-$ $-$ 2(f) $\times^{*}$ @DGCMR CENT non-rigid $-$ 2(e) ? $\times$@DGCMR rigid $-$ 3(b),2$^{**}$(c) ? non-rigid 2(a) ? 2(+$\delta$)$^{***}$(d) : Our Gathering algorithms by robots with lights.<span data-label="tab:Table-Gathering"></span> $^*$Distinct Gathering, $^{**}$local-awareness, $^{***}2\delta$-distant The remainder of the paper is organized as follows. In Section \[sec:model\], we define a robot model with lights, gathering problems, and terminologies. Section \[sec:impo\] shows the previous results for Gathering and Rendezvous problems, and Section \[sec:GatheringAlgorithms\] shows Gathering algorithms of robots with lights in SSYNC on several situations for which Gathering algorithms do not exist by using lights. Section \[sec:CSET\] shows Gathering algorithms of robots with lights in CENT. Section \[sec:conclusion\] concludes the paper. Model and Preliminaries {#sec:model} ======================= We consider a set of anonymous mobile robots $\mathcal{R} = \{ r_1, \ldots, r_n \}$ located in ${{\rm I\kern-.22em R}}^2$. Each robot $r_i$ has a persistent state $\ell_i$ called <span>*light*</span> which may be taken from a finite set of colors $L$. We denote by $\ell_i(t)$ the color that the light of robot $r_i$ has at time $t$ and $p_i(t) \in {{\rm I\kern-.22em R}}^2$ the position occupied by $r_i$ at time $t$ represented in some global coordinate system. A <span>*configuration*</span> $\mathcal{C}(t)$ at time $t$ is a multi-set of $n$ pairs $(\ell_i(t),p_i(t))$, each defining the color of light and the position of robot $r_i$ at time $t$. When no confusion arises, $\mathcal{C}(t)$ is simply denoted by $\mathcal{C}$. For a subset $S$ of $L \times {{\rm I\kern-.22em R}}^2$, $\mathcal{L}(S)$ and $\mathcal{P}(S)$ are denoted as projections to $L$ and ${{\rm I\kern-.22em R}}^2$ from $S$, respectively. Each robot $r_i$ has its own coordinate system where $r_i$ is located at its origin at any time. These coordinate systems do not necessarily agree with those of other robots. It means that there is no common knowledge of unit of distance, directions of its coordinates, or clockwise orientation (<span>*chirality*</span> [^6]). At any point of time, a robot can be active or inactive. When a robot $r_i$ is activated, it executes $\mathit{Look}$, $\mathit{Compute}$, and $\mathit{Move}$ cycles: - <span>**Look:**</span> The robot $r_i$ activates its sensors to obtain a snapshot which consists of a pair of light and position for every robot with respect to the coordinate system of $r_i$. Let $\mathcal{SS}_i(t)$ denote the snapshot of $r_i$ at time $t$. We assume robots can observe all other robots(unlimited visibility). Note that $\mathcal{SS}_i(t)$ represents a sub-multi-set of $\mathcal{C}(t)$ according to imposed assumptions by the local coordinate system of $r_i$, where $r_i$ is at the origin. - <span>**Compute:**</span> The robot $r_i$ executes its algorithm using the snapshot and the color of its own light (if allowed by the model) and returns a destination point $des_i$ expressed in its coordinate system and a light $\ell_i \in L$. The robot $r_i$ sets its own light $\ell_i$ to the color. - <span>**Move:**</span> The robot $r_i$ moves to the computed destination $des_i$. A robot $r$ is said to <span>*collide*</span> with robot $s$ at time $t$ if $p(r,t)=p(s,t)$ and at time $t$ $r$ is performing $\mathit{Move}$. The collision is <span>*accidental*</span> if $r$'s destination is not $p(r,t)$. Since robots are seen as points, we assume that accidental collisions are immaterial. A moving robot, upon causing an accidental collision, proceeds in its movement without changes, in a "hit-and-run" fashion @FPS. If the robot may be stopped by an adversary before reaching the computed destination, the movement is said to be <span>*non-rigid*</span>. Otherwise, it is said to be <span>*rigid*</span>. If stopped before reaching its destination, we assume that a robot moves at least a minimum distance $\delta >0$. Note that without this assumption an adversary could make it impossible for any robot to ever reach its destination. If the distance to the destination is at most $\delta$, the robot can reach it. If the movement is non-rigid and robots know the value of $\delta$, it is called <span>*non-rigid($+\delta$)*</span>. In ${\mathit Look}$ operation, a snapshot $\mathcal{SS}_i$ of $r_i$ should contain positions of all robots including $r_i$. However, if other robots are located on $p_i$ and $r_i$ can recognize the other robots, robots have somehow multiplicity detection at this point. Thus, we need some treatment of observation of other robots located on $p_i$ for robot $r_i$. If any robot $r_i$ can observe other robots located on $p_i$, it is said to be <span>*local-aware*</span>. Otherwise, it is said to be <span>*local-unaware*</span>. Note that if we assume the local-awareness, $r_i$ recognizes whether other robots occupy the location $p_i$ or not. In the following, we usually use the local-unaware assumption but we will show that we can reduce the number of colors for some Gathering algorithm if we assume the local-awareness. A scheduler decides which subset of robots is activated for every configuration. The schedulers we consider are asynchronous and semi-synchronous and it is assumed that schedulers are <span>*fair*</span>, each robot is activated infinitely often. - <span>**ASYNC:**</span> The asynchronous scheduler (ASYNC), activates the robots independently, and the duration of each $\mathit{Compute}$, $\mathit{Move}$ and between successive activities is finite and unpredictable. As a result, robots can be seen while moving and the snapshot obtained with the Look operation and its actual configuration when performing the $\mathit{Compute}$ operation are not the same and so its computation may be done with the old configuration. - <span>**SSYNC:**</span> The semi-synchronous scheduler (SSYNC) activates a subset of all robots synchronously and their $\mathit{Look}$-$\mathit{Compute}$-$\mathit{Move}$ cycles are performed at the same time. We can assume that activated robots at the same time obtain the same snapshot and their $\mathit{Compute}$ and $\mathit{Move}$ are executed instantaneously. In SSYNC, we can assume that each activation defines discrete time called <span>*round*</span> and $\mathit{Look}$-$\mathit{Compute}$-$\mathit{Move}$ is performed instantaneously in one round. In the following, since we consider SSYNC and its subsets, we use round and time interchangeably. As a special case of SSYNC, if all robots are activated in each round, the scheduler is called fully-synchronous (FSYNC). We also consider the following subsets of SSYNC. - <span>**CENT:**</span> In CENT scheduler exactly one robot is activated in each round. - <span>**$k$-BOUNDED:**</span> In $k$-BOUNDED scheduler there exists some bound $k$ such that between any two consecutive activation of any robot, no other robot is activated more than $k$ times. - <span>**ROUND-ROBIN:**</span> ROUND-ROBIN scheduler is $1$-BOUNDED and CENT. It means that robots are activated one in each round and always in the same sequence. Let $\mathcal{C}(t)$ be a configuration at round $t$. When $\mathcal{C}(t)$ reaches $\mathcal{C}(t+1)$ by executing the cycle at $t$, it is denoted as $\mathcal{C}(t) \rightarrow \mathcal{C}(t+1)$. The reflective and transitive closure is denoted as $\rightarrow^*$. Snapshots may be different by using assumptions even if these configurations are the same, and they depend on multiplicity detection or how robots can see lights of other robots when robots equip with lights. The robots are said to be capable of <span>*multiplicity detection*</span> whether they can distinguish if a point is occupied by at least two robots. The multiplicity detection is <span>*strong*</span> if the robots can detect the exact number of robots on the same points. In our settings, robots have persistent lights and can change its color after $\mathit{Compute}$ operation. We consider the following three robot models according to the visibility of lights. - <span>*full-light*</span>, the robot can recognize not only colors of lights of other robots but also its own color of light. - <span>*external-light*</span>, the robot can recognize only colors of lights of other robots but cannot see its own color of light. Note robot can change its own color. - <span>*internal-light*</span>, the robot can recognize only its own color of light but cannot see colors of lights of other robots. When a robot performs $\mathit{Look}$ operation in the internal-light model, its snapshot is the same as that in the case of robots without lights. On the other hand, in the full-light or external-light model, it obtains a snapshot with locations of other robots and their colors. In this case we consider several types of snapshots according to view robots observe. Given a snapshot $\mathcal{SS}_i$ of a robot $r_i$ and a point $p_j(j \neq i)$ included in $\mathcal{P}(\mathcal{SS}_i)$, a view $V_i[p_j]$ of $p_j$ in $\mathcal{SS}_i$ is a subset of $AL_i[p_j]=\{ \ell | (\ell, p_j) \in \mathcal{SS}_i, r_j \neq r_i \}$, where $AL_i[p_j]$ is a multi-set of colors of other robots that $r_i$ can see at point $p_j$ [^7]. For any robot $r_i$ and any point $p$ of snapshot of $r_i$, if $V_i[p]=AL_i[p]$, view of robots is called <span>*multi-set- view*</span>. If $V_i[p]$ regards $AL_i[p]$ as just a set, it is called <span>*set-view*</span>. If $V_i[p]$ is a set of any single element taken from $AL_i[p]$, it is called <span>*arbitrary-view*</span>. Let $V_i$ denote $\cup_{(\ell,p) \in \mathcal{SS}_i}V_i[p]$. Multi-set-view is a strong assumption, because robots without lights (with one color) can have strong multiplicity detection if multi-set-view is assumed. In fact we can solve a Gathering problem by using robots without lights and jonjenkins@example.com. On the other hand, set-view and arbitrary-view do not imply multiplicity detection. In the following we assume set-view or arbitrary-view. An $n$-<span>*Gathering*</span> problem is defined as follows: given $n (\geq 2)$ robots initially placed at arbitrary positions in ${{\rm I\kern-.22em R}}^2$, they congregate in finite time at a single location which is not predefined. In the following, the case $2$-Gathering problem is called <span>*Rendezvous*</span> and the $n$-Gathering problem ($n \geq 3)$ is simply called Gathering. Gathering is said to be <span>*distinct*</span> if all robots are initially placed in different positions. An algorithm solving Gathering is said to be <span>*self-stabilizing*</span> if robots are initially set their lights to arbitrary colors and they start their execution from $\mathit{Look}$ operation. Let $\mathcal{S}$ be a configuration or a snapshot. Given $\mathcal{S}$, let $\mathcal{H}(\mathcal{S})$ be the convex hull defined by $\mathcal{S}$, let ${\partial}\mathcal{H}(\mathcal{S})$ denote the set of robots on the border of $\mathcal{H}(\mathcal{S})$, and let $\mathcal{I}(\mathcal{S})$ the set of robots that are interior of $\mathcal{H}(\mathcal{S})$. Given two points $p,q \in {{\rm I\kern-.22em R}}^2$, we indicate the line segment by $\overline{pq}$ and its length by $|\overline{pq}|$. Given a snapshot $\mathcal{SS}$, $\mathit{SEC}(\mathcal{SS})$ denotes the smallest enclosing circle containing $\mathcal{P}(\mathcal{SS})$, and the length of its diameter and its center are denoted by $\mathit{Diam}(\mathcal{SS})$ and $\mathit{CTR}(\mathcal{SS})$, respectively. A longest distance segment (*LDS*, for short) in $\mathcal{SS}$ is a line segment $\overline{pq}$ such that $p,q \in \mathcal{P} (\mathcal{SS})$ and $|\overline{pq}|=max_{x,y \in \mathcal{P} (\mathcal{SS})}|\overline{xy}|$ and a set of the longest distance segments in $\mathcal{SS}$ is denoted by $\mathit{LDS}(\mathcal{SS})$. We use the following geometric properties about the smallest enclosing circles and the longest distance segments to obtain a unique longest distance segments. Let $\mathcal{S}$ be a configuration or a snapshot. \[lemma:LDSofCH1\]For any $\overline{pq} \in \mathit{LDS}(\mathcal{S})$, $|\overline{pq}| \leq \mathit{Diam}(\mathcal{S})$. The two points $p$ and $q$ exist in $\mathit{SEC}(\mathcal{S})$. \[lemma:LDSofCH2\] If $\overline{pq} \in \mathit{LDS}(\mathcal{S})$, then $p,q \in \mathcal{H}(S)$. Suppose that $p$ or $q$ is not a vertex of $\mathcal{H}(S)$. Let $\overline{p_1p_2}$ and $\overline{q_1q_2}$ be the nearest edges of $\mathcal{H}(S)$ from $p$ and $q$, respectively. Note that $p$ and/or $q$ can be on the edges not vertices. Comparing $\overline{pq}$ and the convex quadrilateral (or the triangle) composed of $\overline{p_1p_2}$ and $\overline{q_1q_2}$, the longer diagonal (or the longest edge) is longer than $\overline{p_1p_2}$. It contradicts that $\overline{pq}$ is the longest distance segment. \[lemma:LDSofCH3\] If for any $\overline{pq} \in \mathit{LDS}(\mathcal{S})$, both $p$ and $q$ are located on $\mathit{SEC}(\mathcal{S})$, for an endpoint $p$ such that $\overline{pq} \in \mathit{LDS}(\mathcal{S})$, $|\{ q | \overline{pq} \in \mathit{LDS}(\mathcal{S})\}| \leq 2$. Assume that there are three *LDS*s with the endpoint $p$ and let the other endpoints be $q_1, q_2$ and $q_3$. Since $q_1, q_2$ and $q_3$ are located on $\mathit{SEC}(\mathcal{S})$, $\mathit{SEC}(\mathcal{S})$ must be a circle with the center $p$, which is contradiction that $p$ is also on $\mathit{SEC}(\mathcal{S})$. \[lemma:LDSofCH4\] If both $p$ and $q$ are endpoints of *LDS* ($\overline{pq} \in \mathit{LDS}(\mathcal{S}))$ and are located on $\mathit{SEC}(\mathcal{S})$, then $\mathit{Diam}({\cal S})/2 < |\overline{pq}|$. Let $c=\mathit{CTR}(\mathcal{S})$ and let $a$ and $b$ be distinct points on $\mathit{SEC}(\mathcal{S})$ such that $\triangle{apc}$ and $\triangle{bpc}$ are equilateral triangles. If $\mathit{Diam}(\mathcal{S})/2 \geq |\overline{pq}|$, all points in $\mathcal{S}$ must exist in the sector consisting of $\overline{ca}$ and $\overline{cb}$ and the shorter arc $\stackrel{\frown}{a b}$. Then $S\mathit{EC}(\mathcal{S})$ is the circle having $\overline{ab}$ as the diameter. Contradiction. \[lemma:LDSofCH5\] If $\overline{pq}, \overline{rs} \in \mathit{LDS}(\mathcal{S})$ and $p,q,r,s$ are distinct, then $\overline{pq}$ and $\overline{rs}$ have an intersection. If $\overline{pq}$ and $\overline{rs}$ do not have any intersection, the longer diagonal of the quadrilateral composed of $\overline{pq}$ and $\overline{rs}$ becomes the longest line segment. \[lemma:LDSofCH6\] Let $p$ and $q_1 (\overline{pq_1} \in \mathit{LDS}(\mathcal{S}))$ be located on $\mathit{SEC}(\mathcal{S})$ Assume that $\overline{pq_1}$ is not a diameter of $\mathit{SEC}(\mathcal{S)}$. Let $q_2$ be the intersection of a circle with center $p$ and radius $|\overline{pq_1}|$ and $\mathit{SEC}(\mathcal{S})$ and not $q_1$. Then there are no points on arc $\stackrel{\frown}{q_1 q_2}$ of $\mathit{SEC}(\mathcal{S})$ not containing $p$ except $q_1$ and $q_2$ (see Figure \[fig:lemma6\]). If there is a point $q (\neq q_1, q_2)$ on the arc $\stackrel{\frown}{q_1 q_2}$, $| \overline{pq}|$ is greater than the *LDS*. ![image](Fig_lemma6.eps){width="4cm"} \[lemma:LDSofCH7\] Assume that for any $\overline{pq} \in \mathit{LDS}(\mathcal{S})$, both $p$ and $q$ are located on $\mathit{SEC}(\mathcal{S})$. If $\mathcal{H}(\mathcal{S})$ is not a regular polygon, there exists a point $p_0$ such that $\overline{p_0q} \in \mathit{LDS}(\mathcal{S})$ and $\overline{p_0r}\not \in \mathit{LDS}(\mathcal{S})$ for any $r (\neq q) \in \mathcal{P} (\mathcal{S})$. The point $p_0$ is called a <span>*single-endpoint*</span> of *LDS* (Figure \[fig:lemma7\](a)). If there exists no point $p_0$ such that $\overline{p_0q} \in \mathit{LDS}(\mathcal{S})$ and $\overline{p_0r}\not \in \mathit{LDS}(\mathcal{S})$ for any $r (\neq q)$, $|\{ q | \overline{pq} \in \mathit{LDS}(\mathcal{S})\}| \geq 2$ for any point $p$ on $\mathit{SEC}(\mathcal{S})$. Since $|\{ q | \overline{pq} \in \mathit{LDS}(\mathcal{S})\}| \leq 2$ by Lemma \[lemma:LDSofCH3\], $|\{ q | \overline{pq} \in \mathit{LDS}(\mathcal{S})\}| = 2$ for any point $p$. Let $n$ be the number of points located on $\mathit{SEC}(\mathcal{S})$. For a point $p$, let $\overline{pq}$ and $\overline{pr}$ be two *LDS*s having $p$ as the endpoint. Note that $q$ and $r$ are also located on $\mathit{SEC}(\mathcal{S})$. Let $pp'$ be the diameter of $\mathit{SEC}(\mathcal{S})$. Then $\angle{qpp'}=\angle{rpp'}$ (denoted as $\alpha$). Since this property holds for any point on $\mathit{SEC}(\mathcal{S})$, $\alpha$ must be $(n+2)\pi/n$ (Figure \[fig:lemma7\](b)). Otherwise, it is easily verified that it contradict that the number of points located on $\mathit{SEC}(\mathcal{S})$ is $n$. When $\alpha=(n+2)\pi/n$, the points on $\mathit{SEC}(\mathcal{S})$ constitute a regular polygon and it contradicts the assumption of this lemma. ![image](Fig_lemma7.eps){width="100.00000%"} Previous Results for Rendezvous and Gathering {#sec:impo} ============================================= Rendezvous is trivially solvable with CENT or FSYNC scheduler. The multiplicity detection does not help to solve Rendezvous and it is generally unsolved with SSYNC, even if chirality is assumed. \[theorem:Rand\_Impo\] <span>*@FPS*</span> Rendezvous is deterministically unsolvable in SSYNC scheduler even if chirality is assumed. If robots have a constant number of colors in their lights, Rendezvous can be solved shown in the following theorem (see Table \[tab:Table-Rendezvous\]). <span>*@HDT [@FSVY]*</span> 1. Rendezvous is solved in full-light, non-rigid and ASYNC with $2$ colors. 2. Rendezvous is solved in external-light, non-rigid and SSYNC with $3$ colors. 3. Rendezvous is solved in external-light, rigid and ASYNC with $12$ colors. 4. Rendezvous is solved in external-light, non-rigid and ASYNC with $3$ colors and knowledge of a minimum distance $\delta$ robots move. 5. Rendezvous is solved in internal-light, rigid and SSYNC with $6$ colors. 6. Rendezvous is solved in internal-light, non-rigid and SSYNC with $3$ colors and knowledge of a minimum distance $\delta$ robots move. Impossibility and/or possibility results for Gathering are stated in the following theorems. \[theorem:ssync\] <span>*@FPS [@DGCMR]*</span> If we do not assume strong multiplicity detection, the followings holds. 1. Gathering is deterministically unsolvable in SSYNC. \[theorem:centrr\] 2. Gathering is deterministically unsolvable in $2$-BOUNDED and CENT. 3. Distinct Gathering is deterministically unsolvable in ROUND-ROBIN. The impossibility holds even if we assume chirality, and rigid movement or non-rigid movement with knowledge of minimum distance $\delta$. \[theorem:GatheringGen\] <span>*@FPS*</span> 1. With strong multiplicity detection, $n$-Gathering is solved in SSYNC if and only if $n$ is odd. 2. In ASYNC, with strong multiplicity detection, distinct $n$-Gathering is solved with $n (\geq 3)$ robots. Multiplicity detection is a strong assumption to solve Gathering. In the following section, without strong multiplicity detection we consider Gathering algorithms for robots with lights such that the number of colors is the minimum and additional assumptions are the weakest. Gathering Algorithms in SSYNC {#sec:GatheringAlgorithms} ============================= In this section, we show the following four Gathering algorithms with lights in SSYNC. 1. <span>**Algorithm 1**</span>:(2, full, SSYNC, non-rigid), 2. <span>**Algorithm 2**</span>:(3, external, SSYNC, rigid), 3. <span>**Algorithm 3**</span>:(2, external, SSYNC, rigid; local-awareness), and 4. <span>**Algorithm 4**</span>+<span>**5**</span>+<span>**6**</span>):(2, internal, SSYNC, non-rigid; $2\delta$-distant). The idea of Gathering algorithms shown here is that the algorithm divides into two steps as follows: 1. We make a configuration where all robots are located on a line segment (called *onLDS*) from any initial configuration satisfying the corresponding conditions. 2. We make a gathering algorithm from the configuration *onLDS*. Step (1) can be performed with *ElectOneLDS* @IKIW, that reduces any configuration to one where there is the unique *LDS* or Gathering is achieved. This algorithm needs chirality assumption but can be performed in SSYNC and without lights. Thus, we will have to use lights to implement Step (2) from the configuration *onLDS*. It is easily verified that *ElectOneLDS* can be modified so that it can be performed in the following assumptions, (a) non-rigid moving, SSYNC and chirality, (b) non-rigid moving, CENT and non-chirality. \[lemma:ElectLDS\] With chirality, an algorithm can be constructed to make *onLDS* from any configuration in SSYNC and non-rigid moving without lights, unless Gathering is achieved. If CENT is assumed, this algorithm can be implemented without chirality. The algorithm *ElectOneLDS* to make *onLDS* works in rigid movement @FPS. We show a modified *ElectOneLDS* to work in non-rigid movement. The modified *ElectOneLDS* works as follows: We call a configuration <span>*contractible*</span> if (1) its convex hull $CH$ is symmetric and every robot is located at a vertex of *CH* or at the center of *CH*, or (2) *CH* is not symmetric and there are no robots inside *CH*. The algorithm makes a contractible configuration from the current configuration, unless it already contractible. It can be done by each active robot that is not at a vertex of *CH* moves to the center of *CH* if it is symmetric, or each active robot that is neither at a vertex of *CH* nor on an edge of *CH* (that is, inside of *CH*) moves to a vertex of *CH*. In making contractible configurations, since the convex hull is not changed, the algorithm can work in non-rigid moving. Note that robots may be located on edges of *CH* in contractible and non-symmetric configurations but can not be located on edges of *CH* in contractible and symmetric ones. If *CH* becomes contractible, a unique *LDS* is obtained by decreasing the number of edges of *CH* or the diameter of *CH* until the configuration has a unique *LDS*. If *CH* is contractible and symmetric, any active robot moves to the center of *CH*. In this case, if *CH* is not changed the number of robots at vertices of *CH* decreases via non-contractible configurations. Otherwise, the configuration becomes one of the following ones unless Gathering is attained; (1) it remains contractible and symmetric, (2) the number of edges of the convex hull is decreased and it becomes contractible one via non-contractible configurations. In the both cases, the diameter of *CH* is eventually reduced. If *CH* is contractible and asymmetric, the number of edges is decreased by some robots moving so to contract shortest-length edges in *CH*. Each robot $r$ on a vertex of *CH* checks the distance to the clockwise and counter-clockwise neighboring robots at vertices of *CH*. If the edge on the left is a shortest-length edge and the robot is located at the leftmost, this edge becomes contracting. The leftmost robot and the robots on this edge move to the the other vertex of the edge until the edge is contracting. Since all non-contracting robots do not move and the edge remains the shortest-length, this contraction can be done even in non-rigid moving, In this way, the number of edges of the convex hull is decreasing. In SSYNC, chirality is necessary for determining the leftmost robot of the shortest-length edge. However, since only one robot is activated in CENT, contracting the shortest-length edge can be done without chirality. Full-light ---------- \[h\] 111 = 11 = 11 = 11 = 11 = 11 = 11 = : full-light, non-rigid, $2$ colors($A$ and $B$), set-view, SSYNC<span>\ </span><span>*Input*</span>: configuration *onLDS*, all robots have color $A$ <span>\ </span> : ${\cal L}({\cal SS}_i)$ <span>**of** </span> <span>\ </span> : $\{ A \}$: <span>\ </span> : $|{\cal P}_A({\cal SS}_i)| = 1$ <span>**then**</span> $des_i \leftarrow p_i$ // gathered!<span>\ </span> : $|{\cal P}_A({\cal SS}_i)| = 2$ <span>**then**</span> $\ell_i \leftarrow B$; $des_i \leftarrow (p_n + p_f)/2$<span>\ </span> : //$|{\cal P}_A({\cal SS}_i)| \geq 3$<span>\ </span> : $(p_i = p_n)$ <span>**then**</span> $des_i \leftarrow p_i$ //I am at either endpoint<span>\ </span> : $des_i \leftarrow p_n$<span>\ </span> : $\{B \}$: <span>\ </span> : $(p_i = p_n)$ <span>**then**</span> $\ell_i \leftarrow A$<span>\ </span> : $des_i \leftarrow p_i$ // stay<span>\ </span> : $\{A, B \}$: <span>\ </span> : $\ell_i = A$ <span>**then**</span><span>\ </span> : $|{\cal P}_A({\cal SS}_i)| = 1$ <span>**then**</span> $des_i \leftarrow p_i$ // stay<span>\ </span> : ${\cal P}_A({\cal SS}_i) = \{ p_n,p_f\}$ <span>**and**</span> ${\cal P}_B({\cal SS}_i) = \{ \frac{p_n+p_f}{2} \}$ <span>**then**</span><span>\ </span> : $\ell_i \leftarrow B$ <span>\ </span> : $des_i \leftarrow (p_n + p_f)/2$<span>\ </span> : // $\ell_i = B$<span>\ </span> : $|{\cal P}_A({\cal SS}_i)| = 1$ <span>**then**</span> $des_i \leftarrow p (\in {\cal P}_A({\cal SS}_i)) $<span>\ </span> : $des_i \leftarrow (p_n + p_f)/2$ //$|{\cal P}_A({\cal SS}_i)| = 2$ <span>\ </span> : Gathering algorithm with full-light uses two colors of full-light and works in non-rigid movement shown in <span>**Algorithm \[algo:FLG\]**</span>. It reduces any configuration of *onLDS* to a gathering configuration. In the algorithm for robot $r_i$, endpoints of the *LDS* are denoted by $p_n$ and $p_f$, where $p_n$ is the nearest endpoint from $p_i$ and $p_f$ is the farthest one from $p_i$. Note that if $p_i$ is either of endpoints, $p_i=p_n$ and $p_f$ is the other endpoint. Since full-light is assumed, robot $r_i$ can use colors of other robots in $\mathcal{SS}_i$ and its own light $\ell_i$ in the algorithm. For snapshot $\mathcal{SS}_i$ and color $A$ and $B$, $\mathcal{P}_A(\mathcal{SS}_i)$ and $\mathcal{P}_B(\mathcal{SS}_i)$ denote sets of positions on which robots with color $A$ and $B$ are located, respectively. ![image](Fig_algo1.eps) Initially all robots are located on the unique *LDS* and have color A. Figure \[fig:Full-light\] shows the transition diagram of <span>**Algorithm \[algo:FLG\]**</span>, where nodes denote configurations and a directed edge denotes transition from a configuration to a configuration. In Figure \[fig:Full-light\], labels of directed edges have the following meanings. L.\# means that this transition is shown by Lemma \#. "$-\delta$" ("$2\delta$") means when the transition occurs, the distance between the endpoints reduces at least $-\delta (2\delta)$ and "\#A decreases" means the numbers of robots with color A at the endpoints decrease. Each configuration is denoted by a regular-expression-like sequence of colors robots have from one endpoint to another. Formally we define <span>*color-configurations*</span> as follows. Let $C(t)$ be a configuration at time $t$, $p$ and $q$ be the endpoints of the *LDS*. Configuration $C(t)$ has a <span>*color-configuration*</span> 1. $\alpha \beta$, if all robots at $p$ have color $\alpha$, all robots at $q$ have color $\beta$ ($\alpha, \beta \in \{ A, B\}$) and there are no robots inside the *LDS*, 2. $\alpha \gamma \beta$, if all robots at $p$ have color $\alpha$, all robots at $q$ have color $\beta$ ($\alpha, \beta \in \{ A, B\}$), all robots at the mid-point of the *LDS* have color $\gamma$ and there are no robots except on the three locations, and 3. $\alpha \gamma^+ \beta$, if all robots at $p$ have color $\alpha$, all robots at $q$ have color $\beta$ ($\alpha, \beta \in \{ A, B\}$) and there is at least one location except the midpoint of the *LDS* inside the *LDS* where all robots have color $\gamma$. Note that $\alpha \gamma^+ \beta$ contains configurations that the midpoint of the *LDS* may be occupied by some robot(s) with color $\gamma$, and $\alpha \gamma \beta$ and $\alpha \gamma^+ \beta$ are exclusive. If either (1) or (3) is satisfied, we denote $\alpha \gamma^* \beta$. Let $dis(C(t))$ denote the length of the *LDS* in the configuration $C(t)$. The outline of behaviour of <span>Algorithm \[algo:FLG\]</span> is explained as follows. Suppose that all robots become active (FSYNC). From any initial color-configuration of *onLDS* ($AA^*A$ or $AAA$), robots with $A$ located not at endpoints move to endpoints and robots with $A$ located at endpoints stay(<span>**lines**</span> 5-7) it becomes the color-configuration $AA$. When the color-configuration is $AA$, each robot changes its color to $B$ and move to the midpoint(<span>**line**</span> 4). If they can reach to the destination, the gathering is achieved. However, since we assume non-rigid movement, some of them may stop before reaching the midpoint and its configuration becomes $BB^*B$ or $BBB$, where the former is $BB$ if the locations all robots stop are only two, otherwise $BB^+B$ and the latter is possible when there is a robot moving to the midpoint. In the both cases the length of its *LDS* is decreased by at least $2\delta$ (denoted by $-2\delta$ on the directed edge from $AA$ to $BB^*B$ in Fig. \[fig:Full-light\]). From the color-configuration $BB^*B$ or $BBB$, the algorithm changes colors of robots at endpoints to $A$ (<span>**lines**</span> 8-10) and can change the color-configuration directly to $AB^+A$ (from $BB^+B$), $AA$ (from $BB$), or $ABA$ (from $BBB$). If the color-configuration $AB^+A$ occurs, robots with $B$ move to the midpoint (<span>**line**</span> 19), and robots with $A$ stay until all robots with $B$ move to the midpoint(<span>**lines**</span> 14-16). In this case the configuration also become $ABA$ and robots with $A$ change the color to $B$ and move to the midpoint (<span>**lines**</span> 14-16) and Gathering is achieved after repeating the transitions from $ABA$ to $BB^*B$, from $BB^*B$ to $AB^+A$, and from $AB^+A$ to $ABA$. If the color-configuration $AA$ occurs, repeating the above transitions Gathering attained. However, since all robots do not become active at every round in general, the behaviors are complicated and all color-configurations shown in Figure \[fig:Full-light\] can occur. Since any cycle in the graph can reduce the length of *LDS* (denoted by $-\delta$ or $-2\delta$ in Fig. \[fig:Full-light\]) or the number of robots with $A$ and located at endpoints (denoted by $\#A$ decreases in Figure \[fig:Full-light\]), we can show that <span>**Algorithm \[algo:FLG\]**</span> solves Gathering from any initial configuration of *onLDS*. \[AAA-AA\] If $C(t)$ is a configuration at time $t$ with color-configuration $AA^*A$ or $AAA$, there is a time $t' (\geq t)$ such that $C(t) \rightarrow^* C(t')$, $C(t')$ has a color-configuration $AA$, and $dis(C(t'))=dis(C(t))$. If the color-configuration is $AA$, the lemma holds as $t'=t$. Otherwise, since robots located inside the *LDS* move to the nearest endpoint and robots at the endpoint stay there as long as there is a robot located inside the *LDS* (<span>**lines**</span> 5-7), the color-configuration becomes $AA$. Let $C(t)$ be a configuration at time $t$ with color-configuration $AA$. If we consider time $t+1$ such that $C(t) \rightarrow C(t+1)$, then 1. $C(t+1)$ is a gathering configuration, 2. $C(t+1)$ has a color-configuration $BB^*B$ or $BBB$, and $dis(C(t+1)) \leq dis(C(t)) - 2 \delta$, 3. $C(t+1)$ has a color-configuration $AB^*B$ or $ABB$ (or $BB^*A$ or $BBA$), and $dis(C(t+1)) \leq dis(C(t)) - \delta$, 4. $C(t+1)$ has a color-configuration $ABA$, and $dis(C(t+1))=dis(C(t))$, or 5. $C(t+1)$ has a color-configuration $AB^+A$, and $dis(C(t+1))=dis(C(t))$. There are five cases according to the activeness of robots. 1. If all robots become active and they can reach the destination (the midpoint of the *LDS*), the gathering is attained. 2. If all robots become active but they can not reach the destination, they change their color to $B$ and move at least $\delta$. Thus the color-configuration becomes $BB^+B$, $BB$ or $BBB$ as shown in the example above. In any case, since all robots move at least $\delta$, $dis(C(t+1)) \leq dis(C(t)) - 2 \delta$. 3. If all robots at one endpoint become active but some robots at the other endpoint are inactive, all active robots change their color to $B$ and all inactive robots do not change their color and stay there. Since the color of all robots at the endpoint inactive robots are located is $A$ and the color of the other robots become $B$ they move at least $\delta$, the color-configuration becomes $AB^*B$ $ABB$ (or $BB^*A$ or $BBA$). In this case since all active robots move at least $\delta$, $dis(C(t+1)) \leq dis(C(t)) - \delta$. 4. If there exist inactive robots at the both endpoints and active robots can reach the destination, the color-configuration becomes $ABA$ and $dis(C(t+1)) =dis(C(t))$. 5. If there exist inactive robots at the both endpoints and some active robots can not reach the destination, the color-configuration becomes $AB^+A$ and $dis(C(t+1))=dis(C(t))$. If $C(t)$ is a configuration at time $t$ with color-configuration $AB^+A$, there is a time $t' (\geq t)$ such that $C(t) \rightarrow^* C(t')$, $C(t')$ has a color-configuration $ABA$, and $dis(C(t'))=dis(C(t))$. In the configuration with color-configuration $AB^+A$, robots with $A$ do not move until the color-configuration becomes $ABA$ (<span>**lines**</span> 12-16) robots with $B$ move to the midpoint of the *LDS*. Thus it becomes $ABA$ and $dis(C(t'))=dis(C(t))$. If $C(t)$ is a configuration at time $t$ with color-configuration $BB^*B$ or $BBB$, there is a time $t' (> t)$ such that $C(t) \rightarrow^* C(t')$ and one of the followings holds, 1. $C(t')$ is a gathering configuration, 2. $C(t')$ has a color-configuration $AB^+A$, and $dis(C(t')) = dis(C(t))$, 3. $C(t')$ has a color-configuration $ABA$, and $dis(C(t'))=dis(C(t))$, or 4. $C(t')$ has a color-configuration $AA$, and $dis(C(t'))=dis(C(t))$. Assume that all robots become active at time $t$. If the color-configuration is $BB$, then the color-configuration becomes $AA$ at time $t'=t+1$ (case (4)). If the color-configuration is $BB^+B$ or $BBB$, then the color-configuration becomes $AB^+A$ or $ABA$ at time $t'=t+1$, respectively (case (2) or (3)). These transitions occur from <span>**lines**</span> 8-10 of the algorithm. Otherwise, there are two cases, (a) some robots at only one endpoint become active, and (b) robots at the both endpoints become active. Note that active robots not located on the endpoints do nothing in these configurations. 1. In this case, active robots change their color into $A$ at time $t+1$ and since $|\mathcal{P}_A(C(t+1))| = 1$, robots with $A$ stay at the positions (<span>**lines**</span> 12-13) and robots with $B$ move to the position at robots with $A$ (<span>**lines**</span> 17-18) and the gathering is attained (case (1)). 2. In this case, active robots at the both endpoints change their colors into $A$ at time $t+1$ and since $|{\cal P}_A(C(t+1))| = 2$ and robots with $A$ do not move and robots with $B$ move to the midpoints of the *LDS*, the color-configuration eventually becomes $ABA$ (case (3)). Let $C(t)$ be a configuration at time $t$ with color-configuration $ABA$. If we consider time $t'$ such that $C(t) \rightarrow^* C(t')$, then 1. $C(t')$ is a gathering configuration, 2. $C(t')$ has a color-configuration $AB^*A$, and $dis(C(t'))=dis(C(t))$ and the number of robots at the endpoints and with $A$ is decreased, 3. $C(t')$ has a color-configuration $AB^*B$ (or $BB^*A$), and $dis(C(t')) \leq dis(C(t)) - \delta$, or 4. $C(t')$ has a color-configuration $BB^*B$ or $BBB$, and $dis(C(t')) \leq dis(C(t))-2\delta$. This lemma can be proved similar to the one of Lemma \[AAA-AA\]. \[lemma:ABBG\] If $C(t)$ is a configuration at time $t$ with color-configuration $AB^*B$ or $ABB$ (or $BB^*A$ or $BBA$), there is a time $t' (\geq t)$ such that $C(t) \rightarrow^* C(t')$, $C(t')$ is a gathering configuration. Since $|{\cal P}_A(C(t))| = 1$, robots with $A$ stay at the position (<span>**lines**</span> 12-13) and robots with $B$ move to the position at robots with $A$ (<span>**lines**</span> 17-18) and the gathering is attained. We have the following theorem using Lemmas \[lemma:ElectLDS\]-\[lemma:ABBG\]. \[th:Full-light\] Gathering is solvable in full-light of $2$ colors, non-rigid, and SSYNC, with set-view and agreement of chirality. External-light -------------- \[h\] 111 = 11 = 11 = 11 = 11 = 11 = 11 = : external-light, rigid, $3$ colors ($A$,$B$,$C$), local-unawareness, set-view, SSYNC<span>\ </span><span>*Input*</span>: $(|{\cal P}({\cal SS}_i)| =3)$ <span>**and**</span> $(|\overline{p_f p_m}|=|\overline{p_m p_n}|)$ or $|{\cal P}({\cal SS}_i)| =2$, all robots have color $A$.<span>\ </span> : $|{\cal P}({\cal SS}_i)| =2$ <span>**then**</span> <span>\ </span> : $C \in {\cal L}_{p_f}({\cal SS}_i)$ <span>**then**</span> $\ell_i \leftarrow C$; $des_i \leftarrow p_f$ <span>\ </span> : ${\cal L}_{p_f}({\cal SS}_i) = \{ A \}$ <span>**then**</span> $\ell_i \leftarrow B$; $des_i \leftarrow (p_n + p_f)/2$<span>\ </span> : ${\cal L}_{p_f}({\cal SS}_i) = \{ B \}$ <span>**then**</span> $\ell_i \leftarrow C$; $des_i \leftarrow p_i$ // stay<span>\ </span> : $(|{\cal P}({\cal SS}_i)| =3)$ <span>**and**</span> $(|\overline{p_f p_m}|=|\overline{p_m p_n}|)$ <span>**then**</span><span>\ </span> : $p_i =p_m$ <span>**then**</span> //I am at the midpoint.<span>\ </span> : $\ell_i \leftarrow B$<span>\ </span> : $des_i \leftarrow p_m$ //stay<span>\ </span> : $ {\cal L}_{p_f}({\cal SS}_i)=\{B\}$ <span>**and**</span> $ {\cal L}_{p_m}({\cal SS}_i)=\{B\}$ <span>**then**</span><span>\ </span> : $\ell_i \leftarrow C$<span>\ </span> : $des_i \leftarrow p_i$ //stay<span>\ </span> : $ {\cal L}_{p_f}({\cal SS}_i)\cap \{A, C\} \not = \emptyset$ <span>**and**</span> $ {\cal L}_{p_m}({\cal SS}_i)=\{B\}$ <span>**then**</span><span>\ </span> : $\ell_i \leftarrow B$<span>\ </span> : $des_i \leftarrow p_m$ //go to the midpoint We show two algorithms in external-light. One uses $3$ colors in rigid and SSYNC and the other uses only $2$ colors in the same assumption as the former with the local-awareness. <span>**Algorithm \[algo:ELGW3C\]**</span> shows the external-light algorithm in rigid and SSYNC with $3$ colors and its transition diagram is shown in Figure \[fig:Ext-light\]. ![image](Fig_algo2.eps){width="8cm"} Without loss of generality, the algorithm may begin with a configuration of two-location $p_n$ and $p_f$, where all robots have $A$ or three-location $p_n, p_m$, and $p_f$ such that $(|\overline{p_f p_m}|=|\overline{p_m p_n}|)$, where all robots have $A$. Since we assume the rigid movement, these configurations can be reduced from *onLDS* by moving robots to the nearest position among the endpoints and the midpoint. By using notations of the color-configurations, the former has color-configuration $AA$ and the latter has $AAA$ in Fig. \[fig:Ext-light\]. Once the configuration of two- or three-location is obtained, this configuration is preserved hereafter since we assume the rigid movement. <span>**Algorithm \[algo:ELGW3C\]**</span> makes configuration with $BA$ (or $AB$) from the initial configuration with $AAA$ or $AA$ via configuration with $ABA$. After the configuration with $BA$ [^8], (1) when robots observe color $B$, they change their color to $C$ and stay there, where the location becomes the gathering one, (2) when robots observe color $A$, they change their color to $B$ and go to the midpoint. Then, the color-configuration becomes $B(A+C)$ or $BB(A+C)$, where $A+C$ denotes the endpoint is occupied by robots with color $A$ or $C$. Once the configuration with $B(A+C)$ appears, since robots with $A$ or $C$ observe color $B$ and change their color to $C$, and robots with $B$ observe color $C$ and move to the location having robots with $C$, Gathering is successful. The configuration with $BB(A+C)$ becomes one with $B(A+C)$, because robots with $B$ located at the midpoint stay there, robots with $A$ or $C$ observe two $B$'s at the endpoint and the midpoint change their color to $C$, robots with $B$ located at the endpoint observe color $C$ at the endpoint and color $B$ at the midpoint move to the midpoint. \[AAtoABA\] Configuration with $AA$ moves to one with $ABA$, $AB$ or $BA$. In particular, it moves to the gathering configuration, if all robots become active. All active robots perform <span>**line**</span> 3. If all robots become active, the gathering is attained. Otherwise, if all robots at one endpoint only become active, the configuration moves to $AB$ or $BA$. Otherwise, it moves to $ABA$. \[AAAtoABA\] Configuration with $AAA$ moves to one with $ABA$. This case is derived from <span>**line**</span> 3, <span>**lines**</span> 6-8, and the fact that robots at endpoints cannot move until all robots at the midpoint have color $B$ (<span>**line**</span> 12). \[ABAtoBA\] Configuration with $ABA$ moves to the two-point configuration with $BA$ (or $AB$) unless Gathering is achieved. From a configuration with $BA$, robots at the endpoints change their color to $B$ and go to the midpoint (<span>**lines**</span> 12-14), and robots at the midpoint stay there (<span>**lines**</span> 6-8). Then if all robots at the both endpoints go to the midpoint, Gathering is achieved. Otherwise, the two-point configuration with $BA$ (or $AB$) is obtained. \[BAtoBA+C\] Configuration with $BA$ moves to one with $B(A+C)$ or $BB(A+C)$. Robots with $A$ observing $B$ change their color to $C$ and stay (<span>**line**</span> 4) and robots with $B$ observing $A$ change their color to $B$ and move to the midpoint (<span>**line**</span> 3). Thus, the color-configuration $B(A+C)$ or $BB(A+C)$ is obtained. Configuration with $BB(A+C)$ moves to one with $B(A+C)$. It can be derived by <span>**lines**</span> 5-14. \[BCtoGa\] Configuration with $B(A+C)$ moves to the gathering configuration. It can be derived by <span>**lines**</span> 1-4. We have the following theorem using Lemma \[lemma:ElectLDS\] and Lemmas \[AAtoABA\]-\[BCtoGa\]. Gathering is solvable in external-light of $3$ colors, rigid, and SSYNC, if robots have set-view and agreement of chirality. \[h\] 111 = 11 = 11 = 11 = 11 = 11 = 11 = : external-light, rigid, 2 colors (A,B), local-awareness, set-view, SSYNC. <span>\ </span><span>*Input*</span>: $(|{\cal P}({\cal SS}_i)| =3)$ <span>**and**</span> $(|\overline{p_f p_m}|=|\overline{p_m p_n}|)$ or $|{\cal P}({\cal SS}_i)| =2$, all robots have color $A$. <span>\ </span> : $|{\cal P}({\cal SS}_i)| =2$ <span>**then**</span> <span>\ </span> : $B \in {\cal L}({\cal SS}_i)$ <span>**then**</span> $\ell_i \leftarrow B$; $des_i \leftarrow p (\in {\cal P}_B({\cal SS}_i))$<span>\ </span> : ${\cal L}_{p_i}({\cal SS}_i) = \emptyset$ <span>**then**</span> no action //I am alone at $p_i$<span>\ </span> : $\ell_i \leftarrow B$; $des_i \leftarrow (p_n + p_f)/2$ //${\cal L}_{p_f}({\cal SS}_i) = \{ A \}$<span>\ </span> : $(|{\cal P}({\cal SS}_i)| =3)$ <span>**and**</span> $(|\overline{p_f p_m}|=|\overline{p_m p_n}|)$<span>**then**</span><span>\ </span> : $A \in {\cal L}_{p_m}({\cal SS}_i)$ <span>**and**</span> ($p_i =p_m$) <span>**then**</span> $\ell_i \leftarrow B$<span>\ </span> : $\ell_i \leftarrow B$; $des_i \leftarrow p_m$ Although it is unknown whether there exists a $2$-color gathering algorithm in external-light, rigid, and SSYNC, we can construct $2$-color gathering algorithm in the same condition if we assume the local-awareness (<span>**Algorithm \[algo:ELG2C\]**</span>). In <span>**Algorithm \[algo:ELGW3C\]**</span>, we make the location having robots with $C$ the gathering point. Instead we do not use the third color $C$, we make configurations with $AB$ (or $BA$) such that there are at least 2 robots with $B$ at one endpoint utilizing the local-awareness. Thus, since robots with $A$ move to the point having robots with $B$ and robots with $B$ can stay at the point(<span>**line**</span> 2) using the local-awareness, Gathering is attained. Such configurations are created as follows; When the initial color-configuration is $AAA$, it moves to $ABA$ (<span>**line**</span> 6) and reaches to $BA$ (or $AB$) (<span>**lines**</span> 7). When one endpoint contains more than one robot in the initial configuration with $AA$, it moves to a configuration with $ABA$ (<span>**line**</span> 4) and reaches to one with $BA$ (or $AB$) (<span>**lines**</span> 5-7). If one endpoint contains only one robot in configuration with $AA$, since the robot identifies that it is alone due to the local-awareness, the robot makes no action. Thus, all the initial configurations can reach to the desired one with $BA$ (or $AB$). Assume the local-awareness. Gathering is solvable in external-light of $2$ colors, rigid, and SSYNC, if robots have set-view and agreement of chirality. Internal-light -------------- Views of robots in internal-light are the same as those without lights and so robots must determine their behaviors by these views without colors and their own colors of lights. Thus Gathering algorithms in internal-light can not seem to be constructed without additional knowledge such as distance information. In fact, known Rendezvous algorithms use the minimum distance of moving $\delta$ and/or the unit distance @FSVY. In our Gathering algorithm in internal-light, we use
{'source': 'arXiv_out/1811'}