arXiv CSopen access

Conflicting Pattern Formation by Teams of Anonymous, Fully Disoriented Robots

Conflicting Pattern Formation by Teams of Anonymous, Fully Disoriented Robots Animesh Maiti∗

Prakhar Shukla

Subhash Bhagat

arXiv:2609.23454v1 [cs.DC] 20 Sep 2026

Department of Mathematics, Indian Institute of Technology Jodhpur Jodhpur, Rajasthan, India

Abstract Two groups of autonomous, anonymous, and oblivious mobile robots are deployed in the twodimensional Euclidean plane, each assigned a distinct task. We study a setting where the two groups must simultaneously solve two conflicting pattern formation problems: the gathering problem, where robots gather at a point not known to them a priori, and the circle formation problem, where robots occupy distinct positions on the boundary of a circle. Although each robot knows its own task, it cannot identify other members of its group. A prior solution [6] addressed this problem for asynchronous robots having direction-only axis agreement and global weak multiplicity detection capability available to all robots in both groups. In contrast, in this work, we consider fully disoriented robots without any axis agreement or common chirality. We study the feasibility of a solution to this problem for disoriented robots. We propose a distributed algorithm that solves the problem for semi-synchronous disoriented robots with non-rigid movements. Our proposed algorithm assumes global weak multiplicity detection only for the gathering group, while for the circle formation group, it requires local weak multiplicity detection.

Keywords: Mobile robots ; Conflicting pattern formation ; Gathering ; Circle formation ; Fully disoriented robots ; Multiplicity detection

1

Introduction

A swarm of robots consists of several small autonomous mobile robots that cooperatively perform tasks without any centralized control. The robots are anonymous, i.e., they can not be distinguished by their physical appearances or by identity. Robots are homogeneous, i.e., all the robots have the same set of capabilities, and they run the same distributed algorithm. They are oblivious, i.e., they do not carry forward any information from the previous computational cycles. They do not have explicit communication capabilities. They communicate implicitly by changing their positions. Robots do not have access to any global coordinate system. However, each robot has its own local coordinate system centered at its current position. The direction and the orientation of the local coordinate axes may vary among the robots. At a point in time, a robot is either idle or active. The activation of the robots is controlled by an adversarial scheduler. There are mainly three types of scheduler: fully-synchronous (FSYNC), semisynchronous (SSYNC), or asynchronous (ASYNC). In FSYNC and SSYNC scheduling, time is divided ∗

Corresponding author: [email protected]

1

into discrete rounds. An FSYNC scheduler activates all the robots in each round, whereas an SSYNC scheduler activates only a subset of robots in each round. The ASYNC scheduler is the most general one. Under this scheduler, there is no notion of common rounds. The activations and execution times are unpredictable but finite. Each active robot repeatedly executes an atomic Look-Compute-Move cycle. During the Look phase, a robot observes the positions of other robots with respect to its own local coordinate system. In the Compute phase, it computes a destination point using the locations obtained in the Look phase, and in the Move phase, it moves toward that destination point. We assume a fair scheduler that activates each robot infinitely many times. Robot movements may be rigid or non-rigid. For non-rigid movement, an adversary may stop a robot before it reaches its destination; however, the robot always moves at least δ > 0 distance unless it reaches the destination. Robots may be endowed with some extra capabilities, and they may have some agreements on the directions and orientations of the local coordinate axes. Two or more robots may occupy the same point in the plane, and such a point is called a multiplicity point. If robots have global weak multiplicity detection capability, then they can identify a multiplicity point even if they do not lie on the multiplicity point. On the other hand, if robots have local weak multiplicity detection capability, then they can identify a multiplicity point only when they lie at that multiplicity point. The literature contains a large volume of studies on different geometric pattern formation problems under different computational models [20]. The gathering problem and the circle formation problem are two of the fundamental formation problems studied in the literature. The gathering problem asks a set of autonomous robots to coordinate their movements in such a way that, within a finite time, all of them meet at a point not known to them a priori. Whereas the circle formation problem requires the robots to place themselves at distinct points on the boundary of a circle. These two problems have been studied separately under different computational models, and several results and algorithms have been proposed for these two problems in the literature.

2

Related Work

One of the major research directions in distributed mobile robotics is to determine the minimum set of robot capabilities required to solve geometric pattern formation problems under different computational models. Among these problems, gathering and circle formation are two of the most fundamental and extensively studied tasks in the literature. The gathering problem: The gathering problem has been studied extensively in the literature under different computational models [20]. The problem is solvable for fully synchronous robots without any extra assumption on the capabilities of the robots [20]; however, the problem is not solvable for n ≥ 2 semi-synchronous (and hence for asynchronous) robots without additional capabilities of the robots [23, 24]. The problem is solvable in finite time for n ≥ 5 asynchronous oblivious robots when robots are endowed with global weak multiplicity detection capability [11]. The algorithm proposed in [25] solves the gathering problem for n = 2 robots using lights with two colors. Under the limited visibility model, the problem is solvable for asynchronous robots with a consistent compass [19]. The gathering problem has also been studied for f at robots (robots having physical extents). Czyzowicz et al. solved the gathering problem for n = 4 fat robots [12]. Later, Agathangelou et al. proposed a gathering algorithm for an arbitrary number of robots [1]. Their algorithm assumes common chirality. The gathering problem has also been studied under various fault models [2, 3, 22, 4, 9]. The circle formation problem: This problem is solvable for asynchronous robots in finite time without any additional capabilities of the robots [20]. The circle formation problem was also studied with the additional objective of minimizing the maximum distance traversed by any robot [7]. Several variants 2

of circle formation have subsequently been investigated. In particular, the k-circle formation problem has been studied for asynchronous robots under one-axis agreement and, later, for fully disoriented robots [5, 13]. One important variation is the uniform circle formation problem, which requires the robots to occupy distinct equally spaced positions on a common circle. Uniform circle formation is solvable for asynchronous robots without additional assumptions [18, 21]. More recent works have considered uniform circle formation for opaque luminous robots under different schedulers [15], improved the asynchronous time complexity to O(log n) while using a constant number of colors [16], and obtained an asymptotically optimal constant-time, constant-color solution for asynchronous luminous robots [17]. Recently, uniform k-circle formation has also been investigated for asynchronous fat robots [14]. The conflicting patterns formation problem: The majority of the existing works assume that all robots cooperate to achieve a single common objective. Bhagat et al. [6] initiated the study of conflicting task formation, where two groups of robots simultaneously solve two distinct pattern formation problems. They considered the gathering and circle formation as the conflicting patterns and proposed an algorithm to solve the problem for asynchronous robots. Their algorithm assumes direction-only axis agreement, global weak multiplicity detection capability for both the groups and more than 5 robots in the gathering group. In this paper, we extend this line of work for disoriented robots, i.e., for robots without any form of axis agreement. Our objective is to investigate the feasibility of a solution for this problem for disoriented robots.

3

Model and Terminologies

3.1

Model

Let R = {r1 , r2 , . . . , rn } denote the set of n robots represented by points in the Euclidean plane. Robots are anonymous and oblivious, and they do not have any form of direct communication capabilities. Robots do not have any form of axis agreement, and they have non-rigid movements. Robots work under the semi-synchronous scheduler (the SSYNC model). Let Rg ⊂ R denote the set of robots required to solve the gathering problem, and Rf ⊂ R be the team of robots required to solve the circle formation problem. We assume R = Rg ∪ Rf and |Rg | ≥ 6, |Rf | ≥ 2. Let Nf and Ng denote the cardinalities of Rf and, Rg respectively. We assume the following: (i) robots in Rg have global weak multiplicity detection capability, and (ii) robots in Rf have local weak multiplicity capability, and they know the value of |Rf |, i.e., Nf . A robot ri ∈ R knows its task to perform, i.e., it knows the team to which it belongs. However, it can not identify its other team members. Initially, all robots are stationary and lie on distinct points on the plane.

3.2

Terminologies

e = {r1 (t), . . . , rn (t)} be the multiset of Let ri (t) denote the position of robot ri ∈ R at time t. Let R(t) e robot positions occupied by the robots in R at time t. Let R(t) = {p ∈ R2 | p occurs in R(t)} denote the set of distinct occupied positions of the robots in R at time t. Similarly, let Rg (t) and Rf (t) denote the sets of distinct positions occupied by the robots in Rg and Rf , respectively, at time t. A point p ∈ R(t) occupied by at least two robots is called a multiplicity point. A multiplicity point occupied by at least two robots from Rg is called a stable multiplicity point. Let S(t) denote the smallest enclosing circle (SEC) of the robot positions at time t, and let O(t) denote 3

its centre. We use ∂S(t) to denote the circumference of S(t). Let Sout (t) and Sin (t) denote the robot positions in R(t) lying on the circumference of S(t) and inside S(t), respectively. S(0) is the smallest enclosing circle for the initial robot configuration R(0). Let D(t) = {∥p − O(t)∥ : p ∈ R(t), p ̸= O(t)} . Let 0 < ρ1 (t) < ρ2 (t) < · · · < ρm (t) be the distinct values in D(t). For each k ∈ {1, . . . , m}, let Ck (t) denote the circle centered at O(t) with radius ρk (t). Thus, the circles are indexed from the innermost to the outermost radial level, and Cm (t) = S(t). (see Figure 1). Let a and b be two points in the plane. By (a, b) and ab, we denote the open (excluding a and b) and closed (including a and b) line segments joining a and b, respectively.

