Paper deep dive
Min-Max Uniform Circle Formation by Asynchronous Mobile Robots
Animesh Maiti, Prakhar Shukla, Subhash Bhagat
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 10/6/2026, 9:51:41 AM
Summary
This paper addresses the Min-Max Uniform Circle Formation (MMUCF) problem for autonomous mobile robots in the Euclidean plane. The goal is to move a set of robots to form a regular n-gon on a target circle while minimizing the maximum distance traveled by any single robot. The authors analyze the problem under the asynchronous (ASYNC) model with non-rigid movements and oblivious robots. They present impossibility results showing that solutions require specific assumptions like coordinate axis agreement and persistent lights. Furthermore, they propose deterministic, distributed, and collision-free algorithms that achieve the min-max objective in finite time.
Entities (8)
Relation Signals (7)
Min-Max Uniform Circle Formation → isavariantof → Uniform Circle Formation
confidence 97% · we study the min--max versions of the circle formation and uniform circle formation problems
Min-Max Uniform Circle Formation → optimizes → Maximum distance traveled
confidence 96% · minimizing the maximum distance traveled by any robot
Min-Max Uniform Circle Formation → requires → Regular n-gon
confidence 95% · the Min-Max Uniform Circle Formation (MMUCF) problem requires the robots to move to distinct positions on C such that the final configuration forms a regular n-gon
Min-Max Uniform Circle Formation → analyzedunder → ASYNC Model
confidence 94% · We consider these problems under the ASYNC model
Robots → operateusing → Look-Compute-Move
confidence 93% · operate under the Look--Compute--Move model
Robots → exhibitmovementtype → Non-Rigid Motion
confidence 92% · operate under the Look--Compute--Move model with non-rigid motion.
Robots → possesscapability → Persistent Lights
confidence 88% · robots equipped with visible lights
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Given a set of point robots $\mathcal{R}$ in the Euclidean plane and a target circle $\mathbf C$ enclosing all robot positions, the \textsc{Min-Max Uniform Circle Formation (MMUCF)} problem requires the robots to move to distinct positions on $\mathbf C$ such that the final configuration forms a regular $n$-gon while minimizing the maximum distance traveled by any robot. Uniform circle formation is a fundamental coordination task in swarm robotics with applications in perimeter monitoring, surveillance, boundary coverage, and pattern formation. The literature does not address the optimization of the maximum individual displacement during the formation process. In this work, we study the min--max versions of the circle formation and uniform circle formation problems, where the goal is to minimize the maximum distance traveled by any robot. We consider these problems under the $\mathcal{ASYNC}$ model, where robots are autonomous, anonymous, identical, homogeneous, oblivious, and silent, and operate under the \textit{Look--Compute--Move} model with non-rigid motion. We first give necessary conditions for a deterministic solution and then present deterministic, distributed, and collision-free algorithms that form a circle and a uniform circle in finite time while minimizing the maximum movement. The algorithms ensure that robots reach distinct positions on the circle and, in the uniform case, equally spaced positions on $\mathbf C$ under the considered model.
Tags
Links
- Source: https://arxiv.org/abs/2610.05008v1
- Canonical: https://arxiv.org/abs/2610.05008v1
Trouble viewing inline? Open PDF directly →
Full Text
142,933 characters extracted from source content.
Expand or collapse full text
Min-Max Uniform Circle Formation by Asynchronous Mobile Robots Animesh Maiti †thanks: Corresponding author: p22ma201@iitj.ac.in Affiliation: Department of Mathematics Prakhar Shukla Affiliation: Indian Institute of Technology Jodhpur Subhash Bhagat Affiliation: Jodhpur, Rajasthan, India Abstract Given a set of point robots ℛR in the Euclidean plane and a target circle C enclosing all robot positions, the Min-Max Uniform Circle Formation (MMUCF) problem requires the robots to move to distinct positions on C such that the final configuration forms a regular n-gon while minimizing the maximum distance traveled by any robot. Uniform circle formation is a fundamental coordination task in swarm robotics with applications in perimeter monitoring, surveillance, boundary coverage, and pattern formation. The literature does not address the optimization of the maximum individual displacement during the formation process. In this work, we study the min–max versions of the circle formation and uniform circle formation problems, where the goal is to minimize the maximum distance traveled by any robot. We consider these problems under the ASYNC model, where robots are autonomous, anonymous, identical, homogeneous, oblivious, and silent, and operate under the Look–Compute–Move model with non-rigid motion. We first give necessary conditions for a deterministic solution and then present deterministic, distributed, and collision-free algorithms that form a circle and a uniform circle in finite time while minimizing the maximum movement. The algorithms ensure that robots reach distinct positions on the circle and, in the uniform case, equally spaced positions on C under the considered model. Keywords: Uniform Circle Formation, Autonomous Mobile Robots, Asynchronous Model, Non-Rigid Movements, Persistent Lights, Min–Max Travel-Distance Optimization, Optimal Assignment. 1 Introduction In the past two decades, multi-robot systems have become an important research focus because of their robustness, scalability, and versatility in diverse applications [1, 8, 21, 24, 28]. A swarm of mobile robots is a distributed multi-agent system consisting of numerous small, autonomous, homogeneous, and anonymous robots that cooperate to accomplish a common task. Each robot operates as an independent computational unit with limited sensing, processing, and actuation capabilities, and coordinated interactions among robots lead to complex collective behavior. Inspired by the self-organizing mechanisms observed in social insects, swarm-based systems are particularly suited for hazardous or inaccessible environments where human intervention is impractical. Their fully decentralized nature enables deployment in unknown and dynamic scenarios and provides robustness against individual failures. In addition, the relatively simple design of individual robots makes such systems cost-effective and fault-tolerant compared to relying on a single sophisticated robot. Consequently, multi-robot systems have been utilized in disaster response and search-and-rescue missions [5], autonomous exploration and mapping [9], surveillance and environmental monitoring [26], agriculture and mining in hazardous environments [2], education and construction [5], and coordinated geometric formation tasks requiring robots to surround a region or target [26, 5]. In distributed computing, theoretical research on multi-robot systems has focused on coordination and complexity issues arising in systems of autonomous mobile entities operating without centralized control. Several computational models emphasizing different capabilities have been proposed, including models with explicit communication [19], memory [20], or identifiers [30]. Our Model. In this paper, we consider the oblivious (no memory of past actions) mobile robots model. In this model, robots are simple computational entities represented as points in the Euclidean plane and operate in repeated Look-Compute-Move cycles. During each cycle, an active robot observes the positions of other robots in its local coordinate system (Look), computes a destination based on the observed configuration (Compute), and moves toward that destination (Move). Movements may be rigid, meaning the robot always reaches its destination, or non-rigid, meaning the robot may be stopped before reaching the destination but is guaranteed to move at least a minimum distance δ toward it. The robots are autonomous (operate without centralized coordination), homogeneous (identical in capabilities and behavior), anonymous (without unique identifiers), oblivious (no memory of past actions), and silent (no explicit communication). Robots do not retain any memory between computational cycles. In extended models, they may be equipped with a constant amount of persistent memory [20], usually implemented through externally visible lights, commonly known as the luminous model, with a finite set of colors [27]. Such persistent memory can be used for communication and state retention (FALL model) [13], only for remembering the robot’s internal state (FSTATE model) [12], or only for communication without storing past states (FCOMM model) [20]. Each robot uses its own local Cartesian coordinate system centreed at its current position, with its own unit of length and orientation of the coordinate axes. Depending on the model [29], different levels of agreement among robots may be assumed. In the strongest case, robots agree on the directions and orientations of all axes, forming a common global reference frame. In weaker settings, robots may agree only on the direction and orientation of one axis. Robots may also share chirality, meaning they have a common notion of clockwise direction even if their axes are not aligned. In the weakest case, robots may have no agreement on axis directions or orientations, and their coordinate systems are completely independent. In this paper, we consider robots with one axis of agreement and equipped with visible lights. Robot activations are controlled by an adversarial but fair scheduler under one of the standard models. In the fully synchronous model (ℱFSYNC), all robots execute their cycles simultaneously in discrete rounds. In the semi-synchronous model (SSYNC), an arbitrary subset of robots is activated in each round. In the asynchronous model (ASYNC), there is no common notion of time, and the duration of each phase is finite but unpredictable. Fairness guarantees that each robot is activated infinitely often, allowing progress to be measured in rounds or epochs depending on the synchronization model. Problem Setting. Let C be a circle of finite radius h, and let ℛ=r1,…,rnR=\r_1,…,r_n\ be a set of n robots initially placed at distinct positions inside C. Let =p1,…,pnP=\p_1,…,p_n\ be a set of n target points on the boundary of C. The goal is to move the robots so that each robot occupies a distinct point of P while minimizing the maximum distance traveled by any robot. In the MMUCF problem, P consists of the vertices of a regular n-gon inscribed in C, i.e., the points are equally spaced along the circumference. Bhattacharya et al. [4] studied a centralized version of this problem in which robot movements are computed centrally. In contrast, we consider a distributed setting where robots act autonomously and make decisions based only on their local observations. Our Contributions. In this problem, we prove three impossibility results in Section 3 (Theorems 1–3), showing that it cannot be solved without additional assumptions about the robots. In Section 4, we then design a deterministic algorithm MinMaxUniformCircle() for robots equipped with visible lights and one-axis agreement that achieves uniform circle formation under the min–max objective. These results indicate that the uniform variant is strictly more difficult than the non-uniform variant and requires additional capabilities to be solvable. Related Works. Geometric formation problems for autonomous mobile robots have been extensively studied in the distributed computing literature since the seminal work of Suzuki and Yamashita [29], which introduced the framework for pattern formation by anonymous robots operating without centralized control. Subsequent research by Flocchini et al. [17], Défago and Konagaya [10], Défago and Souissi [11], and Flocchini et al. [18] established feasibility and impossibility results for circle formation and related tasks under different synchronization models and visibility constraints. In the circle formation problem, robots must move to the boundary of a common circle, and the problem has been studied under asynchronous settings, limited visibility, and weak agreement on coordinate systems. A stricter variant, Uniform Circle Formation (ℱUCF), requires robots to occupy equally spaced positions on the circle and has received significant attention due to its symmetry requirements. Deterministic solutions for ℱUCF have been obtained even under the fully asynchronous model by Flocchini et al. [16] and Viglietta [22], resolving long-standing open cases. Several extensions also consider additional capabilities such as persistent visible lights, obstructed visibility, fat robots, and rigid movements; for example, ℱUCF with persistent lights and rigid motion has been solved by Pattanayak et al. [25]. Other works study trade-offs between time, memory, and communication complexity, including results by Feletti et al. [14, 15] and Mondal et al. [23]. However, most existing works focus on feasibility and symmetry breaking rather than optimizing movement costs, and relatively little attention has been given to minimizing the maximum distance traveled by any robot in fully distributed and oblivious settings. Bhagat et al. [3] study this objective in a distributed setting for circle formation, whereas Bhattacharya et al. [4] consider a centralized formulation. Table 1 summarizes the existing results on circle formation and uniform circle formation under different assumptions. Table 1: Related work on circle formation and uniform circle formation. Problem Input circle Additional capabilities Movement Optimization criterion Reference ℱCF No Lights Non-rigid Yes Solved in [3] ℱUCF No None Non-rigid No Solved in [16] ℱUCF No Persistent lights Rigid No Solved in [25] ℱUCF Yes One axis and lights Non-rigid Yes This paper 2 Preliminaries Let r(t)r(t) denote the location of robot ri∈ℛr_i at time t, and let ℛ(t)R(t) denote the configuration of robots at time t, defined as the multiset of occupied positions, i.e., ℛ(t)=r1(t),r2(t),⋯,rn(t)R(t)=\r_1(t),r_2(t),·s,r_n(t)\. Let ℛ~ R denote the set of all such robot configurations. Robots operate in repeated Look-Compute-Move cycles under the ASYNC model, and all robots execute the same algorithm. For each robot ri∈ℛr_i , let radR(t)rad_R(t) denote the half-line originating at O and passing through r(t)r(t) at time t , where O is the centre of C. Let ~ C denote the set of all circles with finite positive radius, and let ~ G denote the set of all algorithms that solve the uniform circle formation problem over any given circle ∈~C∈ C. Note that ~≠∅ G≠ [14]. Consider an algorithm ∈~A∈ G, a circle C, and an initial robot configuration ℛ(t0)R(t_0). Let pip_i be the final position of robot rir_i on C during the execution of A starting from ℛ(t0)R(t_0), so that the points p1,p2,…,pn\p_1,p_2,…,p_n\ form a regular n-gon. Then there exists t∗≥t0t^*≥ t_0 such that ℛ(t∗)=p1,p2,…,pnR(t^*)=\p_1,p_2,…,p_n\. Let li(,)l_i(A,C) denote the path traversed by robot rir_i from ri(t0)r_i(t_0) to pip_i, and let |li(,)||l_i(A,C)| denote its length. Define λ(,ℛ(t0)) _C(A,R(t_0)) as the maximum distance traveled by any robot during the execution of A, i.e., λ(,ℛ(t0))=max|li(,)|:ri∈ℛ. _C(A,R(t_0))= \|l_i(A,C)|:r_i \. A uniform circle formation algorithm ¯∈~ A∈ G solves the MMUCF problem if λ(¯,ℛ(t0))=minλ(,ℛ(t0)):∈~ _C( A,R(t_0))= \ _C(A,R(t_0)):A∈ G\ for all ∈~C∈ C and ℛ(t0)∈ℛ~R(t_0)∈ R. When there is no ambiguity, we denote λ(¯,ℛ(t0)) _C( A,R(t_0)) by λ∗λ^*_C. Let ∗~ G^* denote the set of all MMUCF algorithms over ~ C. Bhattacharya et al. [4], and Chen et al. [7] presented centralized deterministic algorithms that solve the MMUCF problem over ~ C. These algorithms also solve the problem under the ℱFSYNC model with unlimited visibility, agreement on both coordinate axes, and rigid movements, implying ∗~≠∅ G^*≠ . According to these results, there exists at least one robot position ri(t0)r_i(t_0) such that li(,)l_i(A,C) is a straight-line segment ri(t0)pi¯ r_i(t_0)p_i and λ∗=|li(,)|λ^*_C=|l_i(A,C)|. Let uR(t)u_R(t) and vR(t)v_R(t) be the nearest and farthest points on C from r(t)r(t), respectively; these are the intersection points of C with the line joining r(t)r(t) and O. We next state two known results that characterize the optimal value λ∗λ^*_C and are used later in our analysis. Result 1. [4] For a given circle C and initial configuration ℛ(t0)R(t_0), the value of λ∗λ^*_C is unique. Result 2. [7] Let ¯ A be an algorithm for the MMUCF problem with λ∗=ri(t0)pi¯λ^*_C= r_i(t_0)p_i. Then either pi=ui(t0)p_i=u_i(t_0) or there exists another robot rj(t0)r_j(t_0), j≠ij≠ i, such that λ∗=rj(t0)pj¯λ^*_C= r_j(t_0)p_j. Figure 1: An illustration of target point set and corresponding assignments: initial positions of six robots r1,…,r6r_1,…,r_6 and the corresponding target set is =p1,…,p6P=\p_1,…,p_6\. Here, λ∗(ℛ(t0))=|r2p2¯|=|r5p5¯|λ^*_C(R(t_0))=| r_2p_2|=| r_5p_5| and r1,r5\r_1,r_5\ is the critical set. There are two different assignments for the given configuration: (i) r1→p1,r2→p2,r3→p3,r4→p4,r5→p5,r6→p6\r_1→ p_1,r_2→ p_2,r_3→ p_3,r_4→ p_4,r_5→ p_5,r_6→ p_6\ and (i) r1→p6,r2→p2,r3→p4,r4→p3,r5→p5,r6→p1\r_1→ p_6,r_2→ p_2,r_3→ p_4,r_4→ p_3,r_5→ p_5,r_6→ p_1\ Let Cr(t)C_r(t) denote the circle centreed at r(t)r(t) with radius λ∗λ^*_C. Let p(t)p(t) and q(t)q(t) be the intersection points of Cr(t)C_r(t) with C, and let ℛ(t)R(t) be the set of all such intersection points for all robots. A robot position r(t)r(t) is called pivotal if λ∗=r(t)pi¯λ^*_C= r(t)p_i. The set of all pivotal robot positions is denoted ℛ′(t)R (t). A subset ℛ∗(t)⊆ℛ′(t)R^*(t) (t) is called a critical set if it is minimal such that λ∗(ℛ(t))>λ∗(ℛ(t)∖ℛ∗(t))λ^*_C(R(t))>λ^*_C(R(t) ^*(t)). A set of co-circular points P on C is a regular point set if its convex hull forms a regular k-gon where ||=k|P|=k. An assignment of robots to P is a bijection f:ℛ(t)→f:R(t) . The set P is called the target point set if there exists an assignment f such that λ∗(ℛ(t))=maxdist(r(t),f(r(t))):r(t)∈ℛ(t).λ^*_C(R(t))= \dist(r(t),f(r(t))):r(t) (t)\. Such an assignment is called an optimal assignment. The target point set is unique, though the optimal assignment may not be. Computing the target point set [4]. We compute the target point set P∗P^*, corresponding to λC∗(ℛ(t))λ^*_C(R(t)) in the following way: • For each robot position ri(t)∈ℛ(t)r_i(t) (t), draw circle Ci(t)C_i(t) having centre at ri(t)r_i(t) and radius λC∗(ℛ(t))λ^*_C(R(t)). The circle Ci(t)C_i(t) intersect the circle C at least one point. Let C be the set of all such circles. Let pi(t)p_i(t) and qi(t)q_i(t) be the intersection points between circles Ci(t)C_i(t) and C (these two points may be the same if these two circles intersect exactly at one point). Let B be the set of all such intersection points for the robots positions in ℛ(t)R(t). • For each ax∈Ba_x∈ B, do the following: – compute the point set W=a1,a2,…,anW=\a_1,a_2,…,a_n\ such that all aia_i lies on C, a1=axa_1=a_x and these points form a regular n-gon. – compute a bipartite graph Gx=(V1∪V2,E)G_x=(V_1∪ V_2,E) where V1=BV_1=B, V2=V_2=C and there is an edge in E between al∈V1a_l∈ V_1 and Cj∈V2C_j∈ V_2 iff ala_l lies within or on the circle CjC_j. – If there is a perfect matching in the graph GxG_x, then by lemma 2, we can conclude that W=P∗W=P^* where the perfect matching provides us an optimum assignment. 3 Impossibility Results for MMUCF Problem In this section we present two impossibility results for the MMUCF problem. These impossibility results are with respect to the minimal capabilities of the robots required to solve the problem. According to the Theorem 2, during the execution of each algorithm ∈∗~A∈ G^*, first robots require to compute their final destination points on the circle C and then accordingly move the towards respective destination points. A robot can use the algorithm presented in [4] or in [7] to compute its final destination point. However, this simple strategy can not be adopted directly to a swarm of robots. There are many factors that forbid the direct adaptation of this strategy, like the activation schedule of the robots, the non-rigid movements of the robots, the lack of a global coordinate system, the obliviousness of the robots, etc. Observation 1. Let ℛ(t)R(t) be a configuration for the MMUCF problem on a target circle C with centre O. Suppose there exists a robot rc(t)∈ℛ(t)r_c(t) (t) such that rc(t)=r_c(t)=O, and rcr_c is a critical robot. Then the corresponding regular target point set on C may not be unique, although the optimal min–max value λ∗(ℛ(t)) _C^*(R(t)) is unique, because every point on C is at the same distance from O. Theorem 1. In the absence of any agreement on the local coordinate axes and common chirality, robots cannot agree on a common optimal assignment. Figure 2: Illustration for the proof of Theorem 1. In this symmetric configuration of ℛ=r1,r2,…,r8R=\r_1,r_2,…,r_8\, the min-max distance is λ∗(t0)=d(r5,p1)=d(r6,p3)=d(r7,p5)=d(r8,p7) _C^*(t_0)=d(r_5,p_1)=d(r_6,p_3)=d(r_7,p_5)=d(r_8,p_7). Consequently, the critical robots are r5,r6,r7,r_5,r_6,r_7, and r8r_8. Proof. Let ℛ=r1,…,r8R=\r_1,…,r_8\ be a set of robots operating under ℱFSYNC model. Let C be a given circle with O as its centre. Consider an initial configuration ℛ(t0)=r1(t0),…,r8(t0)R(t_0)=\r_1(t_0),…,r_8(t_0)\ of robots in ℛR as depicted in Figure 2 such that ℛ(t0)R(t_0) has two lines of symmetry ℒ1L_1 and ℒ2L_2. In this case, λ∗(ℛ(t0))=|r5p1¯|λ^*_C(R(t_0))=| r_5p_1|. Let A be an optimal assignment algorithm. Algorithm A should have following assignments: r5→p1r_5→ p_1, r6→p3r_6→ p_3, r7→p5r_7→ p_5 and r8→p7r_8→ p_7. Now, we argue about the rest of the assignments. Since algorithm A outputs an optimal assignment, the assignments of the robots r1,r2,r3r_1,r_2,r_3 and r4r_4 should belong to the sets p2,p8\p_2,p_8\, p2,p4\p_2,p_4\,p4,p6\p_4,p_6\, and p6,p8\p_6,p_8\ respectively. For the robot configuration ℛ(t0)R(t_0), the local views of the robots r1r_1 and r3r_3 are symmetric about the line ℒ1L_1 and the local views of the robots r2r_2 and r4r_4 are symmetric about the line ℒ2L_2. This implies that whatever assignment algorithm A makes for the robots r1r_1 and r3r_3, these two points are images of each other about the line ℒ1L_1. A similar argument can be made for the assignments of r2r_2 and r4r_4 about the line ℒ2L_2. Thus, algorithm A assigns r1r_1 and r3r_3 to either p2p_2 and p4p_4 respectively or p8p_8 and p6p_6 respectively. Without loss of generality, suppose r1r_1 and r3r_3 are assigned to p2p_2 and p4p_4 respectively. Then, algorithm A can not assign robot r2r_2 any of the points in p2,p4\p_2,p_4\. This contradicts that A is an optimal assignment algorithm. Hence, the robots can not agree on a common optimal assignment. ∎ Definition 1 (k-fold rotational symmetry). A configuration ℛ(t)R(t) has k-fold rotational symmetry about the centre O of C if a rotation ρ by angle 2π/k2π/k, k≥2k≥ 2, maps ℛ(t)R(t) onto itself. For a robot position ri∈ℛ(t)r_i (t), the set ri=ri,ρ(ri),ρ2(ri),…,ρk−1(ri)Orbit_r_i=\r_i,ρ(r_i),ρ^2(r_i),…,ρ^k-1(r_i)\ is called the rotational orbit of rir_i under ρ. Theorem 2. In absence of any agreement on the local coordinate systems, the MMUCF problem is unsolvable in ℱFSYNC model for the robots having non -rigid movements, even if robots have common chirality and lights (Fall light model). (a) (b) Figure 3: Illustration for the proof of Theorem 2. (a) A symmetric initial configuration ℛ(t0)=r1(t0),…,r6(t0)R(t_0)=\r_1(t_0),…,r_6(t_0)\, where the optimal min-max distance is λ∗(t0)=d(ri(t0),pi) _C^*(t_0)=d(r_i(t_0),p_i) for i=1,…,6i=1,…,6. (b) A symmetric configuration ℛ(t)=r1(t),…,r6(t)R(t)=\r_1(t),…,r_6(t)\, where the optimal min-max distance is λ∗(t)=d(r1(t0),p1′)=d(r3(t0),p3′)=d(r5(t0),p5′) _C^*(t)=d(r_1(t_0),p_1 )=d(r_3(t_0),p_3 )=d(r_5(t_0),p_5 ). Proof. Let ℛ=r1,r2,…,r6R=\r_1,r_2,…,r_6\ be a set of robots operating under fully-synchronous Fall light model. Suppose robots in ℛR have non-rigid movements and common chirality. Let C be a given circle with O as its centre. Consider an initial configuration ℛ(t0)=r1(t0),r2(t0),…,r6(t0)R(t_0)=\r_1(t_0),r_2(t_0),…,r_6(t_0)\ of robots in ℛR as depicted in Figure 3(A) such that (i) ℛ(t0)R(t_0) is rotationally symmetric around O with 120o120^o angle of rotation (i) all the robots are equidistant from O. Consider another configuration ℛ(t)=r1(t),r2(t),…,r6(t)R(t)=\r_1(t),r_2(t),…,r_6(t)\, t>t0t>t_0, of robots in ℛR as depicted in Figure 3(B) such that (i) ℛ(t)R(t) is rotationally symmetric around O with 120o120^o angle of rotation (i) robots r1r_1, r3r_3 and r5r_5 are equidistant from O and robots r2r_2, r4r_4 and r6r_6 are equidistant from O (i) dist(r2,)>dist(r1,)dist(r_2,O)>dist(r_1,O). If we run algorithm proposed in [4], we get (i) for ℛ(t0)R(t_0), λ∗(¯,ℛ(t0))=d(p1,r1(t0))λ^*_C( A,R(t_0))=d(p_1,r_1(t_0)) and (i) for ℛ(t)R(t), λ∗(¯,ℛ(t))=d(p1′,r1(t0))λ^*_C( A,R(t))=d(p _1,r_1(t_0)), where ¯∈∗~ A∈ G^*. Suppose A is an algorithm which solves the MMUCF problem, i.e., ∈∗~A∈ G^*. First, consider an execution of algorithm A for the initial configuration ℛ(t0)R(t_0). In this case, λ∗=d(p1,r1(t0))λ^*_C=d(p_1,r_1(t_0)). Since ℛ(t0)R(t_0) is rotationally symmetric, algorithm A decides to move either all the robots in A at a time or the robots in r1,r3,r5\r_1,r_3,r_5\ at a time or the robots in r2,r4,r6\r_2,r_4,r_6\ at a time. Suppose at the beginning of the execution, algorithm A decides to move r2,r4r_2,r_4 and r6r_6 at a time towards their respective destination points p2p_2, p4p_4 and p6p_6 respectively. Since the movements of the robots are non-rigid, an adversary can stop robots before reaching their destination points. Suppose adversary stops the robots r2,r4r_2,r_4 and r6r_6 at points p2p_2, p4p_4 and p6p_6 respectively at time t>t0t>t_0 so that the initial configuration is converted to the configuration ℛ(t)R(t) as depicted in Figure 3(B). The value of λ∗(,ℛ(t))λ^*_C(A,R(t)) is strictly less than the value of λ∗(,ℛ(t0))λ^*_C(A,R(t_0)). If robots compute their final destination points in ℛ(t)R(t) considering the value of λ∗(ℛ(t))λ^*_C(R(t)), the final destination points of the robots are then changed: for robot rir_i, the destination point is vi′v _i, 1≤i≤61≤ i≤ 6. If robots start moving towards these points, then robots travel more than λ∗(,ℛ(t0))λ^*_C(A,R(t_0)) distance i.e., they violate the constraint of the MMUCF problem. Therefore, robots somehow need the access of the value λ∗(,ℛ(t0))λ^*_C(A,R(t_0)). They can do this by any one of the following ways (i) they remember the value of λ∗(,ℛ(t0))λ^*_C(A,R(t_0)) or (i) they remember locations of their destination points or (i) remember or recompute their initial configuration ℛ(t0)R(t_0). For options (i) and (i), robots need to remember some angles and/or distances in the initial configuration ℛ(t0)R(t_0). All these methods require to store real numbers which may take unbounded amount of memory. Since robots operate under Fall model, they have constant amount of persistent memory and they can use their lights to communicate their states. The informations that the robots can carry forward from configuration ℛ(t0)R(t_0) to ℛ(t)R(t) is of constant amount. Thus, they can not recompute or remember the exact value of λ∗(,ℛ(t0))λ^*_C(A,R(t_0)). This implies that the MMUCF problem is not solvable under Fall model. ∎ Theorem 3. In the absence of persistent external lights, the MMUCF problem is unsolvable in the ℱFSYNC model for the robots having non-rigid movements, even if robots have both axis agreement. (a) (b) Figure 4: An illustration in the proof of Theorem 3: (A) In this configuration of ℛ(t0)=r1(t0),r2(t0),…,r6(t0)R(t_0)=\r_1(t_0),r_2(t_0),…,r_6(t_0)\, the min-max distance is λ∗(ℛ(t0))=d(r1,p1)=d(r2,p2) _C^*(R(t_0))=d(r_1,p_1)=d(r_2,p_2). (B) In this configuration of ℛ′=r1(t),r2(t),r3′(t),r4′(t),r5(t),r6(t)R =\r_1(t),r_2(t),r_3 (t),r_4 (t),r_5(t),r_6(t)\, the min-max distance is λ∗(ℛ(t))=d(r3′(t),p1)=d(r4′(t),p2) _C^*(R(t))=d(r_3 (t),p_1)=d(r_4 (t),p_2). Proof. Let ℛ=r1,r2,…,r6R=\r_1,r_2,…,r_6\ be a set of oblivious robots operating under the ℱFSYNC model. The robots have non-rigid movements and agree on the directions and orientations of both local coordinate axes. Consider an initial configuration ℛ(t0)R(t_0), as shown in Figure 4(A). Let =p1,p2,…,p6P=\p_1,p_2,…,p_6\ be the optimal target point set on the given circle C. Suppose that the optimal value satisfies λ∗(ℛ(t0))=d(r1(t0),p1)=d(r6(t0),p4). _C^*(R(t_0))=d(r_1(t_0),p_1)=d(r_6(t_0),p_4). Thus, r1r_1 and r6r_6 are critical robots in the initial configuration, since they attain the maximum distance under the optimal assignment. Suppose that there exists an algorithm ∈∗~A∈ G^* that solves ℳℳℱMMUCF in finite time under this model without persistent external lights. Since the robots are oblivious, they do not remember the initial configuration, the initial optimal value λ∗(ℛ(t0)) _C^*(R(t_0)), or the initial optimal assignment after a Look–Compute–Move cycle. To preserve the initial min–max value,i.e., λ∗(ℛ(t0)) _C^*(R(t_0)), the critical robots cannot be moved before the remaining robots are fixed at their assigned target positions. If a critical robot is moved and is stopped at an intermediate position by the non-rigid adversary, then the value of λ∗(ℛ(t0)) _C^*(R(t_0)) and the set of critical robots computed from the next snapshot may differ from those of ℛ(t0)R(t_0). Therefore, in any execution that preserves the initial optimal assignment, progress must first be made by non-critical robots while the initial critical robots remain stationary. Consider an execution of A in which the non-critical robots r3r_3 and r4r_4 among the non-critical robots move toward their assigned target points p6p_6 and p3p_3, respectively. Since the movement is non-rigid, the adversary may stop these robots before they reach their destinations, provided that each moving robot makes the required minimum progress. Let r3′r_3 and r4′r_4 be the intermediate positions reached by r3r_3 and r4r_4, respectively, as shown in Figure 4(B). Let ℛ(t)R(t) be the resulting configuration. The adversary chooses the intermediate positions r3′r_3 and r4′r_4 so that, in the current configuration ℛ(t)R(t), the optimal value computed from the current snapshot is attained by r3′r_3 and r4′r_4 . Hence, r3′r_3 and r4′r_4 become critical robots with respect to ℛ(t)R(t). Let their corresponding target points in the optimal assignment of ℛ(t)R(t) be p1p_1 and p2p_2, respectively. Then d(r3′,p1)=d(r4′,p2)=λ∗(ℛ(t)).d(r_3 ,p_1)=d(r_4 ,p_2)= _C^*(R(t)). However, before reaching ℛ(t)R(t), the robots r3r_3 and r4r_4 have already travelled the positive distances d(r3(t0),r3′)d(r_3(t_0),r_3 ) and d(r4(t0),r4′)d(r_4(t_0),r_4 ), respectively. Therefore, if the robots now follow the optimal assignment computed from the current configuration ℛ(t)R(t), then the total distances travelled by r3r_3 and r4r_4 become d(r3(t0),r3′)+d(r3′,p1)d(r_3(t_0),r_3 )+d(r_3 ,p_1) and d(r4(t0),r4′)+d(r4′,p2),d(r_4(t_0),r_4 )+d(r_4 ,p_2), respectively. By choosing the intermediate positions sufficiently far along the movement segments, the adversary can ensure that d(r3(t0),r3′)>λ∗(ℛ(t0))−λ∗(ℛ(t))d(r_3(t_0),r_3 )> _C^*(R(t_0))- _C^*(R(t)) and d(r4(t0),r4′)>λ∗(ℛ(t0))−λ∗(ℛ(t)).d(r_4(t_0),r_4 )> _C^*(R(t_0))- _C^*(R(t)). Consequently, d(r3(t0),r3′)+d(r3′,p1)>λ∗(ℛ(t0))d(r_3(t_0),r_3 )+d(r_3 ,p_1)> _C^*(R(t_0)) and d(r4(t0),r4′)+d(r4′,p2)>λ∗(ℛ(t0)).d(r_4(t_0),r_4 )+d(r_4 ,p_2)> _C^*(R(t_0)). Thus, at least one robot is forced to travel more than the initial min–max optimal value λ∗(ℛ(t0)) _C^*(R(t_0)). Now consider the information available to the robots in configuration ℛ(t)R(t). Since the robots are oblivious and have no persistent external lights, they cannot determine whether ℛ(t)R(t) is an initial configuration or an intermediate configuration produced after previous non-rigid movements. Therefore, the decision of the deterministic algorithm A depends only on the current snapshot. If the robots follow the optimal assignment computed from ℛ(t)R(t), then, as shown above, some robot travels more than λ∗(ℛ(t0)) _C^*(R(t_0)). On the other hand, preserving the initial optimal assignment requires information about ℛ(t0)R(t_0), which is not available to oblivious robots without persistent external lights. This contradicts the assumption that A solves MMUCF in finite time while preserving the min–max objective. Therefore, no such algorithm exists. Hence, in the absence of persistent external lights, the MMUCF problem is unsolvable in the ℱFSYNC model with non-rigid movements, even under both-axis agreement. ∎ 4 Algorithm MinMaxUniformCircle() for MMUCF Problem 4.1 High-level overview of the algorithm We present MinMaxUniformCircle(), a deterministic distributed algorithm for solving MMUCF under the luminous, oblivious, non-rigid ASYNC model. From the initial configuration ℛ(t0)R(t_0), every robot computes the optimal min–max value λ∗ _C^*, a regular target-point set P, and an optimal assignment fopt(t0):ℛ(t0)→f_opt(t_0):R(t_0) using the algorithm in [4]. The main challenge under obliviousness and non-rigid movements is to preserve the initially selected target-point set P and optimal assignment foptf_opt throughout the execution, since robots may observe intermediate configurations after partially completed moves. The preservation mechanism depends on the critical set ℛ∗(t0)R^*(t_0). In a unique-critical configuration, the critical robot determines a radial reference for P; if the critical robot is located at the centre O, a short deterministic movement first establishes the radial reference. Multiple-critical configurations are handled according to the positions of the non-critical robots and unreserved targets relative to the collective critical region ∗(t0)D^*(t_0). Stationary critical robots normally preserve the target-point set. In the special configuration mcrctK_mcr^ct, with exactly two critical robots, a virtual dummy point is used to reconstruct the same target-point set during the movement of candidate robot (see Definition 3). Robots act as critical, secondary critical (see Definition 2), or candidate robots. Critical and secondary critical robots remain stationary with lights λAnchor _ Anchor and λAnchor−λ^-_ Anchor, respectively, while the selected candidate moves toward its computed target point with light TargetTrace or ReferenceTrace. A non-rigid interruption does not change its target point. Upon arrival, the robot displays the light TargetReached and remains stationary. Candidates’ robots move first, followed by secondary critical robots, and finally critical robots. This ordering preserves the target-point set and the selected assignment throughout the subsequent movements of the robots, while the fairness of the ASYNC scheduler guarantees finite-time completion. To ensure deterministic and consistent selections throughout the execution, whenever multiple robot positions or target points are equally eligible, all robots use the common ordering induced by the one-axis agreement to select the same robot position or target point. The overall procedure is summarized in Algorithm 1, while the detailed subroutines for the respective configuration classes are provided in Section 4.5. Algorithm 1 MinMaxUniformCircle() MinMaxUniformCircle() — executed independently by every robot r in each Look–Compute–Move cycle 1: Look: r observes the current configuration ℛ(t)R(t) and the lights of all robots. 2: if r.light=TargetReachedr.light= TargetReached then 3: remain stationary; return ⊳ terminal state 4: end if 5: (λ∗,,fopt,ℛ∗(t),κ)←ClassifyAndPlan(ℛ(t))( _C^*,P,f_opt,R^*(t),κ)← ClassifyAndPlan(R(t)) ⊳ Algorithm 2 6: switch κ do 7: case ucrncK_ucr^nc: 8: ProcUCR-NC(r,ℛ(t),λ∗,,fopt) ProcUCR-NC(r,R(t), _C^*,P,f_opt) ⊳ Algorithm 3 9: end case 10: case ucrcK_ucr^c: 11: ProcUCR-C(r,ℛ(t),λ∗,,fopt) ProcUCR-C(r,R(t), _C^*,P,f_opt) ⊳ Algorithm 4 12: end case 13: case mcrallK_mcr^all: 14: ProcMCR-ALL(r,ℛ(t),λ∗,,fopt) ProcMCR-ALL(r,R(t), _C^*,P,f_opt) ⊳ Algorithm 5 15: end case 16: case mcrotK_mcr^ot: 17: ProcMCR-OT(r,ℛ(t),λ∗,,fopt) ProcMCR-OT(r,R(t), _C^*,P,f_opt) ⊳ Algorithm 6 18: end case 19: case mcrctK_mcr^ct: 20: ProcMCR-CT(r,ℛ(t),λ∗,,fopt) ProcMCR-CT(r,R(t), _C^*,P,f_opt) ⊳ Algorithm 7 21: end case 22: case mcriiK_mcr^i or mcrioK_mcr^io: 23: ProcMCR-I-IO(r,ℛ(t),λ∗,,fopt) ProcMCR-I-IO(r,R(t), _C^*,P,f_opt) ⊳ Algorithm 8 24: end case 25: end switch 26: Move: r executes the movement determined by the invoked procedure; a non-rigid interruption is handled by the corresponding persistent light state. 4.2 Configuration Classes Based on the Critical Set Let ℛ∗(t0)R^*(t_0) denote the set of critical robots in the initial configuration ℛ(t0)R(t_0). After computing the optimal min–max value λ∗ _C^*, and the corresponding target-point set P, the robots classify the initial configuration according to the cardinality of ℛ∗(t0)R^*(t_0). For each critical robot ri∗∈ℛ∗(t0)r_i^* ^*(t_0), let pi∗∈p_i^* be its assigned critical target point. The associated closed critical disk is defined by ¯i∗(t0)=x∈ℝ2:d(x,pi∗)≤λ∗. D_i^*(t_0)= \x ^2:d(x,p_i^*)≤ _C^* \. Thus, ¯i∗(t0) D_i^*(t_0) is the closed disk of radius λ∗ _C^* centreed at pi∗p_i^*. The collective critical region is defined by ∗(t0)=⋃ri∗∈ℛ∗(t0)¯i∗(t0).D^*(t_0)= _r_i^* ^*(t_0) D_i^*(t_0). Let ∗(t0)=pi∗∈:ri∗∈ℛ∗(t0)P^*(t_0)= \p_i^* :r_i^* ^*(t_0) \ denote the set of target points reserved for the critical robots and let rj∈(t0)r_j (t_0) be a selected non-critical robot. Define the set of its possible unreserved target points by j<=p∈(t0):d(rj(t0),p)<λ0,P_j^<= \p _N(t_0):d (r_j(t_0),p )< _0 \, where (t0)=∖∗(t0)P_N(t_0)=P ^*(t_0) is the set of target points not reserved for the critical robots. Accordingly, the configurations are classified into the following two main classes. (A) Unique-Critical Robot Configuration (ucr)(K_ucr): A configuration ℛ(t0)R(t_0) belongs to ucrK_ucr if |ℛ∗(t0)|=1|R^*(t_0)|=1. This class is further divided into the following two subclasses. (A.1) Unique Non-centre-Critical Configuration (ucrnc)(K_ucr^nc): A configuration ℛ(t0)R(t_0) belongs to ucrncK_ucr^nc if the unique critical robot is not located at O. (A.2) Unique centre-Critical Configuration (ucrc)(K_ucr^c): A configuration ℛ(t0)R(t_0) belongs to ucrcK_ucr^c if the unique critical robot is located at the centre O of the target circle C. Thus, ucr=ucrnc∪ucrcK_ucr=K_ucr^nc _ucr^c. (B) Multiple-Critical Robot Configurations (mcr)(K_mcr): A configuration ℛ(t0)R(t_0) belongs to mcrK_mcr if |ℛ∗(t0)|≥2.|R^*(t_0)|≥ 2. We consider the family mcrout=ℛ(t0)∈mcr:(t0)≠∅and(t0)∩∗(t0)=∅.K_mcr^out= \R(t_0) _mcr:N(t_0)≠ \ and\ N(t_0) ^*(t_0)= \. Thus, every configuration in mcroutK_mcr^out contains at least one non-critical robot, and every non-critical robot lies outside the collective critical region ∗(t0)D^*(t_0). We further define mcrin=ℛ(t0)∈mcr:(t0)∩∗(t0)≠∅.K_mcr^in= \R(t_0) _mcr:N(t_0) ^*(t_0)≠ \. Thus, a configuration belongs to mcrinK_mcr^in if at least one non-critical robot lies inside or on the boundary of the collective critical region. For every ℛ(t0)∈mcrinR(t_0) _mcr^in, let (rc,pc)(r_c,p_c) be the deterministically selected robot–target pair satisfying (rc,pc)∈argminrj∈(t0)∩∗(t0)p∈(t0)d(rj(t0),p).(r_c,p_c)∈ *arg\,min_ subarraycr_j (t_0) ^*(t_0)\\ p _N(t_0) subarrayd (r_j(t_0),p ). Thus, rcr_c is a non-critical robot lying in ∗(t0)D^*(t_0), and pcp_c is its closest unreserved target point. If more than one robot–target pair has the same minimum distance, the tie is resolved using the one-axis agreement. This family is divided into the following three subclasses according to the positions of the unreserved target points. Table 2: Classification of initial configurations based on the critical set. Class Defining condition ucrncK_ucr^nc |ℛ∗(t0)|=1|R^*(t_0)|=1 and the unique critical robot is not at O ucrcK_ucr^c |ℛ∗(t0)|=1|R^*(t_0)|=1 and the unique critical robot is at O mcrallK_mcr^all ℛ∗(t0)=ℛ(t0)R^*(t_0)=R(t_0) mcrotK_mcr^ot (t0)∩∗(t0)=∅N(t_0) ^*(t_0)= and (t0)∖∗(t0)≠∅P_N(t_0) ^*(t_0)≠ mcrctK_mcr^ct (t0)∩∗(t0)=∅N(t_0) ^*(t_0)= and (t0)⊆∗(t0)P_N(t_0) ^*(t_0) mcriiK_mcr^i rc∈∗(t0)r_c ^*(t_0) and pc∈∗(t0)p_c ^*(t_0) mcrioK_mcr^io rc∈∗(t0)r_c ^*(t_0) and pc∉∗(t0)p_c ^*(t_0) (B.1) All-Critical Robot Configuration (mcrall)(K_mcr^all): A configuration ℛ(t0)R(t_0) belongs to mcrallK_mcr^all if every robot is a critical robot with respect to the selected optimal assignment foptf_opt. Formally, mcrall=ℛ(t0)∈mcr:ℛ∗(t0)=ℛ(t0).K_mcr^all= \R(t_0) _mcr:R^*(t_0)=R(t_0) \. In this configuration, d(ri(t0),fopt(ri))=λ∗,for every ri∈ℛ(t0).d (r_i(t_0),f_opt(r_i) )= _C^*,\ for every r_i (t_0). Consequently, every target point is reserved for a critical robot, and hence ∗(t0)=P^*(t_0)=P and (t0)=∅.P_N(t_0)= . Thus, no non-critical robot exists in this configuration. (B.2) Outside-Target Type (mcrot)(K_mcr^ot): A configuration ℛ(t0)R(t_0) belongs to mcrotK_mcr^ot if there exists at least one unreserved target point p∈(t0)p _N(t_0) that lies outside the collective critical region ∗(t0)D^*(t_0). Formally, mcrot=ℛ(t0)∈mcrout:∃p∈(t0) such that p∉∗(t0).K_mcr^ot= \R(t_0) _mcr^out:∃\,p _N(t_0) such that p ^*(t_0) \. Thus, at least one unreserved target point lies outside ∗(t0)D^*(t_0). Moreover, since ℛ(t0)∈mcroutR(t_0) _mcr^out, every non-critical robot lies outside ∗(t0)D^*(t_0). (B.3) Covered-Target Type (mcrct)(K_mcr^ct): A configuration belongs to mcrctK_mcr^ct if every unreserved target point lies inside or on the boundary of the collective critical region. Formally, mcrct=ℛ(t0)∈mcrout:(t0)⊆∗(t0).K_mcr^ct= \R(t_0) _mcr^out:P_N(t_0) ^*(t_0) \. Equivalently, (t0)∖∗(t0)=∅.P_N(t_0) ^*(t_0)= . Thus, every unreserved target point lies inside or on the boundary of ∗(t0)D^*(t_0), whereas every non-critical robot lies outside ∗(t0)D^*(t_0). Therefore, mcrout=mcrot∪mcrct.K_mcr^out=K_mcr^ot _mcr^ct. (B.4) Inner-Robot–Inner-Target Type (mcrii)(K_mcr^i): A configuration ℛ(t0)R(t_0) belongs to mcriiK_mcr^i if the selected non-critical robot rcr_c lies in the collective critical region and its closest unreserved target point pcp_c also lies in the same collective critical region. Formally, mcrii=ℛ(t0)∈mcrin:pc∈∗(t0).K_mcr^i= \R(t_0) _mcr^in:p_c ^*(t_0) \. Thus, both rc(t0)r_c(t_0) and its closest unreserved target point pcp_c lie inside or on the boundary of ∗(t0)D^*(t_0). (B.5) Inner-Robot–Outer-Target Type (mcrio)(K_mcr^io): A configuration ℛ(t0)R(t_0) belongs to mcrioK_mcr^io if the selected non-critical robot rcr_c lies in the collective critical region but its closest unreserved target point pcp_c lies outside this region. Formally, mcrio=ℛ(t0)∈mcrin:pc∉∗(t0).K_mcr^io= \R(t_0) _mcr^in:p_c ^*(t_0) \. Thus, rc(t0)r_c(t_0) lies inside or on the boundary of ∗(t0)D^*(t_0), whereas its closest unreserved target point pcp_c lies outside ∗(t0)D^*(t_0). Therefore, mcrin=mcrii∪mcrio.K_mcr^in=K_mcr^i _mcr^io. So we have mcr=mcrall∪mcrot∪mcrct∪mcrii∪mcrio.K_mcr=K_mcr^all _mcr^ot _mcr^ct _mcr^i _mcr^io. Thus, ucr=ucrnc∪ucrc,K_ucr=K_ucr^nc _ucr^c, and mcr=mcrall∪mcrot∪mcrct∪mcrii∪mcrio.K_mcr=K_mcr^all _mcr^ot _mcr^ct _mcr^i _mcr^io. Table 2 summarizes the configuration classes used by the algorithm. 4.3 Configuration Classification and Planning The following procedure summarizes how a robot determines the configuration class from its current snapshot. Algorithm 2 ClassifyAndPlan(ℛ(t)) ClassifyAndPlan(R(t)) 1: Compute λ∗(¯,ℛ(t)) _C^*( A,R(t)) and the target-point set P using [4, 7] 2: Compute the selected optimal assignment foptf_opt (one-axis agreement breaks ties among multiple optima) 3: ℛ∗(t)←ri∈ℛ(t):d(ri(t),fopt(ri))=λ∗R^*(t)←\r_i (t):d(r_i(t),f_opt(r_i))= _C^*\ 4: if |ℛ∗(t)|=1|R^*(t)|=1 then 5: return ucrncK_ucr^nc if the critical robot ≠ else ucrcK_ucr^c 6: else 7: if ℛ∗(t)=ℛ(t)R^*(t)=R(t) then return mcrallK_mcr^all 8: end if 9: Compute ∗(t)D^*(t), (t)P_N(t) 10: if ∃p∈(t):p∉∗(t)∃\,p _N(t):p ^*(t) then return mcrotK_mcr^ot 11: end if 12: if (t)⊆∗(t)P_N(t) ^*(t) and (t)∩∗(t)=∅N(t) ^*(t)= then return mcrctK_mcr^ct 13: end if 14: Select (rc,pc)←argminrj∈(t)∩∗(t),p∈(t)d(rj(t),p)(r_c,p_c)← _r_j (t) ^*(t),\,p _N(t)d(r_j(t),p) 15: return mcriiK_mcr^i if pc∈∗(t)p_c ^*(t) else mcrioK_mcr^io 16: end if 4.4 States of Robots To maintain the invariance of the target point set and the optimal assignment foptf_opt during the execution, robots use visible lights to encode their current states. Let X denote the finite set of possible light states. In our algorithm, =Off,λAnchor,λAnchor−,TargetTrace,ReferenceTrace,TargetReached.X= \ Off, _ Anchor,λ^-_ Anchor, TargetTrace, ReferenceTrace, TargetReached \. The meaning of each state is as follows. • Off indicates that the robot has not yet performed its first Look–Compute–Move cycle. • λAnchor _ Anchor indicates that the robot is critical and currently acts as an anchor for the optimal min–max value λ∗ _C^* and the target-point set. A robot displaying λAnchor _ Anchor remains stationary until the selected candidate robot reaches its target point and displays TargetReached. • λAnchor−λ^-_ Anchor indicates that the robot is the secondary critical robot. Although it is not itself a critical robot, its movement is deferred until every currently selected candidate robot reaches its target point and displays TargetReached. • TargetTrace indicates that the candidate robot is moving directly toward its assigned target point. If its movement is interrupted because of non-rigidity, it retains TargetTrace and continues toward the same target point in its next activation. Upon reaching the target, it changes its light to TargetReached. • ReferenceTrace indicates the special movement used for a configuration in mcrctK_mcr^ct. The robot moves toward its assigned target point while reconstructing the original target-point set from the dummy point and the stationary critical reference robots. It retains ReferenceTrace throughout every interrupted movement and changes its light to TargetReached upon reaching the target. • TargetReached indicates that the robot has reached its assigned target point. A robot displaying TargetReached remains stationary and never moves again. 4.5 Computation of the Assignment There may exist more than one optimal assignment of the robot positions to the points in P. We have the following observation. To solve the MMUCF problem, robots need to agree on a common optimal assignment foptf_opt to the points in P. Moreover, in the asynchronous setting with non-rigid movements, robots may observe intermediate configurations. Therefore, the initially computed assignment foptf_opt must be preserved throughout the execution; in particular, no robot may change its assigned target on the basis of an intermediate snapshot. In this section, we describe an algorithm to output such an assignment. We assume that, in the initial configuration, no robot lies on the circle C. However, during the execution of the algorithm, robots move to the points on C. Our algorithm uses axis-only agreement to compute such an assignment foptf_opt (as stated in Theorem 1), particularly in symmetric configurations or when a candidate robot has two target points at the same minimum distance. The computation of the optimal assignment foptf_opt depends on the structure of the critical robot set in the initial configuration ℛ(t0)R(t_0). The configuration may contain either a unique critical robot or multiple critical robots. The unique-critical case is further divided according to whether the critical robot is located at the centre O of the target circle C, since a robot located at O does not initially determine a unique radial target point. Accordingly, the computation of foptf_opt is divided into the following three cases: (1) the configuration contains a unique critical robot that is not located at O; (2) the configuration contains a unique critical robot located at O; and (3) the configuration contains multiple critical robots. The algorithms presented in [4] and [7] are used to compute λ∗(ℛ(t0)) _C^*(R(t_0)) and identify the corresponding critical set, which determines the assignment procedure to be applied. Figure 5: Illustration of secondary critical robot in a configuration of six robots r1,r2,…,r6.r_1,r_2,…,r_6. In this configuration, the critical distance is λ∗=d(r3,p2) _C^*=d(r_3,p_2) and r2r_2 is a secondary critical robot with secondary critical target position p6p_6. Definition 2 (Secondary Critical Robot). Let ∗P^* be the set of critical target positions. A robot rs∈ℛ(t)r_s (t) is called a secondary critical robot if rsr_s is not a critical robot and the circle kC_k, centreed at rsr_s with radius λ∗ _C^*, contains exactly one target position ps∈∖∗p_s ^* such that d(rs,ps)<λ∗d(r_s,p_s)< _C^*. The target position psp_s is called the secondary critical target position corresponding to rsr_s. The purpose of introducing secondary critical robots is to preserve the invariance of the optimal assignment foptf_opt under the asynchronous scheduler with non-rigid movements. Critical robots preserve the value of λ∗ _C^*, but they may not be sufficient to preserve the optimal assignment foptf_opt of non-critical robots. During the movement of a candidate robot, the set of feasible target positions for other robots may change, and this may force some robots to travel more than λ∗ _C^*. A secondary critical robot is therefore kept fixed temporarily so that its uniquely determined target position remains reserved. This prevents the optimal assignment foptf_opt from changing before the candidate robots settle. Figure 5 illustrates this situation. The robot r3r_3 is a critical robot because its assigned target point p2p_2 is at distance λ∗ _C^* from r3r_3; hence p2∈∗p_2 ^*. The robot r2r_2 is not critical, but the circle Cr2C_r_2 centreed at r2r_2 with radius λ∗ _C^* contains exactly one target point in ∖∗P ^*, namely p6p_6. Therefore, r2r_2 is a secondary critical robot and p6p_6 is its secondary critical target position. If r2r_2 is allowed to move too early or if its target position is not kept fixed, then another candidate robot may be assigned to p6p_6, which can change the optimal assignment foptf_opt and may violate the min–max bound. Definition 3 (Candidate Robot). Let ℛsec(t)R_sec(t) denote the set of secondary critical robots, and let sec(t)P_sec(t) denote their reserved target points. Define can(t)=(t)∖ℛsec(t),can(t)=∖(∗∪sec(t)).N_can(t)=N(t) _sec(t),\ P_can(t)=P (P^* _sec(t) ). A robot rj∈can(t)r_j _can(t) is called a candidate robot if there exists a target point pj∈can(t)p_j _can(t) such that (rj,pj)∈argminr∈can(t)p∈can(t)d(r(t),p).(r_j,p_j)∈ *arg\,min_ subarraycr _can(t)\\ p _can(t) subarrayd (r(t),p ). The pair (rj,pj)(r_j,p_j) is called the corresponding candidate robot–target pair. This selection rule is used in every unique-critical and multiple-critical configuration. 4.5.1 Common Light-Transition Patterns Candidate robot:Off⟶TargetTrace⟶TargetReachedSecondary critical robot:Off⟶λAnchor−⟶TargetTrace⟶TargetReachedCritical robot:Off⟶λAnchor⟶TargetTrace⟶TargetReached. array[]rclCandidate robot&:&Off TargetTrace TargetReached\\[4.0pt] Secondary critical robot&:&Off λ^-_ Anchor TargetTrace TargetReached\\[4.0pt] Critical robot&:&Off _ Anchor TargetTrace TargetReached. array 4.5.2 Assignment Computation for ucrK_ucr In this subsection, we describe the computation of the optimal assignment foptf_opt for configurations containing exactly one critical robot. According to the classification above, ucr=ucrnc∪ucrc.K_ucr=K_ucr^nc _ucr^c. Therefore, the assignment computation is considered separately according to whether the unique critical robot is located away from or at the centre O of the target circle C. We first consider configurations in ucrncK_ucr^nc. The following lemma identifies the target point associated with the unique non-centre critical robot and thereby determines the radial direction used to fix the target-point set. Lemma 1. Let C be the target circle with centre O, and let rc≠r_c be the unique critical robot in an optimal assignment foptf_opt. Let pcp_c be the intersection point of the circumference of C with the ray starting from O and passing through rcr_c. Then, pc∈p_c , where P denotes the optimal target point set. Proof. Let pc∈p_c be the target point assigned to rcr_c. Since rcr_c is critical, d(rc,pc)=λ∗d(r_c,p_c)= _C^*. Because rcr_c is the unique critical robot, no other robot attains the value λ∗ _C^*. By Lemma 2 in [7], if an optimal solution attains the min–max value at a sensor AiA_i, then either its assigned target point is the closest boundary point XiX_i, or there exists another sensor attaining the same value. Since the second case is impossible here, we obtain pc=pcp_c=p_c. Hence, pc∈p_c . Further, since rc≠Or_c≠ O, the point pcp_c is exactly the nearest intersection point of the line through O and rcr_c with the circumference. ∎ Observation 2 (Angular rigidity of a unique-critical configuration). Let rc≠r_c be the unique critical robot, and let pcp_c be its reserved target point with d(rc(t0),pc)=λ∗d(r_c(t_0),p_c)= _C^*. The point pcp_c, together with the angular separation 2π/n2π/n, uniquely determines the regular target polygon PolyPoly_P. If this polygon is rotated about O through any sufficiently small nonzero angle, either clockwise or counter-clockwise, the distance from rcr_c to its nearest target point becomes strictly greater than λ∗ _C^*. Hence, the min–max cost of the rotated target-point set is strictly greater than λ∗ _C^*. Case-I (Configuration ucrncK_ucr^nc). In this scenario, the initial asymmetric configuration ℛ(t0)R(t_0) about the line ℒL contains exactly one critical robot, not lying at centre O, say rcr_c and let this line ℒL intersect the circumference of the given circle C at p1p_1 (nearest). Fix an ordering [6], say ℱF of the points in P. Let (p1,p2,…,pn)(p_1,p_2,…,p_n) be the sequence of points in P according to ℱF. Let CP_C be the set of points of the critical robot target positions in P. Figure 6: Illustration of a configuration of six robots r1,r2,…,r6r_1,r_2,…,r_6. Here, rc=r1r_c=r_1, ∗=p1P^*=p_1, and the optimal assignment fopt(ri)=pif_opt(r_i)=p_i, i=1,2,…,6i=1,2,…,6. Let pi∈∖Cp_i _C. Draw a circle CpiC_p_i of radius λC∗λ^*_C centreed at pip_i. Let ℛpi(t)R_p_i(t) be the set of all robot positions lying on or inside the circle CpiC_p_i. If the circle CpiC_p_i contains a single robot rir_i, i.e., |ℛpi|=1|R_p_i|=1, then the target position of rir_i is pip_i, i.e., ri→pir_i→ p_i. If the circle CpiC_p_i contains more than one robot, i.e., |ℛpi|>1|R_p_i|>1, then the target positions of all robots in ℛpi(t)R_p_i(t) are computed as follows: Define an order ℋH on ℛpi(t)R_p_i(t) based on the distance between the robots in ℛpi(t)R_p_i(t) and the vertex pip_i. Let robots rjr_j and rkr_k belong to ℛpi(t)R_p_i(t) with d(rj,pi)<d(rk,pi)d(r_j,p_i)<d(r_k,p_i). If either of these two robots is not a secondary critical robot for vertex pip_i, then the target position of rjr_j is pip_i, i.e., rj→pir_j→ p_i. If either of these two robots is a secondary critical robot, say rkr_k for vertex pip_i, then the target position of rkr_k is pip_i, i.e., rk→pir_k→ p_i (See Figure 6). If rj,rk∈ℛpi(t)r_j,r_k _p_i(t) with d(rj,pi)=d(rk,pi)d(r_j,p_i)=d(r_k,p_i) (where the distance is closest to pip_i), then to break this tie, we use the agreement on the Y-axis as follows: let ℬB be the set of robots that are at the same distance from pip_i and lie on the circle bC_b centreed at pip_i. Let c1c_1 and c2c_2 be the two intersection points between bC_b and C. Consider the set ∪c1,c2P∪\c_1,c_2\. Fix an ordering J of the points in ∪c1,c2P∪\c_1,c_2\. Without loss of generality, suppose that c1c_1 has a higher order in J than c2c_2. Order the robots in ℬB according to their distances from c1c_1 to break the ties and obtain the original ordering of the robot positions in ℛpi(t)R_p_i(t). Let (rj,pj)(r_j,p_j) be the candidate robot–target pair selected according to the candidate-selection rule defined above. Figure 7: Illustration of the target-point construction for a centre-critical robot rcr_c for ℛ=rc,r1,r2,r3,r4R=\r_c,r_1,r_2,r_3,r_4\. The maximum angular sector S23S_23 determines the bisector L, along which the auxiliary point qcq_c and the target point pcp_c are selected. During the execution of the above assignment, each robot changes its light according to its assigned role. When the unique critical robot rcr_c is activated, it changes its light from Off to λAnchor _ Anchor and remains stationary. For a target point pip_i, if |ℛpi(t)|=1|R_p_i(t)|=1, the selected candidate robot is rir_i. If |ℛpi(t)|>1|R_p_i(t)|>1 and no secondary critical robot is selected for pip_i, the candidate robot selected by the ordering ℋH is rjr_j. In either case, the selected candidate changes its light according to Off⟶TargetTrace Off TargetTrace and moves toward pip_i. If rkr_k is identified as the secondary critical robot for pip_i, it changes its light from Off to λAnchor−λ^-_ Anchor and remains stationary while the candidate robots move. Every other robot also remains stationary whenever a robot displays TargetTrace. A robot displaying TargetTrace retains this light whenever its movement is interrupted and continues toward the same target point in its next activation. Upon reaching its target, it changes its light to TargetReached and remains stationary. After all candidate robots display TargetReached, the secondary critical robot rkr_k, if one exists, changes its light from λAnchor−λ^-_ Anchor to TargetTrace and moves toward its assigned target point pip_i. Finally, after every non-critical robot has reached its target, the unique critical robot rcr_c changes its light from λAnchor _ Anchor to TargetTrace and moves toward its assigned critical target point p1p_1. Each of these robots changes its light to TargetReached upon reaching its target. The robots follow the common light-transition pattern given in 4.5.1. Algorithm 3 ProcUCR-NC(r,ℛ(t),λ∗,,fopt) ProcUCR-NC(r,R(t), _C^*,P,f_opt) — configuration ucrncK_ucr^nc 1: rc←r_c← the unique critical robot; pc←fopt(rc)p_c← f_opt(r_c) 2: Determine rsr_s (secondary critical robot, Def. 2), if any, and its target psp_s 3: (rj,pj)←(r_j,p_j)← candidate–target pair selected by the candidate-selection rule 4: ⊳ — Light transitions — 5: if r=rcr=r_c then 6: if r.light=Offr.light= Off then 7: r.light←λAnchorr.light← _ Anchor; remain stationary return 8: end if 9: if every ri≠rcr_i≠ r_c displays TargetReached then 10: r.light←TargetTracer.light← TargetTrace; move toward pcp_c 11: else remain stationary 12: end if 13: else if r=rsr=r_s then 14: if r.light=Offr.light= Off then 15: r.light←λAnchor−r.light←λ^-_ Anchor; remain stationary return 16: end if 17: if every candidate robot displays TargetReached then 18: r.light←TargetTracer.light← TargetTrace; move toward psp_s 19: else remain stationary 20: end if 21: else if r=rjr=r_j then 22: r.light←TargetTracer.light← TargetTrace; move toward pjp_j 23: else 24: remain stationary ⊳ not yet eligible 25: end if 26: if r reaches its assigned target then r.light←TargetReachedr.light← TargetReached 27: end if Case-I (Configuration ucrcK_ucr^c). We consider a configuration having a unique critical robot, denoted by rcr_c, which is located at the centre O of the given circle C; that is, ℛ∗(t0)=rcR^*(t_0)=\r_c\ and rc(t0)=.r_c(t_0)=O. The configuration may be asymmetric or symmetric; in the symmetric case, rcr_c breaks the symetricity. Since rcr_c is located at the centre of C, every point on the circumference of C is at the same distance from rc(t0)r_c(t_0). Therefore, the target point corresponding to rcr_c is not unique initially (See Observation 1). Hence, before fixing the target point set, a deterministic direction must be selected so that the ambiguity in choosing the target point of rcr_c is removed. Let ρc=minr∈ℛ(t0)r≠rcd(rc(t0),r(t0)). _c= _ subarraycr (t_0)\\ r≠ r_c subarrayd (r_c(t_0),r(t_0) ). Thus, ρc _c denotes the minimum distance from the centre-critical robot rcr_c to any other robot in the initial configuration. Consider the circle CρcC_ _c centreed at O with radius ρc _c. The robot rcr_c considers the rays from O through all non-central robots in their cyclic order. For every pair of consecutive rays, including the last and the first rays, it considers the angular sector containing no other non-central robot in its interior. It then selects a sector of maximum angular measure, denoted by SijS_ij. The same set of sectors is obtained whether the cyclic order is traversed clockwise or counterclockwise. If several maximum sectors exist, the tie is resolved using the one-axis agreement. The angle bisector ray from O, say L of this sector SijS_ij is the direction of the first movement of rcr_c. We choose an auxiliary point qcq_c on L such that 0<d(,qc)<ρc0<d(O,q_c)< _c (see Figure 7). In particular, qcq_c can be chosen with d(,qc)=ρc/2d(O,q_c)= _c/2. This choice ensures that qcq_c lies strictly closer to O than to any other robot position. Hence, when the direction from O to qcq_c is used for fixing the target point of the centre-critical robot, no other robot becomes critical, and the original centre-critical robot rcr_c remains the critical robot. Moreover, qcq_c is chosen so that it does not lie on any line passing through O and another robot position in ℛ(t0)∖rcR(t_0) \r_c\. This avoids choosing a direction already determined by another robot position and fixes a deterministic direction from O for computing the target point set. Let pcp_c be the intersection point of L with the circumference of c. The point pcp_c is chosen as the target point corresponding to the centre-critical robot rcr_c. Once pcp_c is fixed, the remaining target points are placed on c by maintaining equal arc distance 2πhn 2π hn between consecutive target points, where h is the radius of c. Thus, the ambiguity caused by the centre-critical robot is removed, and the target point set is uniquely determined. The remaining robots compute their assignments with respect to this fixed target point set by following the optimal assignment foptf_opt procedure described above. In particular, no new target point set is recomputed for the remaining robots; they use the target point set determined by the line L. Therefore, the auxiliary choice of qcq_c is used only to fix a deterministic direction for computing the target point set. It does not create any new critical robot and does not violate the optimal min–max value λ∗(¯,ℛ(t0)) _C^*( A,R(t_0)). Algorithm 4 ProcUCR-C(r,ℛ(t),λ∗,,fopt) ProcUCR-C(r,R(t), _C^*,P,f_opt) — configuration ucrcK_ucr^c 1: rc←r_c← the unique critical robot located at O 2: if r=rcr=r_c and r.light=Offr.light= Off then 3: Compute ρc _c, the maximum empty angular sector, its bisector ray L, and qcq_c with d(,qc)=δ<minρc,γcd(O,q_c)=δ< \ _c, _c\ ⊳ Lemma 3 4: r.light←λAnchorr.light← _ Anchor; move toward qcq_c 5: return ⊳ every other robot remains stationary during this step 6: end if 7: if r=rcr=r_c and r has reached qcq_c then 8: ℛ(t)R(t) now belongs to ucrncK_ucr^nc with critical target pcp_c fixed by ray L 9: ProcUCR-NC(r,ℛ(t),λ∗,,fopt) ProcUCR-NC(r,R(t), _C^*,P,f_opt) ⊳ delegate; rcr_c retains λAnchor _ Anchor until eligible 10: else if r≠rcr≠ r_c then 11: ProcUCR-NC(r,ℛ(t),λ∗,,fopt) ProcUCR-NC(r,R(t), _C^*,P,f_opt) ⊳ remaining robots follow the ucrncK_ucr^nc procedure 12: end if During the execution of this case, the centre-critical robot rcr_c first moves slightly away from the centre O in the direction of L. When rcr_c is activated, it changes its light according to Off⟶λAnchor. Off _ Anchor. Let qcq_c be the point on the selected ray L satisfying 0<d(,qc)=δ<ρc.0<d(O,q_c)=δ< _c. Robot rcr_c moves from O toward qcq_c while retaining λAnchor _ Anchor. Every other robot remains stationary during this movement. Since the destination is at distance δ, rcr_c reaches qcq_c in this movement even under the non-rigid model. By the choice δ<ρcδ< _c, robot rcr_c remains the unique critical robot after reaching qcq_c. Since qc≠q_c , the resulting configuration belongs to ucrncK_ucr^nc. The ray from O through qcq_c fixes the critical target point pcp_c and consequently the complete target-point set. Moreover, by Corollary 1, this initial movement does not violate the original optimal min–max travel bound. Therefore, the configuration changes according to ucrc⟶ucrncK_ucr^c _ucr^nc. After this transformation, the candidate robot–target pair (rj,pj)(r_j,p_j) is selected according to the candidate-selection rule defined above. The robots then follow the procedure described for ucrncK_ucr^nc. In particular, rcr_c retains λAnchor _ Anchor while the candidate and secondary critical robots complete their movements. Finally, after the remaining n−1n-1 robots have reached their respective target points and display TargetReached, robot rcr_c changes its light from λAnchor _ Anchor to TargetTrace and moves toward pcp_c. Upon reaching pcp_c, it changes its light to TargetReached and remains stationary. The robots follow the common light-transition pattern given in 4.5.1. Observation 3 (Angular balance of multiple critical robots). Let ℛ(t)∈mcrR(t) _mcr, and let θ∗θ^* be the selected optimal rotation. For any sufficiently small rotation that preserves the critical robot–target associations, decreasing the distance of one critical robot forces the distance of another critical robot to remain at least λ∗ _C^*. Otherwise, the min–max value could be reduced below λ∗ _C^*, contradicting the optimality of θ∗θ^*. Hence, while the critical robots remain stationary, an angular rotation cannot reduce the min–max value determined by them. Observation 4 (First movement in an all-critical configuration). Let ℛ(t0)∈mcrallR(t_0) _mcr^all. Suppose that the selected critical robots move toward their assigned targets, while the remaining critical robots stay stationary. After any positive movement, each selected robot becomes non-critical since its remaining distance is strictly smaller than λ∗ _C^*. The stationary critical robots continue to preserve λ∗ _C^* and the target-point set, regardless of whether the initial symmetry is preserved or broken. 4.5.3 Assignment Computation for mcrK_mcr In a unique critical robot configuration, the line passing through the centre O and the critical robot determines a target point on C. This point anchors the remaining target points at angular intervals of 2π/n2π/n, making the target-point set invariant. In a multiple-critical configuration, no single critical robot provides such a unique anchor. Moreover, robot movements may change the observed critical structure, making it difficult to reconstruct the same target-point set from an intermediate configuration. Therefore, the robots use their lights to preserve the required reference information and consistently recompute the original target-point set without changing its orientation or the assignment. Once at least one robot reaches its assigned target point, that occupied target point serves as an anchor, and the complete target-point set can be reconstructed by placing the remaining points on C at angular intervals of 2π/n2π/n. According to the classification, mcrK_mcr, we consider these two types separately and describe how the target-point set and assignment are reconstructed after at least one robot has moved. Before describing the assignment computation for the different multiple-critical configurations, we recall the observations concerning critical robots given in Appendix. Case-I (Configuration mcrallK_mcr^all). In this configuration, every robot is critical and every target point is reserved under the selected optimal assignment. If the configuration is rotationally symmetric, the robots use the common ordering induced by the one-axis agreement and select a critical robot having the highest y-coordinate with respect to the agreed axis. If several symmetry-equivalent robots have the same highest position, the highest-priority robot is selected. If they remain indistinguishable, they may be selected simultaneously, provided that they have distinct assigned target points. Algorithm 5 ProcMCR-ALL(r,ℛ(t),λ∗,,fopt) ProcMCR-ALL(r,R(t), _C^*,P,f_opt) — configuration mcrallK_mcr^all 1: if r.light=Offr.light= Off then 2: r.light←λAnchorr.light← _ Anchor; remain stationary return 3: end if 4: rj←r_j← selected critical robot(s) by one-axis agreement / symmetry-breaking rule (Case-I, § 4.5) 5: if r=rjr=r_j (or r∈r∈ selected symmetric set) then 6: r.light←TargetTracer.light← TargetTrace; move toward fopt(r)f_opt(r) 7: if r reaches its target then r.light←TargetReachedr.light← TargetReached 8: end if 9: else 10: remain stationary, retaining λAnchor _ Anchor ⊳ once rjr_j moves positively, ℛ(t)→mcriiR(t) _mcr^i; subsequent cycles call ProcMCR-I-IO 11: end if Let rjr_j be a selected critical robot and let pj∗=fopt(rj)p_j^*=f_opt(r_j) be its assigned critical target point. Robot rjr_j moves along the segment [rj(t0),pj∗][r_j(t_0),p_j^*], while every unselected critical robot remains stationary. Due to non-rigid movement, rjr_j may be stopped before reaching pj∗p_j^*. In that case, it retains the same target point and continues toward it in every subsequent activation. No additional robot is allowed to initiate a movement until every currently selected robot reaches its assigned target point. Since rjr_j is initially critical, d(rj(t0),pj∗)=λ∗.d (r_j(t_0),p_j^* )= _C^*. Hence, rj(t0)r_j(t_0) lies on the boundary of its closed critical disk ¯j∗(t0) D_j^*(t_0). After any positive movement toward pj∗p_j^*, at some time t1>t0t_1>t_0, d(rj(t1),pj∗)<λ∗,d (r_j(t_1),p_j^* )< _C^*, and therefore rjr_j becomes non-critical with respect to the retained assignment. Moreover, since ¯j∗(t0) D_j^*(t_0) is convex, [rj(t0),pj∗]⊆¯j∗(t0)⊆∗(t0).[r_j(t_0),p_j^*] D_j^*(t_0) ^*(t_0). Consequently, rj(t1)∈∗(t0)andpj∗∈∗(t0).r_j(t_1) ^*(t_0)\ and\ p_j^* ^*(t_0). Once rjr_j becomes non-critical, its target point pj∗p_j^* becomes an unreserved target point. Thus, the resulting configuration belongs to mcriiK_mcr^i. By Observation 4, the stationary critical robots continue to preserve λ∗ _C^* and the target-point set, even if unequal non-rigid movements break the initial symmetry. Therefore, every moving robot retains its previously assigned target point. After this transition, every subsequent candidate robot–target pair is selected according to the candidate-selection rule defined above, and the robots follow the procedure for mcriiK_mcr^i.. During the execution of this case, every critical robot changes its light from Off to λAnchor _ Anchor when it is activated. Based on the selection rule described above, the selected critical robot rjr_j changes its light according to λAnchor⟶TargetTrace _ Anchor TargetTrace and starts moving toward its previously assigned critical target point pj∗p_j^*. Every unselected critical robot retains λAnchor _ Anchor and remains stationary. If several symmetry-equivalent critical robots are selected simultaneously, each of them changes its light to TargetTrace and moves toward a distinct assigned target point. Every other robot remains stationary while these lights are visible. Due to non-rigid movement, a selected robot rjr_j may be stopped before reaching pj∗p_j^*. In that case, it retains TargetTrace and continues toward the same target point in each subsequent activation. After making any positive movement, rjr_j becomes non-critical, but its light and assigned target point remain unchanged. The stationary robots continue to display λAnchor _ Anchor and preserve λ∗ _C^* and the target-point set. Thus, after the transition mcrall⟶mcrii,K_mcr^all _mcr^i, the moving robot rjr_j continues to execute the candidate-robot procedure for mcriiK_mcr^i. Upon reaching pj∗p_j^*, it changes its light according to TargetTrace⟶TargetReached TargetTrace TargetReached and remains stationary. After every initially selected robot displays TargetReached, the remaining robots follow the light and movement procedure specified for mcriiK_mcr^i. Each remaining critical robot retains λAnchor _ Anchor until it becomes eligible to move. It then changes its light to TargetTrace, moves toward its assigned target point, and changes its light to TargetReached upon reaching it. The light sequences are summarized as follows: Initially selected critical robot rj:Off⟶λAnchor⟶TargetTrace⟶TargetReachedRemaining critical robot ri∗:Off⟶λAnchor⟶TargetTrace⟶TargetReached. array[]rclInitially selected critical robot r_j&:& aligned Off& _ Anchor TargetTrace\\ & TargetReached aligned\\[6.0pt] Remaining critical robot r_i^*&:& aligned Off& _ Anchor TargetTrace\\ & TargetReached. aligned array Case-I (Configuration mcrotK_mcr^ot). In this configuration, at least one unreserved target point lies outside the collective critical region. Let out(t0)=p∈(t0):p∉∗(t0)P_out(t_0)= \p _N(t_0):p ^*(t_0) \ denote the set of such target points. Let (rj,pj)(r_j,p_j) be selected according to the candidate-selection rule defined above, with the candidate target set restricted to out(t0)P_out(t_0). Thus, rjr_j is a non-critical robot closest to an unreserved target point pjp_j lying outside ∗(t0)D^*(t_0). If more than one robot–target pair has the same minimum distance, the tie is resolved using the one-axis agreement. The selected robot rjr_j moves along the segment [rj(t0),pj][r_j(t_0),p_j], while every other robot remains stationary. If its movement is interrupted because of non-rigidity, it retains the same target point and continues toward pjp_j in each subsequent activation. No other robot is allowed to initiate a movement until rjr_j reaches pjp_j. Once rjr_j reaches pjp_j, the remaining assignment procedure is continued using the fixed target-point set. Algorithm 6 ProcMCR-OT(r,ℛ(t),λ∗,,fopt) ProcMCR-OT(r,R(t), _C^*,P,f_opt) — configuration mcrotK_mcr^ot 1: out(t)←p∈(t):p∉∗(t)P_out(t)←\p _N(t):p ^*(t)\ 2: (rj,pj)←(r_j,p_j)← candidate–target pair selected by the candidate-selection rule restricted to out(t)P_out(t) 3: rs←r_s← secondary critical robot, if any 4: if r∈ℛ∗(t)r ^*(t) then 5: r.light←λAnchorr.light← _ Anchor (if Off); remain stationary until every non-critical robot reaches its target 6: then r.light←TargetTracer.light← TargetTrace; move toward fopt(r)f_opt(r) 7: else if r=rsr=r_s then 8: r.light←λAnchor−r.light←λ^-_ Anchor (if Off); remain stationary until all candidates reach targets 9: then r.light←TargetTracer.light← TargetTrace; move toward its reserved target 10: else if r=rjr=r_j then 11: r.light←TargetTracer.light← TargetTrace; move toward pjp_j 12: else 13: remain stationary 14: end if 15: if r reaches its assigned target then r.light←TargetReachedr.light← TargetReached 16: end if During the execution of this case, every critical robot ri∗∈ℛ∗(t0)r_i^* ^*(t_0) changes its light from Off to λAnchor _ Anchor when it is activated and remains stationary. A secondary critical robot rsr_s, if one exists, changes its light from Off to λAnchor−λ^-_ Anchor and also remains stationary. The selected candidate robot rjr_j changes its light according to Off⟶TargetTrace Off TargetTrace and moves toward the selected target point pjp_j. Every other robot remains stationary while rjr_j displays TargetTrace. If its movement is interrupted because of non-rigidity, rjr_j retains the same light and continues toward pjp_j in each subsequent activation. Upon reaching pjp_j, robot rjr_j changes its light according to TargetTrace⟶TargetReached TargetTrace TargetReached and remains stationary. Its position then provides a direct reference for the fixed target-point set. After every candidate robot displays TargetReached, the secondary critical robot rsr_s, if one exists, changes its light from λAnchor−λ^-_ Anchor to TargetTrace and moves toward its assigned target point. After all non-critical robots have reached their respective targets, the critical robots become eligible to move toward their assigned critical target points. Each critical robot changes its light from λAnchor _ Anchor to TargetTrace when it becomes eligible. Every robot changes its light to TargetReached upon reaching its target and remains stationary thereafter. The robots follow the common light-transition pattern given in 4.5.1. Case-I (Configuration mcrctK_mcr^ct). Let λ0=λ∗(¯,ℛ(t0)), _0= _C^* ( A,R(t_0) ), and let (0,fopt)(P_0,f_opt) be the deterministically selected optimal target-point set and assignment at time t0t_0. In this configuration, every non-critical robot lies outside ∗(t0)D^*(t_0), whereas every unreserved target point lies inside or on its boundary. Therefore, a candidate robot may enter ∗(t0)D^*(t_0) while moving toward its assigned target point. Due to non-rigid movements and the oblivious nature of the robots, the main difficulty is to ensure that 0P_0 and foptf_opt remain invariant throughout all intermediate ASYNC configurations. Before any candidate robot moves, every critical robot changes its light according to Off⟶λAnchorOff _ Anchor and remains stationary. A secondary critical robot, if one exists, changes its light according to Off⟶λAnchor−Off λ^-_ Anchor and also remains stationary. Let (rj,pj)(r_j,p_j) be the candidate robot–target pair selected according to the candidate-selection rule defined above. If a symmetry-equivalent pair or orbit is selected, let S denote the set of all such selected candidate robots. If a robot displaying TargetReached is visible, its position is given priority over every critical or dummy reference for reconstructing the target-point set. Algorithm 7 ProcMCR-CT(r,ℛ(t),λ∗,,fopt) ProcMCR-CT(r,R(t), _C^*,P,f_opt) — configuration mcrctK_mcr^ct 1: (rj,pj)←(r_j,p_j)← candidate–target pair selected by the candidate-selection rule; S←S← symmetry-equivalent selected set 2: if r∈ℛ∗(t)r ^*(t) then 3: r.light←λAnchorr.light← _ Anchor (if Off); remain stationary until all non-critical robots settle 4: else if r∈Sr∈ S and |ℛ∗(t)|>2|R^*(t)|>2 then ⊳ Subcase I(a) 5: r.light←TargetTracer.light← TargetTrace; move toward pj=fopt(r)p_j=f_opt(r) ⊳ reference == stationary critical robots 6: else if r∈Sr∈ S and |ℛ∗(t)|=2|R^*(t)|=2 then ⊳ Subcase I(b) 7: Recompute mab,ℓab,H+,z+m_ab, _ab,H^+,z^+, dummy point w=mab+z+2w= m_ab+z^+2 8: r.light←ReferenceTracer.light← ReferenceTrace; move toward pj=fopt(r)p_j=f_opt(r), using w to reconstruct P 9: else if r=rsr=r_s (secondary critical) then 10: r.light←λAnchor−r.light←λ^-_ Anchor (if Off); remain stationary until all candidates reach TargetReached 11: else 12: remain stationary (Off) ⊳ eligible only after the first TargetReached 13: end if 14: if r reaches its assigned target then 15: r.light←TargetReachedr.light← TargetReached ⊳ its position now anchors P for all later robots 16: end if Subcase-I(a): More Than Two Critical Robots. This subcase applies when |ℛ∗(t0)|>2.|R^*(t_0)|>2. The positions and λAnchor _ Anchor lights of the stationary critical robots determine the original target-point set 0P_0. Therefore, no dummy point or additional geometric reference is required. Every selected candidate rj∈Sr_j∈ S changes its light according to Off⟶TargetTraceOff TargetTrace and moves toward its assigned target point pj=fopt(rj)p_j=f_opt(r_j). For every rj∈Sr_j∈ S, once it makes a positive movement toward pjp_j, at any time t>t0t>t_0 after such movement, we have d(rj(t),pj)=d(rj(t0),pj)−d(rj(t0),rj(t))<d(rj(t0),pj)<λ0.d (r_j(t),p_j )=d (r_j(t_0),p_j )-d (r_j(t_0),r_j(t) )<d (r_j(t_0),p_j )< _0. Thus, every moving candidate remains non-critical throughout its movement. Since all critical robots remain stationary, Observation 4 ensures that λ∗(¯,ℛ(t))=λ0,(t)=0. _C^* ( A,R(t) )= _0,\ P(t)=P_0. If the movement of a candidate is interrupted because of non-rigidity, it retains TargetTrace and continues toward the same target point in its next activation. Figure 8: A six-robot configuration with exactly two critical robots, ra∗=r1r_a^*=r_1 and rb∗=r6r_b^*=r_6, and critical distance λ∗ _C^*. The midpoint m16m_16, selected region H+H^+, and dummy point w determine the invariant target-point set 0P_0. Subcase-I(b): Exactly Two Critical Robots. This subcase applies when |ℛ∗(t0)|=2.|R^*(t_0)|=2. Let ra∗r_a^* and rb∗r_b^* be the two critical robots. As illustrated in Figure 8, let mab=ra∗(t0)+rb∗(t0)2m_ab= r_a^*(t_0)+r_b^*(t_0)2 be the midpoint of the segment joining them. Define ℓab=ra∗(t0)rb∗(t0)↔,ℒ=mab↔, _ab= r_a^*(t_0)r_b^*(t_0),\ L= Om_ab, where mab≠m_ab . The line ℓab _ab divides the disk bounded by C into two regions. The robots select the region containing the largest number of stationary robots. The selected candidates in S are excluded from this count because their positions may change during the movement phase. Denote the selected region by H+H^+. Note that ∗(t0)∩H+=∅D^*(t_0)∩ H^+= . Let z+z^+ be the intersection of ℒ L with the circumference of C lying in H+H^+. The virtual dummy point is defined by w=mab+z+2.w= m_ab+z^+2. Thus, w lies on ℒ L in H+H^+, and every candidate computes the same virtual point. The dummy point provides a common geometric reference from which every robot reconstructs the invariant target-point set 0P_0, consisting of n distinct points regularly spaced on the circumference of C. Since it is neither a robot position nor a target point, it does not participate in the computation of λ0 _0 or foptf_opt. Each selected candidate rj∈Sr_j∈ S changes its light according to Off⟶ReferenceTraceOff ReferenceTrace and moves toward its assigned target point pj=fopt(rj)p_j=f_opt(r_j). If the movement of a candidate is interrupted, it retains ReferenceTrace. Since the two critical robots and all uncounted stationary robots remain fixed, the candidate recomputes the same region H+H^+, dummy point w, and target-point set 0P_0 before continuing toward the same target point. For every rj∈Sr_j∈ S and every time t during its movement, d(rj(t),pj)<d(rj(t0),pj)<λ0.d (r_j(t),p_j )<d (r_j(t_0),p_j )< _0. Since the two critical robots remain stationary, they preserve the optimal min–max value and the original target-point set: λ∗(¯,ℛ(t))=λ0,(t)=0. _C^* ( A,R(t) )= _0,\ P(t)=P_0. While any initially selected candidate in S displays TargetTrace or ReferenceTrace, every non-critical robot outside S retains Off and remains stationary. The critical robots and the secondary critical robot retain their respective anchor lights and also remain stationary. In the subcase |ℛ∗(t0)|=2|R^*(t_0)|=2, no robot displays TargetTrace during the ReferenceTrace phase. Therefore, no new candidate is selected until every initially selected candidate in S reaches its assigned target point. Upon reaching pjp_j, a selected candidate changes its light according to TargetTrace⟶TargetReached,if |ℛ∗(t0)|>2,ReferenceTrace⟶TargetReached,if |ℛ∗(t0)|=2. casesTargetTrace TargetReached,&if |R^*(t_0)|>2,\\[4.0pt] ReferenceTrace TargetReached,&if |R^*(t_0)|=2. cases The position pjp_j of the first robot displaying TargetReached fixes the target-point set 0P_0. The remaining n−1n-1 target points are placed successively on the circumference of C at an equal angular separation of 2π/n2π/n from pjp_j. Equivalently, consecutive target points are separated by an arc distance of 2πh/n2π h/n, where h is the radius of C. After all initially selected candidates have reached their targets, the remaining robots compute their assignments with respect to the fixed target-point set 0P_0, excluding the occupied target points. The remaining candidate robots move toward their assigned targets using Off⟶TargetTrace⟶TargetReached.Off TargetTrace TargetReached. After all remaining candidate robots display TargetReached, the secondary critical robot, if one exists, moves toward its assigned target point. Finally, the critical robots move toward their respective critical target points according to the procedure described for ucrncK_ucr^nc. The light sequences are summarized as follows: Initial candidate, |ℛ∗(t0)|>2:Off⟶TargetTrace⟶TargetReachedInitial candidate, |ℛ∗(t0)|=2:Off⟶ReferenceTrace⟶TargetReachedRemaining candidate:Off⟶TargetTrace⟶TargetReachedSecondary critical robot:Off⟶λAnchor−⟶TargetTrace⟶TargetReachedCritical robot:Off⟶λAnchor⟶TargetTrace⟶TargetReached. array[]rclInitial candidate, |R^*(t_0)|>2&:&Off TargetTrace TargetReached\\[3.0pt] Initial candidate, |R^*(t_0)|=2&:&Off ReferenceTrace TargetReached\\[3.0pt] Remaining candidate&:&Off TargetTrace TargetReached\\[3.0pt] Secondary critical robot&:&Off λ^-_ Anchor TargetTrace TargetReached\\[3.0pt] Critical robot&:&Off _ Anchor TargetTrace TargetReached. array Case-IV (Configurations mcriiK_mcr^i and mcrioK_mcr^io). In both configurations, at least one non-critical robot lies inside or on the boundary of ∗(t0)D^*(t_0). For a configuration in mcriiK_mcr^i, its closest unreserved target point also lies in ∗(t0)D^*(t_0), whereas for a configuration in mcrioK_mcr^io, that target point lies outside ∗(t0)D^*(t_0). Accordingly, define adm(t0)=(t0)∩∗(t0),if ℛ(t0)∈mcrii,(t0)∖∗(t0),if ℛ(t0)∈mcrio.P_adm(t_0)= casesP_N(t_0) ^*(t_0),&if R(t_0) _mcr^i,\\[4.0pt] P_N(t_0) ^*(t_0),&if R(t_0) _mcr^io. cases Algorithm 8 ProcMCR-I-IO(r,ℛ(t),λ∗,,fopt) ProcMCR-I-IO(r,R(t), _C^*,P,f_opt) — configurations mcriiK_mcr^i, mcrioK_mcr^io 1: adm(t)←(t)∩∗(t)P_adm(t) _N(t) ^*(t) if mcriiK_mcr^i else (t)∖∗(t)P_N(t) ^*(t) 2: (rj,pj)←(r_j,p_j)← candidate–target pair selected from can(t)∩∗(t)N_can(t) ^*(t) and can(t)∩adm(t)P_can(t) _adm(t) 3: rs←r_s← secondary critical robot, if any 4: if r∈ℛ∗(t)r ^*(t) then 5: r.light←λAnchorr.light← _ Anchor (if Off); remain stationary until all non-critical robots settle 6: else if r=rsr=r_s then 7: r.light←λAnchor−r.light←λ^-_ Anchor (if Off); remain stationary until all candidates reach TargetReached 8: else if r=rjr=r_j then 9: r.light←TargetTracer.light← TargetTrace; move along [r(t),pj][r(t),p_j] ⊳ may cross into/out of ∗(t)D^*(t), target unchanged 10: else 11: remain stationary 12: end if 13: if r reaches its assigned target then r.light←TargetReachedr.light← TargetReached 14: end if Before a candidate moves, every critical robot changes its light from Off to λAnchor _ Anchor and remains stationary. The secondary critical robot rsr_s, if it exists, changes its light from Off to λAnchor−λ^-_ Anchor and also remains stationary. Let (rj,pj)(r_j,p_j) be selected according to the candidate-selection rule defined above, with the eligible robot set restricted to can(t0)∩∗(t0)N_can(t_0) ^*(t_0) and the candidate target set restricted to can(t0)∩adm(t0)P_can(t_0) _adm(t_0). If several pairs attain the same minimum distance, the tie is resolved using the one-axis agreement. The selected candidate rjr_j changes its light according to Off⟶TargetTraceOff TargetTrace and moves along [rj(t0),pj][r_j(t_0),p_j]. While rjr_j displays TargetTrace, every other non-critical robot retains Off, and the critical and secondary critical robots retain their respective anchor lights. All of them remain stationary. If the movement is interrupted because of non-rigidity, rjr_j retains TargetTrace and continues toward pjp_j in its next activation. No new candidate is selected until rjr_j reaches pjp_j. For mcriiK_mcr^i, both rj(t0)r_j(t_0) and pjp_j lie in ∗(t0)D^*(t_0). For mcrioK_mcr^io, the robot initially lies in ∗(t0)D^*(t_0) but leaves this region while moving toward pj∉∗(t0)p_j ^*(t_0). In either case, it retains the same target point throughout its movement. Upon reaching pjp_j, robot rjr_j changes its light according to TargetTrace⟶TargetReachedTargetTrace TargetReached and remains stationary. Its position fixes the target-point set. The remaining candidate robots then move toward their assigned target points one at a time using the same light transition. After all candidate robots display TargetReached, the secondary critical robot changes its light from λAnchor−λ^-_ Anchor to TargetTrace and moves toward its assigned target point. Finally, after every non-critical robot reaches its target, the critical robots move toward their assigned critical target points in the deterministic order used in the procedure for ucrncK_ucr^nc. Every robot changes its light to TargetReached upon reaching its target and remains stationary thereafter. The robots follow the common light-transition pattern given in 4.5.1. 4.6 Correctness of MinMaxUniformCircle() The correctness of the algorithm follows from the invariance of the selected optimal solution and the finite progress of robots toward their assigned targets. We first prove that the target-point set and the corresponding assignment remain unchanged during the execution. We then show that a selected candidate preserves its assigned target until reaching it, and that simultaneously selected candidates have distinct reserved targets. These properties ensure collision-free movements. Finally, the fairness of the scheduler and the non-rigid movement assumption guarantee that every robot reaches its target in finite time. Hence, the final configuration realizes the initial optimal assignment and achieves the optimal min–max travel distance. 4.6.1 Unique-Critical Invariants Lemma 2 (Invariance of the target-point set for ucrncK_ucr^nc). Let ℛ(t0)∈ucrncR(t_0) _ucr^nc have the unique critical robot rcr_c, and let (0,fopt)(P_0,f_opt) be the selected optimal solution with value λ0 _0. If a non-critical candidate rjr_j moves only toward fopt(rj)f_opt(r_j) while every other robot remains stationary, then, throughout its movement, λ∗(¯,ℛ(t))=λ0,(t)=0. _C^* ( A,R(t) )= _0,\ P(t)=P_0. Moreover, foptf_opt remains optimal, ℛ∗(t)=rcR^*(t)=\r_c\, and rjr_j remains non-critical. Proof. Section 4.1 of [4] associates each robot and each feasible value λ with the arc of the circumference that the robot can reach within distance λ. Since rcr_c is not located at O, the point pcp_c is its unique closest point on the circumference of C. Therefore, for every point p on the circumference, d(rc(t0),p)≥d(rc(t0),pc)=λ0,d (r_c(t_0),p )≥ d (r_c(t_0),p_c )= _0, with equality only for p=pcp=p_c. We first establish the upper bound. Since rjr_j moves directly toward pjp_j, its distance from pjp_j never increases. After any positive movement, d(rj(t),pj)<d(rj(t0),pj)<λ0.d (r_j(t),p_j )<d (r_j(t_0),p_j )< _0. All other non-critical robots remain stationary at distances strictly smaller than λ0 _0 from their retained targets, whereas d(rc(t),pc)=λ0.d (r_c(t),p_c )= _0. Hence, the original target-point set 0P_0 and the retained assignment foptf_opt remain feasible with maximum distance λ0 _0. Consequently, λ∗(¯,ℛ(t))≤λ0. _C^* ( A,R(t) )≤ _0. For the lower bound, consider any regular target-point set and any assignment at time t. Since every target point lies on the circumference of C, the stationary robot rcr_c must be assigned to some point p satisfying d(rc(t),p)≥λ0.d (r_c(t),p )≥ _0. Thus, no value smaller than λ0 _0 is feasible, and hence λ∗(¯,ℛ(t))≥λ0. _C^* ( A,R(t) )≥ _0. Combining the two bounds gives λ∗(¯,ℛ(t))=λ0. _C^* ( A,R(t) )= _0. Furthermore, every optimal assignment at value λ0 _0 must assign rcr_c to pcp_c, because pcp_c is the unique circumference point at distance λ0 _0 from rcr_c. Therefore, every optimal regular target-point set contains pcp_c. Once pcp_c is fixed, the remaining n−1n-1 target points are uniquely determined at angular separations 2π/n2π/n. Hence, the target-point set remains (t)=0P(t)=P_0. The light λ-Anchor keeps the stationary critical robot rcr_c identifiable throughout the candidate movement. Thus, after every non-rigid interruption, robot rjr_j reconstructs the same point pcp_c, the same target-point set 0P_0, and continues toward the same target pjp_j with light TargetTrace. When rjr_j reaches pjp_j and changes its light to TargetReached, its position provides an additional reference for 0P_0. The remaining target points can then be computed at angular separations 2π/n2π/n, and the next eligible candidate moves with respect to the same invariant target-point set. ∎ Let γc=λ0−maxri∈ℛ(t0)∖rcd(ri(t0),fopt(ri)). _c= _0- _r_i (t_0) \r_c\d (r_i(t_0),f_opt(r_i) ). Since rcr_c is the unique critical robot, γc>0 _c>0. Lemma 3 (centre-critical reduction). Let qcq_c be the point on L satisfying d(,qc)=δd(O,q_c)=δ, where 0<δ<minρc,γc.0<δ< \ _c, _c\. Suppose that rcr_c moves from O toward qcq_c along L, while every other robot remains stationary. Then, at every intermediate time t satisfying 0<σt=d(,rc(t))≤δ,0< _t=d (O,r_c(t) )≤δ, the target-point set remains 0P_0, rcr_c remains the unique critical robot, and ℛ(t)∈ucrnc.R(t) _ucr^nc. Proof. Since rcr_c moves only along L, the ray starting from O and passing through rc(t)r_c(t) remains L. Therefore, its intersection with the circumference of C remains pcp_c. Since pcp_c and the angular separation 2π/n2π/n uniquely determine the regular target-point set, we have (t)=0.P(t)=P_0. Let h be the radius of C. Since rc(t0)=r_c(t_0)=O and rcr_c is critical, λ0=h _0=h. At time t, d(rc(t),pc)=h−σt=λ0−σt.d (r_c(t),p_c )=h- _t= _0- _t. For every ri≠rcr_i≠ r_c, the robot remains stationary and hence d(ri(t),fopt(ri))≤λ0−γc<λ0−δ≤λ0−σt.d (r_i(t),f_opt(r_i) )≤ _0- _c< _0-δ≤ _0- _t. Thus, under the retained assignment, rcr_c is the unique robot attaining the maximum distance. Moreover, every point of C is at distance at least h−σth- _t from rc(t)r_c(t), with equality only at pcp_c. Therefore, no assignment can attain a min–max value smaller than h−σth- _t, while the retained assignment attains this value. Hence, it remains optimal and rcr_c remains the unique critical robot. Finally, δ<ρcδ< _c ensures that the segment [,qc][O,q_c] contains no other robot. Since rc(t)≠r_c(t) for every σt>0 _t>0, we obtain ℛ(t)∈ucrnc.R(t) _ucr^nc. ∎ Corollary 1 (Preservation of the original min–max travel bound). Let s=d(qc,pc).s=d(q_c,p_c). Since O, qcq_c, and pcp_c are collinear and qcq_c lies between O and pcp_c, δ+s=d(,qc)+d(qc,pc)=d(,pc)=h=λ0.δ+s=d(O,q_c)+d(q_c,p_c)=d(O,p_c)=h= _0. Therefore, the movement through qcq_c only divides the original optimal path of rcr_c into two consecutive segments and does not violate the original min–max travel bound. By Lemma 3, after the initial movement of rcr_c, the resulting configuration belongs to ucrncK_ucr^nc with the same target-point set. Therefore, the remaining execution follows from the correctness of the procedure for ucrncK_ucr^nc. Moreover, by Corollary 1, the original optimal min–max travel bound is preserved. 4.6.2 Multiple-Critical Invariants Lemma 4 (Invariance of the target-point set for multiple-critical configurations). Let ℛ(t0)∈mcrR(t_0) _mcr, and let 0P_0 be the target-point set selected at time t0t_0. If the robots execute the corresponding procedure described in Cases I–IV, then, at every time t during the execution, (t)=0.P(t)=P_0. Proof. Let t1t_1 be the first time at which a robot displays TargetReached. We first prove that (t)=0P(t)=P_0 for every t<t1t<t_1. Case-I: mcrallK_mcr^all. The unselected critical robots retain λAnchor _ Anchor and remain stationary while the selected critical robots move. Therefore, the reference positions and lights used to determine the initial orientation remain unchanged. Every interrupted robot displaying TargetTrace consequently reconstructs the same target-point set 0P_0. This requires that the selected robots do not exhaust the complete reference set before one of them reaches its target. Case-I: mcrotK_mcr^ot. Every critical robot retains λAnchor _ Anchor, and the secondary critical robot, if one exists, retains λAnchor−λ^-_ Anchor. All these robots remain stationary while the selected candidate moves. Hence, the reference information used to reconstruct the target-point set remains unchanged, and every intermediate snapshot yields 0P_0. Case-I: mcrctK_mcr^ct. If |ℛ∗(t0)|>2|R^*(t_0)|>2, the stationary critical robots displaying λAnchor _ Anchor preserve the prescribed reference information. Therefore, each candidate displaying TargetTrace reconstructs 0P_0 after every interrupted movement. Now suppose that |ℛ∗(t0)|=2|R^*(t_0)|=2. The two critical robots ra∗r_a^* and rb∗r_b^* remain stationary. Moreover, the selected set S is fixed before any of its members moves and is excluded from the count defining H+H^+. Consequently, the midpoint mabm_ab, the region H+H^+, the point z+z^+, and the dummy point w=mab+z+2w= m_ab+z^+2 remain unchanged. Hence, every robot displaying ReferenceTrace applies the same dummy-point reconstruction rule and obtains the same target-point set 0P_0. Case-IV: mcriiK_mcr^i or mcrioK_mcr^io. The critical and secondary critical robots retain their respective anchor lights and remain stationary while the selected candidate moves. Therefore, the reference information remains unchanged, irrespective of whether the candidate stays inside ∗(t0)D^*(t_0) or leaves this region. Thus, the candidate reconstructs the same target-point set 0P_0 throughout its movement. It remains to consider the execution at and after t1t_1. Let pjp_j be the target occupied by the first robot displaying TargetReached. Since pj∈0p_j _0, the point pjp_j together with the angular separation 2π/n2π/n uniquely determines the regular target-point set 0P_0, up to cyclic relabelling. The robot at pjp_j retains TargetReached and remains stationary. Hence, from time t1t_1 onward, every robot reconstructs the target-point set directly from pjp_j, without using the earlier critical or dummy reference. Therefore, (t)=0P(t)=P_0 throughout the complete execution. ∎ 4.6.3 Supporting Invariants for Multiple-Critical Configurations Lemma 5 (Preservation of the retained optimal solution). Let ℛ(t0)∈mcr∖mcrallR(t_0) _mcr _mcr^all, and let (0,fopt)(P_0,f_opt) be the selected optimal solution with value λ0=λ∗(¯,ℛ(t0)) _0= _C^*( A,R(t_0)). Let tct_c be the first time at which an initially critical robot starts moving. Then, for every t∈[t0,tc)t∈[t_0,t_c), λ∗(¯,ℛ(t))=λ0, _C^* ( A,R(t) )= _0, and the retained assignment foptf_opt remains optimal with respect to the invariant target-point set 0P_0. In particular, maxri∈ℛ(t)d(ri(t),fopt(ri))=λ0. _r_i (t)d (r_i(t),f_opt(r_i) )= _0. Proof. Fix any t∈[t0,tc)t∈[t_0,t_c). By Lemma 4, the target-point set remains 0P_0 throughout this interval. From the critical characterization used in the computation of λ0 _0, for every admissible regular target-point set (θ)P(θ) and every injective assignment g:ℛ∗(t0)→(θ)g:R^*(t_0) (θ), we have maxri∗∈ℛ∗(t0)d(ri∗(t0),g(ri∗))≥λ0. _r_i^* ^*(t_0)d (r_i^*(t_0),g(r_i^*) )≥ _0. Since t<tct<t_c, every initially critical robot remains stationary. Therefore, for each ri∗∈ℛ∗(t0)r_i^* ^*(t_0), d(ri∗(t),fopt(ri∗))=d(ri∗(t0),fopt(ri∗))=λ0.d (r_i^*(t),f_opt(r_i^*) )=d (r_i^*(t_0),f_opt(r_i^*) )= _0. Every initially non-critical robot has assigned distance strictly smaller than λ0 _0. By the movement procedure, such a robot either remains stationary or moves only toward its retained target. Hence, for every rj∈(t0)r_j (t_0), d(rj(t),fopt(rj))≤d(rj(t0),fopt(rj))<λ0.d (r_j(t),f_opt(r_j) )≤ d (r_j(t_0),f_opt(r_j) )< _0. Consequently, maxri∈ℛ(t)d(ri(t),fopt(ri))=λ0. _r_i (t)d (r_i(t),f_opt(r_i) )= _0. Thus, the retained solution (0,fopt)(P_0,f_opt) remains feasible at value λ0 _0, and therefore λ∗(¯,ℛ(t))≤λ0. _C^* ( A,R(t) )≤ _0. Conversely, consider any admissible target-point set (θ)P(θ) and any assignment f for ℛ(t)R(t). Its restriction to ℛ∗(t0)R^*(t_0) is an injective assignment. Since the initially critical robots remain stationary, Condition (C)(C) gives maxri∈ℛ(t)d(ri(t),f(ri)) _r_i (t)d (r_i(t),f(r_i) ) ≥maxri∗∈ℛ∗(t0)d(ri∗(t),f(ri∗)) ≥ _r_i^* ^*(t_0)d (r_i^*(t),f(r_i^*) ) ≥λ0. ≥ _0. Hence, no solution having value smaller than λ0 _0 exists, and λ∗(¯,ℛ(t))≥λ0. _C^* ( A,R(t) )≥ _0. Combining the two inequalities yields λ∗(¯,ℛ(t))=λ0. _C^* ( A,R(t) )= _0. Since (0,fopt)(P_0,f_opt) attains this value, foptf_opt remains optimal throughout [t0,tc)[t_0,t_c). ∎ Lemma 6 (Persistence of the critical set). Let ℛ(t0)∉mcrallR(t_0) _mcr^all, and let tct_c be the first time at which an initially critical robot starts moving. Then, for every t∈[t0,tc)t∈[t_0,t_c), ℛ∗(t)=ℛ∗(t0).R^*(t)=R^*(t_0). Proof. Let λ0=λ∗(¯,ℛ(t0)) _0= _C^*( A,R(t_0)). By the applicable result among Lemmas 2–4, the target-point set, the retained assignment, and the optimal min–max value remain invariant before any critical robot moves. Every ri∗∈ℛ∗(t0)r_i^* ^*(t_0) remains stationary during this interval. Hence, for its reserved target pi∗p_i^*, d(ri∗(t),pi∗)=d(ri∗(t0),pi∗)=λ0.d (r_i^*(t),p_i^* )=d (r_i^*(t_0),p_i^* )= _0. Thus, every initially critical robot remains critical. For every initially non-critical robot rjr_j, its assigned distance is strictly smaller than λ0 _0. If rjr_j remains stationary, this distance does not change; if it moves, it moves toward its fixed target point, and hence the distance decreases. Therefore, rjr_j cannot become critical. By Lemmas 4 and 5, the target-point set, the retained optimal assignment, and the optimal min–max value remain unchanged until an initially critical robot starts moving. Consequently, ℛ∗(t)=ℛ∗(t0)R^*(t)=R^*(t_0) for every t<tct<t_c. ∎ 4.6.4 Persistence of Candidates and Target Reservations Lemma 7 (Invariance of the assigned target point). Let (rj,pj)(r_j,p_j) be the candidate–target pair selected at time tst_s. By the applicable result among Lemmas 2–4, the target-point set remains invariant. Under the movement procedure, rjr_j moves only along [rj(ts),pj][r_j(t_s),p_j] and retains its movement light. Then pjp_j remains assigned to rjr_j until rjr_j reaches it. Proof. Let avP_av be the set of target points available to rjr_j at time tst_s. By the candidate-selection rule, d(rj(ts),pj)≤d(rj(ts),q)d(r_j(t_s),p_j)≤ d(r_j(t_s),q) for every q∈avq _av. At any intermediate time t, there exists α∈[0,1]α∈[0,1] such that rj(t)=(1−α)rj(ts)+αpjr_j(t)=(1-α)r_j(t_s)+α p_j. For every q∈av∖pjq _av \p_j\, we have d2(rj(t),q)−d2(rj(t),pj) d^2 (r_j(t),q )-d^2 (r_j(t),p_j ) =(1−α)[d2(rj(ts),q)−d2(rj(ts),pj)]+αd2(pj,q). =(1-α) [d^2 (r_j(t_s),q )-d^2 (r_j(t_s),p_j ) ]+α d^2(p_j,q). The first term is non-negative, and the second term is strictly positive whenever α>0α>0. Hence, after any positive movement, pjp_j is the unique closest available target point of rjr_j. At α=0α=0, any initial tie is resolved by the prescribed one-axis agreement. If the movement is interrupted, rjr_j retains TargetTrace, or ReferenceTrace in the corresponding case, and every other robot remains stationary. Therefore, the available target-point set does not change, and every subsequent activation of rjr_j yields the same target point pjp_j. Consequently, the assignment of rjr_j remains unchanged until it reaches pjp_j. ∎ Lemma 8 (Persistence and exclusive reservation of candidate targets). Let (rj,pj)(r_j,p_j) be a candidate–target pair selected at time tst_s. Then rjr_j retains pjp_j as its assigned target until reaching it. Moreover, distinct simultaneously selected candidates are assigned distinct target points, and every such target remains reserved for its candidate until it is reached. Proof. Let (rj,pj)(r_j,p_j) be a candidate–target pair selected at time tst_s. By the applicable target-set invariance result, the target-point set P remains unchanged throughout the movement of rjr_j. Moreover, by Lemma 7, once rjr_j starts moving toward pjp_j, the point pjp_j remains its assigned target until it is reached. In particular, if the movement is interrupted because of non-rigidity, rjr_j retains TargetTrace, or ReferenceTrace in the corresponding case, and resumes its movement toward the same point pjp_j at its next activation. Hence, the candidate–target pair (rj,pj)(r_j,p_j) persists until rjr_j reaches pjp_j. Now consider two distinct candidates ri,rjr_i,r_j selected from the same snapshot. Since the selected optimal assignment foptf_opt is a bijection, fopt(ri)≠fopt(rj).f_opt(r_i)≠ f_opt(r_j). Thus, simultaneously selected candidates are assigned distinct target points. Furthermore, once pjp_j is assigned to rjr_j, it remains reserved while rjr_j displays TargetTrace or ReferenceTrace and is therefore excluded from every subsequent candidate selection. When rjr_j reaches pjp_j, it changes its light to TargetReached and remains stationary at pjp_j; hence, pjp_j remains unavailable to all subsequently selected robots. Consequently, every selected candidate retains its assigned target until reaching it, and no two candidates can ever reserve the same target point. ∎ 4.6.5 Collision Freedom and Finite Progress Theorem 4 (Collision-Free Execution of MinMaxUniformCircle()). If all robots initially occupy pairwise distinct positions, then every execution of MinMaxUniformCircle() preserves this property, provided that every authorized movement phase obeys the clear-path rule. Proof. By Lemma 8, the targets assigned to the robots in S are pairwise distinct. By the clear-path rule, their movement paths satisfy the required disjointedness conditions. Consider an arbitrary movement phase starting at time tst_s. Let S denote the set of robots authorized to move during this phase, and let pip_i be the target assigned to each robot ri∈Sr_i∈ S. By the clear-path rule, the following conditions hold: 1. the assigned targets pi:ri∈S\p_i:r_i∈ S\ are pairwise distinct and unoccupied at time tst_s; 2. for every ri∈Sr_i∈ S, (ri(ts),pi]∩rk(ts):rk∉S=∅;(r_i(t_s),p_i]∩\r_k(t_s):r_k∉ S\= ; 3. for any two distinct robots ri,rj∈Sr_i,r_j∈ S, [ri(ts),pi]∩[rj(ts),pj]=∅.[r_i(t_s),p_i]∩[r_j(t_s),p_j]= . By Lemma 7, every robot in S preserves its assigned target throughout the phase. Consequently, for every time t during this phase, ri(t)∈[ri(ts),pi],ri∈S.r_i(t)∈[r_i(t_s),p_i],\ r_i∈ S. Under non-rigid motion, an adversarial interruption may stop a robot at an intermediate point of this segment, but cannot alter its prescribed trajectory. Moreover, while robots display TargetTrace or ReferenceTrace, no robot outside S is allowed to initiate a movement. Robots displaying λAnchor _ Anchor or λAnchor−λ^-_ Anchor also remain stationary. Hence, during the considered phase, only robots in S may change their positions. Assume, for contradiction, that a collision occurs during this phase, and consider the first such collision. There are only two possibilities. If a moving robot ri∈Sr_i∈ S collides with a stationary robot rk∉Sr_k∉ S, then rk(ts)∈(ri(ts),pi],r_k(t_s)∈(r_i(t_s),p_i], contradicting Condition 2. Otherwise, two robots ri,rj∈Sr_i,r_j∈ S collide. Their common collision point must then belong to both prescribed movement segments, implying [ri(ts),pi]∩[rj(ts),pj]≠∅,[r_i(t_s),p_i]∩[r_j(t_s),p_j]≠ , which contradicts Condition 3. Thus, no collision can occur during the phase. In particular, when a robot rir_i reaches pip_i, it changes its light to TargetReached and remains stationary there; since pip_i is included in its movement segment, Condition 3 already prevents any simultaneously moving robot from reaching the same position. In every subsequent movement phase, this stationary robot is again taken into account by the clear-path rule. The preliminary displacement of a centre-critical robot is also collision-free, since it is performed entirely inside an empty sector and within its prescribed safe distance ρc _c. Therefore, every movement phase of MinMaxUniformCircle() is collision-free. Since the robots occupy pairwise distinct positions initially, induction over successive movement phases implies that no two robots ever occupy the same position. Hence, every execution of MinMaxUniformCircle() is collision-free. ∎ Lemma 9 (Finite-time achievement). Under a fair ASYNC scheduler and the non-rigid movement model with minimum progress δ>0δ>0, every execution of MinMaxUniformCircle() terminates after finitely many Look–Compute–Move cycles. At termination, every robot occupies a distinct target point of P, and hence ℳℳℱMMUCF is achieved. Proof. Let rir_i be a robot selected at time tst_s, and let pip_i be its assigned target point. By Lemmas 7 and 8, the pair (ri,pi)(r_i,p_i) remains unchanged until rir_i reaches pip_i. Let Di=d(ri(ts),pi)D_i=d(r_i(t_s),p_i). Under the non-rigid movement model, every effective Move of rir_i either brings it directly to pip_i or decreases its remaining distance by at least δ. Therefore, rir_i reaches pip_i after at most ⌈Diδ⌉ D_iδ Effective move operations. Fairness guarantees that every selected robot is activated sufficiently often to complete these movements. If several candidates are selected from the same snapshot, the same argument applies independently to each of them because their target points are distinct and remain reserved by Lemma 8. Now consider any nonterminal configuration. If a robot displays TargetTrace or ReferenceTrace, it remains eligible and continues toward its fixed target. Otherwise, the selection rule of the applicable configuration class selects at least one eligible robot–target pair. After the candidate robots have settled, the secondary critical robot and subsequently the critical robots become eligible according to the movement procedure. Hence, no nonterminal configuration is a deadlock. Whenever a selected robot reaches its target, it changes its light to TargetReached and never moves again. Thus, every completed target-reaching phase increases the number of robots displaying TargetReached by at least one. Since there are only n robots, at most n such phases can occur. The preliminary displacement of the centre-critical robot is the only phase that may not immediately place a robot at a target point. This movement has finite length and, by the same minimum-progress argument, is completed after finitely many effective Moves. It occurs only once and transforms the configuration into ucrncK_ucr^nc, after which the usual target-reaching procedure is followed. Consequently, every selected movement is completed after finitely many effective Moves, and only finitely many movement phases occur. Under the fair ASYNC scheduler, the execution therefore terminates after finitely many Look–Compute–Move cycles. By Lemmas 2, 3, and 4, all robots use the same invariant regular target-point set P. Moreover, the selected optimal assignment is bijective, and assigned targets remain distinct and reserved. Hence, at termination, the n robots occupy the n distinct points of P, one robot at each target point. Therefore, ℳℳℱMMUCF is achieved. ∎ Theorem 5 (Correctness of MinMaxUniformCircle()). Under a fair ASYNC scheduler and non-rigid movements, MinMaxUniformCircle() terminates in finite time without collisions, places the robots at the distinct points of 0P_0, and solves MMUCF optimally with maximum travel distance λ∗(¯,ℛ(t0)) _C^*( A,R(t_0)). Proof. The classification based on the critical set covers all possible configurations. For ucrncK_ucr^nc and ucrcK_ucr^c, Lemmas 2 and 3 preserve the optimal solution and reduce the execution to the non-centre case. For multiple-critical configurations, Lemma 4 preserves the target-point set throughout the execution. By Lemmas 5–8, the selected optimal assignment remains invariant, and every selected candidate preserves its assigned target until reaching it. Hence, asynchronous activations and non-rigid interruptions do not affect the execution. By Theorem 4 and Lemma 9, the execution is collision-free and terminates in finite time. Since foptf_opt is a bijection, the robots finally occupy all points of 0P_0. It remains to prove optimality. For each robot rir_i, let LiL_i denote the total distance travelled by rir_i during the execution. Since every robot moves only along the segment joining its initial position to its assigned target, and non-rigid movements only split this segment into smaller parts, we have Li=d(ri(t0),fopt(ri)).L_i=d(r_i(t_0),f_opt(r_i)). The preliminary movement in the center-critical case is collinear with the final movement and, by Corollary 1, does not increase the optimal bound. Thus, maxiLi=λ∗(¯,ℛ(t0)). _iL_i= _C^*( A,R(t_0)). No algorithm can achieve a smaller value by the definition of the min–max objective. Hence, MinMaxUniformCircle() is collision-free, terminates in finite time, and solves MMUCF optimally. ∎ 5 Conclusion In this paper, we studied the min–max uniform circle formation problem for autonomous mobile robots under the asynchronous and non-rigid movement model. We established three impossibility results and proposed a distributed algorithm for robots equipped with externally visible lights and one-axis agreement. The algorithm preserves the optimal target-point set and assignment despite asynchronous activations and non-rigid interruptions, guarantees collision-free execution, and achieves the optimal min–max travel distance in finite time. Several directions remain open, including weakening the robot capabilities, considering the case where the target circle is not given in advance, studying limited visibility settings, and developing fault-tolerant variants in the presence of obstacles. References [1] D. Albiero, A. P. Garcia, C. K. Umezu, and R. L. de Paulo (2021) Swarm robots in agriculture. arXiv preprint arXiv:2103.06732. Cited by: §1. [2] L. Bayindir (2016) A review of swarm robotics tasks. Neurocomputing 172, p. 292–321. Cited by: §1. [3] 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: Table 1, §1. [4] B. Bhattacharya, M. Burmester, Y. Hu, E. Kranakis, Q. Shi, and A. Wiese (2009) Optimal movement of mobile sensors for barrier coverage of a planar region. Theoretical Computer Science 410 (52), p. 5515–5528. Cited by: §1, §1, §2, §2, §3, §3, §4.1, §4.5, §4.6.1, Result 1, 1. [5] M. Brambilla, E. Ferrante, M. Birattari, and M. Dorigo (2013) Swarm robotics: a review from the swarm engineering perspective. Swarm Intelligence 7 (1), p. 1–41. Cited by: §1. [6] S. G. Chaudhuri and K. Mukhopadhyaya (2015) Leader election and gathering for asynchronous fat robots without common chirality. J. Discrete Algorithms 33, p. 171–192. External Links: Document Cited by: §4.5.2. [7] D. Z. Chen, X. Tan, H. Wang, and G. Wu (2015) Optimal point movement for covering circular regions. Algorithmica 72 (2), p. 379–399. Cited by: §2, §3, §4.5.2, §4.5, Result 2, 1. [8] W. H. Chun and N. Papanikolopoulos (2016) Robot surveillance and security. springer Handbook of Robotics, p. 1605–1626. Cited by: §1. [9] P. Corke, R. Peterson, and D. Rus (2005) Networked robots: flying robot navigation using a sensor net. Robotics Research. Cited by: §1. [10] X. Défago and A. Konagaya (2002) Circle formation for oblivious anonymous mobile robots with no common sense of orientation. In Proceedings of the second ACM international workshop on Principles of mobile computing, POMC ’02, New York, NY, USA, p. 97–104. External Links: ISBN 1-58113-511-4, Link, Document Cited by: §1. [11] X. Défago and S. Souissi (2008) Non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformity. Theoretical Computer Science 396 (1-3), p. 97–112. Cited by: §1. [12] G. A. Di Luna, P. Flocchini, S. G. Chaudhuri, F. Poloni, N. Santoro, and G. Viglietta (2017) Mutual visibility by luminous robots without collisions. Information and Computation 254, p. 392–418. Cited by: §1. [13] G. A. Di Luna, P. Flocchini, S. Gan Chaudhuri, N. Santoro, and G. Viglietta (2014) Robots with lights: overcoming obstructed visibility without colliding. In Symposium on Self-Stabilizing Systems, p. 150–164. Cited by: §1. [14] C. Feletti, C. Mereghetti, and B. Palano (2018) Uniform circle formation for swarms of opaque robots with lights. In International Symposium on Stabilizing, Safety, and Security of Distributed Systems, p. 317–332. Cited by: §1, §2. [15] C. Feletti, D. Pattanayak, and G. Sharma (2024) Optimal uniform circle formation by asynchronous luminous robots. arXiv preprint arXiv:2405.06617. Cited by: §1. [16] P. Flocchini, G. Prencipe, N. Santoro, and G. Viglietta (2017) Distributed computing by mobile robots: uniform circle formation. Distributed Computing 30 (6), p. 413–457. Cited by: Table 1, §1. [17] P. Flocchini, G. Prencipe, N. Santoro, and P. Widmayer (1999) Hard tasks for weak robots: the role of common knowledge in pattern formation by autonomous mobile robots. In International Symposium on Algorithms and Computation, p. 93–102. Cited by: §1. [18] P. Flocchini, G. Prencipe, and N. Santoro (2012) Distributed computing by oblivious mobile robots. Synthesis Lectures on Distributed Computing Theory, Morgan & Claypool Publishers. External Links: Link, Document, ISBN 978-3-031-00880-1 Cited by: §1. [19] P. Flocchini, G. Prencipe, and N. Santoro (Eds.) (2019) Distributed computing by mobile entities, current research in moving and computing. Springer. Cited by: §1. [20] P. Flocchini, N. Santoro, G. Viglietta, and M. Yamashita (2013) Rendezvous of two robots with constant memory. In International Colloquium on Structural Information and Communication Complexity, p. 189–200. Cited by: §1, §1. [21] M. Kegeleirs, D. Garzón Ramos, and M. Birattari (2019) Random walk exploration for swarm mapping. In Annual conference towards autonomous robotic systems, p. 211–222. Cited by: §1. [22] 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: §1. [23] M. Mondal and S. Gan Chaudhuri (2019) Uniform circle formation by swarm robots under limited visibility. In International Conference on Distributed Computing and Internet Technology, p. 420–428. Cited by: §1. [24] H. V. D. Parunak (1996) Applications of distributed artificial intelligence in industry. Foundations of distributed artificial intelligence 2. Cited by: §1. [25] D. Pattanayak and G. Sharma (2024) Time-color tradeoff on uniform circle formation by asynchronous robots. In 2024 IEEE International Parallel and Distributed Processing Symposium (IPDPS), p. 987–997. Cited by: Table 1, §1. [26] M. Schwager, B. Julian, and D. Rus (2009) Decentralized, adaptive coverage control for networked robots. The International Journal of Robotics Research 28 (3), p. 357–375. Cited by: §1. [27] G. Sharma, R. Vaidyanathan, and J. L. Trahan (2017) Constant-time complete visibility for asynchronous robots with lights. In International Symposium on Stabilization, Safety, and Security of Distributed Systems, p. 265–281. Cited by: §1. [28] M. Steinberg (2006) Intelligent autonomy for unmanned naval systems. In Proc. Defense and Security Symposium, p. 623013–623013. Cited by: §1. [29] 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: §1, §1. [30] S. Terai, K. Wada, and Y. Katayama (2018) Gathering problems for autonomous mobile robots with lights. arXiv preprint arXiv:1811.12068. Cited by: §1.