Min-Max Uniform Circle Formation by Asynchronous Mobile Robots

Min-Max Uniform Circle Formation by Asynchronous Mobile Robots Animesh Maiti∗, Prakhar Shukla, Subhash Bhagat

arXiv:2610.05008v1 [cs.DC] 4 Oct 2026

Department of Mathematics Indian Institute of Technology Jodhpur 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 ASYN C 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 ∗

Corresponding author: p22ma201@iitj.ac.in

1

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 [17], 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 (FSYN C), all robots execute their cycles simultaneously in discrete rounds. In the semi-synchronous model (SSYN C), an arbitrary subset of robots is activated in each round. In the asynchronous model (ASYN C), 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 R = {r1 , . . . , rn } be a set of n robots initially placed at distinct positions inside C. Let P = {p1 , . . . , pn } 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. 2

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. [19], Défago and Konagaya [10], Défago and Souissi [11], and Flocchini et al. [16] 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. [18] 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 UCF UCF

No No No

Non-rigid Non-rigid Rigid

Yes No No

Solved in [3] Solved in [18] Solved in [25]

UCF

Yes

Lights None Persistent lights One axis and lights

Non-rigid

Yes

This paper

2

Preliminaries

Let r(t) denote the location of robot ri ∈ R at time t, and let R(t) denote the configuration of robots e at time t, defined as the multiset of occupied positions, i.e., R(t) = {r1 (t), r2 (t), · · · , rn (t)}. Let R denote the set of all such robot configurations. Robots operate in repeated Look-Compute-Move cycles under the ASYN C model, and all robots execute the same algorithm. For each robot ri ∈ R, let radR (t) denote the half-line originating at O and passing through r(t) at time t , where O is the centre 3

e denote the set of all circles with finite positive radius, and let Ge denote the set of all of C. Let C e Note that algorithms that solve the uniform circle formation problem over any given circle C ∈ C. e a circle C, and an initial robot configuration R(t0 ). Let pi be Ge ̸= ∅ [14]. Consider an algorithm A ∈ G, the final position of robot ri on C during the execution of A starting from R(t0 ), so that the points {p1 , p2 , . . . , pn } form a regular n-gon. Then there exists t∗ ≥ t0 such that R(t∗ ) = {p1 , p2 , . . . , pn }. Let li (A, C) denote the path traversed by robot ri from ri (t0 ) to pi , and let |li (A, C)| denote its length. Define λC (A, R(t0 )) as the maximum distance traveled by any robot during the execution of A, i.e., λC (A, R(t0 )) = max{|li (A, C)| : ri ∈ R}. A uniform circle formation algorithm Ā ∈ Ge solves the e and R(t0 ) ∈ R. e for all C ∈ C e When MMUCF problem if λC (Ā, R(t0 )) = min{λC (A, R(t0 )) : A ∈ G} f∗ denote the set of all MMUCF algorithms there is no ambiguity, we denote λC (Ā, R(t0 )) by λ∗C . Let G e over C. Bhattacharya et al. [4], and Chen et al. [7] presented centralized deterministic algorithms that solve e These algorithms also solve the problem under the FSYN C model the MMUCF problem over C. f∗ ̸= ∅. 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 ) such that li (A, C) is a straightline segment ri (t0 )pi and λ∗C = |li (A, C)|. Let uR (t) and vR (t) be the nearest and farthest points on C from r(t), respectively; these are the intersection points of C with the line joining 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 R(t0 ), the value of λ∗C is unique. Result 2. [7] Let Ā be an algorithm for the MMUCF problem with λ∗C = ri (t0 )pi . Then either pi = ui (t0 ) or there exists another robot rj (t0 ), j ̸= i, such that λ∗C = rj (t0 )pj .