Figure 1: Illustrations of the circles Ck (t) for k ≥ 1: blue robots represent the set Rf and red robots represent the set Rg . We use the concept of quasi-regularity originally studied in [8, 3]. Before defining quasi-regularity, we introduce a few related definitions. Definition 1 (Successor). Let R be a set of robot positions in R2 and let c ∈ R2 be a point. For any robot position ri ∈ R, the successor of ri with respect to c, denoted by S(ri , c), is the next robot position in R encountered when moving in clockwise order around c. Robot positions lying on the same ray from c are ordered consecutively according to their increasing distance from c. The k-th successor is defined recursively as S k (ri , c) = S(S k−1 (ri , c), c), with S 0 (ri , c) = ri . (see Figure 2(b)) Definition 2 (String of Angles). Let R be a set of robot positions and let c ∈ R2 . Let r1 , r2 , . . . , rn be the robot positions of R ordered clockwise around c according to the successor relation. The string of angles of R with respect to c, denoted by SA(R, c), is defined as SA(R, c) = (α1 , α2 , . . . , αn ), where αi = ∠(ri , c, ri+1 ) for i = 1, . . . , n, and rn+1 = r1 . Note that if multiple robots lie on the same ray from c, then they appear consecutively in the ordering and contribute zero angular gaps in the string of angles. Thus, SA(R, c) captures both the angular ordering and the multiplicities of robots. (see Figure 2(b) ) Definition 3 (Regular Configuration). A configuration R is said to be regular with respect to a point c if the string of angles SA(R, c) can be written as SA(R, c) = X k , for some non-empty sequence X and integer k > 1. The regularity of R, denoted by reg(R), is defined as the maximum such integer k. The point c is called the centre of regularity. The point c is called the centre of regularity. (see Figure 2(b)) Definition 4 (Quasi-Regularity). Let R(t) be a configuration of robots at time t. The configuration R(t) is said to be quasi-regular (Q-regular) if there exists a subset B(t) ⊆ R(t) and a point c ∈ R2 such that the 4

(a)

(b)

Figure 2: (a) Illustration of the successor relation and the string of angles around the centre c. In the clockwise ordering, S(ri , c) = rj , S(rj , c) = rk , S(rk , c) = rl , and so on. The string of angles is SA(R, c) = (α, 0, β, α, 0, β, α, 0, β, α, 0, β), which can be written as SA(R, c) = X 4 , where X = (α, 0, β). Therefore, the configuration is regular with reg(R) = 4. (b) Illustration of a quasi-regular configuration R(t) with centre of quasi-regularity cq , where B(t) = R(t)\{rcq (t)}. The half-line qradi (t) denotes the ray starting from cq and passing through ri (t). subset B(t) forms a regular configuration with respect to c, i.e., the string of angles SA(B(t), c) is periodic with period greater than 1, and all robots in R(t) \ B(t) lie at the point c. The point c is called the centre of quasi-regularity, denoted by cq . The quasi-regularity of R(t) is defined as qreg(R(t)) = reg(B(t)), and qreg(R(t)) = 1 if no such subset exists. For each robot ri (t) ∈ R(t) with ri (t) ̸= cq , the half-line qradi (t) is defined as the ray starting from cq and passing through ri (t). (see Figure 2(b)) Let R(t) be a quasi-regular configuration with center cq . For each robot ri (t), let qradi (t) be the segment joining cq to ri (t). The configuration is said to be free-path quasi-regular if no other robot lies on qradi (t) between cq and ri (t) for any ri (t) ∈ R(t) (see Figure 3(a)). The configuration is said to be totally symmetric if O(t) = cq (see Figure 3(a)); otherwise, O(t) ̸= cq (see Figure 3(c)). Definition 5 (Radial ray). For a robot position ri (t) ∈ R(t) with ri (t) ̸= O(t), the half-line radi (t) is defined as the ray starting from O(t) and passing through ri (t). (Compare qradi (t) in Definition 4, which is defined analogously with respect to the centre of quasi-regularity cq rather than O(t).) To describe our algorithm, we will consider the following classes of configurations: Multiple: This class contains all the robot configurations having exactly one multiplicity point. Dense: This class contains all robot configurations having no multiplicity points, with |Sout (t)| ≤ 4. N on − Dense: A robot configuration belongs to this class if it does not contain any multiplicity points, with |Sout (t)| > 4. F inal: A robot configuration R(t) belongs to this class if it satisfies both of the following conditions: (i) ∃ p∗ ∈ R2 such that ri (t′ ) = p∗ ,

∀ ri ∈ Rg , ∀ t′ ≥ t, i.e., all the robots in Rg achieve gathering.

(ii) ∃ a circle S ⊂ R2 such that rj (t′ ) ∈ ∂S, circle formation.

∀ rj ∈ Rf , ∀ t′ ≥ t, i.e., all the robots in Rf achieve 5

(a)

(b)

(c)

Figure 3: Illustration of different types of quasi-regular configurations: (a) a free-path quasi-regular robot configuration which is also totally symmetric, (b) a quasi-regular configuration which is not freepath quasi-regular, (c) a quasi-regular configuration with O(t) ̸= cq .

4

Algorithm PatternFormation()

The algorithm proposed in [6] has three phases: the reduction phase, the multiplicity phase and the formation phase. The reduction phase ensures that at least two gathering robots are inside the SEC, S(0). This phase depends on the assumption of axis-only agreements, and this helps to keep S(0) intact. Keeping S(0) intact ensures finite-time termination of the reduction phase with at least two robots inside S(0) from the gathering group Rg . Furthermore, this also helps to decide and keep the final gathering point (the centre of S(0)) invariant during the execution of the whole algorithm. The global weak multiplicity detection for the robots forming a circle helps to design synchronized movements of the robots during the formation phase, which is essential to avoid collisions and the creation of multiple multiplicity points (robots use multiplicity detection capability to identify the gathering point).

4.1

Challenges

To solve the gathering problem, the robots must first establish a unique and persistent gathering point. Our approach achieves this by creating a unique stable multiplicity point, which is subsequently identified by robots in Rg using global weak multiplicity detection. Since the robots are anonymous and cannot distinguish members of their own team, creating such a multiplicity point is non-trivial: it must not be formed solely by robots in Rf , and if an Rf robot participates in its creation, it must remain there until the multiplicity becomes stable. To this end, robots in Rf are equipped with local weak multiplicity detection. During the multiplicity-creation phase, the initial smallest enclosing circle is preserved by fixing a small set of pivotal boundary robots. The assumption |Rg | ≥ 6 guarantees that at least two gathering robots remain in the interior of the SEC to create the stable multiplicity point. Consequently, unlike the algorithm of [6], new movement strategies are required. The main challenges are: 1. creating a unique stable multiplicity point while handling symmetric configurations without any axis agreement; 2. ensuring that no additional stable multiplicity point is created throughout the execution; and 3. coordinating the gathering and circle-formation phases so that both terminate within a finite time. 6

4.2

Overview of the Algorithm

Algorithm PatternFormation() consists of three phases: multiplicity creation, gathering, and circle formation. These phases are not globally synchronized. In particular, gathering and circle formation may overlap after a multiplicity point has been created. If the initial configuration is N on − Dense, the algorithm first moves selected non-pivotal boundary robots into the interior of the current smallest enclosing circle S(t). By Lemma 1, the pivotal robots preserve S(t). This reduction either creates a stable multiplicity point directly or produces a Dense configuration. In a Dense configuration, at most four robot positions lie on ∂S(t). Since |Rg | ≥ 6, at least two gathering robots lie inside S(t). These robots move toward a common geometrically defined point, namely the quasi-regular centre cq when the configuration is free-path quasi-regular, and O(t) otherwise. Hence, a unique stable multiplicity point pm is eventually created. Once pm exists, every gathering robot moves toward pm . At the same time, circle-forming robots may start moving outward when |R(t)| ≤ Nf +1. The movement rules ensure that gathering remains directed toward pm and that circle-forming robots occupy distinct positions on the current SEC. The high-level execution flow of Algorithm PatternFormation() is illustrated in Figure 4. direct creation

N on − Dense

reduction

creation

Dense

Stable multiplicity

Gathering (Rg )

Circle formation (Rf ) Final

Figure 4: High-level execution of Algorithm PatternFormation(). The algorithm applies the following priority order: 1. if a multiplicity point exists, execute the gathering or formation rule according to the number of distinct robot positions in the system. 2. otherwise, reduce a N on − Dense configuration into Dense configuration while preserving the SEC; 3. in a Dense configuration, create a stable multiplicity point.

4.3

Routine Pivotal-Robot-Position-Selection()

