Paper deep dive
Conflicting Pattern Formation by Teams of Anonymous, Fully Disoriented Robots
Animesh Maiti, Prakhar Shukla, Subhash Bhagat
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 96%
Last extracted: 9/22/2026, 4:24:22 AM
Summary
This paper addresses the problem of conflicting pattern formation by two groups of autonomous, anonymous, and fully disoriented mobile robots in a 2D Euclidean plane. One group solves the gathering problem (meeting at a point), while the other solves the circle formation problem (occupying distinct positions on a circle boundary). The authors propose a distributed algorithm for semi-synchronous robots with non-rigid movements, requiring global weak multiplicity detection for the gathering group and local weak multiplicity detection for the circle formation group. This extends prior work that required axis agreement.
Entities (11)
Relation Signals (8)
Animesh Maiti → affiliatedwith → Indian Institute of Technology Jodhpur
confidence 99% · Animesh Maiti ... Department of Mathematics, Indian Institute of Technology Jodhpur
Prakhar Shukla → affiliatedwith → Indian Institute of Technology Jodhpur
confidence 99% · Prakhar Shukla ... Department of Mathematics, Indian Institute of Technology Jodhpur
Subhash Bhagat → affiliatedwith → Indian Institute of Technology Jodhpur
confidence 99% · Subhash Bhagat ... Department of Mathematics, Indian Institute of Technology Jodhpur
Gathering Problem → conflictswith → Circle Formation Problem
confidence 98% · two groups must simultaneously solve two conflicting pattern formation problems: the gathering problem ... and the circle formation problem
Gathering Group → requirescapability → Global Weak Multiplicity Detection
confidence 96% · assumes global weak multiplicity detection only for the gathering group
Circle Formation Group → requirescapability → Local Weak Multiplicity Detection
confidence 96% · for the circle formation group, it requires local weak multiplicity detection
Disoriented Robots → solves → Conflicting Pattern Formation
confidence 95% · We propose a distributed algorithm that solves the problem for semi-synchronous disoriented robots
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Two groups of autonomous, anonymous, and oblivious mobile robots are deployed in the two-dimensional Euclidean plane, each assigned a distinct task. We study a setting where the two groups must simultaneously solve two conflicting pattern formation problems: the \textit{gathering problem}, where robots gather at a point not known to them a priori, and the \textit{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~\cite{Conflict-1} addressed this problem for asynchronous robots having {\it direction-only axis agreement} and {\it global weak multiplicity detection} capability available to all robots in both groups. In contrast, in this work, we consider fully {\it disoriented robots} without any axis agreement or common \textit{chirality}. We study the feasibility of a solution to this problem for {\it 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.
Tags
Links
- Source: https://arxiv.org/abs/2609.23454v1
- Canonical: https://arxiv.org/abs/2609.23454v1
Trouble viewing inline? Open PDF directly →
Full Text
102,032 characters extracted from source content.
Expand or collapse full text
Conflicting Pattern Formation by Teams of Anonymous, Fully Disoriented Robots Animesh Maiti †thanks: Corresponding author: p22ma201@iitj.ac.in Prakhar Shukla Subhash Bhagat 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 two-dimensional 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 (FSYNCFSYNC), semi-synchronous (SSYNCSSYNC), or asynchronous (ASYNCASYNC). In FSYNCFSYNC and SSYNCSSYNC scheduling, time is divided into discrete rounds. An FSYNCFSYNC scheduler activates all the robots in each round, whereas an SSYNCSSYNC scheduler activates only a subset of robots in each round. The ASYNCASYNC 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δ>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≥2n≥ 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≥5n≥ 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=2n=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 fatfat robots (robots having physical extents). Czyzowicz et al. solved the gathering problem for n=4n=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 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(logn)O( 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 55 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 ℛ=r1,r2,…,rnR=\r_1,r_2,…,r_n\ 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 SSYNCSSYNC model). Let ℛg⊂ℛR_g denote the set of robots required to solve the gathering problem, and ℛf⊂ℛR_f be the team of robots required to solve the circle formation problem. We assume ℛ=ℛg∪ℛfR=R_g _f and |ℛg|≥6|R_g|≥ 6, |ℛf|≥2|R_f|≥ 2. Let NfN_f and NgN_g denote the cardinalities of ℛfR_f and, ℛgR_g respectively. We assume the following: (i) robots in ℛgR_g have global weak multiplicity detection capability, and (i) robots in ℛfR_f have local weak multiplicity capability, and they know the value of |ℛf||R_f|, i.e., NfN_f. A robot ri∈ℛr_i 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 Let ri(t)r_i(t) denote the position of robot ri∈ℛr_i at time t. Let ℛ~(t)=r1(t),…,rn(t) R(t)=\r_1(t),…,r_n(t)\ be the multiset of robot positions occupied by the robots in ℛR at time t. Let ℛ(t)=p∈ℝ2∣p occurs in ℛ~(t)R(t)=\p ^2 p occurs in R(t)\ denote the set of distinct occupied positions of the robots in ℛR at time t. Similarly, let ℛg(t)R_g(t) and ℛf(t)R_f(t) denote the sets of distinct positions occupied by the robots in ℛgR_g and ℛfR_f, respectively, at time t. A point p∈ℛ(t)p (t) occupied by at least two robots is called a multiplicity point. A multiplicity point occupied by at least two robots from ℛgR_g is called a stable multiplicity point. Let S(t)S(t) denote the smallest enclosing circle (SECSEC) of the robot positions at time t, and let (t)O(t) denote its centre. We use ∂S(t)∂ S(t) to denote the circumference of S(t)S(t). Let Sout(t)S_out(t) and Sin(t)S_in(t) denote the robot positions in ℛ(t)R(t) lying on the circumference of S(t)S(t) and inside S(t)S(t), respectively. S(0)S(0) is the smallest enclosing circle for the initial robot configuration ℛ(0)R(0). Let D(t)=∥p−(t)∥:p∈ℛ(t),p≠(t).D(t)= \\|p-O(t)\|:p (t),\;p (t) \. Let 0<ρ1(t)<ρ2(t)<⋯<ρm(t)0< _1(t)< _2(t)<·s< _m(t) be the distinct values in D(t)D(t). For each k∈1,…,mk∈\1,…,m\, let Ck(t)C_k(t) denote the circle centered at (t)O(t) with radius ρk(t) _k(t). Thus, the circles are indexed from the innermost to the outermost radial level, and Cm(t)=S(t)C_m(t)=S(t). (see Figure 1). Let a and b be two points in the plane. By (a,b)(a,b) and ab¯ 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)C_k(t) for k≥1k≥ 1: blue robots represent the set ℛfR_f and red robots represent the set ℛgR_g. 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 ℝ2R^2 and let c∈ℝ2c ^2 be a point. For any robot position ri∈ℛr_i , the successor of rir_i with respect to c, denoted by S(ri,c)S(r_i,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 Sk(ri,c)=S(Sk−1(ri,c),c),S^k(r_i,c)=S(S^k-1(r_i,c),c), with S0(ri,c)=riS^0(r_i,c)=r_i. (see Figure 2(b)) Definition 2 (String of Angles). Let ℛR be a set of robot positions and let c∈ℝ2c ^2. Let r1,r2,…,rnr_1,r_2,…,r_n 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(ℛ,c)SA(R,c), is defined as SA(ℛ,c)=(α1,α2,…,αn),SA(R,c)=( _1, _2,…, _n), where αi=∠(ri,c,ri+1)for i=1,…,n, _i= (r_i,c,r_i+1)\ for i=1,…,n, and rn+1=r1.r_n+1=r_1. 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(ℛ,c)SA(R,c) captures both the angular ordering and the multiplicities of robots. (see Figure 2(b) ) (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)=rjS(r_i,c)=r_j, S(rj,c)=rkS(r_j,c)=r_k, S(rk,c)=rlS(r_k,c)=r_l, and so on. The string of angles is SA(ℛ,c)=(α,0,β,α,0,β,α,0,β,α,0,β)SA(R,c)=(α,0,β,α,0,β,α,0,β,α,0,β), which can be written as SA(ℛ,c)=X4,where X=(α,0,β)SA(R,c)=X^4, 9.24994ptwhere X=(α,0,β). Therefore, the configuration is regular with reg(ℛ)=4reg(R)=4. (b) Illustration of a quasi-regular configuration ℛ(t)R(t) with centre of quasi-regularity cqc_q, where ℬ(t)=ℛ(t)∖rcq(t)B(t)=R(t) \r_c_q(t)\. The half-line qradi(t)qrad_i(t) denotes the ray starting from cqc_q and passing through ri(t)r_i(t). Definition 3 (Regular Configuration). A configuration ℛR is said to be regular with respect to a point c if the string of angles SA(ℛ,c)SA(R,c) can be written as SA(ℛ,c)=Xk,SA(R,c)=X^k, for some non-empty sequence X and integer k>1k>1. The regularity of ℛR, denoted by reg(ℛ)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 ℛ(t)R(t) be a configuration of robots at time t. The configuration ℛ(t)R(t) is said to be quasi-regular (Q-regular) if there exists a subset ℬ(t)⊆ℛ(t)B(t) (t) and a point c∈ℝ2c ^2 such that the subset ℬ(t)B(t) forms a regular configuration with respect to c, i.e., the string of angles SA(ℬ(t),c)SA(B(t),c) is periodic with period greater than 11, and all robots in ℛ(t)∖ℬ(t)R(t) (t) lie at the point c. The point c is called the centre of quasi-regularity, denoted by cqc_q. The quasi-regularity of ℛ(t)R(t) is defined as qreg(ℛ(t))=reg(ℬ(t))qreg(R(t))=reg(B(t)), and qreg(ℛ(t))=1qreg(R(t))=1 if no such subset exists. For each robot ri(t)∈ℛ(t)r_i(t) (t) with ri(t)≠cqr_i(t)≠ c_q, the half-line qradi(t)qrad_i(t) is defined as the ray starting from cqc_q and passing through ri(t)r_i(t). (see Figure 2(b)) Let ℛ(t)R(t) be a quasi-regular configuration with center cqc_q. For each robot ri(t)r_i(t), let qradi(t)qrad_i(t) be the segment joining cqc_q to ri(t)r_i(t). The configuration is said to be free-path quasi-regular if no other robot lies on qradi(t)qrad_i(t) between cqc_q and ri(t)r_i(t) for any ri(t)∈ℛ(t)r_i(t) (t) (see Figure 3(a)). The configuration is said to be totally symmetric if (t)=cqO(t)=c_q (see Figure 3(a)); otherwise, (t)≠cqO(t)≠ c_q (see Figure 3(c)). Definition 5 (Radial ray). For a robot position ri(t)∈ℛ(t)r_i(t) (t) with ri(t)≠(t)r_i(t) (t), the half-line radi(t)rad_i(t) is defined as the ray starting from (t)O(t) and passing through ri(t)r_i(t). (Compare qradi(t)qrad_i(t) in Definition 4, which is defined analogously with respect to the centre of quasi-regularity cqc_q rather than (t)O(t).) (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 free-path quasi-regular, (c) a quasi-regular configuration with (t)≠cqO(t)≠ c_q. 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|S_out(t)|≤ 4. −Non-Dense: A robot configuration belongs to this class if it does not contain any multiplicity points, with |Sout(t)|>4|S_out(t)|>4. Final: A robot configuration ℛ(t)R(t) belongs to this class if it satisfies both of the following conditions: (i) ∃p∗∈ℝ2∃\,p^* ^2 such that ri(t′)=p∗,∀ri∈ℛg,∀t′≥t,r_i(t )=p^*, ∀\,r_i _g,\;∀\,t ≥ t, i.e., all the robots in ℛgR_g achieve gathering. (i) ∃ a circle S⊂ℝ2S ^2 such that rj(t′)∈∂S,∀rj∈ℛf,∀t′≥t,r_j(t )∈∂ S, ∀\,r_j _f,\;∀\,t ≥ t, i.e., all the robots in ℛfR_f achieve circle formation. 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 SECSEC, S(0)S(0). This phase depends on the assumption of axis-only agreements, and this helps to keep S(0)S(0) intact. Keeping S(0)S(0) intact ensures finite-time termination of the reduction phase with at least two robots inside S(0)S(0) from the gathering group ℛgR_g. Furthermore, this also helps to decide and keep the final gathering point (the centre of S(0)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 ℛgR_g 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 ℛfR_f, and if an ℛfR_f robot participates in its creation, it must remain there until the multiplicity becomes stable. To this end, robots in ℛfR_f 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 |ℛg|≥6|R_g|≥ 6 guarantees that at least two gathering robots remain in the interior of the SECSEC 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. 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 on−DenseNon-Dense, the algorithm first moves selected non-pivotal boundary robots into the interior of the current smallest enclosing circle S(t)S(t). By Lemma 1, the pivotal robots preserve S(t)S(t). This reduction either creates a stable multiplicity point directly or produces a enseDense configuration. In a enseDense configuration, at most four robot positions lie on ∂S(t)∂ S(t). Since |ℛg|≥6|R_g|≥ 6, at least two gathering robots lie inside S(t)S(t). These robots move toward a common geometrically defined point, namely the quasi-regular centre cqc_q when the configuration is free-path quasi-regular, and (t)O(t) otherwise. Hence, a unique stable multiplicity point pmp_m is eventually created. Once pmp_m exists, every gathering robot moves toward pmp_m. At the same time, circle-forming robots may start moving outward when |ℛ(t)|≤Nf+1|R(t)|≤ N_f+1. The movement rules ensure that gathering remains directed toward pmp_m and that circle-forming robots occupy distinct positions on the current SECSEC. The high-level execution flow of Algorithm PatternFormation() is illustrated in Figure 4. on−DenseNon-DenseenseDenseStablemultiplicityGathering(ℛgR_g)Circleformation (ℛfR_f)ℱinalFinalreductioncreationdirect creation 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 on−DenseNon-Dense configuration into enseDense configuration while preserving the SECSEC; 3. in a enseDense 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 ′(t)⊆Sout(t),P (t) S_out(t), called the pivotal set. A subset ′(t)⊆Sout(t)P (t) S_out(t) is called a pivotal set if SEC(′(t))=S(t).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 p0p_0 be the first robot position in Sout(t)S_out(t) under the canonical ordering of the configuration (since ℛ(t)R(t) is asymmetric, we can obtain an ordering of the robot positions in ℛ(t)R(t) ([10]). Let ℒL be the line through p0p_0 and (t)O(t). If the antipodal point of p0p_0 is occupied by a robot position in Sout(t)S_out(t), then ′(t)P (t) consists of these two antipodal positions. Otherwise, ′(t)P (t) contains p0p_0 together with the two robot positions in Sout(t)S_out(t) adjacent to its antipodal point. • Configurations with one symmetry axis: Let ℒL be the unique symmetry axis, and let a,b∈∂S(t)a,b∈∂ S(t) be its intersections with ∂S(t)∂ S(t). The pivotal set consists of every occupied intersection and, for each unoccupied intersection x∈a,bx∈\a,b\, the first occupied boundary positions encountered from x along the two circular directions of ∂S(t)∂ S(t), after removing duplicates.(see Figure 5) • Quasi-regular configurations with cq≠(t)c_q (t). Let D denote the set of robot positions in Sout(t)S_out(t) having maximum distance from cqc_q. Note that 1≤D≤21≤ D≤ 2, as cq≠O(t)c_q≠ O(t). The canonical line is defined as the line through (t)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|A|≥ 3, and let B⊆AB A with 2≤|B|≤42≤|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|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 p1p_1 and p2p_2 contain robot positions, (b) exactly one of p1p_1 and p2p_2 contains a robot position, and (c) none of p1p_1 and p2p_2 contains a robot position. Lemma 1. For every configuration in which the pivotal set is defined, the smallest enclosing circle of ′(t)P (t) coincides with S(t)S(t); that is, SEC(′(t))=S(t).SEC (P (t) )=S(t). Proof. By construction, ′(t)P (t) contains either (i) two antipodal boundary positions of S(t)S(t), or (i) at least three occupied boundary positions that are not contained in any open semicircle of S(t)S(t). The property 1 of the smallest enclosing circle implies that either condition uniquely determines S(t)S(t). Therefore, SEC(′(t))=S(t).SEC(P (t))=S(t). Let S(t)S(t) be the smallest enclosing circle (SECSEC) of the configuration ℛ(t)R(t) with center (t)O(t), and let ′(t)⊆Sout(t)P (t) S_out(t) be the set of pivotal robot positions. We prove that ′(t)P (t) uniquely determines S(t)S(t) using Property 1. Step 1: Characterization of SECSEC. It is well known that the SECSEC of a point set is uniquely determined by either: (i) two diametrically opposite boundary points, or (i) at least three boundary points not contained in any open semicircle. Step 2: Diametrically opposite case. If ′(t)P (t) contains two diametrically opposite points, then these two points uniquely define S(t)S(t). Note that this may occur even when |′(t)|≥3|P (t)|≥ 3. Step 3: Non-diametrical case. Assume that no two points in ′(t)P (t) are diametrically opposite. Then |′(t)|≥3|P (t)|≥ 3. Order the points of ′(t)P (t) along S(t)S(t) in clockwise order: ri1(t),ri2(t),…,rik(t),k=|′(t)|andk=3,4.r_i_1(t),r_i_2(t),…,r_i_k(t),\ k=|P (t)|\ and\ k=3,4. These points partition the circumference into k arcs. Let αj _j denote the arc between rij(t)r_i_j(t) and rij+1(t)r_i_j+1(t) (indices modulo k). Step 4: Arc bound. We claim that αj≤πR _j≤π R for all j, i.e., no arc exceeds a semicircle. Suppose, for contradiction, that there exists an arc αm>πR _m>π R. Then all points of ′(t)P (t) lie within the complementary semicircle, say Sc(t)S_c(t). We first show that if all points of ′(t)P (t) lie within the semicircle, Sc(t)S_c(t), then all points of ℛ(t)R(t) must also lie within the semicircle, Sc(t)S_c(t). Now, by construction, the points in ′(t)P (t) are obtained using a well-defined line ℒ(t)L(t) passing through (t)O(t). The line ℒ(t)L(t) divides the circle S(t)S(t) into two semicircles, say, S1(t)S_1(t) and S2(t)S_2(t). If |′(t)|=3|P (t)|=3, there is a unique robot position, say ri(t)r_i(t) on the boundary of S(t)S(t) that lies on ℒ(t)L(t) and the other two robot positions in ′(t)P (t), say rj(t)r_j(t) and rk(t)r_k(t), are farthest robot positions from ri(t)r_i(t) lying on S(t)S(t). When |′(t)|=4|P (t)|=4, then there are two pairs of points in ′(t)P (t) such that one pair lies on S1S_1 and the other pair lies on S2S_2. Now consider any one of these pairs, say the pair lying on S1(t)S_1(t). Then points in this pair lie on the same side of ℒ(t)L(t), and they are the farthest robot positions on S1(t)S_1(t). Thus ′(t)P (t) captures extremal or symmetry-critical positions of ℛ(t)R(t). Hence, if ′(t)P (t) lies within a semicircle, then all points of ℛ(t)R(t) must also lie within that semicircle. This contradicts a fundamental property of the SECSEC: no open semicircle of S(t)S(t) can contain all points of ℛ(t)R(t), otherwise a smaller enclosing circle would exist. Step 5: Conclusion. Thus, no arc between consecutive points of ′(t)P (t) exceeds a semicircle. Therefore, ′(t)P (t) is not contained in any open semicircle. By Property 1, ′(t)P (t) uniquely determines S(t)S(t). ∎ Algorithm 1 : MoveToDestination(ri,τ,d)(r_i,τ,d) 1: Robot rir_i, movement type τ∈StepIn,StepAside,StepOutτ∈\ StepIn, StepAside, StepOut\, and reference point d whenever required 2: if τ=StepInτ= StepIn then 3: StepIn(ri,dr_i,d) 4: else if τ=StepAsideτ= StepAside then 5: StepAside(ri,dr_i,d) 6: else if τ=StepOutτ= StepOut then 7: StepOut(rir_i) 8: else 9: remain stationary 10: end if 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_i , let Hi(t)H_i(t) denotes the set of lines joining two robot positions in ℛ(t)\ri(t)R(t) \r_i(t)\. Algorithm 1 summarizes the routine MoveToDestination(), which invokes the appropriate movement procedure according to the movement type assigned to robot rir_i. We describe each of these movements in detail as follows: (A) Step-in movement: This movement places a robot, lying on S(t)S(t), inside the circle. Suppose robot rir_i wants a step-in movement w.r.t. the point p. Note that p=(t)p=O(t) if ℛ(t)R(t) is not quasi-regular, otherwise p=cqp=c_q. Let us first consider the case when the line segment ri(t)p¯ r_i(t)p intersects at least one line from Hi(t)H_i(t) (we exclude lines which coincide with ri(t)p¯ r_i(t)p from Hi(t)H_i(t) while computing the intersection points). Let xix_i be the nearest of such intersection points to ri(t)r_i(t) (see Figure 6(a)). The destination point did_i of rir_i is the middle point of the segment ri(t)xi¯ r_i(t)x_i. If none of the lines in Hi(t)H_i(t) intersects ri(t)p¯ r_i(t)p, then the did_i is the middle point ri(t)p¯ r_i(t)p (in this case also, we exclude lines which coincide with ri(t)p¯ r_i(t)p from Hi(t)H_i(t) while computing the intersection points)(see Figure 6(b)). Robot rir_i moves towards did_i along the line segment ri(t)di¯ r_i(t)d_i. Algorithm 2 summarizes the StepIn procedure. (a) (b) Figure 6: Step-in movement for computing did_i: (a) The line segment ri(t)p¯ r_i(t)p intersects the dotted line in Hi(t)H_i(t), (b) None of the line in Hi(t)H_i(t) intersect ri(t)p¯ r_i(t)p. Algorithm 2 : StepIn(ri,p)(r_i,p) 1: Robot rir_i and reference point p∈(t),cqp∈\O(t),c_q\ 2: Compute Hi(t)H_i(t), the set of lines determined by pairs of positions in ℛ(t)∖ri(t)R(t) \r_i(t)\ 3: Remove from Hi(t)H_i(t) every line coincident with ri(t)p¯ r_i(t)p 4: Xi←x∈ri(t)p¯:x∈h for some h∈Hi(t)X_i← \x∈ r_i(t)p:x∈ h for some h∈ H_i(t) \ 5: if Xi≠∅X_i≠ then 6: Let xi∈Xix_i∈ X_i be nearest to ri(t)r_i(t) 7: di←d_i← midpoint of ri(t)xi¯ r_i(t)x_i 8: else 9: di←d_i← midpoint of ri(t)p¯ r_i(t)p 10: end if 11: move toward did_i along ri(t)di¯ r_i(t)d_i (B) Step-aside movement: We describe the step-aside movement of a robot rir_i w.r.t. a point d. Note that robot rir_i have a step-aside movement in the following two cases: (i) the open line segment (ri(t),di)(r_i(t),d_i) contains at least one robot position, where did_i is the destination point of rir_i and (i) when ℛ(t)R(t) is not free-path quasi-regular and cq=(t)c_q=O(t). Thus, we have d∈pm,(t)d∈\p_m,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. (a) (b) Figure 7: Step-aside movement for computing xix_i when pm=(t)p_m=O(t): (a) Dotted lines in Hi(t)H_i(t) intersect the arc Cij(t)C_ij(t) of circle Cl(t)C_l(t) (with l=3l=3), (b) None of the lines in Hi(t)H_i(t) intersect Cij(t)C_ij(t). First, consider the case when pm=(t)p_m=O(t). This implies that d=(t)d=O(t) for all robots in ℛR. The robots in ℛgR_g need to check pm=(t)p_m=O(t). According to our algorithm, if a robot in ℛfR_f has a step-aside movement, then its movement is w.r.t. (t)O(t). Thus, the robots in ℛfR_f have step-aside movements as described in this case (the robots in ℛgR_g have different movement strategies when pm≠(t)p_m (t) to guarantee finite time reachability of the robots in ℛgR_g to pmp_m). Let robot rir_i lie on the circle Cl(t)C_l(t). The destination point xix_i of rir_i lies on ClC_l and it is computed as follows (see Figure 7): let Bi(t)B_i(t) be the set of robot positions in ℛ(t)R(t) which do not lie on ri(t)(t)¯ r_i(t)O(t). Let rj(t)(t)¯ r_j(t)O(t) and rk(t)(t)¯ r_k(t)O(t) be the clockwise and counterclockwise neighbors of ri(t)(t)¯ r_i(t)O(t). Consider the angle θi(t)=max∠ri(t)drj(t),∠ri(t)drk(t) _i(t)=max\ r_i(t)dr_j(t), r_i(t)dr_k(t)\ (tie, if any, broken arbitrarily). Without loss of generality suppose, θi(t)=∠ri(t)drj(t) _i(t)= r_i(t)dr_j(t). Let c be the intersection point between Cl(t)C_l(t) and radj(t)rad_j(t). Let Wi(t)W_i(t) be the wedge defined by the angle θi(t) _i(t) and Cij(t)C_ij(t) be the arc of Cl(t)C_l(t) which lies in the wedge Wi(t)W_i(t). If at least one line in Hi(t)H_i(t) intersects Cl(t)C_l(t), then let qiq_i be the nearest to ri(t)r_i(t) among all such intersection points. In this case, xix_i is the intersection point between Cij(t)C_ij(t) and the bisector of the segment ri(t)qi¯ r_i(t)q_i (see Figure 7(a)). If none of the lines in Hi(t)H_i(t) intersects Cij(t)C_ij(t) (see Figure 7(b)), then we define xix_i to be a point lying on Cij(t)C_ij(t) such that ∠ri(t)dxi=13niθi(t) r_i(t)dx_i= 13n_i _i(t), where nin_i is the number of distinct robot positions on the line segment ri(t)d¯ r_i(t)d. (a) (b) Figure 8: Step-aside movement for computing xix_i when pm≠(t)p_m (t): (a) Dotted lines in Hi(t)H_i(t) intersect the circle Ck∗C^*_k, (b) None of the lines in Hi(t)H_i(t) intersect Ck∗C^*_k. Note that since we are computing the step-aside movements w.r.t. (t)O(t), we have θi(t)>0 _i(t)>0. Now consider the case when pm≠(t)p_m (t) (see Figure 8). According to the strategy described here, only the robots in ℛgR_g have step-aside movements. Let ℒiL_i be the line passing through ri(t)r_i(t) and pmp_m. Line ℒiL_i divides the whole plane into two open halves. We define a half plane VoV_o delimited by ℒiL_i as follows: VoV_o be the half plane delimited by ℒiL_i which contains (t)O(t) if ℒiL_i does not pass through (t)O(t), otherwise VoV_o is chosen as any one of the two half planes delimited by ℒiL_i. Let D∗(t)=∥p−pm∥:p∈ℛ(t),p≠pm,D^*(t)= \\|p-p_m\|:p (t),\;p≠ p_m \, and let 0<ρ1∗(t)<ρ2∗(t)<⋯<ρq∗(t)0<ρ^*_1(t)<ρ^*_2(t)<·s<ρ^*_q(t) be the distinct values in D∗(t)D^*(t). For each k∈1,…,qk∈\1,…,q\, let Ck∗(t)C_k^*(t) denote the circle centered at pmp_m with radius ρk∗(t) _k^*(t). The destination point xix_i of rir_i lies on Ck∗C^*_k and it is computed as follows: we define a point ziz_i on Ck∗C^*_k as follows: if at least one line in Hi(t)H_i(t) (excluding the lines coincide with ℒiL_i) intersects Ck∗C^*_k. This intersection point lies in VoV_o, then ziz_i is the nearest of such intersection points to ri(t)r_i(t) (see Figure 8(a)). Otherwise ziz_i is a point on Ck∗∩VoC^*_k∩ V_o such that ∠zipmri(t)=15∘ z_ip_mr_i(t)=15 (other suitable point may also work)(see Figure 8(b)). Then xix_i is the intersection point between the Ck∗C^*_k and the bisector of the angle ∠ri(t)pmzi r_i(t)p_mz_i. Algorithm 3 summarizes the StepAside procedure. (a) (b) (c) Figure 9: Step-out movement for computing ui(t)u_i(t) and xix_i: (a) The line segment ri(t)ui(t)¯ r_i(t)u_i(t) contains no other robot when ri(t)≠(t)r_i(t) (t), (b) the segment ri(t)ui(t)¯ r_i(t)u_i(t) contains multiple robots with ri(t)≠(t)r_i(t) (t), and (c) the case when ri(t)=(t)r_i(t)=O(t). Algorithm 3 : StepAside(ri,d)(r_i,d) 1: Robot rir_i and reference point d∈(t),pmd∈\O(t),p_m\ 2: if pm=(t)p_m=O(t) then 3: d←(t)d (t) 4: Let Cl(t)C_l(t) be the radial circle containing ri(t)r_i(t) 5: Determine the clockwise and counterclockwise neighboring radial lines of radi(t)rad_i(t), containing positions rj(t)r_j(t) and rk(t)r_k(t), respectively 6: θi(t)←max∠ri(t)drj(t),∠ri(t)drk(t) _i(t)← \ r_i(t)dr_j(t), r_i(t)dr_k(t)\ 7: Let rj(t)r_j(t) denote a neighbor attaining the maximum 8: Let Wi(t)W_i(t) be the corresponding wedge 9: Let Cij(t)C_ij(t) be the arc of Cl(t)C_l(t) contained in Wi(t)W_i(t) 10: Compute all intersections of the lines in Hi(t)H_i(t) with Cij(t)C_ij(t) 11: if at least one such intersection exists then 12: Let qiq_i be the intersection nearest to ri(t)r_i(t) 13: Let xix_i be the intersection of Cij(t)C_ij(t) with the perpendicular bisector of ri(t)qi¯ r_i(t)q_i 14: else 15: Let nin_i be the number of distinct occupied positions on ri(t)d¯ r_i(t)d 16: Choose xi∈Cij(t)x_i∈ C_ij(t) such that ∠ri(t)dxi=θi(t)3ni r_i(t)dx_i= _i(t)3n_i 17: end if 18: else⊳ pm≠(t)p_m (t) 19: d←pmd← p_m 20: Let ℒiL_i be the line through ri(t)r_i(t) and pmp_m 21: if (t)∉ℒiO(t) _i then 22: Let VoV_o be the open half-plane bounded by ℒiL_i that contains (t)O(t) 23: else 24: Choose one admissible open half-plane VoV_o bounded by ℒiL_i 25: end if 26: Let Ck∗(t)C_k^*(t) be the radial circle centered at pmp_m containing ri(t)r_i(t) 27: Zi←z∈Ck∗(t)∩Vo:z∈h,h∈Hi(t),h≠ℒiZ_i← \z∈ C_k^*(t)∩ V_o:z∈ h,\;h∈ H_i(t),\;h _i \ 28: if Zi≠∅Z_i≠ then 29: Let zi∈Ziz_i∈ Z_i be nearest to ri(t)r_i(t) 30: else 31: Choose zi∈Ck∗(t)∩Voz_i∈ C_k^*(t)∩ V_o such that ∠zipmri(t)=15∘ z_ip_mr_i(t)=15 32: end if 33: Let xix_i be the intersection of Ck∗(t)C_k^*(t) with the internal angle bisector of ∠ri(t)pmzi r_i(t)p_mz_i 34: end if 35: move toward xix_i (C) Step-out movement: This movement is taken by robots in ℛfR_f during the formation phase. Consider a robot ri∈ℛfr_i _f having position in Sin(t)S_in(t). Step-out movements place robot rir_i at a point on the circle (t)S(t). First consider the case when ri(t)≠(t)r_i(t) (t) (see Figure 9(A-B)). Let radi(t)rad_i(t) intersect S(t)S(t) at ui(t)u_i(t) and ri(t)r_i(t) lies on Ck(t)C_k(t) for some k. If the line segment ri(t)ui(t)¯ r_i(t)u_i(t) does not contain any other robot position, then robot rir_i moves towards ui(t)u_i(t) along the line segment ri(t)ui(t)¯ r_i(t)u_i(t) (see Figure 9(a)). Otherwise, robot rir_i computes its destination point xi(t)x_i(t) on Ck+1(t)C_k+1(t) as follows (see Figure 9(b)). Let Ai(t)A_i(t) be the set of robot positions not lying on radi(t)rad_i(t). Let rj(t),rk(t)∈Ai(t)r_j(t),r_k(t)∈ A_i(t) be such that radj(t)rad_j(t) and radk(t)rad_k(t) are the two clockwise and counterclockwise neighbors of radi(t)rad_i(t). Let βi(t)=max∠ri(t)(t)rj(t),∠ri(t)(t)rk(t) _i(t)=max\ r_i(t)O(t)r_j(t), r_i(t)O(t)r_k(t)\ (tie, if any, broken arbitrarily). Without loss of generality, suppose βi(t)=∠ri(t)(t)rj(t) _i(t)= r_i(t)O(t)r_j(t). Since S(t)S(t) contains at least two robot positions on its boundary, βi(t)≠0 _i(t)≠ 0. Let ViV_i be the wedge defined by the angle βi(t) _i(t). We define xix_i to be a point lying on Vi(t)∩Ck+1(t)V_i(t)∩ C_k+1(t) such that ∠ri(t)(t)xi(t)=13miβi(t) r_i(t)O(t)x_i(t)= 13m_i _i(t), mim_i is the number of distinct robot positions on the line segment ri(t)ui(t)r_i(t)u_i(t). Now, consider the case when ri(t)=(t)r_i(t)=O(t) (see Figure 9(c)). Let rj(t)r_j(t) and rl(t)r_l(t) be two robot positions not lying at (t)O(t) such that radj(t)rad_j(t) and radl(t)rad_l(t) are neighbors and ∠rj(t)(t)rl(t) r_j(t)O(t)r_l(t) is maximum for all such consecutive radial lines (tie, if any, broken arbitrarily). Let ℒ0L_0 be the bisector of ∠rj(t)(t)rl(t) r_j(t)O(t)r_l(t). Then xi(t)x_i(t) is the intersection point between S(t)S(t) at ℒ0L_0. Algorithm 4 summarizes the StepOut procedure, which determines an outward destination for a robot in ℛfR_f during the formation phase. Table 1 summarizes the movement rules followed by the robots in ℛgR_g and ℛfR_f for the different configuration classes during the multiplicity-creation phase. Algorithm 4 : StepOut(ri)(r_i) 1: Robot ri∈ℛfr_i _f 2: if ri(t)≠(t)r_i(t) (t) then 3: Let ui(t)=radi(t)∩S(t)u_i(t)=rad_i(t)∩ S(t) 4: if (ri(t),ui(t))(r_i(t),u_i(t)) contains no occupied position then 5: move toward ui(t)u_i(t) along ri(t)ui(t)¯ r_i(t)u_i(t) 6: return 7: end if 8: Let Ck(t)C_k(t) be the radial circle containing ri(t)r_i(t) 9: Determine the clockwise and counterclockwise neighboring radial lines of radi(t)rad_i(t), containing positions rj(t)r_j(t) and rℓ(t)r_ (t), respectively 10: βi(t)←max∠ri(t)(t)rj(t),∠ri(t)(t)rℓ(t) _i(t)← \ r_i(t)O(t)r_j(t), r_i(t)O(t)r_ (t)\ 11: Let Vi(t)V_i(t) be the wedge corresponding to a neighbor attaining βi(t) _i(t) 12: Let mim_i be the number of distinct occupied positions on ri(t)ui(t)¯ r_i(t)u_i(t) 13: Choose xi(t)∈Vi(t)∩Ck+1(t)x_i(t)∈ V_i(t)∩ C_k+1(t) such that ∠ri(t)(t)xi(t)=βi(t)3mi r_i(t)O(t)x_i(t)= _i(t)3m_i 14: move toward xi(t)x_i(t) 15: else⊳ ri(t)=(t)r_i(t)=O(t) 16: Find two consecutive radial lines radj(t)rad_j(t) and radℓ(t)rad_ (t) whose enclosed angle is maximum 17: Let ℒ0+L_0^+ be the ray from (t)O(t) bisecting this maximum angular sector 18: xi(t)←ℒ0+∩S(t)x_i(t) _0^+∩ S(t) 19: move toward xi(t)x_i(t) 20: end if Table 1: Summary of movement rules during the multiplicity-creation phase. Configuration class Sub-case ℛgR_g robots ℛfR_f robots enseDense free-path Q-regular direct →cq→ c_q stationary enseDense Q-regular, not free-path direct/step-aside →(t) (t) stationary enseDense not quasi-regulara direct/step-aside →(t) (t) stationary on−DenseNon-Dense free-path Q-regular direct →cq→ c_q stationary on−DenseNon-Dense Q-regular, cq≠(t)c_q (t) stationary (non-pivotal step-in) stationary (non-pivotal step-in) on−DenseNon-Dense Q-regular, cq=(t)c_q=O(t) step-aside w.r.t. (t)O(t) if blocked step-aside w.r.t. (t)O(t) if blocked on−DenseNon-Dense not quasi-regular step-in w.r.t. (t)O(t) (non-pivotal) step-in w.r.t. (t)O(t) (non-pivotal) a Does not occur for linear configurations when n≥8n≥ 8; see Observation 1. 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)S_in(t) and the symmetry of ℛ(t)R(t). Algorithm 6 summarizes the MultiplicityCreation 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 ℛ(t)∈R(t)∈ Dense be a linear configuration, i.e., all robot positions lie on a common line ℒ(t)L(t), and let n=|ℛ(t)|≥8n=|R(t)|≥ 8. Then ℛ(t)R(t) is quasi-regular with a unique centre of quasi-regularity cqc_q, and ℛ(t)R(t) is not free-path quasi-regular. Algorithm 5 : PatternFormation(ri)(r_i) 1: if ri∈ℛgr_i _g and a multiplicity point pmp_m exists then 2: Gathering(ri,pmr_i,p_m) 3: return 4: end if 5: if ri∈ℛfr_i _f and |ℛ(t)|≤Nf+1|R(t)|≤ N_f+1 then 6: Formation(rir_i) 7: return 8: end if 9: if ri∈ℛfr_i _f and ri(t)r_i(t) is a multiplicity point then 10: remain stationary 11: return 12: end if 13: MultiplicityCreation(rir_i) Algorithm 6 : MultiplicityCreation(ri)(r_i) 1: By default, rir_i remains stationary. 2: if ℛ(t)∈R(t)∈enseDense then 3: if ℛ(t)R(t) is free-path quasi-regular then 4: if ri∈ℛgr_i _g and ri(t)∈Sin(t)r_i(t)∈ S_in(t) then 5: move directly toward cqc_q 6: end if 7: else if ri∈ℛgr_i _g and ri(t)∈Sin(t)r_i(t)∈ S_in(t) then 8: if (ri(t),(t))(r_i(t),O(t)) contains no robot position then 9: move directly toward (t)O(t) 10: else 11: StepAside(ri,(t)r_i,O(t)) 12: end if 13: end if 14: else if ℛ(t)∈R(t)∈on−DenseNon-Dense then 15: if ℛ(t)R(t) is free-path quasi-regular then 16: if ri∈ℛgr_i _g then 17: move directly toward cqc_q 18: end if 19: else if ℛ(t)R(t) is quasi-regular then 20: if cq≠(t)c_q (t) then 21: Compute the pivotal set ′(t)P (t) 22: if ri(t)∈Sout(t)r_i(t)∈ S_out(t) and ri(t)∉′(t)r_i(t) (t) then 23: StepIn(ri,cqr_i,c_q) 24: end if 25: else 26: Let xi=radi(t)∩S(t)x_i=rad_i(t)∩ S(t) 27: if ri(t)∈Sin(t)r_i(t)∈ S_in(t) and (xix_i is occupied or (ri(t),(t))(r_i(t),O(t)) contains a robot position) then 28: StepAside(ri,(t)r_i,O(t)) 29: end if 30: end if 31: else 32: Compute the pivotal set ′(t)P (t) 33: if ri(t)∈Sout(t)r_i(t)∈ S_out(t) and ri(t)∉′(t)r_i(t) (t) then 34: StepIn(ri,(t)r_i,O(t)) 35: end if 36: end if 37: end if Proof. Since the robot positions in ℛ(t)R(t) are collinear, they admit a total order along ℒ(t)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∈ℒ(t)c (t) be the unique balanced split point of ℛ(t)R(t) along ℒ(t)L(t): if n is even, c is the midpoint of the two median consecutive positions r(n/2),r(n/2+1)r_(n/2),r_(n/2+1); if n is odd, c is the median robot position r(⌈n/2⌉)r_( n/2 ) itself. In either case, taking ℬ(t)=ℛ(t)B(t)=R(t) (even case) or ℬ(t)=ℛ(t)∖cB(t)=R(t) \c\ (odd case), exactly ⌊n/2⌋ n/2 positions of ℬ(t)B(t) lie on each side of c along ℒ(t)L(t), all robots on a given side sharing one ray from c. Hence SA(ℬ(t),c)=X2,X=(0,…,0⏟⌊n/2⌋−1,π),SA(B(t),c)=X^2, X= ( 0,…,0_ n/2 -1,π ), so ℛ(t)R(t) is quasi-regular with centre cq=c_q=c. Uniqueness of cqc_q. Any other point c′∈ℒ(t)c (t), c′≠cqc ≠ c_q, changes the count of robot positions on at least one side of the split (since all positions are distinct and cqc_q is the unique balanced split point), so c′c cannot yield SA(⋅,c′)=X2SA(·,c )=X^2. Hence cqc_q is unique, and every robot can identify it consistently despite full disorientation. Failure of the free-path property. Since cq∈ℒ(t)c_q (t), every qradi(t)qrad_i(t) is a sub-ray of ℒ(t)L(t) itself, so all positions in ℛ(t)∖cqR(t) \c_q\ lie on exactly two rays from cqc_q, each containing ⌈(n−1)/2⌉≥⌈7/2⌉=4 (n-1)/2 ≥ 7/2 =4 robot positions (using n≥8n≥ 8). Hence for the farthest position ri(t)r_i(t) on a ray, every other position on that ray lies on qradi(t)qrad_i(t) strictly between cqc_q and ri(t)r_i(t). By Definition 4, ℛ(t)R(t) is not free-path quasi-regular. ∎ Remark 1. Observation 1 shows that for enseDense configurations with n≥8n≥ 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 (t)O(t) rather than cqc_q, 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)∈ enseDense: Since |ℛg|≥6|R_g|≥ 6 and |Sout(t)|≤4|S_out(t)|≤ 4, there are at least two robot positions from ℛg(t)R_g(t) which lies in Sin(t)S_in(t). Two robots are sufficient to create a multiplicity point and thus, the robots having positions in Sin(t)S_in(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) ℛ(t)R(t) is free-path quasi-regular: Since robots in ℛfR_f do not have global multiplicity detection capability, they can recognize ℛ(t)R(t) quasi-regular configurations until at least two robots reach cqc_q, the centre of the quasi-regularity. Once two robots reach cqc_q, a multiplicity point is created at cqc_q. Since robots have free paths towards cqc_q, 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)∩ℛg(t)r_i(t)∈ S_in(t) _g(t), the centre cqc_q is the destination point for rir_i and robot rir_i has a direct movement towards cqc_q. In the rest of the cases, robots do not move. Since robots in ℛfR_f do not move, if the centre cqc_q contains a robot from ℛfR_f, then the multiplicity point contains a robot from ℛfR_f. To make this multiplicity point stable, our approach does not move this robot from ℛfR_f until at least two robots from ℛgR_g reach cqc_q (this case is handled during the formation phase using the local weak multiplicity detection capability of robots in ℛfR_f). (1.b) ℛ(t)R(t) is quasi-regular but not free-path quasi-regular or ℛ(t)R(t) is not quasi-regular: We maintain S(t)S(t), until a multiplicity point is created. Our approach does not move the robots lying on S(t)S(t). Otherwise, if ri(t)∈Sin(t)∩ℛg(t)r_i(t)∈ S_in(t) _g(t), then (t)O(t) is the destination point of rir_i. In the rest of the cases, robots do not move. A robot has either a direct movement or step-aside movement w.r.t. (t)O(t) depending on its position. Case 2 ()∈ R(t)∈ on−DenseNon-Dense: In this case, ℛ(t)R(t) can not be linear. The movement of a robot rir_i depends on the symmetry of ℛ(t)R(t) as follows: (2.a) ℛ(t) R(t) is free-path quasi-regular: Our approach maintains the quasi-regularity until at least two robots reach cqc_q. A robot ri∈ℛgr_i _g moves towards cqc_q following a direct movement. If a robot belongs to ℛfR_f, it does not move. In this case, robots have only direct movements with respect to cqc_q. (2.b) ℛ(t) 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 enseDense or to create free paths to (t)O(t) for robots. The approach depends on the positions of (t)O(t) and cqc_q. First, consider the case when cq≠(t)c_q (t). Robot rir_i computes ′(t)P (t), that is, the set of pivotal robots. If ri(t)∈Sout(t)r_i(t)∈ S_out(t) and ri(t)∉′(t)r_i(t) (t), robot rir_i computes a destination point on ri(t)cq¯ r_i(t)c_q according to the step-in movement and moves towards this point. Otherwise, it does not move. Now suppose cq=(t)c_q=O(t). Consider a robot rir_i such that ri(t)∈Sin(t)r_i(t)∈ S_in(t). Let radi(t)rad_i(t) intersect S(t)S(t) at the point xix_i. If xix_i contains a robot position or the open line segment (ri(t),(t))(r_i(t),O(t)) contains at least one robot position, then robot rir_i takes a step-aside movement w.r.t. (t)O(t) (robot rir_i moves out of the line segment ri(t)(t)¯ r_i(t)O(t)). In the rest of the cases, robot rir_i does not move. (2.c) ℛ(t) R(t) is not quasi-regular: In this case, we try to convert the current configuration into a configuration in enseDense and in order to do so, we maintain S(t)S(t). If ri(t)∈Sout(t)r_i(t)∈ S_out(t) and ri(t)∉′(t)r_i(t) (t), then robot rir_i has a step-in movement w.r.t. (t)O(t) (robot rir_i moves to a point on ri(t)(t)¯ r_i(t)O(t)). Otherwise, it does not move. Algorithm 7 : Gathering(ri,pm)(r_i,p_m) 1: Robot ri∈ℛgr_i _g and stable multiplicity point pmp_m 2: if ri(t)=pmr_i(t)=p_m then 3: remain stationary 4: return 5: end if 6: if (ri(t),pm)(r_i(t),p_m) contains no robot position then 7: move directly toward pmp_m 8: return 9: end if 10: if ℛ(t)∈R(t)∈on−DenseNon-Dense and ℛ(t)R(t) is quasi-regular but not free-path quasi-regular and cq=(t)c_q=O(t) then 11: remain stationary 12: else 13: StepAside(ri,pmr_i,p_m) 14: end if (B) The gathering phase: Robots in ℛgR_g executes this phase when a multiplicity point pmp_m is created. However, not all robots in ℛfR_f can detect the execution of this phase. If a robot in ℛfR_f lies at the multiplicity point pmp_m, it does not move (robots in ℛfR_f have local weak multiplicity capability). Otherwise, the robots in ℛfR_f continue acting in the same way as they do during the multiplicity creation phase. Now, consider a robot ri∈ℛgr_i _g. If robot ri(t)=pmr_i(t)=p_m, then robot rir_i does not move. Otherwise, robot rir_i moves towards the multiplicity point pmp_m in the following way: (B.1) If the line segment (ri(t),pm)(r_i(t),p_m) does not contain any other robot position, then robot rir_i has a direct movement towards pmp_m. (B.2) Otherwise, the line segment (ri(t),pm)(r_i(t),p_m) contains at least one robot position. If ℛ(t)∈R(t)∈on−DenseNon-Dense and ℛ(t)R(t) is quasi regular but not free-path quasi regular with cq=(t)c_q=O(t), then rir_i does not move. Otherwise, robot rir_i has a step-aside movement w.r.t. pmp_m. Algorithm 7 summarizes the Gathering procedure, which directs a robot in ℛgR_g toward the stable multiplicity point pmp_m 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 ℛfR_f when the total number of distinct robot positions in the system is at most Nf+1N_f+1, i.e., |ℛ(t)|≤Nf+1|R(t)|≤ N_f+1. Since the multiplicity point pmp_m may contain a robot from ℛfR_f, a robot from ℛgR_g may not lie at pmp_m. Since the robots in ℛgR_g do not know the size of ℛgR_g, they can not determine the start of this phase. Thus, exactly one robot in ℛgR_g may execute the gathering phase while the robots in ℛfR_f 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 ℛfR_f. Note that there is a special case in which we can not avoid a collision between a robot from ℛgR_g and a robot from ℛfR_f. However, this multiplicity point is unstable (once the robot from ℛfR_f moves, this multiplicity is broken). Robots in ℛfR_f move in some order. Algorithm 8 : Formation(ri)(r_i) 1: Robot ri∈ℛfr_i _f and |ℛ(t)|≤Nf+1|R(t)|≤ N_f+1 2: if ri(t)r_i(t) is a multiplicity point then 3: if ri(t)∉∂S(t)r_i(t)∉∂ S(t) then 4: StepOut(ri,S(t)r_i,S(t)) 5: else 6: Let yiy_i be the midpoint of ri(t)(t)¯ r_i(t)O(t) 7: move toward yiy_i 8: end if 9: return 10: end if 11: Let Ck(t)=S(t)C_k(t)=S(t) 12: if ri(t)∈S(t)r_i(t)∈ S(t) then 13: remain stationary 14: else if ri(t)∈Ck−1(t)r_i(t)∈ C_k-1(t) then 15: Let xi=radi(t)∩S(t)x_i=rad_i(t)∩ S(t) 16: if xix_i is not occupied then 17: move directly toward xix_i 18: else 19: StepOut(ri,S(t)r_i,S(t)) 20: end if 21: else if ri(t)∈Ck−2(t)r_i(t)∈ C_k-2(t) and Ck−1(t)C_k-1(t) contains exactly one occupied position then 22: StepOut(ri,Ck−1(t)r_i,C_k-1(t)) 23: else 24: remain stationary 25: end if First, consider the case when a robot ri∈ℛfr_i _f does not lie at a multiplicity point. Let Ck=S(t)C_k=S(t) for some k. Robot rir_i moves according to one of the following ways: (C.1) If robot rir_i lies on S(t)S(t), it does not move. (C.2) Suppose rir_i lies on Ck−1(t)C_k-1(t). If xix_i, the intersection point between S(t)S(t) and radi(t)rad_i(t), does not contain any robot position, then rir_i has a direct movement towards xix_i. Otherwise, robot rir_i moves according to the step-out movement w.r.t. S(t)S(t). (C.3) Suppose robot rir_i lies on Ck−2(t)C_k-2(t) and Ck−1(t)C_k-1(t) contains exactly one robot position. In this case, robot rir_i moves towards the circle Ck−1(t)C_k-1(t) by a step-out movement w.r.t. the circle Ck−1(t)C_k-1(t). (C.4) In the rest of the cases, robot rir_i does not move. Next, consider the case when robot rir_i lies at a multiplicity point. In this case, robot rir_i moves even if it lies on S(t)S(t) (the multiplicity point may lie on S(t)S(t)). Robot rir_i moves according to the step-out movement w.r.t. S(t)S(t), if it does not lie on the boundary of S(t)S(t). Otherwise, robot rir_i first moves towards the middle point of the line segment, ri(t)t¯ r_i(t)O_t and then it moves according to the step-out movement w.r.t. S(t)S(t). The formation rules for robots in ℛfR_f 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∈Rr_i,r_j∈ 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 ℛ(t)∈ R(t)∈ enseDense: In this case, (t)O(t) is the destination point for all the robots in ℛgR_g and the robots in ℛfR_f do not move. Robots have two types of movements: the direct movement and these movements are w.r.t. (t)O(t) only. Consider radi(t)rad_i(t) and radj(t)rad_j(t). First suppose that radi(t)rad_i(t) and radj(t)rad_j(t) coincide. Let rir_i and rjr_j lie on the circles Ck(t)C_k(t) and Cl(t)C_l(t) respectively. Without loss of generality, suppose l<kl<k. In this case, at most one of rir_i and rjr_j can have direct movement. Now, in round t, consider all possible combinations of movements of robots rir_i and rjr_j. In all of them, the paths of movement of these two robots are completely separated by the circle Cl(t)C_l(t). Thus, robots rir_i and rjr_j do not collide. Next suppose that radi(t)rad_i(t) and radj(t)rad_j(t) are distinct. Let ℒ∗L^* be the bisector of the angle ∠ri(t)(t)rj(t) r_i(t)O(t)r_j(t). In this case, all possible paths of the two robots are separated by the bisector ℒ∗L^*. Case 2 ℛ(t)∈ R(t)∈ on−DenseNon-Dense: The movements of robots rir_i and rjr_j depend on the symmetry of ℛ(t)R(t) as follows: Case 2.1 ℛ(t)R(t) is free-path quasi regular: In this case, robots in ℛgR_g have direct movements and the robots in ℛfR_f do not move. If robots rir_i and rjr_j move, they move along radi(t)rad_i(t) and radj(t)rad_j(t) respectively. These two paths meet at cqc_q, the robot’s destination point. Thus, robots do not collide during movements. Case 2.2 ℛ(t)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)rad_i(t) and radj(t)rad_j(t) are coincident, then the paths of rir_i and rjr_j are separated by Cl(t)C_l(t). Otherwise, the paths are separated by ℒ∗L^*. Case 2.3 ℛ(t)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)rad_i(t) and radj(t)rad_j(t) coincide, then at most one of them moves. Without loss of generality, suppose rir_i moves. Robot rir_i moves to a point on radi(t)rad_i(t), and this point is at most as far away as the middle point of ri(t)rj(t)¯ r_i(t)r_j(t) from rj(t)r_j(t). Thus, these two robots do not collide in this case. Next, consider the case when both robots move. In this case, radi(t)rad_i(t) and radj(t)rad_j(t) are different, and the paths of these two robots are separated by the bisector ℒ∗L^* of the angle ∠ri(t)(t)rj(t) r_i(t)O(t)r_j(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)∈ enseDense: In this case, only the robots having position in ℛg(t)∩Sin(t)R_g(t)∩ S_in(t) move. The robots lying on S(t)S(t) remain stationary, and hence the smallest enclosing circle S(t)S(t) and O(t) remain invariant. Since |ℛg|≥6|R_g|≥ 6 and out(t)≤4S_out(t)≤ 4, at least two robots from ℛgR_g lie inside S(t)S(t). – ℛ(t)R(t) is free path quasi-regular: In this case robots move straight towards cqc_q. Since robots move in straight lines towards cqc_q, the configuration remains free path quasi-regular until at least two robots reach cqc_q. Thus, at least two robots lie at cqc_q within a finite time. Thus, at least two robots from ℛgR_g reach cqc_q within finite time and create a stable multiplicity point at cqc_q. Since the robots in ℛgR_g have global weak multiplicity detection capability, every robot in ℛgR_g can identify cqc_q as the multiplicity point and subsequently execute the gathering phase. This implies the lemma in this case. – ℛ(t)R(t) is not free path quasi-regular: Robots in ℛg(t)∩Sin(t)R_g(t)∩ S_in(t) move towards (t)O(t). Since S(t)S(t) remains invariant under the movements of these robots, (t)O(t) also remains fixed. Consider a robot ri∈ℛgr_i _g lying inside S(t)S(t). If (ri(t,(t))CLOSE(r_i(t,O(t)) does not contain any robot position, then robot rir_i moves straight towards (t)O(t). Now, let radj(t)rad_j(t) be one of the neighbors of radi(t)rad_i(t) such that rj∈ℛgr_j _g and it has a side-aside movement w.r.t. (t)O(t). Then the paths of movements of rir_i and rjr_j are separated by the bisector of the angle ∠ri(t)(t)rj(t) r_i(t)O(t)r_j(t). Thus, robot rir_i reaches (t)O(t) in finite time by moving along ri(t)(t)¯ r_i(t)O(t). Now suppose (ri(t),(t))(r_i(t),O(t)) has at least one robot position. In this, case, robot rir_i has a step-aside movement w.r.t. (t)O(t). We show that robot rir_i gets a free corridor towards (t)O(t) within finite time. Suppose robot rir_i lies on Ck(t)C_k(t). During the step-aside movement, robot rir_i moves towards a point on the circle Ck(t)C_k(t). The robot on (ri(t),(t))(r_i(t),O(t)), which is closest to (t)O(t), does not move out of the line radi(t)rad_i(t). This implies that for each step-aside movement of robot rir_i, at least one robot is removed from its straight line path to (t)O(t). Since there is a finite number of robots on (ri(t),(t))(r_i(t),O(t)) and by Lemma 2, robots do not collide during this phase, within finite time, robot rir_i gets a robot-free straight path to (t)O(t). Thus, within a finite time, at least two robots reach (t)O(t) and make it a multiplicity point. Lemma 2 guarantees the uniqueness of the multiplicity point. • ()∈ R(t)∈on−DenseNon-Dense: We show that either a multiplicity point is created or the configuration is converted into a one configuration belonging to enseDense. – () R(t) is free-path quasi-regular: In this case only the robots in ℛgR_g move and they move towards cqc_q following direct movements. Due to these movements the current robot configuration ℛ(t)R(t) reaches to a robot configuration ℛ(t∗)R(t^*) having any one of the following properties: (i) at least two robots reach cqc_q and thus ℛ(t∗)R(t^*) contains a multiplicity point or (i) ℛ(t∗)R(t^*) is free-path quasi-regular with ℛ(t∗)∈R(t^*)∈enseDense or (i) ℛ(t∗)R(t^*) is free-path quasi-regular with ℛ(t∗)∈R(t^*)∈ on−DenseNon-Dense. In cases (i) and (i), we are done. Now consider the case (i). Since cqc_q remains invariant under the direct movements of the robots, ℛ(t∗)R(t^*) has cqc_q as its centre of quasi-regularity. This implies that there are some robots in ℛgR_g whose distance from cqc_q is reduced. Thus, the robot configuration satisfies property (i) or (i) within a finite time. This implies the lemma in this case. – () R(t) is quasi-regular but not free-path quasi-regular: First consider the case when cq≠(t)c_q (t). In this case, robots compute ′(t)P (t). The robots lying on S(t)S(t) and not having positions in ′(t)P (t) take step-in movements towards cqc_q. By Lemma 1, the points in the set ′(t)P (t) are sufficient to define S(t)S(t). Since robots move towards cqc_q along straight lines, the configuration remains quasi-regular but not free-path quasi-regular. Thus, within a finite time, configuration ℛ(t)R(t) is converted to a configuration ℛ(t∗)R(t^*) in enseDense. This implies the lemma in this case. Now consider the case when cq=(t)c_q=O(t). In this case, the robots are lying on S(t)S(t) do not move. Thus, S(t)S(t) does not change due to the robots’ movements. The robots, lying inside S(t)S(t) and not having free corridors to (t)O(t), perform step-aside movements. These movements convert ℛ(t)R(t) to a configuration ℛ(t∗)R(t^*) having one of the following properties: (i) ℛ(t∗)R(t^*) is free-path quasi-regular or (i) ℛ(t∗)R(t^*) is not quasi-regular or (i) ℛ(t∗)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 (i) is discussed below. Consider the case (i). If the centre of quasi-regularity of ℛ(t∗)R(t^*) is different from (t)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)S(t) remains the same and robots take the step-aside movements w.r.t. (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 (i). This completes the proof in this case. – (t) R(t) is not quasi regular: In this case, robots compute ′(t)P (t). A robot rir_i moves if ri(t)∈Sout(t)r_i(t)∈ S_out(t) and ri(t)∉P′(t)r_i(t)∉ P (t). By Lemma 1, the robot positions in ′(t)P (t) are sufficient to maintain S(t)S(t). The moving robots only have step-in movements for O(t)O(t). Due to these movements, ℛ(t)R(t) is converted into configuration ℛ(t∗)R(t^*) having any one of the following properties: (i) ℛ(t∗)R(t^*) in enseDense or (i) ℛ(t∗)R(t^*) in on−DenseNon-Dense with |Sin(t∗)|>|Sin(t)||S_in(t^*)|>|S_in(t)|. We are done in case (i). Now for case (i), there are two possibilities: either ℛ(t∗)R(t^*) is quasi-regular or ℛ(t∗)R(t^*) is not quasi-regular. If ℛ(t∗)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 ℛ(t∗)R(t^*) is reached from another quasi- regular configuration ℛ(t)R(t), we have |Sin(t∗)|>|Sin(t)||S_in(t^*)|>|S_in(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 enseDense. 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 ℛgR_g lie at the multiplicity point, then the multiplicity point is stable. Since robots are indistinguishable, the multiplicity point can contain a robot from ℛfR_f. Since the robots’ movements are collision-free during this phase, at most one point from ℛfR_f lies at the multiplicity point. If the multiplicity point contains a robot from ℛfR_f, 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 |ℛ(t)|≤Nf+1.|R(t)|≤ N_f+1. At this time, at most one robot from ℛgR_g can lie outside the multiplicity point. Hence, since |ℛg|≥6|R_g|≥ 6, at least |ℛg|−1≥5|R_g|-1≥ 5 robots from ℛgR_g remain at the multiplicity point. Therefore, the multiplicity point remains stable even after the robot from ℛfR_f 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 robot from ℛfR_f, then MoveToDestination() provides collision-free movements during the gathering and formation phases. Proof. Since the multiplicity point pmp_m does not contain a robot from ℛfR_f, the formation phase cannot start before all the robots in ℛgR_g gather at pmp_m. Indeed, as long as at least one robot from ℛgR_g remains outside pmp_m, the number of distinct occupied positions is greater than Nf+1N_f+1. Hence, the condition |ℛ(t)|=Nf+1|R(t)|=N_f+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 ℛfR_f do not have global weak multiplicity detection capability, they continue acting according to the multiplicity creation phase until |ℛ(t)|=Nf+1|R(t)|=N_f+1. Their movements are limited to step-in and step-aside movements, both with respect to a single point, either (t)O(t) or cqc_q. The robots in ℛgR_g move toward pmp_m by either direct or step-aside movements. Let rir_i and rjr_j be two active robots in round t. • Robots ri,rj∈ℛgr_i,r_j _g: If the line segments ri(t)pm¯ r_i(t)p_m and rj(t)pm¯ r_j(t)p_m are not coincident, then the paths of movements of rir_i and rjr_j are completely separated by the bisector of the angle ∠ri(t)pmrj(t) r_i(t)p_mr_j(t). Next suppose that ri(t)pm¯ r_i(t)p_m and rj(t)pm¯ r_j(t)p_m are coincident. Without loss of generality, suppose that ri(t)r_i(t) lies on (rj(t),pm)(r_j(t),p_m). Let ri(t)r_i(t) lie on Cl∗(t)C_l^*(t) and rj(t)r_j(t) lie on Ck∗(t)C_k^*(t) for some l,kl,k. Let Ckl∗(t)C_kl^*(t) be the circle having centre at pmp_m and lying midway between Cl∗(t)C_l^*(t) and Ck∗(t)C_k^*(t). Then the movement paths of rir_i and rjr_j are completely separated by the circle Ckl∗(t)C_kl^*(t). • Robots ri,rj∈ℛfr_i,r_j _f: Robots rir_i and rjr_j continue to act according to the multiplicity creation phase. Hence, by Lemma 2, their movements are collision-free. • Robots ri,rjr_i,r_j belong to different groups: Without loss of generality, suppose that ri∈ℛgr_i _g and rj∈ℛfr_j _f. If pm=(t)p_m=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≠(t)p_m (t). If rjr_j does not move, then rir_i does not collide with rjr_j. If rjr_j has a step-aside movement during the multiplicity creation phase, then according to the gathering rule, rir_i does not move. Hence, no collision occurs. Finally, if both robots move, then rjr_j has a step-in movement with respect to (t)O(t), while rir_i has either a direct movement or a step-aside movement with respect to pmp_m. If rir_i has a direct movement and the segments ri(t)pm¯ r_i(t)p_m and rj(t)(t)¯ r_j(t)O(t) intersect at a point x, then by construction the destination of rjr_j lies on the open segment (rj(t),x)(r_j(t),x). Hence, the two robots do not collide. If rir_i has a step-aside movement and ri(t)r_i(t) lies on Cl∗(t)C_l^*(t), then its destination lies on Cl∗(t)∩VoC_l^*(t)∩ V_o. If rj(t)(t)¯ r_j(t)O(t) does not intersect Cl∗(t)∩VoC_l^*(t)∩ V_o, 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¯ r_i(t)x. Thus, the gathering phase is collision-free. During the formation phase: Once all robots in ℛgR_g gather at pmp_m, we have |ℛ(t)|=Nf+1|R(t)|=N_f+1, and the robots in ℛfR_f start the formation phase. During this phase only the robots in ℛfR_f move, and they have either direct movement or step-out movement with respect to (t)O(t). Their movements are ordered according to their distance from (t)O(t). Consider two robots ri,rj∈ℛfr_i,r_j _f active in round t. Let radi(t)rad_i(t) and radj(t)rad_j(t) intersect S(t)S(t) at uiu_i and uju_j, respectively. If ui≠uju_i≠ u_j and both uiu_i and uju_j do not contain robot positions, then the paths of the direct movements of rir_i and rjr_j are separated by the bisector of the angle ∠ri(t)(t)rj(t) r_i(t)O(t)r_j(t). If ui≠uju_i≠ u_j and exactly one of them contains a robot position, say uiu_i, then the destination point of rir_i is computed so that it lies on a different side of the bisector of ∠ri(t)(t)rj(t) r_i(t)O(t)r_j(t) from uju_j. Hence, rir_i and rjr_j do not collide. Finally, if ui=uju_i=u_j, then the robots lie on the same radial line. Without loss of generality, suppose that rjr_j lies on Ck−1(t)C_k-1(t) and rir_i lies on Ck−2(t)C_k-2(t). Then the destination point of rir_i lies on Ck−1(t)C_k-1(t), and the movement paths of rir_i and rjr_j are completely separated by Ck−1(t)C_k-1(t). 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 ℛfR_f, then the gathering and formation phases may overlap. In that case, no two robots from ℛfR_f collide during the formation phase. Moreover, if a robot from ℛgR_g collides with a robot from ℛfR_f, the resulting additional multiplicity point is unstable and disappears once the robot from ℛfR_f moves away from it. Proof. Suppose that the multiplicity point pmp_m created during the multiplicity creation phase contains a robot from ℛfR_f. Since the movements during the multiplicity creation phase are collision-free, at most one robot from ℛfR_f can lie at pmp_m. The gathering and formation phases may overlap only in the following situation: exactly one robot from ℛgR_g remains outside pmp_m, while at least one robot from ℛfR_f not lying at pmp_m finds |ℛ(t)|=Nf+1|R(t)|=N_f+1 and starts the formation phase. This is possible because one robot from ℛfR_f already lies at pmp_m and the robots in ℛfR_f have only local weak multiplicity detection capability. Let ri∈ℛgr_i _g be the unique robot not lying at pmp_m, and let rj∈ℛfr_j _f be a robot active in the same round. Robot rir_i has either a direct or a step-aside movement toward pmp_m, whereas rjr_j has a step-out movement toward the boundary of S(t)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 ℛgR_g. Once the robot from ℛfR_f 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 ℛfR_f. Hence, no two robots from ℛfR_f 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 ℛgR_g and a robot from ℛfR_f is only temporary and cannot become stable. This completes the proof. ∎ Lemma 6. The gathering phase gathers all robots in ℛgR_g at the unique stable multiplicity point. Proof. By Lemma 2, the multiplicity point created during the multiplicity creation phase is stable. Let pmp_m denote the multiplicity point created during the multiplicity creation phase. Robots in ℛgR_g can identify the multiplicity point using their global weak multiplicity detection capability. First, consider the case when pmp_m contains no robot from ℛfR_f. The robots in ℛfR_f 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, pmp_m remains as the unique multiplicity point in the system. Consider a robot ri∈ℛgr_i _g. If ri(t)=pmr_i(t)=p_m, robot rir_i does not move. If (ri(t),(t))(r_i(t),O(t)) does not contain any other robot positions, then robot rir_i has direct movement towards (t)O(t). Since robots have collision-free movements, robot rir_i reaches (t)O(t) in finite time. Finally, suppose that (ri(t),(t))(r_i(t),O(t)) contains at least one robot position. We must show that robot rir_i gets a free path to (t)O(t) in finite time. Robot rir_i adopts step-aside movement w.r.t. pmp_m. Now, if rir_i and all the robots on (ri(t),pm)(r_i(t),p_m) move in each round, then rir_i may not get a free path to pmp_m (all these robots may land on a new line passing through pmp_m). To tackle this, we consider the possible scenarios when all the robots on (ri(t),pm)(r_i(t),p_m) move. If (ri(t),pm)(r_i(t),p_m) contains all robots from ℛfR_f and ℛ(t)R(t) is quasi-regular but no free-path quasi regular with cq=(t)c_q=O(t), then the robots on (ri(t),pm)(r_i(t),p_m) perform step-aside movements. According to our algorithm, robot rir_i does not move in this case. Due to movements of the robots on (ri(t),(t))(r_i(t),O(t)), robot rir_i either gets a free path to pmp_m or the characteristic of the current configuration is changed. In the first case, we are done. In the second case, robot rir_i makes a step-aside movement and the robots on (ri(t),pm)(r_i(t),p_m) do not move. Thus, rir_i gets a free path to pmp_m. Now, if (ri(t),(t))(r_i(t),O(t)) also contains robots from ℛgR_g, then each movement of the robots from (ri(t),pm)(r_i(t),p_m) reduces the number of robots on the path of rir_i to pmp_m. Since the number of robots is finite, robot rir_i gets a free direct path to pmp_m within finite time. Now consider the other scenarios when the ℛfR_f robots do not have step-aside movements. The ℛfR_f robots can have step-in movements w.r.t. (t)O(t) or cqc_q depending on the configuration. If robots in ℛfR_f do not move, then the movements of the robots on (ri(t),pm)(r_i(t),p_m) reduce the number of robots on the direct path of rir_i to pmp_m and in finite time rir_i gets a free path to pmp_m. Consider the scenario when robots in ℛfR_f have step-in movements. Only the robots on S(t)S(t) can have step-in movements. We show that robots having step-in movements do not become collinear with rir_i and pmp_m. Let rj∈ℛfr_j _f be a robot which takes a step-in movement during this phase. If ri(t)pm¯ r_i(t)p_m does not intersect rj(t)d¯ r_j(t)d, then we have nothing to prove where d∈(t),cqd∈\O(t),c_q\. Otherwise, let x be the intersection point between ri(t)pm¯ r_i(t)p_m and rj(t)p¯ r_j(t)p. The destination point of rjr_j during its step-in movement lies on (rj(t),x)(r_j(t),x). The destination point of rir_i lies in VoV_o. Thus, the paths of these two robots are separated by the perpendicular line to ri(t)rj(t)¯ r_i(t)r_j(t) passing through the point x. This completes the proof in this case. Consider when a robot from ℛfR_f lies at pmp_m. In this case, the gathering phase overlaps with the formation phase. In the proof of Lemma 4, we have seen that no two robots ℛfR_f collided during the formation phase. However, we have shown that exactly one robot from one ℛgR_g, say rir_i, may collide with a robot from ℛfR_f. This will create a multiplicity point, say p∗p^*. According to the algorithm, robots from ℛgR_g do not move when they find that they lie at a multiplicity point. Since all but one robot from ℛgR_g lies at pmp_m, a stable multiplicity point, no other robot from ℛgR_g moves to p∗p^*. Thus, the multiplicity point p∗p^* is unstable: once the robot from ℛfR_f lying at p∗p^* moves, this multiplicity point is broken. The formation phase starts when ℛ(t)=|Nf|R(t)=|N_f|. Thus, according to the algorithm, the robots from ℛfR_f lying at the multiplicity point move during this phase. This implies that the multiplicity of p∗p^* will be broken in finite time. Once this happens, robot rir_i moves towards pmp_m. Robot rir_i may again collide with some other robot from ℛfR_f; however, its distance from pmp_m is decreased by at least δ in each movement. Thus, within a finite time, it reaches pmp_m. This completes the proof of the lemma. ∎ Lemma 7. The formation phase places all robots in ℛfR_f at distinct positions on the boundary of a common circle. Proof. This phase starts when robots in ℛfR_f find |ℛ(t)|≤Nf+1|R(t)|≤ N_f+1. We prove the lemma by considering the following two cases separately: (i) when pmp_m does not contain a robot from ℛfR_f and (i) when pmp_m contains a robot from ℛfR_f. • pmp_m does not contain a robot from ℛfR_f: In this case, only the robots in ℛfR_f 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)S(t) do not move. The robots from ℛfR_f lying inside or at the multiplicity point move according to step-out movement. Thus, S(t)S(t) remains invariant during this phase. The movements of the robots are ordered: a robot ri∈ℛfr_i _f moves if it lies on Ck−1(t)C_k-1(t) or on Ck−2(t)C_k-2(t), where Ck(t)=S(t)C_k(t)=S(t). Robots lying on Ck−2(t)C_k-2(t) moves to Ck−1(t)C_k-1(t) when there is exactly one robot position on Ck−1(t)C_k-1(t). A robot lying on Ck−1(t)C_k-1(t) moves to S(t)S(t). Suppose rir_i lies on Ck−1(t)C_k-1(t) and x is the intersection point between radi(t)rad_i(t) and S(t)S(t). If x contains no robot position, then rir_i moves straight to x. Otherwise, it computes a point on S(t)S(t) which does not contain any robot position. By Lemma 4, no two robots compute the same destination point on S(t)S(t) (otherwise, a collision could happen). Since S(t)S(t) remains invariant under the robots’ movements, robot rir_i reaches S(t)S(t) within finite time. If rir_i lies on Ck−2(t)C_k-2(t), then by the same approach discuss above, robot rir_i first reaches Ck−1(t)C_k-1(t) and then from there to S(t)S(t). This implies the lemma in this case. • pmp_m contains a robot from ℛfR_f: Let rj∈ℛfr_j _f lie at pmp_m. In this case, the formation phase may start before the end of the gathering phase. It may start before exactly one robot, say rkr_k, reaches pmp_m. Thus, the circle S(t)S(t) may change with the robot’s movement rkr_k. However, the robot rkr_k reaches pmp_m within a finite time. Once rkr_k reaches pmp_m, the smallest enclosing circle of the robot positions 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 ℛ=ℛg∪ℛfR=R_g _f be a set of anonymous, oblivious, fully disoriented robots operating under the SSYNCSSYNC scheduler with non-rigid movements. Suppose that |ℛg|≥6|R_g|≥ 6 and |ℛf|≥2|R_f|≥ 2, and that initially all robots occupy distinct positions. If robots in ℛgR_g have global weak multiplicity detection and robots in ℛfR_f have local weak multiplicity detection together with the knowledge of |ℛf|,|R_f|, then Algorithm PatternFormation() terminates in finite time such that all robots in ℛgR_g gather at one point and all robots in ℛfR_f 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 |ℛg|≥6|R_g|≥ 6 and the knowledge of |ℛf||R_f|. 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] C. Agathangelou, C. Georgiou, and M. Mavronicolas (2013) A distributed algorithm for gathering many fat mobile robots in the plane. In Proc. ACM Symposium on Principles of Distributed Computing (PODC), p. 250–259. External Links: ISBN 978-1-4503-2065-8, Link, Document Cited by: §2. [2] N. Agmon and D. Peleg (2006) Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM Journal on Computing 36 (1), p. pages 56–82. Cited by: §2. [3] S. Bhagat and K. Mukhopadhyaya (2017) Fault-tolerant gathering of semi-synchronous robots. In Proc. the 18th International Conference on Distributed Computing and Networking (ICDCN-2017), p. 6. Cited by: §2, §3.2. [4] S. Bhagat, S. G. Chaudhuri, and K. Mukhopadhyaya. (2016) Fault-tolerant gathering of asynchronous oblivious mobile robots under one-axis agreement. J. Discrete Algorithms 36, p. pages 50–62. External Links: ISSN 1570-8667, Link, Document Cited by: §2. [5] S. Bhagat, B. Das, A. Chakraborty, and K. Mukhopadhyaya (2021) k-Circle formation and k-epf by asynchronous robots. Algorithms 14 (2), p. 62. External Links: Document Cited by: §2. [6] S. Bhagat, P. Flocchini, K. Mukhopadyaya, and N. Santoro (2020) Weak robots performing conflicting tasks without knowing who is in their team. In Proceedings of the 21st International Conference on Distributed Computing and Networking, p. 1–6. Cited by: §2, §4.1, §4, §6, Abstract. [7] S. Bhagat and K. Mukhopadhyaya (2018) Optimum circle formation by autonomous robots. In Advanced Computing and Systems for Security: Volume Five, p. 153–165. Cited by: §2. [8] Z. Bouzid, S. Das, and S. Tixeuil (2012) Wait-free gathering of mobile robots. CoRR abs/1207.0226. External Links: Link Cited by: §3.2. [9] Z. Bouzid, S. Das, and S. Tixeuil (2013) Gathering of mobile robots tolerating multiple crash faults. In Proc. IEEE 33rd International Conference on Distributed Computing Systems, p. 337–346. Cited by: §2. [10] S. G. Chaudhuri and K. Mukhopadhyaya (2015) Leader election and gathering for asynchronous fat robots without common chirality. Journal of Discrete Algorithms 33, p. 171–192. Cited by: 1st item. [11] M. Cieliebak, P. Flocchini, G. Prencipe, and N. Santoro (2012) Distributed computing by mobile robots: gathering. SIAM Journal on Computing 41 (4), p. pages 829–879. External Links: Document, Link, http://epubs.siam.org/doi/pdf/10.1137/100796534 Cited by: §2. [12] J. Czyzowicz, L. Gasieniec, and A. Pelc. (2009) Gathering few fat mobile robots in the plane. Theoretical Computer Science 410 (6), p. pages 481–499. Cited by: §2. [13] B. Das, A. Chakraborty, S. Bhagat, and K. Mukhopadhyaya (2022) k-Circle formation by disoriented asynchronous robots. Theoretical Computer Science 916, p. 40–61. External Links: Document Cited by: §2. [14] B. Das and K. Mukhopadhyaya (2025) Uniform k-circle formation by asynchronous fat robots. The Computer Journal 68 (11), p. 1641–1656. External Links: Document Cited by: §2. [15] C. Feletti, C. Mereghetti, and B. Palano (2023) Uniform circle formation for fully, semi-, and asynchronous opaque robots with lights. Applied Sciences 13 (13). External Links: Document Cited by: §2. [16] C. Feletti, C. Mereghetti, and B. Palano (2024) O(logn)O( n)-Time uniform circle formation for asynchronous opaque luminous robots. In 27th International Conference on Principles of Distributed Systems (OPODIS 2023), LIPIcs, Vol. 286, p. 5:1–5:21. External Links: Document Cited by: §2. [17] C. Feletti, D. Pattanayak, and G. Sharma (2024) Brief announcement: optimal uniform circle formation by asynchronous luminous robots. In 38th International Symposium on Distributed Computing (DISC 2024), External Links: Document Cited by: §2. [18] P. Flocchini, G. Prencipe, N. Santoro, and G. Viglietta (2014) Distributed computing by mobile robots: solving the uniform circle formation problem. In The 18th International Conference on Principles of Distributed Systems (OPODIS 2014), p. 217–232. Cited by: §2. [19] P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer (2005) Gathering of asynchronous robots with limited visibility. Theoretical Computer Science 337 (1-3), p. 147 – 168. Note: External Links: ISSN 0304-3975, Document, Link Cited by: §2. [20] P. Flocchini, G. Prencipe, and N. Santoro (2012) Distributed computing by oblivious mobile robots. Synthesis Lectures on Distributed Computing Theory, Morgan & Claypool Publishers. Cited by: §1, §2, §2. [21] M. Mamino and G. Viglietta (2016) Square formation by asynchronous oblivious robots. In In Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG), p. 1–6. Cited by: §2. [22] D. Pattanayak, K. Mondal, H. Ramesh, and P. S. Mandal (2019) Gathering of mobile robots with weak multiplicity detection in presence of crash-faults. Journal of Parallel Distributed Computing 123, p. 145–155. Cited by: §2. [23] G. Prencipe. (2007) Impossibility of gathering by a set of autonomous mobile robots. Theoretical Computer Science 384 (2 - 3), p. pages 222–231. External Links: ISSN 0304-3975, Document, Link Cited by: §2. [24] I. Suzuki and M. Yamashita. (1999) Distributed anonymous mobile robots: formation of geometric patterns. SIAM Journal on Computing 28, p. pages 1347–1363. Cited by: §2. [25] G. Viglietta (2013) Rendezvous of two robots with visible bits. In Proc. International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics (ALGOSENSORS), p. 291–306. Cited by: §2.