Figure 1: An illustration of target point set and corresponding assignments: initial positions of six robots r1 , . . . , r6 and the corresponding target set is P = {p1 , . . . , p6 }. Here, λ∗C (R(t0 )) = |r2 p2 | = |r5 p5 | and {r1 , r5 } 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 } and (ii) {r1 → p6 , r2 → p2 , r3 → p4 , r4 → p3 , r5 → p5 , r6 → p1 } Let Cr (t) denote the circle centreed at r(t) with radius λ∗C . Let p(t) and q(t) be the intersection points of Cr (t) with C, and let R(t) be the set of all such intersection points for all robots. A robot position r(t) is called pivotal if λ∗C = r(t)pi . The set of all pivotal robot positions is denoted R′ (t). A subset R∗ (t) ⊆ R′ (t) is called a critical set if it is minimal such that λ∗C (R(t)) > λ∗C (R(t) \ R∗ (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 |P| = k. An assignment of robots to P is a bijection f : R(t) → P. The set P is called the target point set if there 4

exists an assignment f such that λ∗C (R(t)) = max{dist(r(t), f (r(t))) : r(t) ∈ R(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 ∗ , corresponding to λ∗C (R(t)) in the following way: • For each robot position ri (t) ∈ R(t), draw circle Ci (t) having centre at ri (t) and radius λ∗C (R(t)). The circle Ci (t) intersect the circle C at least one point. Let C be the set of all such circles. Let pi (t) and qi (t) be the intersection points between circles Ci (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 R(t). • For each ax ∈ B, do the following: – compute the point set W = {a1 , a2 , . . . , an } such that all ai lies on C, a1 = ax and these points form a regular n-gon. – compute a bipartite graph Gx = (V1 ∪ V2 , E) where V1 = B, V2 = C and there is an edge in E between al ∈ V1 and Cj ∈ V2 iff al lies within or on the circle Cj . – If there is a perfect matching in the graph Gx , then by lemma 2, we can conclude that 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 f∗ , first robots require to compute their the Theorem 2, during the execution of each algorithm A ∈ G 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 R(t) be a configuration for the MMUCF problem on a target circle C with centre O. Suppose there exists a robot rc (t) ∈ R(t) such that rc (t) = O, and rc is a critical robot. Then the corresponding regular target point set on C may not be unique, although the optimal min–max value λ∗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. Proof. Let R = {r1 , . . . , r8 } be a set of robots operating under FSYN C model. Let C be a given circle with O as its centre. Consider an initial configuration R(t0 ) = {r1 (t0 ), . . . , r8 (t0 )} of robots in R as depicted in Figure 2 such that R(t0 ) has two lines of symmetry L1 and L2 . In this case, λ∗C (R(t0 )) = |r5 p1 |. Let A be an optimal assignment algorithm. Algorithm A should have following assignments: r5 → p1 , r6 → p3 , r7 → p5 and r8 → p7 . Now, we argue about the rest of the assignments. Since algorithm A outputs an optimal assignment, the assignments of the robots r1 , r2 , r3 and r4 should belong to the sets {p2 , p8 }, {p2 , p4 },{p4 , p6 }, and {p6 , p8 } respectively. For the robot configuration R(t0 ), the local views of the robots r1 and r3 are symmetric about the line L1 and the local views of the robots 5

Figure 2: Illustration for the proof of Theorem 1. In this symmetric configuration of R = {r1 , r2 , . . . , r8 }, the min-max distance is λ∗C (t0 ) = d(r5 , p1 ) = d(r6 , p3 ) = d(r7 , p5 ) = d(r8 , p7 ). Consequently, the critical robots are r5 , r6 , r7 , and r8 . r2 and r4 are symmetric about the line L2 . This implies that whatever assignment algorithm A makes for the robots r1 and r3 , these two points are images of each other about the line L1 . A similar argument can be made for the assignments of r2 and r4 about the line L2 . Thus, algorithm A assigns r1 and r3 to either p2 and p4 respectively or p8 and p6 respectively. Without loss of generality, suppose r1 and r3 are assigned to p2 and p4 respectively. Then, algorithm A can not assign robot r2 any of the points in {p2 , p4 }. 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 R(t) has k-fold rotational symmetry about the centre O of C if a rotation ρ by angle 2π/k, k ≥ 2, maps R(t) onto itself. For a robot position ri ∈ R(t), the set Orbitri = {ri , ρ(ri ), ρ2 (ri ), . . . , ρk−1 (ri )} is called the rotational orbit of ri under ρ. Theorem 2. In absence of any agreement on the local coordinate systems, the MMUCF problem is unsolvable in FSYN C model for the robots having non -rigid movements, even if robots have common chirality and lights (Fall light model). Proof. Let R = {r1 , r2 , . . . , r6 } 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 R(t0 ) = {r1 (t0 ), r2 (t0 ), . . . , r6 (t0 )} of robots in R as depicted in Figure 3(A) such that (i) R(t0 ) is rotationally symmetric around O with 120o angle of rotation (ii) all the robots are equidistant from O. Consider another configuration R(t) = {r1 (t), r2 (t), . . . , r6 (t)}, t > t0 , of robots in R as depicted in Figure 3(B) such that (i) R(t) is rotationally symmetric around O with 120o angle of rotation (ii) robots r1 , r3 and r5 are equidistant from O and robots r2 , r4 and r6 are equidistant from O (iii) dist(r2 , O) > dist(r1 , O). If we run algorithm proposed in [4], we get (i) for f∗ . R(t0 ), λ∗C (Ā, R(t0 )) = d(p1 , r1 (t0 )) and (ii) for R(t), λ∗C (Ā, R(t)) = d(p′1 , r1 (t0 )), where Ā ∈ G f∗ . First, consider an execution Suppose A is an algorithm which solves the MMUCF problem, i.e., A ∈ G of algorithm A for the initial configuration R(t0 ). In this case, λ∗C = d(p1 , r1 (t0 )). Since R(t0 ) is rotationally symmetric, algorithm A decides to move either all the robots in A at a time or the robots in {r1 , r3 , r5 } at a time or the robots in {r2 , r4 , r6 } at a time. Suppose at the beginning of the execution, algorithm A decides to move r2 , r4 and r6 at a time towards their respective destination points p2 , p4 and p6 respectively. Since the movements of the robots are non-rigid, an adversary can stop robots before 6

(a)

(b)

Figure 3: Illustration for the proof of Theorem 2. (a) A symmetric initial configuration R(t0 ) = {r1 (t0 ), . . . , r6 (t0 )}, where the optimal min-max distance is λ∗C (t0 ) = d(ri (t0 ), pi ) for i = 1, . . . , 6. (b) A symmetric configuration R(t) = {r1 (t), . . . , r6 (t)}, where the optimal min-max distance is λ∗C (t) = d(r1 (t0 ), p′1 ) = d(r3 (t0 ), p′3 ) = d(r5 (t0 ), p′5 ). reaching their destination points. Suppose adversary stops the robots r2 , r4 and r6 at points p2 , p4 and p6 respectively at time t > t0 so that the initial configuration is converted to the configuration R(t) as depicted in Figure 3(B). The value of λ∗C (A, R(t)) is strictly less than the value of λ∗C (A, R(t0 )). If robots compute their final destination points in R(t) considering the value of λ∗C (R(t)), the final destination points of the robots are then changed: for robot ri , the destination point is vi′ , 1 ≤ i ≤ 6. If robots start moving towards these points, then robots travel more than λ∗C (A, R(t0 )) distance i.e., they violate the constraint of the MMUCF problem. Therefore, robots somehow need the access of the value λ∗C (A, R(t0 )). They can do this by any one of the following ways (i) they remember the value of λ∗C (A, R(t0 )) or (ii) they remember locations of their destination points or (iii) remember or recompute their initial configuration R(t0 ). For options (ii) and (iii), robots need to remember some angles and/or distances in the initial configuration R(t0 ). 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 R(t0 ) to R(t) is of constant amount. Thus, they can not recompute or remember the exact value of λ∗C (A, R(t0 )). 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 FSYN C model for the robots having non-rigid movements, even if robots have both axis agreement. Proof. Let R = {r1 , r2 , . . . , r6 } be a set of oblivious robots operating under the FSYN C model. The robots have non-rigid movements and agree on the directions and orientations of both local coordinate axes. Consider an initial configuration R(t0 ), as shown in Figure 4(A). Let P = {p1 , p2 , . . . , p6 } be the optimal 7

(a)

(b)

Figure 4: An illustration in the proof of Theorem 3: (A) In this configuration of R(t0 ) = {r1 (t0 ), r2 (t0 ), . . . , r6 (t0 )}, the min-max distance is λ∗C (R(t0 )) = d(r1 , p1 ) = d(r2 , p2 ). (B) In this configuration of R′ = {r1 (t), r2 (t), r3′ (t), r4′ (t), r5 (t), r6 (t)}, the min-max distance is λ∗C (R(t)) = d(r3′ (t), p1 ) = d(r4′ (t), p2 ). target point set on the given circle C. Suppose that the optimal value satisfies λ∗C (R(t0 )) = d(r1 (t0 ), p1 ) = d(r6 (t0 ), p4 ). Thus, r1 and r6 are critical robots in the initial configuration, since they attain the maximum distance under the optimal assignment. f∗ that solves MMUCF in finite time under this model Suppose that there exists an algorithm A ∈ G without persistent external lights. Since the robots are oblivious, they do not remember the initial configuration, the initial optimal value λ∗C (R(t0 )), or the initial optimal assignment after a Look–Compute– Move cycle. To preserve the initial min–max value,i.e., λ∗C (R(t0 )), 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 λ∗C (R(t0 )) and the set of critical robots computed from the next snapshot may differ from those of R(t0 ). 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 r3 and r4 among the non-critical robots move toward their assigned target points p6 and p3 , 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′ and r4′ be the intermediate positions reached by r3 and r4 , respectively, as shown in Figure 4(B). Let R(t) be the resulting configuration. The adversary chooses the intermediate positions r3′ and r4′ so that, in the current configuration R(t), the optimal value computed from the current snapshot is attained by r3′ and r4′ . Hence, r3′ and r4′ become critical robots with respect to R(t). Let their corresponding target points in the optimal assignment of R(t) be p1 and p2 , respectively. Then d(r3′ , p1 ) = d(r4′ , p2 ) = λ∗C (R(t)). However, before reaching R(t), the robots r3 and r4 have already travelled the positive distances d(r3 (t0 ), r3′ ) and d(r4 (t0 ), r4′ ), respectively. Therefore, if the robots now follow the optimal assignment computed from the current configuration R(t), then the total distances travelled by r3 and r4 become 8

d(r3 (t0 ), r3′ ) + d(r3′ , p1 ) and d(r4 (t0 ), r4′ ) + d(r4′ , p2 ), respectively. By choosing the intermediate positions sufficiently far along the movement segments, the adversary can ensure that d(r3 (t0 ), r3′ ) > λ∗C (R(t0 )) − λ∗C (R(t)) and d(r4 (t0 ), r4′ ) > λ∗C (R(t0 )) − λ∗C (R(t)). Consequently, d(r3 (t0 ), r3′ ) + d(r3′ , p1 ) > λ∗C (R(t0 )) and d(r4 (t0 ), r4′ ) + d(r4′ , p2 ) > λ∗C (R(t0 )). Thus, at least one robot is forced to travel more than the initial min–max optimal value λ∗C (R(t0 )). Now consider the information available to the robots in configuration R(t). Since the robots are oblivious and have no persistent external lights, they cannot determine whether 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 R(t), then, as shown above, some robot travels more than λ∗C (R(t0 )). On the other hand, preserving the initial optimal assignment requires information about R(t0 ), 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 FSYN C 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 ASYN C model. From the initial configuration R(t0 ), every robot computes the optimal min–max value λ∗C , a regular target-point set P, and an optimal assignment fopt (t0 ) : R(t0 ) → P 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 fopt throughout the execution, since robots may observe intermediate configurations after partially completed moves. The preservation mechanism depends on the critical set R∗ (t0 ). 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 D∗ (t0 ). Stationary critical robots normally preserve the target-point set. In the special ct configuration Kmcr , 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 and λ− 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 ASYN C 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. 9

Algorithm 1 MinMaxUniformCircle() — executed independently by every robot r in each Look– Compute–Move cycle Look: r observes the current configuration R(t) and the lights of all robots. 1: if r.light = TargetReached then 2: remain stationary; return ▷ terminal state 3: end if 4: (λ∗C , P, fopt , R∗ (t), κ) ← ClassifyAndPlan(R(t)) ▷ Algorithm 2 5: switch κ do nc : 6: case Kucr ▷ Algorithm 3 7: ProcUCR-NC(r, R(t), λ∗C , P, fopt ) 8: end case c 9: case Kucr : 10: ProcUCR-C(r, R(t), λ∗C , P, fopt ) ▷ Algorithm 4 11: end case all : 12: case Kmcr 13: ProcMCR-ALL(r, R(t), λ∗C , P, fopt ) ▷ Algorithm 5 14: end case ot : 15: case Kmcr 16: ProcMCR-OT(r, R(t), λ∗C , P, fopt ) ▷ Algorithm 6 17: end case ct 18: case Kmcr : 19: ProcMCR-CT(r, R(t), λ∗C , P, fopt ) ▷ Algorithm 7 20: end case io ii : or Kmcr 21: case Kmcr 22: ProcMCR-II-IO(r, R(t), λ∗C , P, fopt ) ▷ Algorithm 8 23: end case 24: end switch 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 R∗ (t0 ) denote the set of critical robots in the initial configuration R(t0 ). 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 R∗ (t0 ). For each critical robot ri∗ ∈ R∗ (t0 ), let p∗i ∈ P be its assigned critical target point. The associated closed ∗ ∗ critical disk is defined by Di (t0 ) = {x ∈ R2 : d(x, p∗i ) ≤ λ∗C } . Thus, Di (t0 ) is the closed disk of radius λ∗C centreed at p∗i . The collective critical region is defined by [ ∗ D∗ (t0 ) = Di (t0 ). ri∗ ∈R∗ (t0 )

Let P ∗ (t0 ) = {p∗i ∈ P : ri∗ ∈ R∗ (t0 )} denote the set of target points reserved for the critical robots and let rj ∈ N(t0 ) be a selected non-critical robot. Define the set of its possible unreserved target points
< by Pj = p ∈ PN (t0 ) : d rj (t0 ), p < λ0 , where PN (t0 ) = P \ P ∗ (t0 ) 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 (Kucr ): A configuration R(t0 ) belongs to Kucr if 10

Table 2: Classification of initial configurations based on the critical set. Class

Defining condition

nc Kucr c Kucr all Kmcr ot Kmcr ct Kmcr ii Kmcr io Kmcr

|R∗ (t0 )| = 1 and the unique critical robot is not at O |R∗ (t0 )| = 1 and the unique critical robot is at O R∗ (t0 ) = R(t0 ) N (t0 ) ∩ D∗ (t0 ) = ∅ and PN (t0 ) \ D∗ (t0 ) ̸= ∅ N (t0 ) ∩ D∗ (t0 ) = ∅ and PN (t0 ) ⊆ D∗ (t0 ) rc ∈ D∗ (t0 ) and pc ∈ D∗ (t0 ) rc ∈ D∗ (t0 ) and pc ∈ / D∗ (t0 )

|R∗ (t0 )| = 1. This class is further divided into the following two subclasses. nc ): A configuration R(t0 ) belongs to (A.1) Unique Non-centre-Critical Configuration (Kucr nc Kucr if the unique critical robot is not located at O. c c (A.2) Unique centre-Critical Configuration (Kucr ): A configuration R(t0 ) belongs to Kucr if the unique critical robot is located at the centre O of the target circle C. nc c Thus, Kucr = Kucr ∪ Kucr .

(B) Multiple-Critical Robot Configurations (Kmcr ): A configuration R(t0 ) belongs to Kmcr if |R∗ (t0 )| ≥ 2. We consider the family out Kmcr = {R(t0 ) ∈ Kmcr : N (t0 ) ̸= ∅ and N (t0 ) ∩ D∗ (t0 ) = ∅} . out Thus, every configuration in Kmcr contains at least one non-critical robot, and every non-critical robot lies outside the collective critical region D∗ (t0 ). We further define in Kmcr = {R(t0 ) ∈ Kmcr : N (t0 ) ∩ D∗ (t0 ) ̸= ∅} . in Thus, a configuration belongs to Kmcr if at least one non-critical robot lies inside or on the boundary of the collective critical region. in For every R(t0 ) ∈ Kmcr , let (rc , pc ) be the deterministically selected robot–target pair satisfying
(rc , pc ) ∈ arg min d rj (t0 ), p . rj ∈N (t0 )∩D∗ (t0 ) p∈PN (t0 )

Thus, rc is a non-critical robot lying in D∗ (t0 ), and pc 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. all (B.1) All-Critical Robot Configuration (Kmcr ): all A configuration R(t0 ) belongs to Kmcr if every robot is a critical robot with respect to the all selected optimal assignment fopt Kmcr = {R(t0 ) ∈ Kmcr : R∗ (t0 ) = R(t0 )} . In this
. Formally, ∗ configuration, d ri (t0 ), fopt (ri ) = λC , for every ri ∈ R(t0 ). Consequently, every target point is reserved for a critical robot, and hence P ∗ (t0 ) = P and PN (t0 ) = ∅. Thus, no non-critical robot exists in this configuration.

11

ot ): (B.2) Outside-Target Type (Kmcr ot A configuration R(t0 ) belongs to Kmcr if there exists at least one unreserved target point p ∈ PN (t0 ) that lies outside the collective critical region D∗ (t0 ). Formally,  ot out Kmcr = R(t0 ) ∈ Kmcr : ∃ p ∈ PN (t0 ) such that p ∈ / D∗ (t0 ) . out Thus, at least one unreserved target point lies outside D∗ (t0 ). Moreover, since R(t0 ) ∈ Kmcr , every non-critical robot lies outside D∗ (t0 ). ct (B.3) Covered-Target Type (Kmcr ): ct A configuration belongs to Kmcr if every unreserved target point lies inside or on the boundary ct out of the collective critical region. Formally, Kmcr = {R(t0 ) ∈ Kmcr : PN (t0 ) ⊆ D∗ (t0 )} . Equivalently, PN (t0 ) \ D∗ (t0 ) = ∅. Thus, every unreserved target point lies inside or on the boundary of D∗ (t0 ), whereas every non-critical robot lies outside D∗ (t0 ). out ot ct Therefore, Kmcr = Kmcr ∪ Kmcr . ii (B.4) Inner-Robot–Inner-Target Type (Kmcr ): ii A configuration R(t0 ) belongs to Kmcr if the selected non-critical robot rc lies in the collective critical region and its closestunreserved target point pc also lies in the same collective critical ii in region. Formally, Kmcr = R(t0 ) ∈ Kmcr : pc ∈ D∗ (t0 ) . Thus, both rc (t0 ) and its closest unreserved target point pc lie inside or on the boundary of D∗ (t0 ). io (B.5) Inner-Robot–Outer-Target Type (Kmcr ): io A configuration R(t0 ) belongs to Kmcr if the selected non-critical robot rc lies in the collective critical region but its closest unreserved target point pc lies outside this region. Formally,  io in ∗ Kmcr = R(t0 ) ∈ Kmcr : pc ∈ / D (t0 ) . Thus, rc (t0 ) lies inside or on the boundary of D∗ (t0 ), whereas its closest unreserved target point pc lies outside D∗ (t0 ). in ii io Therefore, Kmcr = Kmcr ∪ Kmcr . all ot ct ii io So we have Kmcr = Kmcr ∪ Kmcr ∪ Kmcr ∪ Kmcr ∪ Kmcr . nc c all ot ct ii io Thus, Kucr = Kucr ∪ Kucr , and Kmcr = Kmcr ∪ Kmcr ∪ Kmcr ∪ Kmcr ∪ Kmcr . 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.

4.4

States of Robots

To maintain the invariance of the target point set and the optimal assignment fopt 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,  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. 12

Algorithm 2 ClassifyAndPlan(R(t)) 1: Compute λ∗C (Ā, R(t)) and the target-point set P using [4, 7] 2: Compute the selected optimal assignment fopt (one-axis agreement breaks ties among multiple

optima) 3: R∗ (t) ← {ri ∈ R(t) : d(ri (t), fopt (ri )) = λ∗C } 4: if |R∗ (t)| = 1 then nc c 5: return Kucr if the critical robot ̸= O else Kucr 6: else all 7: if R∗ (t) = R(t) then return Kmcr 8: end if 9: Compute D∗ (t), PN (t) ot 10: if ∃ p ∈ PN (t) : p ∈ / D∗ (t) then return Kmcr 11: end if ct 12: if PN (t) ⊆ D∗ (t) and N (t) ∩ D∗ (t) = ∅ then return Kmcr 13: end if 14: Select (rc , pc ) ← arg minrj ∈N (t)∩D∗ (t), p∈PN (t) d(rj (t), p) ii io 15: return Kmcr if pc ∈ D∗ (t) else Kmcr 16: end if

• λ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 remains stationary until the selected candidate robot reaches its target point and displays TargetReached. • λ− 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. ct • ReferenceTrace indicates the special movement used for a configuration in Kmcr . 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 fopt to the points in P. Moreover, in the asynchronous setting with non-rigid movements, robots may observe intermediate configurations. Therefore, the initially computed assignment fopt must be preserved throughout the execution; in particular, no robot may change its assigned target on the basis of an intermediate snapshot. 13

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 fopt (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 fopt depends on the structure of the critical robot set in the initial configuration R(t0 ). 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 fopt 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 λ∗C (R(t0 )) 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 . In this configuration, the critical distance is λ∗C = d(r3 , p2 ) and r2 is a secondary critical robot with secondary critical target position p6 . Definition 2 (Secondary Critical Robot). Let P ∗ be the set of critical target positions. A robot rs ∈ R(t) is called a secondary critical robot if rs is not a critical robot and the circle Ck , centreed at rs with radius λ∗C , contains exactly one target position ps ∈ P \ P ∗ such that d(rs , ps ) < λ∗C . The target position ps is called the secondary critical target position corresponding to rs . The purpose of introducing secondary critical robots is to preserve the invariance of the optimal assignment fopt 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 fopt 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 fopt from changing before the candidate robots settle. Figure 5 illustrates this situation. The robot r3 is a critical robot because its assigned target point p2 is at distance λ∗C from r3 ; hence p2 ∈ P ∗ . The robot r2 is not critical, but the circle Cr2 centreed at r2 with radius λ∗C contains exactly one target point in P \ P ∗ , namely p6 . Therefore, r2 is a secondary critical robot and p6 is its secondary critical target position. If r2 is allowed to move too early or if its target position is not kept fixed, then another candidate robot may be assigned to p6 , which can change the optimal assignment 14

fopt and may violate the min–max bound. Definition 3 (Candidate Robot). Let Rsec (t) denote the set of secondary critical robots, and let Psec (t)
denote their reserved target points. Define Ncan (t) = N (t) \ Rsec (t), Pcan (t) = P \ P ∗ ∪ Psec (t) . A robot rj ∈ Ncan (t) is called a
candidate robot if there exists a target point pj ∈ Pcan (t) such that (rj , pj ) ∈ arg minr∈Ncan (t) d r(t), p . The pair (rj , pj ) is called the corresponding candidate robot–target p∈Pcan (t)

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 −→ TargetReached Secondary critical robot : Off −→ λ− Anchor −→ TargetTrace −→ TargetReached Critical robot : Off −→ λAnchor −→ TargetTrace −→ TargetReached.

4.5.2

Assignment Computation for Kucr

In this subsection, we describe the computation of the optimal assignment fopt for configurations nc c containing exactly one critical robot. According to the classification above, Kucr = Kucr ∪ Kucr . Therefore, the assignment computation is considered separately according to whether the unique critical robot is nc located away from or at the centre O of the target circle C. We first consider configurations in Kucr . 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 = ̸ O be the unique critical robot in an optimal assignment fopt . Let pc be the intersection point of the circumference of C with the ray starting from O and passing through rc . Then, pc ∈ P, where P denotes the optimal target point set. Proof. Let pc ∈ P be the target point assigned to rc . Since rc is critical, d(rc , pc ) = λ∗C . Because rc 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 Ai , then either its assigned target point is the closest boundary point Xi , or there exists another sensor attaining the same value. Since the second case is impossible here, we obtain pc = pc . Hence, pc ∈ P. Further, since rc ̸= O, the point pc is exactly the nearest intersection point of the line through O and rc with the circumference. Observation 2 (Angular rigidity of a unique-critical configuration). Let rc ̸= O be the unique critical robot, and let pc be its reserved target point with d(rc (t0 ), pc ) = λ∗C . The point pc , together with the angular separation 2π/n, uniquely determines the regular target polygon PolyP . If this polygon is rotated about O through any sufficiently small nonzero angle, either clockwise or counter-clockwise, the distance from rc 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 . nc Case-I (Configuration Kucr ). In this scenario, the initial asymmetric configuration R(t0 ) about the line L contains exactly one critical robot, not lying at centre O, say rc and let this line L intersect the circumference of the given circle C at p1 (nearest). Fix an ordering [6], say F of the points in P. Let (p1 , p2 , . . . , pn ) be the sequence of points in P according to F. Let PC be the set of points of the critical robot target positions in P.

Let pi ∈ P \ PC . Draw a circle Cpi of radius λ∗C centreed at pi . Let Rpi (t) be the set of all robot positions lying on or inside the circle Cpi . If the circle Cpi contains a single robot ri , i.e., |Rpi | = 1, then the target position of ri is pi , i.e., ri → pi . If the circle Cpi contains more than one robot, i.e., |Rpi | > 1, then the 15

Figure 6: Illustration of a configuration of six robots r1 , r2 , . . . , r6 . Here, rc = r1 , P ∗ = p1 , and the optimal assignment fopt (ri ) = pi , i = 1, 2, . . . , 6. target positions of all robots in Rpi (t) are computed as follows: Define an order H on Rpi (t) based on the distance between the robots in Rpi (t) and the vertex pi . Let robots rj and rk belong to Rpi (t) with d(rj , pi ) < d(rk , pi ). If either of these two robots is not a secondary critical robot for vertex pi , then the target position of rj is pi , i.e., rj → pi . If either of these two robots is a secondary critical robot, say rk for vertex pi , then the target position of rk is pi , i.e., rk → pi (See Figure 6). If rj , rk ∈ Rpi (t) with d(rj , pi ) = d(rk , pi ) (where the distance is closest to pi ), 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 pi and lie on the circle Cb centreed at pi . Let c1 and c2 be the two intersection points between Cb and C. Consider the set P ∪ {c1 , c2 }. Fix an ordering J of the points in P ∪ {c1 , c2 }. Without loss of generality, suppose that c1 has a higher order in J than c2 . Order the robots in B according to their distances from c1 to break the ties and obtain the original ordering of the robot positions in Rpi (t). Let (rj , pj ) 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 rc for R = {rc , r1 , r2 , r3 , r4 }. The maximum angular sector S23 determines the bisector L, along which the auxiliary point qc and the target point pc are selected. 16

During the execution of the above assignment, each robot changes its light according to its assigned role. When the unique critical robot rc is activated, it changes its light from Off to λAnchor and remains stationary. For a target point pi , if |Rpi (t)| = 1, the selected candidate robot is ri . If |Rpi (t)| > 1 and no secondary critical robot is selected for pi , the candidate robot selected by the ordering H is rj . In either case, the selected candidate changes its light according to Off −→ TargetTrace and moves toward pi . If rk is identified as the secondary critical robot for pi , it changes its light from Off to λ− 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 rk , if one exists, changes its light from λ− Anchor to TargetTrace and moves toward its assigned target point pi . Finally, after every non-critical robot has reached its target, the unique critical robot rc changes its light from λAnchor to TargetTrace and moves toward its assigned critical target point p1 . 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. nc Algorithm 3 ProcUCR-NC(r, R(t), λ∗C , P, fopt ) — configuration Kucr

1: rc ← the unique critical robot; pc ← fopt (rc ) 2: Determine rs (secondary critical robot, Def. 2), if any, and its target ps 3: (rj , pj ) ← candidate–target pair selected by the candidate-selection rule 4: if r = rc then 5: if r.light = Off then 6: r.light ← λAnchor ; remain stationary return 7: end if 8: if every ri ̸= rc displays TargetReached then 9: r.light ← TargetTrace; move toward pc 10: else remain stationary 11: end if 12: else if r = rs then 13: if r.light = Off then 14: r.light ← λ− Anchor ; remain stationary return 15: end if 16: if every candidate robot displays TargetReached then 17: r.light ← TargetTrace; move toward ps 18: else remain stationary 19: end if 20: else if r = rj then 21: r.light ← TargetTrace; move toward pj 22: else 23: remain stationary 24: end if 25: if r reaches its assigned target then r.light ← TargetReached 26: end if

▷ — Light transitions —

▷ not yet eligible

c Case-II (Configuration Kucr ). We consider a configuration having a unique critical robot, denoted by rc , which is located at the centre O of the given circle C; that is, R∗ (t0 ) = {rc } and rc (t0 ) = O. The

17

configuration may be asymmetric or symmetric; in the symmetric case, rc breaks the symetricity. Since rc is located at the centre of C, every point on the circumference of C is at the same distance from rc (t0 ). Therefore, the target point corresponding to rc 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 rc is removed.
Let ρc = minr∈R(t0 ) d rc (t0 ), r(t0 ) . Thus, ρc denotes the minimum distance from the centre-critical r̸=rc

robot rc to any other robot in the initial configuration. Consider the circle Cρc centreed at O with radius ρc . The robot rc 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 Sij . 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 Sij is the direction of the first movement of rc . We choose an auxiliary point qc on L such that 0 < d(O, qc ) < ρc (see Figure 7). In particular, qc can be chosen with d(O, qc ) = ρc /2. This choice ensures that qc lies strictly closer to O than to any other robot position. Hence, when the direction from O to qc is used for fixing the target point of the centre-critical robot, no other robot becomes critical, and the original centre-critical robot rc remains the critical robot. Moreover, qc is chosen so that it does not lie on any line passing through O and another robot position in R(t0 ) \ {rc }. 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 pc be the intersection point of L with the circumference of c. The point pc is chosen as the target point corresponding to the centre-critical robot rc . Once pc is fixed, the remaining target points are placed on c by maintaining equal arc distance 2πh between consecutive target points, where h is the radius of c. Thus, the ambiguity n 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 fopt 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 qc 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 λ∗C (Ā, R(t0 )). c Algorithm 4 ProcUCR-C(r, R(t), λ∗C , P, fopt ) — configuration Kucr

1: rc ← the unique critical robot located at O 2: if r = rc and r.light = Off then 3: Compute ρc , the maximum empty angular sector, its bisector ray L, and qc with d(O, qc ) = δ <

min{ρc , γc } ▷ Lemma 3 4: r.light ← λAnchor ; move toward qc 5: return ▷ every other robot remains stationary during this step 6: end if 7: if r = rc and r has reached qc then nc 8: R(t) now belongs to Kucr with critical target pc fixed by ray L ∗ 9: ProcUCR-NC(r, R(t), λC , P, fopt ) ▷ delegate; rc retains λAnchor until eligible 10: else if r ̸= rc then nc 11: ProcUCR-NC(r, R(t), λ∗C , P, fopt ) ▷ remaining robots follow the Kucr procedure 12: end if During the execution of this case, the centre-critical robot rc first moves slightly away from the centre O in the direction of L. When rc is activated, it changes its light according to Off −→ λAnchor . Let qc be the point on the selected ray L satisfying 0 < d(O, qc ) = δ < ρc . Robot rc moves from O toward qc while 18

retaining λAnchor . Every other robot remains stationary during this movement. Since the destination is at distance δ, rc reaches qc in this movement even under the non-rigid model. By the choice δ < ρc , robot rc remains the unique critical robot after reaching qc . Since qc ̸= O, the resulting configuration belongs nc to Kucr . The ray from O through qc fixes the critical target point pc and consequently the complete target-point set. Moreover, by Corollary 1, this initial movement does not violate the original optimal c nc min–max travel bound. Therefore, the configuration changes according to Kucr −→ Kucr . After this transformation, the candidate robot–target pair (rj , pj ) is selected according to the candidate-selection nc rule defined above. The robots then follow the procedure described for Kucr . In particular, rc retains λAnchor while the candidate and secondary critical robots complete their movements. Finally, after the remaining n − 1 robots have reached their respective target points and display TargetReached, robot rc changes its light from λAnchor to TargetTrace and moves toward pc . Upon reaching pc , 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 R(t) ∈ Kmcr , 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. all Observation 4 (First movement in an all-critical configuration). Let R(t0 ) ∈ Kmcr . 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 Kmcr

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π/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π/n. According to the classification, Kmcr , 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. all Case-I (Configuration Kmcr ). 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.

19

all Algorithm 5 ProcMCR-ALL(r, R(t), λ∗C , P, fopt ) — configuration Kmcr

1: if r.light = Off then 2: r.light ← λAnchor ; remain stationary return 3: end if 4: rj ← selected critical robot(s) by one-axis agreement / symmetry-breaking rule (Case-I, § 4.5) 5: if r = rj (or r ∈ selected symmetric set) then 6: r.light ← TargetTrace; move toward fopt (r) 7: if r reaches its target then r.light ← TargetReached 8: end if 9: else ii 10: remain stationary, retaining λAnchor ▷ once rj moves positively, R(t) → Kmcr ; subsequent

cycles call ProcMCR-II-IO 11: end if

Let rj be a selected critical robot and let p∗j = fopt (rj ) be its assigned critical target point. Robot rj moves along the segment [rj (t0 ), p∗j ], while every unselected critical robot remains stationary. Due to non-rigid movement, rj may be stopped before reaching 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 rj is initially critical,
∗ ∗ d rj (t0 ), pj = λ∗C . Hence, rj (t0 ) lies on the boundary of its closed critical disk Dj (t0 ). After any positive
movement toward p∗j , at some time t1 > t0 , d rj (t1 ), p∗j < λ∗C , and therefore rj becomes non-critical ∗ ∗ with respect to the retained assignment. Moreover, since Dj (t0 ) is convex, [rj (t0 ), p∗j ] ⊆ Dj (t0 ) ⊆ D∗ (t0 ). Consequently, rj (t1 ) ∈ D∗ (t0 ) and p∗j ∈ D∗ (t0 ). Once rj becomes non-critical, its target point p∗j becomes ii an unreserved target point. Thus, the resulting configuration belongs to Kmcr . 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 ii the candidate-selection rule defined above, and the robots follow the procedure for Kmcr .. During the execution of this case, every critical robot changes its light from Off to λAnchor when it is activated. Based on the selection rule described above, the selected critical robot rj changes its light according to λAnchor −→ TargetTrace and starts moving toward its previously assigned critical target point p∗j . Every unselected critical robot retains λ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 rj may be stopped before reaching p∗j . In that case, it retains TargetTrace and continues toward the same target point in each subsequent activation. After making any positive movement, rj becomes non-critical, but its light and assigned target point remain unchanged. The stationary robots continue to display λAnchor and preserve λ∗C and the target-point set. Thus, after all ii the transition Kmcr −→ Kmcr , the moving robot rj continues to execute the candidate-robot procedure ii ∗ for Kmcr . Upon reaching pj , it changes its light according to TargetTrace −→ TargetReached and remains stationary. After every initially selected robot displays TargetReached, the remaining ii robots follow the light and movement procedure specified for Kmcr . Each remaining critical robot retains λ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:

20

Initially selected critical robot rj : Off −→ λAnchor −→ TargetTrace −→ TargetReached ∗ Remaining critical robot ri : Off −→ λAnchor −→ TargetTrace −→ TargetReached. ot Case-II (Configuration Kmcr ). In this configuration, at least one unreserved target point lies outside the collective critical region. Let Pout (t0 ) = {p ∈ PN (t0 ) : p ∈ / D∗ (t0 )} denote the set of such target points. Let (rj , pj ) be selected according to the candidate-selection rule defined above, with the candidate target set restricted to Pout (t0 ). Thus, rj is a non-critical robot closest to an unreserved target point pj lying outside D∗ (t0 ). If more than one robot–target pair has the same minimum distance, the tie is resolved using the one-axis agreement. The selected robot rj moves along the segment [rj (t0 ), pj ], while every other robot remains stationary. If its movement is interrupted because of non-rigidity, it retains the same target point and continues toward pj in each subsequent activation. No other robot is allowed to initiate a movement until rj reaches pj . Once rj reaches pj , the remaining assignment procedure is continued using the fixed target-point set. ot Algorithm 6 ProcMCR-OT(r, R(t), λ∗C , P, fopt ) — configuration Kmcr

1: Pout (t) ← {p ∈ PN (t) : p ∈ / D∗ (t)} 2: (rj , pj ) ← candidate–target pair selected by the candidate-selection rule restricted to Pout (t) 3: rs ← secondary critical robot, if any 4: if r ∈ R∗ (t) then 5: r.light ← λAnchor (if Off); remain stationary until every non-critical robot reaches its

target 6: then r.light ← TargetTrace; move toward fopt (r) 7: else if r = rs then 8: r.light ← λ− Anchor (if Off); remain stationary until all candidates reach targets 9: then r.light ← TargetTrace; move toward its reserved target 10: else if r = rj then 11: r.light ← TargetTrace; move toward pj 12: else 13: remain stationary 14: end if 15: if r reaches its assigned target then r.light ← TargetReached 16: end if

During the execution of this case, every critical robot ri∗ ∈ R∗ (t0 ) changes its light from Off to λAnchor when it is activated and remains stationary. A secondary critical robot rs , if one exists, changes its light from Off to λ− Anchor and also remains stationary. The selected candidate robot rj changes its light according to Off −→ TargetTrace and moves toward the selected target point pj . Every other robot remains stationary while rj displays TargetTrace. If its movement is interrupted because of non-rigidity, rj retains the same light and continues toward pj in each subsequent activation. Upon reaching pj , robot rj changes its light according to 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 rs , if one exists, changes its light from λ− 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 to TargetTrace 21

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.
ct Case-III (Configuration Kmcr ). Let λ0 = λ∗C Ā, R(t0 ) , and let (P0 , fopt ) be the deterministically selected optimal target-point set and assignment at time t0 . In this configuration, every non-critical robot lies outside D∗ (t0 ), whereas every unreserved target point lies inside or on its boundary. Therefore, a candidate robot may enter D∗ (t0 ) 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 P0 and fopt remain invariant throughout all intermediate ASYNC configurations. Before any candidate robot moves, every critical robot changes its light according to Off −→ λAnchor and remains stationary. A secondary critical robot, if one exists, changes its light according to Off −→ λ− Anchor and also remains stationary. Let (rj , pj ) 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. ct Algorithm 7 ProcMCR-CT(r, R(t), λ∗C , P, fopt ) — configuration Kmcr

1: (rj , pj ) ← candidate–target pair selected by the candidate-selection rule; S ← symmetry-equivalent

selected set 2: if r ∈ R∗ (t) then 3: r.light ← λAnchor (if Off); remain stationary until all non-critical robots settle 4: else if r ∈ S and |R∗ (t)| > 2 then ▷ Subcase III(a) 5: r.light ← TargetTrace; move toward pj = fopt (r) ▷ reference = stationary critical robots 6: else if r ∈ S and |R∗ (t)| = 2 then ▷ Subcase III(b) mab +z + + + 7: Recompute mab , ℓab , H , z , dummy point w = 2 8: r.light ← ReferenceTrace; move toward pj = fopt (r), using w to reconstruct P 9: else if r = rs (secondary critical) then 10: r.light ← λ− remain stationary until all candidates reach Anchor (if Off); 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 ← TargetReached ▷ its position now anchors P for all later robots 16: end if Subcase-III(a): More Than Two Critical Robots. This subcase applies when |R∗ (t0 )| > 2. The positions and λAnchor lights of the stationary critical robots determine the original target-point set P0 . Therefore, no dummy point or additional geometric reference is required. Every selected candidate rj ∈ S changes its light according to Off −→ TargetTrace and moves toward its assigned target point pj = fopt (rj ). For every rj ∈ S, once
it makes a positive movement toward pj , at any


time t > t0 after such movement, we have d rj (t), pj = d rj (t0 ), pj − d rj (t0 ), rj (t) < d rj (t0 ), pj < λ0 . Thus, every moving candidate remains non-critical throughout its movement. Since all critical robots remain
∗ stationary, Observation 4 ensures that λC Ā, R(t) = λ0 , P(t) = P0 . 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. Subcase-III(b): Exactly Two Critical Robots. This subcase applies when |R∗ (t0 )| = 2. Let ra∗ and r∗ (t )+r∗ (t ) rb∗ be the two critical robots. As illustrated in Figure 8, let mab = a 0 2 b 0 be the midpoint of the 22

Figure 8: A six-robot configuration with exactly two critical robots, ra∗ = r1 and rb∗ = r6 , and critical distance λ∗C . The midpoint m16 , selected region H + , and dummy point w determine the invariant target-point set P0 . ←−−−−−−→ ←−−→ segment joining them. Define ℓab = ra∗ (t0 )rb∗ (t0 ), L = Omab , where mab ̸= O. The line ℓ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 + . Note that D∗ (t0 ) ∩ H + = ∅. Let z + be the intersection of L with the circumference of C lying in H + . The virtual dummy point + is defined by w = mab2+z . Thus, w lies on L in 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 P0 , 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 or fopt . Each selected candidate rj ∈ S changes its light according to Off −→ ReferenceTrace and moves toward its assigned target point pj = fopt (rj ). 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 + , dummy point w, and target-point set P0 before continuing
toward the same
target point. For every rj ∈ S and every time t during its movement, d rj (t), pj < d rj (t0 ), pj < λ0 . Since the two critical robots remain
stationary, they preserve the optimal min–max value and the original target-point set: λ∗C Ā, R(t) = λ0 , P(t) = P0 . 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 |R∗ (t0 )| = 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 pj , a selected candidate changes its light according to ( TargetTrace −→ TargetReached, if |R∗ (t0 )| > 2, ReferenceTrace −→ TargetReached, if |R∗ (t0 )| = 2. The position pj of the first robot displaying TargetReached fixes the target-point set P0 . The remaining n − 1 target points are placed successively on the circumference of C at an equal angular 23

separation of 2π/n from pj . Equivalently, consecutive target points are separated by an arc distance of 2π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 P0 , excluding the occupied target points. The remaining candidate robots move toward their assigned targets using 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 nc described for Kucr . The light sequences are summarized as follows: Initial candidate, |R∗ (t0 )| > 2 Initial candidate, |R∗ (t0 )| = 2 Remaining candidate Secondary critical robot Critical robot

: : : : :

Off −→ TargetTrace −→ TargetReached Off −→ ReferenceTrace −→ TargetReached Off −→ TargetTrace −→ TargetReached Off −→ λ− Anchor −→ TargetTrace −→ TargetReached Off −→ λAnchor −→ TargetTrace −→ TargetReached.

ii io Case-IV (Configurations Kmcr and Kmcr ). In both configurations, at least one non-critical robot lies ∗ ii inside or on the boundary of D (t0 ). For a configuration in Kmcr , its closest unreserved target point also io lies in D∗ (t0 ), whereas for a configuration in K , that target point lies outside D∗ (t0 ). Accordingly, mcr ( ii PN (t0 ) ∩ D∗ (t0 ), if R(t0 ) ∈ Kmcr , define Padm (t0 ) = io PN (t0 ) \ D∗ (t0 ), if R(t0 ) ∈ Kmcr . io ii , Kmcr Algorithm 8 ProcMCR-II-IO(r, R(t), λ∗C , P, fopt ) — configurations Kmcr ii 1: Padm (t) ← PN (t) ∩ D ∗ (t) if Kmcr else PN (t) \ D∗ (t) 2: (rj , pj ) ← candidate–target pair selected from Ncan (t) ∩ D ∗ (t) and Pcan (t) ∩ Padm (t) 3: rs ← secondary critical robot, if any 4: if r ∈ R∗ (t) then 5: r.light ← λAnchor (if Off); remain stationary until all non-critical robots settle 6: else if r = rs then remain stationary until all candidates 7: r.light ← λ− Anchor (if Off);

reach

TargetReached 8: else if r = rj then 9: r.light ← TargetTrace; move along

[r(t), pj ]

▷ may cross into/out of D∗ (t), target

unchanged 10: else 11: remain stationary 12: end if 13: if r reaches its assigned target then r.light ← TargetReached 14: end if

Before a candidate moves, every critical robot changes its light from Off to λAnchor and remains stationary. The secondary critical robot rs , if it exists, changes its light from Off to λ− Anchor and also remains stationary. Let (rj , pj ) be selected according to the candidate-selection rule defined above, with the eligible robot set restricted to Ncan (t0 ) ∩ D∗ (t0 ) and the candidate target set restricted to Pcan (t0 ) ∩ Padm (t0 ). If several pairs attain the same minimum distance, the tie is resolved using the one-axis agreement. The selected candidate rj changes its light according to Off −→ TargetTrace and moves along [rj (t0 ), pj ]. While rj displays TargetTrace, every other non-critical robot retains Off, and the critical and secondary critical robots retain their respective anchor lights. All of them 24

remain stationary. If the movement is interrupted because of non-rigidity, rj retains TargetTrace and ii continues toward pj in its next activation. No new candidate is selected until rj reaches pj . For Kmcr , both ∗ io ∗ rj (t0 ) and pj lie in D (t0 ). For Kmcr , the robot initially lies in D (t0 ) but leaves this region while moving toward pj ∈ / D∗ (t0 ). In either case, it retains the same target point throughout its movement. Upon reaching pj , robot rj changes its light according to TargetTrace −→ 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 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 nc procedure for Kucr . 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

nc nc Lemma 2 (Invariance of the target-point set for Kucr ). Let R(t0 ) ∈ Kucr have the unique critical robot rc , and let (P0 , fopt ) be the selected optimal solution with value λ0 . If a non-critical candidate rj moves only
toward fopt (rj ) while every other robot remains stationary, then, throughout its movement, λ∗C Ā, R(t) = λ0 , P(t) = P0 . Moreover, fopt remains optimal, R∗ (t) = {rc }, and rj remains noncritical.

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 rc is not located at O, the point pc is its unique
closest point on the circumference of C. Therefore, for every point p on the circumference, d r (t ), p ≥ c 0
d rc (t0 ), pc = λ0 , with equality only for p = pc . We first establish the upper bound. Since r
j moves directly
toward pj , its distance from pj never increases. After any positive movement, d rj (t), pj < d rj (t0 ), pj < λ0 . All other non-critical robots
remain stationary at distances strictly smaller than λ0 from their retained targets, whereas d rc (t), pc = λ0 . Hence, the original target-point set P0 and
the retained assignment fopt remain feasible with maximum ∗ distance λ0 . Consequently, λC Ā, 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 rc must be assigned to some no value
point p satisfying d rc (t), p ≥ λ0 . Thus,
smaller than λ0 is ∗ ∗ feasible, and hence λC Ā, R(t) ≥ λ0 . Combining the two bounds gives λC Ā, R(t) = λ0 . Furthermore, every optimal assignment at value λ0 must assign rc to pc , because pc is the unique circumference point at distance λ0 from rc . Therefore, every optimal regular target-point set contains pc . Once pc is fixed, the remaining n − 1 target points are uniquely determined at angular separations 2π/n. Hence, the target-point set remains P(t) = P0 . The light λ-Anchor keeps the stationary critical robot rc identifiable throughout the candidate movement. Thus, after every non-rigid interruption, robot rj 25

reconstructs the same point pc , the same target-point set P0 , and continues toward the same target pj with light TargetTrace. When rj reaches pj and changes its light to TargetReached, its position provides an additional reference for P0 . The remaining target points can then be computed at angular separations 2π/n, and the next eligible candidate moves with respect to the same invariant target-point set.
Let γc = λ0 − maxri ∈R(t0 )\{rc } d ri (t0 ), fopt (ri ) . Since rc is the unique critical robot, γc > 0. Lemma 3 (centre-critical reduction). Let qc be the point on L satisfying d(O, qc ) = δ, where 0 < δ < min{ρc , γc }. Suppose that rc moves from O toward qc along L, while
every other robot remains stationary. Then, at every intermediate time t satisfying 0 < σt = d O, rc (t) ≤ δ, the target-point set remains P0 , nc rc remains the unique critical robot, and R(t) ∈ Kucr . Proof. Since rc moves only along L, the ray starting from O and passing through rc (t) remains L. Therefore, its intersection with the circumference of C remains pc . Since pc and the angular separation 2π/n uniquely determine the regular target-point set, we have
P(t) = P0 . Let h be the radius of C. Since rc (t0 ) = O and rc is critical, λ0 = h. At time t, d
rc (t), pc = h − σt = λ0 − σt . For every ri ̸= rc , the robot remains stationary and hence d ri (t), fopt (ri ) ≤ λ0 − γc < λ0 − δ ≤ λ0 − σt . Thus, under the retained assignment, rc is the unique robot attaining the maximum distance. Moreover, every point of C is at distance at least h − σt from rc (t), with equality only at pc . Therefore, no assignment can attain a min–max value smaller than h − σt , while the retained assignment attains this value. Hence, it remains optimal and rc remains the unique critical robot. Finally, δ < ρc ensures that the segment nc [O, qc ] contains no other robot. Since rc (t) ̸= O for every σt > 0, we obtain R(t) ∈ Kucr . Corollary 1 (Preservation of the original min–max travel bound). Let s = d(qc , pc ). Since O, qc , and pc are collinear and qc lies between O and pc , δ + s = d(O, qc ) + d(qc , pc ) = d(O, pc ) = h = λ0 . Therefore, the movement through qc only divides the original optimal path of rc into two consecutive segments and does not violate the original min–max travel bound. nc By Lemma 3, after the initial movement of rc , the resulting configuration belongs to Kucr with the same target-point set. Therefore, the remaining execution follows from the correctness of the procedure for nc Kucr . 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 R(t0 ) ∈ Kmcr , and let P0 be the target-point set selected at time t0 . If the robots execute the corresponding procedure described in Cases I–IV, then, at every time t during the execution, P(t) = P0 . Proof. Let t1 be the first time at which a robot displays TargetReached. We first prove that P(t) = P0 for every t < t1 . all Case-I: Kmcr . The unselected critical robots retain λ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 P0 . This requires that the selected robots do not exhaust the complete reference set before one of them reaches its target. ot Case-II: Kmcr . Every critical robot retains λAnchor , and the secondary critical robot, if one exists, retains − λAnchor . All these robots remain stationary while the selected candidate moves. Hence, the reference

26

information used to reconstruct the target-point set remains unchanged, and every intermediate snapshot yields P0 . ct Case-III: Kmcr . If |R∗ (t0 )| > 2, the stationary critical robots displaying λAnchor preserve the prescribed reference information. Therefore, each candidate displaying TargetTrace reconstructs P0 after every interrupted movement. Now suppose that |R∗ (t0 )| = 2. The two critical robots ra∗ and rb∗ remain stationary. Moreover, the selected set S is fixed before any of its members moves and is excluded from the count defining H + . Consequently, the midpoint mab , the region H + , the point z + , and the dummy + point w = mab2+z remain unchanged. Hence, every robot displaying ReferenceTrace applies the same dummy-point reconstruction rule and obtains the same target-point set P0 . ii io Case-IV: Kmcr or Kmcr . 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 D∗ (t0 ) or leaves this region. Thus, the candidate reconstructs the same target-point set P0 throughout its movement. It remains to consider the execution at and after t1 . Let pj be the target occupied by the first robot displaying TargetReached. Since pj ∈ P0 , the point pj together with the angular separation 2π/n uniquely determines the regular target-point set P0 , up to cyclic relabelling. The robot at pj retains TargetReached and remains stationary. Hence, from time t1 onward, every robot reconstructs the target-point set directly from pj , without using the earlier critical or dummy reference. Therefore, P(t) = P0 throughout the complete execution.

4.6.3

Supporting Invariants for Multiple-Critical Configurations

all Lemma 5 (Preservation of the retained optimal solution). Let R(t0 ) ∈ Kmcr \ Kmcr , and let (P0 , fopt ) ∗ be the selected optimal solution with value λ0 = λC (Ā, R(t0 )). Let tc be the first
time at which an initially critical robot starts moving. Then, for every t ∈ [t0 , tc ), λ∗C Ā, R(t) = λ0 , and the retained assignment fopt remains optimal with respect to the invariant target-point set P0 . In particular,
maxri ∈R(t) d ri (t), fopt (ri ) = λ0 .

Proof. Fix any t ∈ [t0 , tc ). By Lemma 4, the target-point set remains P0 throughout this interval. From the critical characterization used in the computation of λ0 , for every admissible regular target-point set P(θ) and every injective assignment g : R∗ (t0 ) → P(θ), we have
∗ ∗ max d r (t ), g(r ) ≥ λ0 . (C) 0 i i ∗ ∗ ri ∈R (t0 )

∗ ∗ Since t < tc ,
every initially critical
robot remains stationary. Therefore, for each ri ∈ R (t0 ), ∗ ∗ ∗ ∗ d ri (t), fopt (ri ) = d ri (t0 ), fopt (ri ) = λ0 . Every initially non-critical robot has assigned distance strictly smaller than λ0 . By the movement procedure, such a robot either remains stationary or
moves
only toward its retained target. Hence, for every r ∈ N (t ), d r (t), f (r ) ≤ d r j 0 j opt j j (t0 ), fopt (rj ) < λ0 .
Consequently, maxri ∈R(t) d ri (t), fopt
(ri ) = λ0 . Thus, the retained solution (P0 , fopt ) remains feasible at ∗ value λ0 , and therefore λC Ā, R(t) ≤ λ0 . Conversely, consider any admissible target-point set P(θ) and any assignment f for R(t). Its restriction to R∗ (t0 ) is an injective assignment. Since the initially critical robots remain stationary, Condition (C) gives

∗ ∗ max d ri (t), f (ri ) ≥ ∗ max d r (t), f (r ) i i ∗ ri ∈R(t)

ri ∈R (t0 )

≥ λ0 .

27

Hence, no solution having value smaller than λ0 exists, and λ∗C Ā, R(t) ≥ λ0 . Combining the two
inequalities yields λ∗C Ā, R(t) = λ0 . Since (P0 , fopt ) attains this value, fopt remains optimal throughout [t0 , tc ). all Lemma 6 (Persistence of the critical set). Let R(t0 ) ∈ / Kmcr , and let tc be the first time at which an initially critical robot starts moving. Then, for every t ∈ [t0 , tc ), R∗ (t) = R∗ (t0 ).

Proof. Let λ0 = λ∗C (Ā, R(t0 )). 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∗ ∈ R∗ (t0
) remains stationary during this interval. Hence, for its reserved target p∗i ,
∗ ∗ d ri (t), pi = d ri∗ (t0 ), p∗i = λ0 . Thus, every initially critical robot remains critical. For every initially non-critical robot rj , its assigned distance is strictly smaller than λ0 . If rj remains stationary, this distance does not change; if it moves, it moves toward its fixed target point, and hence the distance decreases. Therefore, rj 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, R∗ (t) = R∗ (t0 ) for every t < tc . 4.6.4

Persistence of Candidates and Target Reservations

Lemma 7 (Invariance of the assigned target point). Let (rj , pj ) be the candidate–target pair selected at time ts . By the applicable result among Lemmas 2–4, the target-point set remains invariant. Under the movement procedure, rj moves only along [rj (ts ), pj ] and retains its movement light. Then pj remains assigned to rj until rj reaches it. Proof. Let Pav be the set of target points available to rj at time ts . By the candidate-selection rule, d(rj (ts ), pj ) ≤ d(rj (ts ), q) for every q ∈ Pav . At any intermediate time t, there exists α ∈ [0, 1] such that rj (t) = (1 − α)rj (ts ) + αpj . For every q ∈ Pav \ {pj }, we have

d2 rj (t), q − d2 rj (t), pj 

 = (1 − α) d2 rj (ts ), q − d2 rj (ts ), pj + αd2 (pj , q). The first term is non-negative, and the second term is strictly positive whenever α > 0. Hence, after any positive movement, pj is the unique closest available target point of rj . At α = 0, any initial tie is resolved by the prescribed one-axis agreement. If the movement is interrupted, rj 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 rj yields the same target point pj . Consequently, the assignment of rj remains unchanged until it reaches pj . Lemma 8 (Persistence and exclusive reservation of candidate targets). Let (rj , pj ) be a candidate–target pair selected at time ts . Then rj retains pj 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 ) be a candidate–target pair selected at time ts . By the applicable target-set invariance result, the target-point set P remains unchanged throughout the movement of rj . Moreover, by Lemma 7, once rj starts moving toward pj , the point pj remains its assigned target until it is reached. In particular, if the movement is interrupted because of non-rigidity, rj retains TargetTrace, or ReferenceTrace in the corresponding case, and resumes its movement toward the same point pj at its next activation. Hence, the candidate–target pair (rj , pj ) persists until rj reaches pj . Now consider 28

two distinct candidates ri , rj selected from the same snapshot. Since the selected optimal assignment fopt is a bijection, fopt (ri ) ̸= fopt (rj ). Thus, simultaneously selected candidates are assigned distinct target points. Furthermore, once pj is assigned to rj , it remains reserved while rj displays TargetTrace or ReferenceTrace and is therefore excluded from every subsequent candidate selection. When rj reaches pj , it changes its light to TargetReached and remains stationary at pj ; hence, pj 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 ts . Let S denote the set of robots authorized to move during this phase, and let pi be the target assigned to each robot ri ∈ S. By the clear-path rule, the following conditions hold: 1. the assigned targets {pi : ri ∈ S} are pairwise distinct and unoccupied at time ts ; 2. for every ri ∈ S, (ri (ts ), pi ] ∩ {rk (ts ) : rk ∈ / S} = ∅; 3. for any two distinct robots ri , rj ∈ S, [ri (ts ), pi ] ∩ [rj (ts ), pj ] = ∅. 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. 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 or λ− 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 ∈ S collides with a stationary robot rk ∈ / S, then rk (ts ) ∈ (ri (ts ), pi ], contradicting Condition 2. Otherwise, two robots ri , rj ∈ S collide. Their common collision point must then belong to both prescribed movement segments, implying [ri (ts ), pi ] ∩ [rj (ts ), pj ] ̸= ∅, which contradicts Condition 3. Thus, no collision can occur during the phase. In particular, when a robot ri reaches pi , it changes its light to TargetReached and remains stationary there; since pi 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 . 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, 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 ri be a robot selected at time ts , and let pi be its assigned target point. By Lemmas 7 and 8, the pair (ri , pi ) remains unchanged until ri reaches pi . Let Di = d(ri (ts ), pi ). Under the non-rigid 29

movement model, every effective Move of ri either brings it directly to pi or decreases its remaining  Di distance by at least δ. Therefore, ri reaches pi after at most δ 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. nc It occurs only once and transforms the configuration into Kucr , 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 ASYN C scheduler and nonrigid movements, MinMaxUniformCircle() terminates in finite time without collisions, places the robots at the distinct points of P0 , and solves MMUCF optimally with maximum travel distance λ∗C (Ā, R(t0 )). nc c Proof. The classification based on the critical set covers all possible configurations. For Kucr and Kucr , 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 fopt is a bijection, the robots finally occupy all points of P0 . It remains to prove optimality. For each robot ri , let Li denote the total distance travelled by ri 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 )). 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, maxi Li = λ∗C (Ā, R(t0 )). 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 30

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] Daniel Albiero, Angel Pontin Garcia, Claudio Kiyoshi Umezu, and Rodrigo Leme de Paulo. Swarm robots in agriculture. arXiv preprint arXiv:2103.06732, 2021. [2] Levent Bayindir. A review of swarm robotics tasks. Neurocomputing, 172:292–321, 2016. [3] Subhash Bhagat and Krishnendu Mukhopadhyaya. Optimum circle formation by autonomous robots. In Advanced Computing and Systems for Security: Volume Five, pages 153–165. Springer, 2018. [4] Binay Bhattacharya, Mike Burmester, Yuzhuang Hu, Evangelos Kranakis, Qiaosheng Shi, and Andreas Wiese. Optimal movement of mobile sensors for barrier coverage of a planar region. Theoretical Computer Science, 410(52):5515–5528, 2009. [5] Manuele Brambilla, Eliseo Ferrante, Mauro Birattari, and Marco Dorigo. Swarm robotics: a review from the swarm engineering perspective. Swarm Intelligence, 7(1):1–41, 2013. [6] Sruti Gan Chaudhuri and Krishnendu Mukhopadhyaya. Leader election and gathering for asynchronous fat robots without common chirality. J. Discrete Algorithms, 33:171–192, 2015. [7] Danny Z Chen, Xuehou Tan, Haitao Wang, and Gangshan Wu. Optimal point movement for covering circular regions. Algorithmica, 72(2):379–399, 2015. [8] Wendell H Chun and Nikolaos Papanikolopoulos. Robot surveillance and security. springer Handbook of Robotics, pages 1605–1626, 2016. [9] Peter Corke, Ron Peterson, and Daniela Rus. Networked robots: Flying robot navigation using a sensor net. Robotics Research, 2005. [10] X. Défago and A. Konagaya. 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, pages 97–104, New York, NY, USA, 2002. ACM. [11] Xavier Défago and Samia Souissi. Non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformity. Theoretical Computer Science, 396(1-3):97–112, 2008. [12] Giuseppe Antonio Di Luna, Paola Flocchini, S Gan Chaudhuri, Federico Poloni, Nicola Santoro, and Giovanni Viglietta. Mutual visibility by luminous robots without collisions. Information and Computation, 254:392–418, 2017. [13] Giuseppe Antonio Di Luna, Paola Flocchini, Sruti Gan Chaudhuri, Nicola Santoro, and Giovanni Viglietta. Robots with lights: Overcoming obstructed visibility without colliding. In Symposium on Self-Stabilizing Systems, pages 150–164. Springer, 2014. [14] Caterina Feletti, Carlo Mereghetti, and Beatrice Palano. Uniform circle formation for swarms of opaque robots with lights. In International Symposium on Stabilizing, Safety, and Security of Distributed Systems, pages 317–332. Springer, 2018. [15] Caterina Feletti, Debasish Pattanayak, and Gokarna Sharma. Optimal uniform circle formation by asynchronous luminous robots. arXiv preprint arXiv:2405.06617, 2024. 31

[16] Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro. Distributed Computing by Oblivious Mobile Robots. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers, 2012. [17] Paola Flocchini, Giuseppe Prencipe, and Nicola Santoro, editors. Distributed Computing by Mobile Entities, Current Research in Moving and Computing. Springer, 2019. [18] Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Giovanni Viglietta. Distributed computing by mobile robots: uniform circle formation. Distributed Computing, 30(6):413–457, 2017. [19] Paola Flocchini, Giuseppe Prencipe, Nicola Santoro, and Peter Widmayer. Hard tasks for weak robots: The role of common knowledge in pattern formation by autonomous mobile robots. In International Symposium on Algorithms and Computation, pages 93–102. Springer, 1999. [20] Paola Flocchini, Nicola Santoro, Giovanni Viglietta, and Masafumi Yamashita. Rendezvous of two robots with constant memory. In International Colloquium on Structural Information and Communication Complexity, pages 189–200. Springer, 2013. [21] Miquel Kegeleirs, David Garzón Ramos, and Mauro Birattari. Random walk exploration for swarm mapping. In Annual conference towards autonomous robotic systems, pages 211–222. Springer, 2019. [22] Marcello Mamino and Giovanni Viglietta. Square formation by asynchronous oblivious robots. In In Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG), pages 1–6, 2016. [23] Moumita Mondal and Sruti Gan Chaudhuri. Uniform circle formation by swarm robots under limited visibility. In International Conference on Distributed Computing and Internet Technology, pages 420–428. Springer, 2019. [24] H Van Dyke Parunak. Applications of distributed artificial intelligence in industry. Foundations of distributed artificial intelligence, 2, 1996. [25] Debasish Pattanayak and Gokarna Sharma. Time-color tradeoff on uniform circle formation by asynchronous robots. In 2024 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 987–997. IEEE, 2024. [26] Mac Schwager, Brian Julian, and Daniela Rus. Decentralized, adaptive coverage control for networked robots. The International Journal of Robotics Research, 28(3):357–375, 2009. [27] Gokarna Sharma, Ramachandran Vaidyanathan, and Jerry L Trahan. Constant-time complete visibility for asynchronous robots with lights. In International Symposium on Stabilization, Safety, and Security of Distributed Systems, pages 265–281. Springer, 2017. [28] M. Steinberg. Intelligent autonomy for unmanned naval systems. In Proc. Defense and Security Symposium, pages 623013–623013. International Society for Optics and Photonics, 2006. [29] Ichiro Suzuki and Masafumi Yamashita. Distributed anonymous mobile robots: Formation of geometric patterns. SIAM Journal on Computing, 28:pages 1347–1363, 1999. [30] Satoshi Terai, Koichi Wada, and Yoshiaki Katayama. Gathering problems for autonomous mobile robots with lights. arXiv preprint arXiv:1811.12068, 2018.

32

Related documents

• Min-Max Uniform Circle Formation by Asynchronous Mobile Robots#1200659
• A Randomized Scheduling Framework for Privacy-Preserving Multi-robot Rendezvous given Prior Information#665597
• A Randomized Scheduling Framework for Privacy-Preserving Multi-robot Rendezvous given Prior Information#664097
• Inverse kinematic solution for generic 3R positional robots using Conformal Geometric Algebra#819766
• Inverse kinematic solution for generic 3R positional robots using Conformal Geometric Algebra#809770