When the current configuration is not totally symmetric, our algorithm computes a subset P ′ (t) ⊆ Sout (t), called the pivotal set. A subset P ′ (t) ⊆ Sout (t) is called a pivotal set if SEC(P ′ (t)) = S(t). Robots occupying pivotal positions remain stationary during the multiplicity-creation phase, while the remaining boundary robots may move. The pivotal set is computed according to the geometric symmetry of the current configuration. • Asymmetric configurations: Let p0 be the first robot position in Sout (t) under the canonical ordering of the configuration (since R(t) is asymmetric, we can obtain an ordering of the robot positions 7

in R(t) ([10]). Let L be the line through p0 and O(t). If the antipodal point of p0 is occupied by a robot position in Sout (t), then P ′ (t) consists of these two antipodal positions. Otherwise, P ′ (t) contains p0 together with the two robot positions in Sout (t) adjacent to its antipodal point. • Configurations with one symmetry axis: Let L be the unique symmetry axis, and let a, b ∈ ∂S(t) be its intersections with ∂S(t). The pivotal set consists of every occupied intersection and, for each unoccupied intersection x ∈ {a, b}, the first occupied boundary positions encountered from x along the two circular directions of ∂S(t), after removing duplicates.(see Figure 5) • Quasi-regular configurations with cq ̸= O(t). Let D denote the set of robot positions in Sout (t) having maximum distance from cq . Note that 1 ≤ D ≤ 2, as cq ̸= O(t). The canonical line is defined as the line through O(t) and the unique point determined by D: if D consists of a single position, that position is used; otherwise, the midpoint of the positions in D is used. The pivotal set is then computed exactly as in the single-symmetry-axis case. Property 1. Let A be a set of points in the Euclidean plane with |A| ≥ 3, and let B ⊆ A with 2 ≤ |B| ≤ 4. Consider the non-overlapping division of the circumference of the smallest enclosing circle of A into arcs by the points of B lying on that circumference (or, if |B| = 2 and the two points are diametrically opposite, the trivial division by the diameter). If no arc exceeds a semicircle, then the smallest enclosing circles of A and B coincide, i.e., B alone suffices to determine the smallest enclosing circle of A.

(a)

(b)

(c)

Figure 5: Illustrations of different scenarios of pivotal selection: (a) both p1 and p2 contain robot positions, (b) exactly one of p1 and p2 contains a robot position, and (c) none of p1 and p2 contains a robot position. Lemma 1. For every configuration in which
the pivotal set is defined, the smallest enclosing circle of P ′ (t) coincides with S(t); that is, SEC P ′ (t) = S(t). Proof. By construction, P ′ (t) contains either (i) two antipodal boundary positions of S(t), or (ii) at least three occupied boundary positions that are not contained in any open semicircle of S(t). The property 1 of the smallest enclosing circle implies that either condition uniquely determines S(t). Therefore, SEC(P ′ (t)) = S(t). Let S(t) be the smallest enclosing circle (SEC) of the configuration R(t) with center O(t), and let P ′ (t) ⊆ Sout (t) be the set of pivotal robot positions. We prove that P ′ (t) uniquely determines S(t) using Property 1.

8

Step 1: Characterization of SEC. It is well known that the SEC of a point set is uniquely determined by either: (i) two diametrically opposite boundary points, or (ii) at least three boundary points not contained in any open semicircle. Step 2: Diametrically opposite case. If P ′ (t) contains two diametrically opposite points, then these two points uniquely define S(t). Note that this may occur even when |P ′ (t)| ≥ 3. Step 3: Non-diametrical case. Assume that no two points in P ′ (t) are diametrically opposite. Then |P ′ (t)| ≥ 3. Order the points of P ′ (t) along S(t) in clockwise order: ri1 (t), ri2 (t), . . . , rik (t), k = |P ′ (t)| and k = 3, 4. These points partition the circumference into k arcs. Let αj denote the arc between rij (t) and rij+1 (t) (indices modulo k). Step 4: Arc bound. We claim that αj ≤ πR for all j, i.e., no arc exceeds a semicircle. Suppose, for contradiction, that there exists an arc αm > πR. Then all points of P ′ (t) lie within the complementary semicircle, say Sc (t). We first show that if all points of P ′ (t) lie within the semicircle, Sc (t), then all points of R(t) must also lie within the semicircle, Sc (t). Now, by construction, the points in P ′ (t) are obtained using a well-defined line L(t) passing through O(t). The line L(t) divides the circle S(t) into two semicircles, say, S1 (t) and S2 (t). If |P ′ (t)| = 3, there is a unique robot position, say ri (t) on the boundary of S(t) that lies on L(t) and the other two robot positions in P ′ (t), say rj (t) and rk (t), are farthest robot positions from ri (t) lying on S(t). When |P ′ (t)| = 4, then there are two pairs of points in P ′ (t) such that one pair lies on S1 and the other pair lies on S2 . Now consider any one of these pairs, say the pair lying on S1 (t). Then points in this pair lie on the same side of L(t), and they are the farthest robot positions on S1 (t). Thus P ′ (t) captures extremal or symmetry-critical positions of R(t). Hence, if P ′ (t) lies within a semicircle, then all points of R(t) must also lie within that semicircle. This contradicts a fundamental property of the SEC: no open semicircle of S(t) can contain all points of R(t), otherwise a smaller enclosing circle would exist. Step 5: Conclusion. Thus, no arc between consecutive points of P ′ (t) exceeds a semicircle. Therefore, P ′ (t) is not contained in any open semicircle. By Property 1, P ′ (t) uniquely determines S(t). Algorithm 1 : MoveToDestination(ri , τ, d) Require: Robot ri , movement type τ ∈ {StepIn, StepAside, StepOut}, and reference point d whenever required 1: if τ = StepIn then 2: StepIn(ri , d) 3: else if τ = StepAside then 4: StepAside(ri , d) 5: else if τ = StepOut then 6: StepOut(ri ) 7: else 8: remain stationary 9: end if

9

4.4

Routine MoveToDestination()

The movements of robots are guided by the routine MoveToDestination(). This routine provides collision-free movements for the robots during the multiplicity creation phase. This is required to create a unique stable multiplicity point. As discussed above, robots have different types of movements depending on the different phases of the robots. For a robot ri ∈ R, let Hi (t) denotes the set of lines joining two robot positions in R(t)\{ri (t)}. Algorithm 1 summarizes the routine MoveToDestination(), which invokes the appropriate movement procedure according to the movement type assigned to robot ri . We describe each of these movements in detail as follows: (A) Step-in movement: This movement places a robot, lying on S(t), inside the circle. Suppose robot ri wants a step-in movement w.r.t. the point p. Note that p = O(t) if R(t) is not quasi-regular, otherwise p = cq . Let us first consider the case when the line segment ri (t)p intersects at least one line from Hi (t) (we exclude lines which coincide with ri (t)p from Hi (t) while computing the intersection points). Let xi be the nearest of such intersection points to ri (t) (see Figure 6(a)). The destination point di of ri is the middle point of the segment ri (t)xi . If none of the lines in Hi (t) intersects ri (t)p, then the di is the middle point ri (t)p (in this case also, we exclude lines which coincide with ri (t)p from Hi (t) while computing the intersection points)(see Figure 6(b)). Robot ri moves towards di along the line segment ri (t)di . Algorithm 2 summarizes the StepIn procedure.

(a)

(b)

Figure 6: Step-in movement for computing di : (a) The line segment ri (t)p intersects the dotted line in Hi (t), (b) None of the line in Hi (t) intersect ri (t)p. (B) Step-aside movement: We describe the step-aside movement of a robot ri w.r.t. a point d. Note that robot ri have a step-aside movement in the following two cases: (i) the open line segment (ri (t), di ) contains at least one robot position, where di is the destination point of ri and (ii) when R(t) is not free-path quasi-regular and cq = O(t). Thus, we have d ∈ {pm , O(t)}. Since robots in R can not detect the overlapping of the gathering phase and the formation phase, we have to be careful about designing step-aside movements of the robots. Until the formation phase starts, if two robots from two groups have step-aside movements in the same round, then these movements are w.r.t. to the same point (we assure this by properly designing the movements of the robots during the multiplicity creation phase and formation phase). However, when there is an overlap of the gathering phase and the formation phase, then two robots from two groups have two types of movements: step-aside movements and step-out movements w.r.t. different points. Since robots can not distinguish this overlap, we carefully design these movements. 10

Algorithm 2 : StepIn(ri , p) Require: Robot ri and reference point p ∈ {O(t), cq } 1: Compute Hi (t), the set of lines determined by pairs of positions in R(t) \ {ri (t)} 2: Remove n from Hi (t) every line coincident with o ri (t)p 3: Xi ← x ∈ ri (t)p : x ∈ h for some h ∈ Hi (t) 4: if Xi ̸= ∅ then 5: Let xi ∈ Xi be nearest to ri (t) 6: di ← midpoint of ri (t)xi 7: else 8: di ← midpoint of ri (t)p 9: end if 10: move toward di along ri (t)di

(a)

(b)

Figure 7: Step-aside movement for computing xi when pm = O(t): (a) Dotted lines in Hi (t) intersect the arc Cij (t) of circle Cl (t) (with l = 3), (b) None of the lines in Hi (t) intersect Cij (t). First, consider the case when pm = O(t). This implies that d = O(t) for all robots in R. The robots in Rg need to check pm = O(t). According to our algorithm, if a robot in Rf has a step-aside movement, then its movement is w.r.t. O(t). Thus, the robots in Rf have step-aside movements as described in this case (the robots in Rg have different movement strategies when pm ̸= O(t) to guarantee finite time reachability of the robots in Rg to pm ). Let robot ri lie on the circle Cl (t). The destination point xi of ri lies on Cl and it is computed as follows (see Figure 7): let Bi (t) be the set of robot positions in R(t) which do not lie on ri (t)O(t). Let rj (t)O(t) and rk (t)O(t) be the clockwise and counterclockwise neighbors of ri (t)O(t). Consider the angle θi (t) = max{∠ri (t)drj (t), ∠ri (t)drk (t)} (tie, if any, broken arbitrarily). Without loss of generality suppose, θi (t) = ∠ri (t)drj (t). Let c be the intersection point between Cl (t) and radj (t). Let Wi (t) be the wedge defined by the angle θi (t) and Cij (t) be the arc of Cl (t) which lies in the wedge Wi (t). If at least one line in Hi (t) intersects Cl (t), then let qi be the nearest to ri (t) among all such intersection points. In this case, xi is the intersection point between Cij (t) and the bisector of the segment ri (t)qi (see Figure 7(a)). If none of the lines in Hi (t) intersects Cij (t) (see Figure 7(b)), then we define xi to be a point lying on Cij (t) such that ∠ri (t)dxi = 3n1 i θi (t), where ni is the number of distinct robot positions on the line segment ri (t)d. Note that since we are computing the step-aside movements w.r.t. O(t), we have θi (t) > 0. Now consider the case when pm ̸= O(t) (see Figure 8). According to the strategy described here, only the robots in 11

(a)

(b)

Figure 8: Step-aside movement for computing xi when pm ̸= O(t): (a) Dotted lines in Hi (t) intersect the circle Ck∗ , (b) None of the lines in Hi (t) intersect Ck∗ . Rg have step-aside movements. Let Li be the line passing through ri (t) and pm . Line Li divides the whole plane into two open halves. We define a half plane Vo delimited by Li as follows: Vo be the half plane delimited by Li which contains O(t) if Li does not pass through O(t), otherwise Vo is chosen as any one of the two half planes delimited by Li . Let D∗ (t) = {∥p − pm ∥ : p ∈ R(t), p ̸= pm } , and let 0 < ρ∗1 (t) < ρ∗2 (t) < · · · < ρ∗q (t) be the distinct values in D∗ (t). For each k ∈ {1, . . . , q}, let Ck∗ (t) denote the circle centered at pm with radius ρ∗k (t). The destination point xi of ri lies on Ck∗ and it is computed as follows: we define a point zi on Ck∗ as follows: if at least one line in Hi (t) (excluding the lines coincide with Li ) intersects Ck∗ . This intersection point lies in Vo , then zi is the nearest of such intersection points to ri (t) (see Figure 8(a)). Otherwise zi is a point on Ck∗ ∩ Vo such that ∠zi pm ri (t) = 15◦ (other suitable point may also work)(see Figure 8(b)). Then xi is the intersection point between the Ck∗ and the bisector of the angle ∠ri (t)pm zi . Algorithm 3 summarizes the StepAside procedure.

(a)

(b)

(c)

Figure 9: Step-out movement for computing ui (t) and xi : (a) The line segment ri (t)ui (t) contains no other robot when ri (t) ̸= O(t), (b) the segment ri (t)ui (t) contains multiple robots with ri (t) ̸= O(t), and (c) the case when ri (t) = O(t). (C) Step-out movement: This movement is taken by robots in Rf during the formation phase. Consider a robot ri ∈ Rf having position in Sin (t). Step-out movements place robot ri at a point on the circle S(t). First consider the case when ri (t) ̸= O(t) (see Figure 9(A-B)). Let radi (t) intersect S(t) at ui (t) 12

Algorithm 3 : StepAside(ri , d) Require: Robot ri and reference point d ∈ {O(t), pm } 1: if pm = O(t) then 2: d ← O(t) 3: Let Cl (t) be the radial circle containing ri (t) 4: Determine the clockwise and counterclockwise neighboring radial lines of radi (t), containing positions rj (t) and rk (t), respectively 5: θi (t) ← max{∠ri (t)drj (t), ∠ri (t)drk (t)} 6: Let rj (t) denote a neighbor attaining the maximum 7: Let Wi (t) be the corresponding wedge 8: Let Cij (t) be the arc of Cl (t) contained in Wi (t) 9: Compute all intersections of the lines in Hi (t) with Cij (t) 10: if at least one such intersection exists then 11: Let qi be the intersection nearest to ri (t) 12: Let xi be the intersection of Cij (t) with the perpendicular bisector of ri (t)qi 13: else 14: Let ni be the number of distinct occupied positions on ri (t)d i (t) 15: Choose xi ∈ Cij (t) such that ∠ri (t)dxi = θ3n i 16: end if 17: else ▷ pm ̸= O(t) 18: d ← pm 19: Let Li be the line through ri (t) and pm 20: if O(t) ∈ / Li then 21: Let Vo be the open half-plane bounded by Li that contains O(t) 22: else 23: Choose one admissible open half-plane Vo bounded by Li 24: end if 25: Let Ck∗ (t) be the radial circle centered at pm containing ri (t) 26: Zi ← {z ∈ Ck∗ (t) ∩ Vo : z ∈ h, h ∈ Hi (t), h ̸= Li } 27: if Zi ̸= ∅ then 28: Let zi ∈ Zi be nearest to ri (t) 29: else 30: Choose zi ∈ Ck∗ (t) ∩ Vo such that ∠zi pm ri (t) = 15◦ 31: end if 32: Let xi be the intersection of Ck∗ (t) with the internal angle bisector of ∠ri (t)pm zi 33: end if 34: move toward xi

13

and ri (t) lies on Ck (t) for some k. If the line segment ri (t)ui (t) does not contain any other robot position, then robot ri moves towards ui (t) along the line segment ri (t)ui (t) (see Figure 9(a)). Otherwise, robot ri computes its destination point xi (t) on Ck+1 (t) as follows (see Figure 9(b)). Let Ai (t) be the set of robot positions not lying on radi (t). Let rj (t), rk (t) ∈ Ai (t) be such that radj (t) and radk (t) are the two clockwise and counterclockwise neighbors of radi (t). Let βi (t) = max{∠ri (t)O(t)rj (t), ∠ri (t)O(t)rk (t)} (tie, if any, broken arbitrarily). Without loss of generality, suppose βi (t) = ∠ri (t)O(t)rj (t). Since S(t) contains at least two robot positions on its boundary, βi (t) ̸= 0. Let Vi be the wedge defined by the 1 βi (t), mi angle βi (t). We define xi to be a point lying on Vi (t) ∩ Ck+1 (t) such that ∠ri (t)O(t)xi (t) = 3m i is the number of distinct robot positions on the line segment ri (t)ui (t). Now, consider the case when ri (t) = O(t) (see Figure 9(c)). Let rj (t) and rl (t) be two robot positions not lying at O(t) such that radj (t) and radl (t) are neighbors and ∠rj (t)O(t)rl (t) is maximum for all such consecutive radial lines (tie, if any, broken arbitrarily). Let L0 be the bisector of ∠rj (t)O(t)rl (t). Then xi (t) is the intersection point between S(t) at L0 . Algorithm 4 summarizes the StepOut procedure, which determines an outward destination for a robot in Rf during the formation phase. Table 1 summarizes the movement rules followed by the robots in Rg and Rf for the different configuration classes during the multiplicity-creation phase. Algorithm 4 : StepOut(ri ) Require: Robot ri ∈ Rf 1: if ri (t) ̸= O(t) then 2: Let ui (t) = radi (t) ∩ S(t) 3: if (ri (t), ui (t)) contains no occupied position then 4: move toward ui (t) along ri (t)ui (t) 5: return 6: end if 7: Let Ck (t) be the radial circle containing ri (t) 8: Determine the clockwise and counterclockwise neighboring radial lines of radi (t), containing positions rj (t) and rℓ (t), respectively 9: βi (t) ← max{∠ri (t)O(t)rj (t), ∠ri (t)O(t)rℓ (t)} 10: Let Vi (t) be the wedge corresponding to a neighbor attaining βi (t) 11: Let mi be the number of distinct occupied positions on ri (t)ui (t) i (t) 12: Choose xi (t) ∈ Vi (t) ∩ Ck+1 (t) such that ∠ri (t)O(t)xi (t) = β3m i 13: move toward xi (t) 14: else ▷ ri (t) = O(t) 15: Find two consecutive radial lines radj (t) and radℓ (t) whose enclosed angle is maximum 16: Let L+ 0 be the ray from O(t) bisecting this maximum angular sector 17: xi (t) ← L+ 0 ∩ S(t) 18: move toward xi (t) 19: end if

4.5

Description of Algorithm PatternFormation()

In this section, we describe our proposed algorithm. The execution steps for the robots are described separately for each of the three phases. Algorithm 5 summarizes the overall control flow of PatternFormation(), directing each robot to the appropriate phase according to the current configuration. (A) The multiplicity creation phase: During this phase, our algorithm exploits the number of robot positions in Sin (t) and the symmetry of R(t). Algorithm 6 summarizes the MultiplicityCre14

Table 1: Summary of movement rules during the multiplicity-creation phase. Configuration class

Sub-case

Rg robots

Rf robots

Dense

free-path Q-regular Q-regular, not free-path not quasi-regulara free-path Q-regular Q-regular, cq ̸= O(t) Q-regular, cq = O(t) not quasi-regular

direct → cq

stationary

direct/step-aside → O(t)

stationary

direct/step-aside → O(t)

stationary

direct → cq

stationary

stationary (non-pivotal step-in)

stationary (non-pivotal step-in)

step-aside w.r.t. O(t) if blocked

step-aside w.r.t. O(t) if blocked

step-in w.r.t. O(t) (non-pivotal)

step-in w.r.t. O(t) (non-pivotal)

Dense Dense N on − Dense N on − Dense N on − Dense N on − Dense a

Does not occur for linear configurations when n ≥ 8; see Observation 1.

ation procedure, which determines the movement of a robot according to the configuration class and its quasi-regularity properties. We have the following observation. Observation 1 (Linear configurations are quasi-regular but not free-path quasi-regular). Let R(t) ∈ Dense be a linear configuration, i.e., all robot positions lie on a common line L(t), and let n = |R(t)| ≥ 8. Then R(t) is quasi-regular with a unique centre of quasi-regularity cq , and R(t) is not free-path quasi-regular. Algorithm 5 : PatternFormation(ri ) 1: if ri ∈ Rg and a multiplicity point pm exists then 2: Gathering(ri , pm ) 3: return 4: end if 5: if ri ∈ Rf and |R(t)| ≤ Nf + 1 then 6: Formation(ri ) 7: return 8: end if 9: if ri ∈ Rf and ri (t) is a multiplicity point then 10: remain stationary 11: return 12: end if 13: MultiplicityCreation(ri )

Proof. Since the robot positions in R(t) are collinear, they admit a total order along L(t), computable by every robot without any axis agreement (it only requires comparing distances along the single line on which all positions lie). Existence. Let c ∈ L(t) be the unique balanced split point of R(t) along L(t): if n is even, c is the midpoint of the two median consecutive positions r(n/2) , r(n/2+1) ; if n is odd, c is the median 15

Algorithm 6 : MultiplicityCreation(ri ) 1: By default, ri remains stationary. 2: if R(t) ∈Dense then 3: if R(t) is free-path quasi-regular then 4: if ri ∈ Rg and ri (t) ∈ Sin (t) then 5: move directly toward cq 6: end if 7: else if ri ∈ Rg and ri (t) ∈ Sin (t) then 8: if (ri (t), O(t)) contains no robot position then 9: move directly toward O(t) 10: else 11: StepAside(ri , O(t)) 12: end if 13: end if 14: else if R(t) ∈N on − Dense then 15: if R(t) is free-path quasi-regular then 16: if ri ∈ Rg then 17: move directly toward cq 18: end if 19: else if R(t) is quasi-regular then 20: if cq ̸= O(t) then 21: Compute the pivotal set P ′ (t) 22: if ri (t) ∈ Sout (t) and ri (t) ∈ / P ′ (t) then 23: StepIn(ri , cq ) 24: end if 25: else 26: Let xi = radi (t) ∩ S(t) 27: if ri (t) ∈ Sin (t) and (xi is occupied or (ri (t), O(t)) contains a robot position) then 28: StepAside(ri , O(t)) 29: end if 30: end if 31: else 32: Compute the pivotal set P ′ (t) 33: if ri (t) ∈ Sout (t) and ri (t) ∈ / P ′ (t) then 34: StepIn(ri , O(t)) 35: end if 36: end if 37: end if

16

robot position r(⌈n/2⌉) itself. In either case, taking B(t) = R(t) (even case) or B(t) = R(t) \ {c} (odd case), exactly ⌊n/2⌋ positions of B(t) lie on each side of c along L(t), all robots on a given side sharing one ray from c. Hence
SA(B(t), c) = X 2 , X = 0, . . . , 0, π , | {z } ⌊n/2⌋−1

so R(t) is quasi-regular with centre cq = c. Uniqueness of cq . Any other point c′ ∈ L(t), c′ ̸= cq , changes the count of robot positions on at least one side of the split (since all positions are distinct and cq is the unique balanced split point), so c′ cannot yield SA(·, c′ ) = X 2 . Hence cq is unique, and every robot can identify it consistently despite full disorientation. Failure of the free-path property. Since cq ∈ L(t), every qradi (t) is a sub-ray of L(t) itself, so all positions in R(t) \ {cq } lie on exactly two rays from cq , each containing ⌈(n − 1)/2⌉ ≥ ⌈7/2⌉ = 4 robot positions (using n ≥ 8). Hence for the farthest position ri (t) on a ray, every other position on that ray lies on qradi (t) strictly between cq and ri (t). By Definition 4, R(t) is not free-path quasi-regular. Remark 1. Observation 1 shows that for Dense configurations with n ≥ 8, a linear configuration always falls under sub-case (1.b) (quasi-regular but not free-path quasi-regular), whose movement rule is defined with respect to O(t) rather than cq , and hence applies verbatim without modification. Consequently the qualifier “non-linear” in the statements of sub-cases (1.a) and (1.b) in Section 4.5 is unnecessary and is removed (see Part B, item B.1). Case 1 R(t) ∈ Dense: Since |Rg | ≥ 6 and |Sout (t)| ≤ 4, there are at least two robot positions from Rg (t) which lies in Sin (t). Two robots are sufficient to create a multiplicity point and thus, the robots having positions in Sin (t) can create a multiplicity point within a finite time. We need to coordinate their movement so that no more than one multiplicity point is created during this process, and the process creates the multiplicity point in finite time. In order to achieve so, we consider two cases separately as follows: (1.a) R(t) is free-path quasi-regular: Since robots in Rf do not have global multiplicity detection capability, they can recognize R(t) quasi-regular configurations until at least two robots reach cq , the centre of the quasi-regularity. Once two robots reach cq , a multiplicity point is created at cq . Since robots have free paths towards cq , they reach this point by direct movements, and no other multiplicity point is created during these movements. The robots act in this case as follows: if ri (t) ∈ Sin (t) ∩ Rg (t), the centre cq is the destination point for ri and robot ri has a direct movement towards cq . In the rest of the cases, robots do not move. Since robots in Rf do not move, if the centre cq contains a robot from Rf , then the multiplicity point contains a robot from Rf . To make this multiplicity point stable, our approach does not move this robot from Rf until at least two robots from Rg reach cq (this case is handled during the formation phase using the local weak multiplicity detection capability of robots in Rf ). (1.b) R(t) is quasi-regular but not free-path quasi-regular or R(t) is not quasi-regular: We maintain S(t), until a multiplicity point is created. Our approach does not move the robots lying on S(t). Otherwise, if ri (t) ∈ Sin (t) ∩ Rg (t), then O(t) is the destination point of ri . In the rest of the cases, robots do not move. A robot has either a direct movement or step-aside movement w.r.t. O(t) depending on its position.

17

Case 2 R(t) ∈ N on − Dense: In this case, R(t) can not be linear. The movement of a robot ri depends on the symmetry of R(t) as follows: (2.a) R(t) is free-path quasi-regular: Our approach maintains the quasi-regularity until at least two robots reach cq . A robot ri ∈ Rg moves towards cq following a direct movement. If a robot belongs to Rf , it does not move. In this case, robots have only direct movements with respect to cq . (2.b) R(t) is quasi-regular but not free-path quasi-regular: In this case, robots move either to convert the current configuration to a configuration in Dense or to create free paths to O(t) for robots. The approach depends on the positions of O(t) and cq . First, consider the case when cq ̸= O(t). Robot ri computes P ′ (t), that is, the set of pivotal robots. If ri (t) ∈ Sout (t) and ri (t) ∈ / P ′ (t), robot ri computes a destination point on ri (t)cq according to the step-in movement and moves towards this point. Otherwise, it does not move. Now suppose cq = O(t). Consider a robot ri such that ri (t) ∈ Sin (t). Let radi (t) intersect S(t) at the point xi . If xi contains a robot position or the open line segment (ri (t), O(t)) contains at least one robot position, then robot ri takes a step-aside movement w.r.t. O(t) (robot ri moves out of the line segment ri (t)O(t)). In the rest of the cases, robot ri does not move. (2.c) R(t) is not quasi-regular: In this case, we try to convert the current configuration into a configuration in Dense and in order to do so, we maintain S(t). If ri (t) ∈ Sout (t) and ri (t) ∈ / P ′ (t), then robot ri has a step-in movement w.r.t. O(t) (robot ri moves to a point on ri (t)O(t)). Otherwise, it does not move. Algorithm 7 : Gathering(ri , pm ) Require: Robot ri ∈ Rg and stable multiplicity point pm 1: if ri (t) = pm then 2: remain stationary 3: return 4: end if 5: if (ri (t), pm ) contains no robot position then 6: move directly toward pm 7: return 8: end if 9: if R(t) ∈N on − Dense and R(t) is quasi-regular but not free-path quasi-regular and cq = O(t) then 10: remain stationary 11: else 12: StepAside(ri , pm ) 13: end if (B) The gathering phase: Robots in Rg executes this phase when a multiplicity point pm is created. However, not all robots in Rf can detect the execution of this phase. If a robot in Rf lies at the multiplicity point pm , it does not move (robots in Rf have local weak multiplicity capability). Otherwise, the robots in Rf continue acting in the same way as they do during the multiplicity creation phase. Now, consider a robot ri ∈ Rg . If robot ri (t) = pm , then robot ri does not move. Otherwise, robot ri moves towards the multiplicity point pm in the following way: (B.1) If the line segment (ri (t), pm ) does not contain any other robot position, then robot ri has a direct movement towards pm . 18

(B.2) Otherwise, the line segment (ri (t), pm ) contains at least one robot position. If R(t) ∈N on − Dense and R(t) is quasi regular but not free-path quasi regular with cq = O(t), then ri does not move. Otherwise, robot ri has a step-aside movement w.r.t. pm . Algorithm 7 summarizes the Gathering procedure, which directs a robot in Rg toward the stable multiplicity point pm using either a direct or a step-aside movement, depending on the current configuration. (C) The formation phase: This phase is executed only by the robots in Rf when the total number of distinct robot positions in the system is at most Nf + 1, i.e., |R(t)| ≤ Nf + 1. Since the multiplicity point pm may contain a robot from Rf , a robot from Rg may not lie at pm . Since the robots in Rg do not know the size of Rg , they can not determine the start of this phase. Thus, exactly one robot in Rg may execute the gathering phase while the robots in Rf execute the formation phase simultaneously. However, the robots are unaware of this overlap. Thus, the main challenge here is to avoid collisions between the robots in Rf . Note that there is a special case in which we can not avoid a collision between a robot from Rg and a robot from Rf . However, this multiplicity point is unstable (once the robot from Rf moves, this multiplicity is broken). Robots in Rf move in some order. Algorithm 8 : Formation(ri ) Require: Robot ri ∈ Rf and |R(t)| ≤ Nf + 1 1: if ri (t) is a multiplicity point then 2: if ri (t) ∈ / ∂S(t) then 3: StepOut(ri , S(t)) 4: else 5: Let yi be the midpoint of ri (t)O(t) 6: move toward yi 7: end if 8: return 9: end if 10: Let Ck (t) = S(t) 11: if ri (t) ∈ S(t) then 12: remain stationary 13: else if ri (t) ∈ Ck−1 (t) then 14: Let xi = radi (t) ∩ S(t) 15: if xi is not occupied then 16: move directly toward xi 17: else 18: StepOut(ri , S(t)) 19: end if 20: else if ri (t) ∈ Ck−2 (t) and Ck−1 (t) contains exactly one occupied position then 21: StepOut(ri , Ck−1 (t)) 22: else 23: remain stationary 24: end if First, consider the case when a robot ri ∈ Rf does not lie at a multiplicity point. Let Ck = S(t) for some k. Robot ri moves according to one of the following ways: (C.1) If robot ri lies on S(t), it does not move. 19

(C.2) Suppose ri lies on Ck−1 (t). If xi , the intersection point between S(t) and radi (t), does not contain any robot position, then ri has a direct movement towards xi . Otherwise, robot ri moves according to the step-out movement w.r.t. S(t). (C.3) Suppose robot ri lies on Ck−2 (t) and Ck−1 (t) contains exactly one robot position. In this case, robot ri moves towards the circle Ck−1 (t) by a step-out movement w.r.t. the circle Ck−1 (t). (C.4) In the rest of the cases, robot ri does not move. Next, consider the case when robot ri lies at a multiplicity point. In this case, robot ri moves even if it lies on S(t) (the multiplicity point may lie on S(t)). Robot ri moves according to the step-out movement w.r.t. S(t), if it does not lie on the boundary of S(t). Otherwise, robot ri first moves towards the middle point of the line segment, ri (t)Ot and then it moves according to the step-out movement w.r.t. S(t). The formation rules for robots in Rf are summarized in Algorithm 8.

5

Correctness of Algorithm PatternFormation()

In this section, we prove the correctness of Algorithm PatternFormation() by establishing the required properties through a sequence of lemmas and concluding with the main theorem. Lemma 2. Routine MoveToDestination() provides collision-free movements for the robots during the multiplicity creation phase. Proof. Consider two robots ri , rj ∈ R which are to move in round t. Two robots do not collide if their movement paths do not intersect each other except at the desired destination point. We consider each of the phases separately : Case 1 R(t) ∈ Dense: In this case, O(t) is the destination point for all the robots in Rg and the robots in Rf do not move. Robots have two types of movements: the direct movement and these movements are w.r.t. O(t) only. Consider radi (t) and radj (t). First suppose that radi (t) and radj (t) coincide. Let ri and rj lie on the circles Ck (t) and Cl (t) respectively. Without loss of generality, suppose l < k. In this case, at most one of ri and rj can have direct movement. Now, in round t, consider all possible combinations of movements of robots ri and rj . In all of them, the paths of movement of these two robots are completely separated by the circle Cl (t). Thus, robots ri and rj do not collide. Next suppose that radi (t) and radj (t) are distinct. Let L∗ be the bisector of the angle ∠ri (t)O(t)rj (t). In this case, all possible paths of the two robots are separated by the bisector L∗ . Case 2 R(t) ∈ N on − Dense: The movements of robots ri and rj depend on the symmetry of R(t) as follows: Case 2.1 R(t) is free-path quasi regular: In this case, robots in Rg have direct movements and the robots in Rf do not move. If robots ri and rj move, they move along radi (t) and radj (t) respectively. These two paths meet at cq , the robot’s destination point. Thus, robots do not collide during movements. Case 2.2 R(t) is quasi regular but not free-path quasi regular: Robots in R have two types of movements: step-in and step-aside. The arguments are the same as in case 1. If radi (t) and radj (t) are coincident, then the paths of ri and rj are separated by Cl (t). Otherwise, the paths are separated by L∗ . Case 2.3 R(t) is not quasi regular: Both types of robots in R move in this case and have only step-in movements. If radi (t) and radj (t) coincide, then at most one of them moves. Without loss of generality, suppose ri moves. Robot ri moves to a point on radi (t), and this point is at most as far away 20

as the middle point of ri (t)rj (t) from rj (t). Thus, these two robots do not collide in this case. Next, consider the case when both robots move. In this case, radi (t) and radj (t) are different, and the paths of these two robots are separated by the bisector L∗ of the angle ∠ri (t)O(t)rj (t). Lemma 3. The multiplicity-creation phase creates a unique stable multiplicity point in finite time. Proof. We prove this lemma by considering each case separately: • R(t) ∈ Dense: In this case, only the robots having position in Rg (t) ∩ Sin (t) move. The robots lying on S(t) remain stationary, and hence the smallest enclosing circle S(t) and O(t) remain invariant. Since |Rg | ≥ 6 and Sout (t) ≤ 4, at least two robots from Rg lie inside S(t). – R(t) is free path quasi-regular: In this case robots move straight towards cq . Since robots move in straight lines towards cq , the configuration remains free path quasi-regular until at least two robots reach cq . Thus, at least two robots lie at cq within a finite time. Thus, at least two robots from Rg reach cq within finite time and create a stable multiplicity point at cq . Since the robots in Rg have global weak multiplicity detection capability, every robot in Rg can identify cq as the multiplicity point and subsequently execute the gathering phase. This implies the lemma in this case. – R(t) is not free path quasi-regular: Robots in Rg (t) ∩ Sin (t) move towards O(t). Since S(t) remains invariant under the movements of these robots, O(t) also remains fixed. Consider a robot ri ∈ Rg lying inside S(t). If (ri (t, O(t)) does not contain any robot position, then robot ri moves straight towards O(t). Now, let radj (t) be one of the neighbors of radi (t) such that rj ∈ Rg and it has a side-aside movement w.r.t. O(t). Then the paths of movements of ri and rj are separated by the bisector of the angle ∠ri (t)O(t)rj (t). Thus, robot ri reaches O(t) in finite time by moving along ri (t)O(t). Now suppose (ri (t), O(t)) has at least one robot position. In this, case, robot ri has a step-aside movement w.r.t. O(t). We show that robot ri gets a free corridor towards O(t) within finite time. Suppose robot ri lies on Ck (t). During the step-aside movement, robot ri moves towards a point on the circle Ck (t). The robot on (ri (t), O(t)), which is closest to O(t), does not move out of the line radi (t). This implies that for each step-aside movement of robot ri , at least one robot is removed from its straight line path to O(t). Since there is a finite number of robots on (ri (t), O(t)) and by Lemma 2, robots do not collide during this phase, within finite time, robot ri gets a robot-free straight path to O(t). Thus, within a finite time, at least two robots reach O(t) and make it a multiplicity point. Lemma 2 guarantees the uniqueness of the multiplicity point. • R(t) ∈N on − Dense: We show that either a multiplicity point is created or the configuration is converted into a one configuration belonging to Dense. – R(t) is free-path quasi-regular: In this case only the robots in Rg move and they move towards cq following direct movements. Due to these movements the current robot configuration R(t) reaches to a robot configuration R(t∗ ) having any one of the following properties: (i) at least two robots reach cq and thus R(t∗ ) contains a multiplicity point or (ii) R(t∗ ) is free-path quasi-regular with R(t∗ ) ∈Dense or (iii) R(t∗ ) is free-path quasi-regular with R(t∗ ) ∈ N on − Dense. In cases (i) and (ii), we are done. Now consider the case (iii). Since cq remains invariant under the direct movements of the robots, R(t∗ ) has cq as its centre of quasi-regularity. This implies that there are some robots in Rg whose distance from cq is reduced. Thus, the robot configuration satisfies property (i) or (ii) within a finite time. This implies the lemma in this case. 21

– R(t) is quasi-regular but not free-path quasi-regular: First consider the case when cq ̸= O(t). In this case, robots compute P ′ (t). The robots lying on S(t) and not having positions in P ′ (t) take step-in movements towards cq . By Lemma 1, the points in the set P ′ (t) are sufficient to define S(t). Since robots move towards cq along straight lines, the configuration remains quasi-regular but not free-path quasi-regular. Thus, within a finite time, configuration R(t) is converted to a configuration R(t∗ ) in Dense. This implies the lemma in this case. Now consider the case when cq = O(t). In this case, the robots are lying on S(t) do not move. Thus, S(t) does not change due to the robots’ movements. The robots, lying inside S(t) and not having free corridors to O(t), perform step-aside movements. These movements convert R(t) to a configuration R(t∗ ) having one of the following properties: (i) R(t∗ ) is free-path quasi-regular or (ii) R(t∗ ) is not quasi-regular or (iii) R(t∗ ) is quasi-regular, but not free-path quasi-regular, and the number of robots having free-paths is increased. We have discussed the case (i) above, and the case (ii) is discussed below. Consider the case (iii). If the centre of quasi-regularity of R(t∗ ) is different from O(t), then, as discussed above, we have the lemma in this case. Otherwise, the number of robots having free-paths is increased (since the smallest enclosing circle S(t) remains the same and robots take the step-aside movements w.r.t. O(t)). Since, by Lemma 2, robots do not collide during this phase, if this process is repeated, within finite time, we have either case (i) or case (ii). This completes the proof in this case. – R(t) is not quasi regular: In this case, robots compute P ′ (t). A robot ri moves if ri (t) ∈ Sout (t) and ri (t) ∈ / P ′ (t). By Lemma 1, the robot positions in P ′ (t) are sufficient to maintain S(t). The moving robots only have step-in movements for O(t). Due to these movements, R(t) is converted into configuration R(t∗ ) having any one of the following properties: (i) R(t∗ ) in Dense or (ii) R(t∗ ) in N on − Dense with |Sin (t∗ )| > |Sin (t)|. We are done in case (i). Now for case (ii), there are two possibilities: either R(t∗ ) is quasi-regular or R(t∗ ) is not quasi-regular. If R(t∗ ) is quasi-regular, then by the above case analysis, either we reach a configuration with a multiplicity point or a configuration which is not quasi-regular. Whenever a quasi-regular configuration R(t∗ ) is reached from another quasiregular configuration R(t), we have |Sin (t∗ )| > |Sin (t)| (since the algorithm maintains the smallest enclosing circle in those cases). Since the number of robots is finite, within finite time either the system has a multiplicity point, or the configuration belongs to Dense. The latter case also implies the former case in finite time. Lemma 2 guarantees the uniqueness of the multiplicity point. Now we show that the multiplicity point created during this phase is stable. If at least two robots from Rg lie at the multiplicity point, then the multiplicity point is stable. Since robots are indistinguishable, the multiplicity point can contain a robot from Rf . Since the robots’ movements are collision-free during this phase, at most one point from Rf lies at the multiplicity point. If the multiplicity point contains a robot from Rf , then this robot can recognize that it lies at a multiplicity point using its local weak multiplicity detection capability. Such a robot moves from the multiplicity point only after the formation phase starts, that is, when |R(t)| ≤ Nf + 1. At this time, at most one robot from Rg can lie outside the multiplicity point. Hence, since |Rg | ≥ 6, at least |Rg | − 1 ≥ 5 robots from Rg remain at the multiplicity point. Therefore, the multiplicity point remains stable even after the robot from Rf leaves it. This completes the proof of the lemma.

Lemma 4. If the multiplicity point created during the multiplicity creation phase does not contain a 22

robot from Rf , then MoveToDestination() provides collision-free movements during the gathering and formation phases. Proof. Since the multiplicity point pm does not contain a robot from Rf , the formation phase cannot start before all the robots in Rg gather at pm . Indeed, as long as at least one robot from Rg remains outside pm , the number of distinct occupied positions is greater than Nf + 1. Hence, the condition |R(t)| = Nf + 1 required for the start of the formation phase is not satisfied. Thus, in this case, the gathering phase and the formation phase are executed sequentially. During the gathering phase: Since robots in Rf do not have global weak multiplicity detection capability, they continue acting according to the multiplicity creation phase until |R(t)| = Nf + 1. Their movements are limited to step-in and step-aside movements, both with respect to a single point, either O(t) or cq . The robots in Rg move toward pm by either direct or step-aside movements. Let ri and rj be two active robots in round t. • Robots ri , rj ∈ Rg : If the line segments ri (t)pm and rj (t)pm are not coincident, then the paths of movements of ri and rj are completely separated by the bisector of the angle ∠ri (t)pm rj (t). Next suppose that ri (t)pm and rj (t)pm are coincident. Without loss of generality, suppose that ri (t) lies ∗ on (rj (t), pm ). Let ri (t) lie on Cl∗ (t) and rj (t) lie on Ck∗ (t) for some l, k. Let Ckl (t) be the circle ∗ ∗ having centre at pm and lying midway between Cl (t) and Ck (t). Then the movement paths of ri ∗ and rj are completely separated by the circle Ckl (t). • Robots ri , rj ∈ Rf : Robots ri and rj continue to act according to the multiplicity creation phase. Hence, by Lemma 2, their movements are collision-free. • Robots ri , rj belong to different groups: Without loss of generality, suppose that ri ∈ Rg and rj ∈ Rf . If pm = O(t), then both robots act exactly as in the multiplicity creation phase. Hence, by Lemma 2, they do not collide. Now consider the case when pm ̸= O(t). If rj does not move, then ri does not collide with rj . If rj has a step-aside movement during the multiplicity creation phase, then according to the gathering rule, ri does not move. Hence, no collision occurs. Finally, if both robots move, then rj has a step-in movement with respect to O(t), while ri has either a direct movement or a step-aside movement with respect to pm . If ri has a direct movement and the segments ri (t)pm and rj (t)O(t) intersect at a point x, then by construction the destination of rj lies on the open segment (rj (t), x). Hence, the two robots do not collide. If ri has a step-aside movement and ri (t) lies on Cl∗ (t), then its destination lies on Cl∗ (t) ∩ Vo . If rj (t)O(t) does not intersect Cl∗ (t) ∩ Vo , then the paths do not intersect. Otherwise, let x be the intersection point. Then the paths are separated by the bisector of the segment ri (t)x. Thus, the gathering phase is collision-free. During the formation phase: Once all robots in Rg gather at pm , we have |R(t)| = Nf + 1, and the robots in Rf start the formation phase. During this phase only the robots in Rf move, and they have either direct movement or step-out movement with respect to O(t). Their movements are ordered according to their distance from O(t). Consider two robots ri , rj ∈ Rf active in round t. Let radi (t) and radj (t) intersect S(t) at ui and uj , respectively. If ui ̸= uj and both ui and uj do not contain robot positions, then the paths of the direct movements of ri and rj are separated by the bisector of the angle ∠ri (t)O(t)rj (t). If ui ̸= uj and exactly one of them contains a robot position, say ui , then the destination point of ri is computed so that it lies on a different side of the bisector of ∠ri (t)O(t)rj (t) from uj . Hence, ri and rj do not collide. Finally, if ui = uj , then the robots lie on the same radial line. Without loss of generality, suppose that rj lies on Ck−1 (t) and ri lies on Ck−2 (t). Then the destination point of ri lies on Ck−1 (t), and the movement paths of ri and rj are completely separated by Ck−1 (t). 23

Therefore, the formation phase is collision-free. This completes the proof. Lemma 5. If the multiplicity point created during the multiplicity creation phase contains a robot from Rf , then the gathering and formation phases may overlap. In that case, no two robots from Rf collide during the formation phase. Moreover, if a robot from Rg collides with a robot from Rf , the resulting additional multiplicity point is unstable and disappears once the robot from Rf moves away from it. Proof. Suppose that the multiplicity point pm created during the multiplicity creation phase contains a robot from Rf . Since the movements during the multiplicity creation phase are collision-free, at most one robot from Rf can lie at pm . The gathering and formation phases may overlap only in the following situation: exactly one robot from Rg remains outside pm , while at least one robot from Rf not lying at pm finds |R(t)| = Nf + 1 and starts the formation phase. This is possible because one robot from Rf already lies at pm and the robots in Rf have only local weak multiplicity detection capability. Let ri ∈ Rg be the unique robot not lying at pm , and let rj ∈ Rf be a robot active in the same round. Robot ri has either a direct or a step-aside movement toward pm , whereas rj has a step-out movement toward the boundary of S(t). Hence, the paths of these two robots may intersect. Due to non-rigid movement, the adversary may stop both robots at such an intersection point, thereby creating another multiplicity point. However, this multiplicity point is not stable, because it contains only one robot from Rg . Once the robot from Rf moves away from that point, the multiplicity is broken. Moreover, the collision-avoidance argument used in the formation phase depends only on the movements of robots in Rf . Hence, no two robots from Rf collide during the formation phase, even when the overlap occurs. Therefore, during the overlap of the gathering and formation phases, any additional multiplicity point created by a collision between a robot from Rg and a robot from Rf is only temporary and cannot become stable. This completes the proof. Lemma 6. The gathering phase gathers all robots in Rg at the unique stable multiplicity point. Proof. By Lemma 2, the multiplicity point created during the multiplicity creation phase is stable. Let pm denote the multiplicity point created during the multiplicity creation phase. Robots in Rg can identify the multiplicity point using their global weak multiplicity detection capability. First, consider the case when pm contains no robot from Rf . The robots in Rf do not have global weak multiplicity detection capability. Thus, they can not detect the start of the gathering phase and continue performing the actions according to the multiplicity creation phase. By Lemma 4, robots do not collide during movements in this case. Thus, pm remains as the unique multiplicity point in the system. Consider a robot ri ∈ Rg . If ri (t) = pm , robot ri does not move. If (ri (t), O(t)) does not contain any other robot positions, then robot ri has direct movement towards O(t). Since robots have collision-free movements, robot ri reaches O(t) in finite time. Finally, suppose that (ri (t), O(t)) contains at least one robot position. We must show that robot ri gets a free path to O(t) in finite time. Robot ri adopts step-aside movement w.r.t. pm . Now, if ri and all the robots on (ri (t), pm ) move in each round, then ri may not get a free path to pm (all these robots may land on a new line passing through pm ). To tackle this, we consider the possible scenarios when all the robots on (ri (t), pm ) move. If (ri (t), pm ) contains all robots from Rf and R(t) is quasi-regular but no free-path quasi regular with cq = O(t), then the robots on (ri (t), pm ) perform step-aside movements. According to our algorithm, robot ri does not move in this case. Due to movements of the robots on (ri (t), O(t)), robot ri either gets a free path to pm or the characteristic of the current configuration is changed. In the first case, we are done. In the second case, robot ri makes a step-aside movement and the robots on (ri (t), pm ) do not move. Thus, ri gets a free path to pm . Now, if (ri (t), O(t)) also contains robots from Rg , then each movement of the robots from (ri (t), pm ) reduces the number of robots on the path of ri to pm . Since the number of robots is finite, robot ri gets a free direct path to pm within finite time. Now consider the other scenarios when the 24

Rf robots do not have step-aside movements. The Rf robots can have step-in movements w.r.t. O(t) or cq depending on the configuration. If robots in Rf do not move, then the movements of the robots on (ri (t), pm ) reduce the number of robots on the direct path of ri to pm and in finite time ri gets a free path to pm . Consider the scenario when robots in Rf have step-in movements. Only the robots on S(t) can have step-in movements. We show that robots having step-in movements do not become collinear with ri and pm . Let rj ∈ Rf be a robot which takes a step-in movement during this phase. If ri (t)pm does not intersect rj (t)d, then we have nothing to prove where d ∈ {O(t), cq }. Otherwise, let x be the intersection point between ri (t)pm and rj (t)p. The destination point of rj during its step-in movement lies on (rj (t), x). The destination point of ri lies in Vo . Thus, the paths of these two robots are separated by the perpendicular line to ri (t)rj (t) passing through the point x. This completes the proof in this case. Consider when a robot from Rf lies at pm . In this case, the gathering phase overlaps with the formation phase. In the proof of Lemma 4, we have seen that no two robots Rf collided during the formation phase. However, we have shown that exactly one robot from one Rg , say ri , may collide with a robot from Rf . This will create a multiplicity point, say p∗ . According to the algorithm, robots from Rg do not move when they find that they lie at a multiplicity point. Since all but one robot from Rg lies at pm , a stable multiplicity point, no other robot from Rg moves to p∗ . Thus, the multiplicity point p∗ is unstable: once the robot from Rf lying at p∗ moves, this multiplicity point is broken. The formation phase starts when R(t) = |Nf |. Thus, according to the algorithm, the robots from Rf lying at the multiplicity point move during this phase. This implies that the multiplicity of p∗ will be broken in finite time. Once this happens, robot ri moves towards pm . Robot ri may again collide with some other robot from Rf ; however, its distance from pm is decreased by at least δ in each movement. Thus, within a finite time, it reaches pm . This completes the proof of the lemma. Lemma 7. The formation phase places all robots in Rf at distinct positions on the boundary of a common circle. Proof. This phase starts when robots in Rf find |R(t)| ≤ Nf + 1. We prove the lemma by considering the following two cases separately: (i) when pm does not contain a robot from Rf and (ii) when pm contains a robot from Rf . • pm does not contain a robot from Rf : In this case, only the robots in Rf moves during this phase. By Lemma 4, robots do not collide with each other during movements in this case. The robots lying on S(t) do not move. The robots from Rf lying inside or at the multiplicity point move according to step-out movement. Thus, S(t) remains invariant during this phase. The movements of the robots are ordered: a robot ri ∈ Rf moves if it lies on Ck−1 (t) or on Ck−2 (t), where Ck (t) = S(t). Robots lying on Ck−2 (t) moves to Ck−1(t) when there is exactly one robot position on Ck−1 (t). A robot lying on Ck−1 (t) moves to S(t). Suppose ri lies on Ck−1 (t) and x is the intersection point between radi (t) and S(t). If x contains no robot position, then ri moves straight to x. Otherwise, it computes a point on S(t) which does not contain any robot position. By Lemma 4, no two robots compute the same destination point on S(t) (otherwise, a collision could happen). Since S(t) remains invariant under the robots’ movements, robot ri reaches S(t) within finite time. If ri lies on Ck−2 (t), then by the same approach discuss above, robot ri first reaches Ck−1 (t) and then from there to S(t). This implies the lemma in this case. • pm contains a robot from Rf : Let rj ∈ Rf lie at pm . In this case, the formation phase may start before the end of the gathering phase. It may start before exactly one robot, say rk , reaches pm . Thus, the circle S(t) may change with the robot’s movement rk . However, the robot rk reaches pm within a finite time. Once rk reaches pm , the smallest enclosing circle of the robot positions 25

becomes stable. Thus, we can conclude the proof in this case using the same argument as in the above.

From the above lemmas, we obtain our main result, stated in Theorem 1. Theorem 1. Let R = Rg ∪ Rf be a set of anonymous, oblivious, fully disoriented robots operating under the SSYNC scheduler with non-rigid movements. Suppose that |Rg | ≥ 6 and |Rf | ≥ 2, and that initially all robots occupy distinct positions. If robots in Rg have global weak multiplicity detection and robots in Rf have local weak multiplicity detection together with the knowledge of |Rf |, then Algorithm PatternFormation() terminates in finite time such that all robots in Rg gather at one point and all robots in Rf occupy distinct positions on a common circle.

6

Conclusions

In this paper, we have extended the study initiated in [6]. We propose a distributed algorithm that solves the problem for disoriented semi-synchronous robots with non-rigid movements. Our algorithm works without any kind of assumption on the local coordinate axes of the robots. The proposed algorithm assumes global weak multiplicity detection capability for the robots, which solves the gathering problem and local weak multiplicity detection capability for the robots, which solves the circle formation problem. The proposed algorithm works with robots that do not have rigid movements. One of the future directions of this work is to extend it to disoriented asynchronous robots. It would also be interesting to remove the assumptions |Rg | ≥ 6 and the knowledge of |Rf |.

Funding Animesh Maiti and Prakhar Shukla were supported by the INSPIRE Fellowship of the Department of Science and Technology (DST), Government of India.

Declaration of competing interest The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.

References [1] Chrysovalandis Agathangelou, Chryssis Georgiou, and Marios Mavronicolas. A distributed algorithm for gathering many fat mobile robots in the plane. In Proc. ACM Symposium on Principles of Distributed Computing (PODC), pages 250–259, 2013. [2] Noa Agmon and David Peleg. Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM Journal on Computing, 36(1):pages 56–82, 2006. [3] S. Bhagat and K. Mukhopadhyaya. Fault-tolerant gathering of semi-synchronous robots. In Proc. the 18th International Conference on Distributed Computing and Networking (ICDCN-2017), page 6, 2017.

26

[4] Subhash Bhagat, Sruti Gan Chaudhuri, and Krishnendu Mukhopadhyaya. Fault-tolerant gathering of asynchronous oblivious mobile robots under one-axis agreement. J. Discrete Algorithms, 36:pages 50–62, 2016. [5] Subhash Bhagat, Bibhuti Das, Abhinav Chakraborty, and Krishnendu Mukhopadhyaya. k-circle formation and k-epf by asynchronous robots. Algorithms, 14(2):62, 2021. [6] Subhash Bhagat, Paola Flocchini, Krishnendu Mukhopadyaya, and Nicola Santoro. Weak robots performing conflicting tasks without knowing who is in their team. In Proceedings of the 21st International Conference on Distributed Computing and Networking, pages 1–6, 2020. [7] Subhash Bhagat and Krishnendu Mukhopadhyaya. Optimum circle formation by autonomous robots. In Advanced Computing and Systems for Security: Volume Five, pages 153–165. Springer, 2018. [8] Zohir Bouzid, Shantanu Das, and Sébastien Tixeuil. Wait-free gathering of mobile robots. CoRR, abs/1207.0226, 2012. [9] Zohir Bouzid, Shantanu Das, and Sébastien Tixeuil. Gathering of mobile robots tolerating multiple crash faults. In Proc. IEEE 33rd International Conference on Distributed Computing Systems, pages 337–346, 2013. [10] Sruti Gan Chaudhuri and Krishnendu Mukhopadhyaya. Leader election and gathering for asynchronous fat robots without common chirality. Journal of Discrete Algorithms, 33:171–192, 2015. [11] Mark Cieliebak, Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Distributed computing by mobile robots: Gathering. SIAM Journal on Computing, 41(4):pages 829–879, 2012. [12] Jurek Czyzowicz, Leszek Gasieniec, and Andrzej Pelc. Gathering few fat mobile robots in the plane. Theoretical Computer Science, 410(6):pages 481–499, 2009. [13] Bibhuti Das, Abhinav Chakraborty, Subhash Bhagat, and Krishnendu Mukhopadhyaya. k-circle formation by disoriented asynchronous robots. Theoretical Computer Science, 916:40–61, 2022. [14] Bibhuti Das and Krishnendu Mukhopadhyaya. Uniform k-circle formation by asynchronous fat robots. The Computer Journal, 68(11):1641–1656, 2025. [15] Caterina Feletti, Carlo Mereghetti, and Beatrice Palano. Uniform circle formation for fully, semi-, and asynchronous opaque robots with lights. Applied Sciences, 13(13), 2023. [16] Caterina Feletti, Carlo Mereghetti, and Beatrice Palano. o(log n)-time uniform circle formation for asynchronous opaque luminous robots. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023), volume 286 of LIPIcs, pages 5:1–5:21, 2024. [17] Caterina Feletti, Debasish Pattanayak, and Gokarna Sharma. Brief announcement: Optimal uniform circle formation by asynchronous luminous robots. In 38th International Symposium on Distributed Computing (DISC 2024), 2024. [18] P. Flocchini, G. Prencipe, N. Santoro, and G. Viglietta. Distributed computing by mobile robots: Solving the uniform circle formation problem. In The 18th International Conference on Principles of Distributed Systems (OPODIS 2014), pages 217–232, 2014. [19] P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer. Gathering of asynchronous robots with limited visibility. Theoretical Computer Science, 337(1-3):147 – 168, 2005.

27

[20] Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Distributed Computing by Oblivious Mobile Robots. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers, 2012. [21] M. Mamino and G. Viglietta. Square formation by asynchronous oblivious robots. In In Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG), pages 1–6, 2016. [22] D. Pattanayak, K. Mondal, H. Ramesh, and P. S. Mandal. Gathering of mobile robots with weak multiplicity detection in presence of crash-faults. Journal of Parallel Distributed Computing, 123:145–155, 2019. [23] Giuseppe Prencipe. Impossibility of gathering by a set of autonomous mobile robots. Theoretical Computer Science, 384(2 - 3):pages 222–231, 2007. [24] Ichiro Suzuki and Masafumi Yamashita. Distributed anonymous mobile robots: Formation of geometric patterns. SIAM Journal on Computing, 28:pages 1347–1363, 1999. [25] Giovanni Viglietta. Rendezvous of two robots with visible bits. In Proc. International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS), pages 291–306, 2013.

28