Paper deep dive
Budget-Constrained Fault-Tolerant Mutual Visibility for Autonomous Robots under the Mobility Fault Model
Prakhar Shukla, Animesh Maiti, Shivam Kumar, Subhash Bhagat
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 90%
Last extracted: 10/6/2026, 9:46:33 AM
Summary
This paper presents a deterministic distributed algorithm for the mutual visibility problem in a swarm of autonomous mobile robots under a budget-constrained mobility fault model. The robots are opaque, luminous, and operate in the semi-synchronous (SSYNC) model with non-rigid movements and no coordinate agreement, relying only on a common fixed reference point. The algorithm ensures that non-faulty robots achieve unobstructed visibility of all robots (including faulty ones) within a finite time, respecting individual movement budgets, avoiding collisions, and using only 12 light colors.
Entities (15)
Relation Signals (11)
Prakhar Shukla → affiliatedwith → Indian Institute of Technology Jodhpur
confidence 95% · Affiliation: Indian Institute of Technology Jodhpur
Animesh Maiti → affiliatedwith → Indian Institute of Technology Jodhpur
confidence 95% · Affiliation: Indian Institute of Technology Jodhpur
Shivam Kumar → affiliatedwith → Indian Institute of Technology Jodhpur
confidence 95% · Affiliation: Indian Institute of Technology Jodhpur
Subhash Bhagat → affiliatedwith → Indian Institute of Technology Jodhpur
confidence 95% · Affiliation: Indian Institute of Technology Jodhpur
This Work → operatesunder → Budget-Constrained Mobility Fault Model
confidence 95% · We investigate the mutual visibility problem... under the budget-constrained mobility fault model.
This Work → solves → Mutual Visibility Problem
confidence 95% · We present a deterministic distributed algorithm that solves the problem despite an arbitrary number of mobility faults.
This Work → uses → 12 Light Colors
confidence 95% · uses only 12 light colors.
This Work → assumes → Reference Point P*
confidence 90% · equipped only with a common fixed reference point P*.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:We investigate the mutual visibility problem for a swarm of $n\ge3$ autonomous mobile robots under the budget-constrained mobility fault model. The robots are opaque, so if three robots are collinear, the middle robot obstructs the visibility between the other two. Each robot is assigned a finite movement budget, reflecting its limited energy, that bounds the total distance it may traverse during the execution. Moreover, an arbitrary number of robots may become permanently immobile due to mobility faults. The objective is to design a distributed algorithm that enables the non-faulty robots to coordinate their movements so that, within a finite time, every non-faulty robot attains unobstructed visibility of all robots in the system, including the faulty ones, while respecting the prescribed movement budget. We consider luminous robots operating under the $\mathsf{SSYNC}$ model with non-rigid movements, without any agreement on their local coordinate systems, and equipped only with a {\it common fixed reference point}. We present a deterministic distributed algorithm that solves the problem despite an arbitrary number of mobility faults. The algorithm guarantees mutual visibility for the non-faulty robots, respects the movement budget of every robot, provides collision-free movements for the robots, and uses only 12 light colors.
Tags
Links
- Source: https://arxiv.org/abs/2610.04402v1
- Canonical: https://arxiv.org/abs/2610.04402v1
Trouble viewing inline? Open PDF directly →
Full Text
79,297 characters extracted from source content.
Expand or collapse full text
Budget-Constrained Fault-Tolerant Mutual Visibility for Autonomous Robots under the Mobility Fault Model Prakhar Shukla Animesh Maiti †thanks: Corresponding author: p22ma201@iitj.ac.in Shivam Kumar Subhash Bhagat Affiliation: Department of Mathematics Affiliation: Indian Institute of Technology Jodhpur Affiliation: Jodhpur, Rajasthan, India Abstract We investigate the mutual visibility problem for a swarm of n≥3n≥ 3 autonomous mobile robots under the budget-constrained mobility fault model. The robots are opaque, so if three robots are collinear, the middle robot obstructs the visibility between the other two. Each robot is assigned a finite movement budget, reflecting its limited energy, that bounds the total distance it may traverse during the execution. Moreover, an arbitrary number of robots may become permanently immobile due to mobility faults. The objective is to design a distributed algorithm that enables the non-faulty robots to coordinate their movements so that, within a finite time, every non-faulty robot attains unobstructed visibility of all robots in the system, including the faulty ones, while respecting the prescribed movement budget. We consider luminous robots operating under the SSYNC model with non-rigid movements, without any agreement on their local coordinate systems, and equipped only with a common fixed reference point. We present a deterministic distributed algorithm that solves the problem despite an arbitrary number of mobility faults. The algorithm guarantees mutual visibility for the non-faulty robots, respects the movement budget of every robot, provides collision-free movements for the robots, and uses only 12 light colors. Keywords: Autonomous mobile robots; Mutual visibility; Mobility faults; Budget-constrained movement; Luminous robots; Semi-synchronous model; Non-rigid movement; Common reference point. 1 Introduction We consider a finite set ℛR of n anonymous, homogeneous, opaque, and luminous point robots deployed in the Euclidean plane. Robots have unlimited visibility, but their line of sight is obstructed by opaque robots. Each robot has its own local coordinate system, with no agreement on the coordinate axes or chirality, and executes the same deterministic algorithm. Communication is achieved only by observing the positions and light colors of visible robots. Robots are oblivious except for persistent lights operating under the FALL model. Each robot is equipped with a persistent light that can assume a color from a finite set shared by all robots. The selected color remains unchanged across subsequent activations until the robot explicitly changes it. Thus, the light serves both as persistent local memory and as a means of communication among the robots. The robots operate under the semi-synchronous ( SSYNC) model. Under the SSYNC model, time is divided into discrete rounds. In each round, the scheduler activates an arbitrary nonempty subset of robots, while the remaining robots stay stationary. All robots activated in the same round simultaneously execute one complete Look–Compute–Move cycle. During the Look phase, each activated robot takes a snapshot containing the positions and light colors of all robots visible to it, together with its own current light color. During the Compute phase, it uses the obtained snapshot to compute a destination point according to the algorithm and may also update its light color. Finally, during the Move phase, the robot moves toward its computed destination. The scheduler is fair, meaning that every robot is activated infinitely often. An epoch is the shortest sequence of consecutive rounds during which every robot is activated at least once. A robot may be activated multiple times within the same epoch. By the fairness of the scheduler, every epoch is finite. Robot movements are non-rigid, i.e., a robot may be stopped before reaching its computed destination after moving at least an unknown positive distance δ. In addition, every robot can detect a common fixed external reference beacon P∗P^* and obtain its relative position in its local coordinate system during each Look phase. Each robot is initially assigned the same finite movement budget B, which bounds the total Euclidean distance it may traverse during the execution. A robot may suffer a mobility fault at any time, after which it becomes permanently immobile while retaining its sensing, computation, and light capabilities. Faulty robots cannot distinguish themselves from fault-free robots. Throughout the paper, we consider the budget-constrained mobility fault model, in which an arbitrary number of robots may become mobility faulty. 1.1 Related Work The mutual visibility problem for autonomous mobile robots was formally introduced by Di Luna et al. [9] in the classical oblivious robot model. Under obstructed visibility, robots are considered opaque, and hence a robot lying on the line segment joining two other robots prevents them from seeing each other. The objective is therefore to transform an arbitrary initial configuration into one in which no three robots are collinear, while avoiding collisions. Di Luna et al. studied the problem for oblivious robots under the SSYNC scheduler and proposed a convex-hull-based solution. Closely related to mutual visibility is the problem of forming a general position. Bhagat et al. [3] studied this problem for asynchronous opaque robots under one-axis agreement and provided a collision-free algorithm that removes collinearities. Early investigations also focused on the efficiency of mutual-visibility algorithms. Sharma et al. [17] analyzed bounds on existing mutual-visibility algorithms, while subsequent work improved the running time for oblivious robots; in particular, Sharma et al. [20] obtained an (n)O(n)-time algorithm in the fully synchronous setting. A major line of research considers the luminous robot model, in which each robot carries a persistent externally visible light whose color can be used both as a small amount of persistent memory and as a means of communication. Di Luna et al. [10] gave fundamental results for this model, showing that mutual visibility can be solved using two colors in the rigid SSYNC setting and three colors in ASYNC; they also considered non-rigid movements and established solutions under additional assumptions such as one-axis agreement. Sharma et al. [18] subsequently studied the number of colors required and obtained color-efficient solutions. In parallel, Vaidyanathan et al. [24] investigated the time complexity of complete visibility and proposed a logarithmic-time algorithm for robots with lights. Sharma et al. [21] further reduced the running time to (1)O(1) rounds in synchronous settings. Bhagat and Mukhopadhyaya [5] considered an energy-oriented variant and proposed an algorithm that restricts the number of movements performed by each robot. For the asynchronous setting, constant-time complete visibility was subsequently obtained by Sharma et al. [22]. Thus, much of the luminous-robot literature has concentrated on reducing either the number of colors, the number of movements, or the overall running time. Mutual visibility has also been investigated under alternative computational models and geometric domains. Bhagat and Mukhopadhyaya [6] considered the FSTATE model, in which robots have a constant amount of persistent internal memory rather than externally visible lights, and showed that one bit of memory is sufficient in the semi-synchronous setting. This direction was further developed by Bhagat [7], who studied optimum mutual visibility with finite-state robots. The problem has also been extended from point robots to robots having physical extent. Sharma et al. [16] studied complete visibility for fat luminous robots, whereas Sharma et al. [19] investigated the corresponding problem for non-transparent fat robots without lights. More recently, Bose et al. [8] considered a more realistic sensing model in which a fat robot is equipped with a slim omnidirectional camera and proposed a mutual-visibility algorithm under the SSYNC scheduler. Another line of work restricts robot movements to discrete environments. Adhikary et al. [1] studied asynchronous luminous robots on an infinite grid, where movements are restricted to grid edges, and Kim et al. [11] subsequently investigated two-color complete-visibility algorithms on the grid under stronger coordinate-agreement assumptions. These results demonstrate that the difficulty of mutual visibility depends strongly on the robots’ geometric representation, movement domain, memory, and degree of coordinate agreement. Fault-tolerant mutual visibility constitutes another important branch of the literature. Aljohani and Sharma [2] considered crash faults and gave a complete-visibility algorithm tolerating a faulty robot under coordinate-agreement assumptions. Poudel et al. [12] studied the more general mobility-fault model, in which a faulty robot loses its ability to move but can continue to execute the other phases of its Look–Compute–Move cycle. Their algorithm works under one-axis agreement and tolerates multiple mobility faults. A different fault model was considered by Sharma [23], where faults affect the lights of the robots rather than their mobility. More recently, Pramanick et al. [13] investigated mutual visibility in the presence of angular inaccuracies in robot movements and also considered the simultaneous presence of mobility faults. Their algorithms work for luminous robots under one-axis agreement and show that mutual visibility can still be obtained despite bounded directional errors. The assumption of a common axis was subsequently relaxed in fault-tolerant settings. Pramanick et al. [14] studied mobility failures for completely disoriented robots, i.e., robots having no agreement on their local coordinate systems. They established fault-tolerant algorithms for multiple faults in the FSYNC setting and for a single fault in the SSYNC and ASYNC settings. More recently, Pramanick et al. [15] further investigated asynchronous fault-tolerant mutual visibility for disoriented robots. Along a different direction, Bhagat et al. [4] studied the min-move mutual visibility problem under the strong combination of disorientation, ASYNC scheduling, and non-rigid movements. They showed that the problem is impossible without additional persistent information and proposed a luminous algorithm in which every robot moves at most once. From the viewpoint of solution techniques, a large fraction of the above algorithms are convex-hull-based: robots progressively expand, contract, or otherwise manipulate the convex hull until all relevant robots occupy suitable hull vertices [9, 10, 24, 21, 18, 22, 16, 19, 14]. Although this approach is powerful, it generally requires robots to travel to geometrically prescribed hull positions and therefore provides limited control over the amount of movement performed by an individual robot. Non-convex-hull techniques instead remove collinearities by carefully selecting local destinations without requiring all robots to become vertices of a common convex hull. Such approaches have been used for general-position formation and movement-efficient mutual visibility [3, 5, 4]. However, existing non-convex-hull solutions either rely on additional coordinate agreement, do not tolerate mobility failures, or address substantially different fault assumptions. To the best of our knowledge, no existing algorithm simultaneously provides a non-convex-hull-based solution for disoriented robots under mobility faults while also enforcing an explicit budget on robot movement. In this paper, we address this gap by studying the mutual visibility problem under a budget-constrained mobility fault model. Our algorithm follows a non-convex-hull strategy and is designed so that the motion of every non-faulty robot remains compatible with the prescribed movement budget. This additional constraint fundamentally distinguishes our setting from earlier mobility-fault algorithms [12, 14, 15]: directly moving robots toward convex-hull vertices may require an arbitrarily large displacement relative to the available budget, and hence the existing convex-hull-based techniques cannot be applied without substantial modification. 1.2 Motivation and Our Contribution We study fault-tolerant mutual visibility under a finite movement budget, where each robot can traverse a total Euclidean distance of at most B. Existing fault-tolerant solutions either rely on one-axis agreement or use convex-hull based relocation strategies. In contrast, we assume no agreement on local coordinate axes or chirality. Instead, every robot can identify a common fixed reference point P∗P^* lying outside the convex hull of the initial configuration. The point P∗P^* provides only a common geometric landmark; it does not induce a common direction, orientation, or coordinate system. We consider a strong fault-tolerant visibility requirement: every non-faulty robot must eventually have unobstructed visibility of every robot in the system, including mobility-faulty robots. We present a deterministic non-convex-hull-based algorithm for luminous robots operating under SSYNC with non-rigid movements. The algorithm uses the relative distances of robots from P∗P^* to coordinate movements and resolve cyclic dependencies. Each movement is chosen using local geometric clearances and the robot’s remaining movement budget, so no robot is required to reach a prescribed distant target. Our algorithm tolerates an arbitrary number of permanent mobility faults, guarantees collision-free movements, respects the movement budget of every robot, uses 1212 light colors, and terminates in O(n)O(n) epochs. Table 1 summarizes the main differences between the existing mutual visibility algorithms under mobility faults and our proposed approach. Table 1: Existing work on mutual visibility algorithms under mobility fault. Reference Faults Scheduler Axis/assumption Colors Time Approach Poudel et al. [12] f ASYNC One-axis agreement 33 O(n)O(n) Non-convex hull Pramanick et al. [15] f ASYNC No axis agreement 3535 O(n)O(n) Convex hull This work f SSYNC Beacon and uniform movement budget 12 () O(n) Non-convex hull 2 Model and Definitions We consider the following robot model and terminologies to design our algorithms: • Robots: Let ℛ=r1,r2,…,rnR=\r_1,r_2,…,r_n\ be a set of n anonymous, homogeneous, autonomous, opaque, and luminous point robots deployed in the Euclidean plane. The robots do not know the value of n, have unlimited visibility range, and communicate only through observations. Due to opacity, if three robots are collinear, then the middle robot obstructs the visibility between the other two. • For two points x and y in the plane, let ‖x−y‖\|x-y\| denote the Euclidean distance between x and y. • Computation Model: Robots execute the Look–Compute–Move cycle under the semi-synchronous ( SSYNC) model with a fair scheduler. Robot movements are non-rigid. There exists a fixed but unknown constant δ>0δ>0 such that, if a non-faulty robot rir_i computes a destination did_i and ‖ri−di‖≤δ,\|r_i-d_i\|≤δ, then it reaches did_i; otherwise, the scheduler may stop it after any displacement in [δ,‖ri−di‖][δ,\|r_i-d_i\|]. Thus, whenever a non-faulty robot computes a destination distinct from its current position, it performs a strictly positive movement. Robots are oblivious except for persistent externally visible lights operating under the FALL model. • Reference Beacon: The robots have access to a common fixed external reference beacon P∗P^*. The beacon is not a robot and is detected through an external localization or beacon-sensing mechanism; hence its detection is not affected by the opacity of the robots. During every Look operation, robot rir_i obtains the relative position of P∗P^* expressed in its current local coordinate system. Thus, P∗P^* provides a common geometric landmark, but does not induce a common coordinate system, axis orientation, handedness, or chirality. We assume that P∗P^* is distinct from every initial robot position and lies strictly outside the convex hull of the initial robot configuration. We henceforth refer to P∗P^* simply as the reference point. • Movement Budget: Each robot is assigned the same finite movement budget B>0B>0, representing the maximum Euclidean distance it may traverse during the execution. At every activation, robot rir_i can locally obtain its current remaining movement budget, denoted by Bi(t)B_i(t). Initially, Bi(0)=B_i(0)=B. Only the distance actually traveled is deducted from Bi(t)B_i(t). Thus, interrupted non-rigid movements consume only the executed portion, while a movement attempt by a mobility-faulty robot that fails to initiate consumes no budget. If ℓi _i denotes the total distance traveled by rir_i, then ℓi≤B _i≤ B. • Mobility Faults: A robot may develop a permanent mobility fault at any stage of the execution. A mobility-faulty robot can continue to perform the Look and Compute phases and update its light, but it can no longer move. Faulty robots cannot distinguish themselves from fault-free robots. In contrast to a non-rigid interruption, a mobility fault may result in zero executed displacement even when the computed destination is different from the robot’s current position. • Configuration: The position of robot rir_i at time t is denoted by ri(t)r_i(t), and its light color by ci(t)c_i(t). The geometric configuration at time t is ℛ(t)=r1(t),r2(t),…,rn(t).R(t)=\r_1(t),r_2(t),…,r_n(t)\. The complete robot configuration is (t)=(ri(t),ci(t)):1≤i≤n.C(t)=\(r_i(t),c_i(t)):1≤ i≤ n\. Thus, ℛ(t)R(t) describes only the robot positions, whereas (t)C(t) also records the persistent light states that govern the execution of the algorithm. A configuration is called linear if all robot positions lie on a single line, and non-linear otherwise. Let R~L R_L and R~NL R_NL denote, respectively, the sets of linear and non-linear geometric configurations. • Collinearity: A line containing at least three robot positions is called a line of collinearity. A robot is non-terminal on such a line if it lies in the interior of the segment joining two other robot positions on the line; otherwise, it is terminal. A non-terminal robot lying on at least two lines of collinearity is called a junction robot. For each robot rir_i, let ℒi0L_i^0 denote the set of initial lines of collinearity containing ri(0)r_i(0). • Visibility: The vision of robot rir_i at time t is the set i(t)V_i(t) consisting of all robot positions visible to rir_i, including its own position. Figure 1: Illustration of adjacent and friend robots. The adjacent robot pairs are (ri,rj)(r_i,r_j), (rj,rk)(r_j,r_k), and (rk,rl)(r_k,r_l). Since rjr_j and rkr_k are non-terminal robots, rir_i and rkr_k are the friend robots of rjr_j, whereas rjr_j and rlr_l are the friend robots of rkr_k. • Adjacent and friend robots: Two robots rir_i and rjr_j are said to be adjacent at time t if they are collinear and no robot lies in the open line segment joining ri(t)r_i(t) and rj(t)r_j(t). Equivalently, they are mutually visible along the line containing them. Furthermore, let rir_i be a non-terminal robot on a line of collinearity ℒL at time t, and let rj(t)r_j(t) and rk(t)r_k(t) lie on the two opposite sides of ri(t)r_i(t) along ℒL, with both robots visible to rir_i. Then rjr_j and rkr_k are called the friend robots of rir_i with respect to ℒL. (see Figure 1) • Cyclic Dependency: A set of lines of collinearity forms a cyclic dependency if consecutive lines intersect at distinct junction robots and the first and last lines also intersect, thereby forming a cycle. The shared junction robots are called critical non-terminal robots. If the first and last lines do not intersect, the collection forms a non-cyclic dependency chain. (see Figure 2) Problem Definition. Let ℛ=r1,…,rnR=\r_1,…,r_n\, n≥3n≥ 3, be a set of robots initially occupying distinct positions in the Euclidean plane. An arbitrary number of robots may suffer permanent mobility faults during the execution. Let ℛNF(t)R_NF(t) denote the set of non-faulty robots at time t. The budget-constrained strong fault-tolerant mutual visibility problem requires that, from every admissible initial configuration, there exists a finite time T such that every non-faulty robot has unobstructed visibility of every other robot in the system. Formally, for every ri∈ℛNF(T)r_i _NF(T) and every rj∈ℛ∖rir_j \r_i\, int(ri(T)rj(T)¯)∩(ℛ(T)∖ri(T),rj(T))=∅.int\! ( r_i(T)r_j(T) )∩ (R(T) \r_i(T),r_j(T)\ )= . Moreover, if ℓi _i is the total Euclidean distance traversed by rir_i, then ℓi≤Bfor every ri∈ℛ. _i≤ B\ for every r_i . Thus, unlike the standard fault-tolerant mutual visibility problem, a non-faulty robot must eventually see not only every non-faulty robot but also every mobility-faulty robot. (a) (b) Figure 2: Illustration of cyclic dependencies: (a) a cyclic configuration involving four non-terminal robots, where the black robots are faulty, and (b) a cyclic dependency involving multiple critical non-terminal robot positions. 3 Algorithm Mutual-Visibility-Mobility-Fault() The algorithm consists of four logical stages encoded by the light colors. These stages need not start or terminate simultaneously for all robots. In particular, a robot never needs to infer that a phase has been completed by all robots in the system. Instead, it advances according to its own light state and the states of the visible robots on which its current movement depends. Such robots are adjacent or friend robots and hence are visible by definition. Therefore, all state transitions used by the algorithm are locally detectable. 3.1 Computation of destination point Before describing the four phases, we define the destination computed by an eligible robot. Let desti(t)dest_i(t) denote the destination of robot rir_i at time t. Its destination is determined by a movement direction DIRi(t)DIR_i(t) and a displacement σi(t) _i(t). The construction below guarantees that the movement respects the remaining budget, avoids collisions, and prevents the creation of collinearities among robots that were initially non-collinear. We first define a few terms needed to compute the destination points of the robots. • Let ri(t)r_i(t) and rj(t)r_j(t) be two distinct robot positions in ℛ(t)R(t). We denote the straight line joining these two robot positions by ℒij(t)L_ij(t). • Let ri(t)r_i(t), rj(t)r_j(t) and rk(t)r_k(t) be three non-collinear robot positions in ℛ(t)R(t). We denote the perpendicular distance of the line ℒij(t)L_ij(t) from the point rk(t)r_k(t) by dijk(t)d^k_ij(t). • For every robot position rm(t)∈Vi(t)∖ri(t)r_m(t)∈ V_i(t) \r_i(t)\, let Lm∗(t)L_m^*(t) denote the line passing through rm(t)r_m(t) and the reference point P∗P^*. Whenever ri(t)∉Lm∗(t)r_i(t)∉ L_m^*(t), define di,mP∗(t)=dist(ri(t),Lm∗(t)).d^P^*_i,m(t)=dist (r_i(t),L_m^*(t) ). Suppose that ℛ(t)∈ℛNLR(t) _NL. Define i(t)=di,mP∗(t):rm(t)∈Vi(t)∖ri(t),ri(t)∉Lm∗(t)D_i(t)= \d^P^*_i,m(t):r_m(t)∈ V_i(t) \r_i(t)\,\ r_i(t)∉ L_m^*(t) \ ∪dijk(t),dikj(t),djki(t):rj(t),rk(t)∈Vi(t)∖ri(t),ri(t),rj(t),rk(t) are non-collinear. ∪ \d^k_ij(t),d^j_ik(t),d^i_jk(t):r_j(t),r_k(t)∈ V_i(t) \r_i(t)\,\ r_i(t),r_j(t),r_k(t) are non-collinear \. We define di(t)=mini(t),if i(t)≠∅,+∞,if i(t)=∅.d_i(t)= cases _i(t),&if D_i(t)≠ ,\\[2.84526pt] +∞,&if D_i(t)= . cases Thus, whenever finite, di(t)d_i(t) is the minimum perpendicular clearance induced by the relevant lines considered in the destination construction. • Let ri(t)r_i(t) be a robot positions. Let NTi(t)NT_i(t) be the set of non-terminal robot positions visible to rir_i such that NTi(t)= NT_i(t)= \ rk(t)∈Vi(t)∖ri(t): r_k(t)∈ V_i(t) \r_i(t)\: rk(t) is non-terminal and r_k(t) is non-terminal and P∗∉Lik(t). P^*∉ L_ik(t)\, \. For every rk(t)∈NTi(t)r_k(t)∈ NT_i(t), the line Lik(t)L_ik(t) joining ri(t)r_i(t) and rk(t)r_k(t) divides the plane into two open half-planes. Let HPik+(t)HP^+_ik(t) denote the open half-plane containing P∗P^*. Let HPik+HP^+_ik be the open half plane that contains P∗P^*. Define the safe region of rir_i by Regi(t)=⋂rk(t)∈NTi(t)HPik+(t).Reg_i(t)= _r_k(t)∈ NT_i(t)HP^+_ik(t). If NTi(t)=∅NT_i(t)= , we set Regi(t)=ℝ2Reg_i(t)=R^2. For every rk(t)∈NTi(t)r_k(t)∈ NT_i(t), the segment from ri(t)r_i(t) toward P∗P^* locally enters HPik+(t)HP^+_ik(t); hence a direction toward P∗P^* is contained in the corresponding safe side. Direction of movement. We distinguish the direction used in Phase I from the radial direction used in Phases I–IV. For a Phase I movement, When ℛ(t)∈ℛNLR(t) _NL, let xix_i be any point in Regi(t)Reg_i(t) such that the segment ri(t)xi¯ r_i(t)x_i does not lie on any line Lik(t)L_ik(t), where rk(t)∈Vi(t)∖ri(t).r_k(t)∈ V_i(t) \r_i(t)\. Define iI(t)=xi−ri(t)‖xi−ri(t)‖.u^I_i(t)= x_i-r_i(t)\|x_i-r_i(t)\|. If ℛ(t)∈ℛLR(t) _L and ℒ0L_0 denotes the current line containing all robot positions, let ℒ0⟂L_0 be the line perpendicular to ℒ0L_0 at ri(t)r_i(t), and choose an arbitrary point yi∈ℒ0⟂∖ri(t)y_i _0 \r_i(t)\. Define iI(t)=yi−ri(t)‖yi−ri(t)‖.u^I_i(t)= y_i-r_i(t)\|y_i-r_i(t)\|. For every radial movement in Phases I–IV, define ρi(t)=‖ri(t)−P∗‖ _i(t)=\|r_i(t)-P^*\| and iR(t)=P∗−ri(t)ρi(t).u^R_i(t)= P^*-r_i(t) _i(t). Thus, iR(t)u^R_i(t) is the unit vector directed from ri(t)r_i(t) towards the reference point P∗P^*. The amount of displacement: Let Di(t)D_i(t) denote the minimum distance of any two robot positions in ri(t),i(t)\r_i(t),V_i(t)\. Let Bi(t)B_i(t) denote the remaining movement budget locally available to robot rir_i at time t. The amount of displacement of rir_i at time t is denoted by σi(t) _i(t) and it is defined as follows, For a Phase I movement, σi(t)=134mindi(t),Di(t),Bi(t),ℛ(t)∈ℛNL,134minDi(t),Bi(t),ℛ(t)∈ℛL. _i(t)= cases 13^4 \d_i(t),D_i(t),B_i(t)\,&R(t) _NL,\\[5.69054pt] 13^4 \D_i(t),B_i(t)\,&R(t) _L. cases For a radial movement toward P∗P^* in Phases I–IV, σi(t)=134mindi(t),Di(t),Bi(t),ρi(t),ℛ(t)∈ℛNL,134minDi(t),Bi(t),ρi(t),ℛ(t)∈ℛL. _i(t)= cases 13^4 \d_i(t),D_i(t),B_i(t), _i(t)\,&R(t) _NL,\\[5.69054pt] 13^4 \D_i(t),B_i(t), _i(t)\,&R(t) _L. cases The quantity σi(t) _i(t) is computed to keep the total movements of each robot within budget and also to avoid the creation of new collinearities with those robots which are not initially collinear. For every radial movement, σi(t)<ρi(t) _i(t)< _i(t); hence the computed destination lies strictly in the interior of the segment joining ri(t)r_i(t) and P∗P^*, and the robot neither reaches nor crosses the reference point. Destination point. The destination of an eligible robot rir_i is defined according to the phase in which it moves: desti(t)=ri(t)+σi(t)iI(t),in Phase I,ri(t)+σi(t)iR(t),in Phases I–IV.dest_i(t)= casesr_i(t)+ _i(t)u^I_i(t),&in Phase I,\\[5.69054pt] r_i(t)+ _i(t)u^R_i(t),&in Phases I--IV. cases For a radial movement, σi(t)≤ρi(t)34<ρi(t). _i(t)≤ _i(t)3^4< _i(t). Hence, desti(t)∈int(ri(t)P∗¯),dest_i(t) ( r_i(t)P^* ), so the robot moves strictly towards P∗P^* without reaching or crossing the reference point. 3.2 Algorithm Description Initially, all the robots have the lights off. During Phase I, both terminal and non-terminal robots move to break initial collinearities. During Phase I and Phase I, only non-terminal robots move to break newly created collinearies, including the cyclic dependencies, and during Phase IV, only terminal robots move to break newly created collinearities with faulty non-terminal robots. Phase I (Both terminal and non-terminal robots move): Let rir_i, rjr_j, rkr_k, rlr_l and rmr_m be collinear robots on a line ℒL such that robots rir_i and rmr_m are terminal, other robots are non-terminal, rjr_j is adjacent to rir_i, and rlr_l is adjacent to rmr_m. As the terminal robots move first, initially only rir_i and rmr_m are eligible to move. Without loss of generality, let us consider the following order of activations of the robots: rir_i is activated first, followed by rjr_j, then rmr_m is activated, followed by rlr_l, and lastly rkr_k is activated. Upon activation, robot rir_i turns its light moving-1 and moves. The moving-1 keeps the information that robot rir_i has made its initial move. In the next activation, robot rir_i finds itself as the terminal robot with light moving-1 and changes its light to moved-T-1 to let others know that it is currently a terminal robot that has made its initial movement. Now, after the initial movement of rir_i, robot rjr_j may become terminal or may remain non-terminal (due to a fault in rir_i). If rjr_j becomes terminal, then it acts like rir_i. Otherwise, rjr_j finds one of its friends with light move-T-1 (rir_i and rkr_k are friends of rjr_j) has light moved-T-1. We allow robot rjr_j to move while changing its light to moving-1. If it becomes terminal, it changes its light to move-T-1. Otherwise, it changes its light to move-NT-1 to indicate that it is currently a non-terminal robot that has made its initial movement. Now suppose that both rjr_j and rlr_l are initially faulty. According to the activation schedule and moving rule, when rkr_k becomes active, it finds both of its friends with light moved-NT-1, this let rkr_k know that all the collinear robots on ℒL have moved. We allow the robot rkr_k to move like a non-terminal robot. Now, a non-terminal robot may find one of its friends as moved-T-1 and another as moved-NT-1. In this case also, we allow the non-terminal robot with the light off to move. During Phase I, every eligible robot computes its destination according to Section 3.1 and moves toward it. We summarize these movement strategies as follows: r_i is a physically terminal robot: The robot rir_i finds itself as a physically terminal robot and 1. its light is off: it changes its light to moving-1 and moves. 2. its light is moving-1: it changes its light to moved-T-1 and does not move. r_i is a physically non-terminal robot: Robot rir_i finds itself as a physically non-terminal robot and 1. its light is off, and at least one friend robot in each friend-pair of rir_i has light moved-T-1 or moved-NT-1: it changes its light to moving-1 and moves. 2. its light is moving-1: it changes its light to moved-NT-1 and does not move. After completing its Phase I action, every robot has light either moved-T-1 or moved-NT-1. A robot proceeds to its next logical stage according to its own light state and the states of the visible robots on which its subsequent action depends; no global Phase I completion test is required. The movements performed by the robots during Phase I satisfy several useful properties. For ease of presentation, we first state these properties, without proofs, as observations to facilitate understanding of the algorithm. Lemma 1. During the whole execution of Phase I, each non-faulty robot moves exactly once. Proof. A robot with light off performs at most one Phase I movement, because after moving it changes its light to moving-1 and then to either moved-T-1 or moved-NT-1. To show existence, observe that terminal robots are eligible immediately, and their completed movements make the adjacent non-terminal robots eligible. Repeating this argument propagates eligibility from the two ends of every initial line towards its interior. By fairness, every non-faulty robot is eventually activated when eligible and hence performs exactly one Phase I movement. ∎ Lemma 2. During the whole execution of Phase I, at most two robots from the same initial line of collinearity move in a single round. Proof. According to movement strategies of Phase I, on any line of collinearity, eligibility propagates from its two terminal ends towards the interior. Initially, only the two terminal robots can move. After a robot completes its Phase I movement, at most its next non-terminal neighbor on that side can become eligible. Since all robots activated in an SSYNC round compute from the same pre-movement configuration, eligibility cannot propagate by more than one position from either end in the same round. Hence, at most two robots from a line of collinearity move in any round. ∎ Lemma 3. Let ri,rj,rkr_i,r_j,r_k be three robots that are non-collinear in the initial configuration. Then they remain non-collinear throughout Phase I. Proof. We prove the claim by induction over the rounds of Phase I. Suppose that ri,rj,rkr_i,r_j,r_k are non-collinear immediately before some round, and let h>0h>0 denote the minimum altitude of the triangle △rirjrk r_ir_jr_k at that time. We first show that every robot among ri,rj,rkr_i,r_j,r_k that moves in this round is displaced by less than h/2h/2. Consider robot rir_i. If both rjr_j and rkr_k are visible to rir_i, then the three altitudes of △rirjrk r_ir_jr_k are among the distances considered in the computation of di(t)d_i(t). Hence, di(t)≤h.d_i(t)≤ h. Since the configuration is non-linear, the destination construction gives σi(t)≤di(t)34≤h34<h2. _i(t)≤ d_i(t)3^4≤ h3^4< h2. Now suppose that one or both of rj,rkr_j,r_k are not visible to rir_i. Let r^j r_j and r^k r_k be the first visible robots on the segments rirj¯ r_ir_j and rirk¯ r_ir_k, respectively; if rjr_j (respectively, rkr_k) is visible, take r^j=rj r_j=r_j (respectively, r^k=rk r_k=r_k). There exist α,β∈(0,1]α,β∈(0,1] such that r^j−ri=α(rj−ri),r^k−ri=β(rk−ri). r_j-r_i=α(r_j-r_i), r_k-r_i=β(r_k-r_i). Let A be the area of △rirjrk r_ir_jr_k, and let M=max|rirj|,|rirk|,|rjrk|.M= \|r_ir_j|,\,|r_ir_k|,\,|r_jr_k|\. Then h=2AM.h= 2AM. Let h h be the minimum altitude of △rir^jr^k r_i r_j r_k, and let M M be the length of its longest side. Since its area is αβAαβ A, h^=2αβAM^. h= 2αβ A M. Furthermore, αβM αβ M ≤αβ(|rirj|+|rirk|) ≤αβ (|r_ir_j|+|r_ir_k| ) ≤α|rirj|+β|rirk|≤2M^. ≤α|r_ir_j|+β|r_ir_k|≤ 2 M. Therefore, h^≤2h. h≤ 2h. Since r^j r_j and r^k r_k are visible to rir_i, the altitudes of △rir^jr^k r_i r_j r_k are considered in the computation of di(t)d_i(t). Thus, di(t)≤h^≤2h,d_i(t)≤ h≤ 2h, and consequently σi(t)≤di(t)34≤2h34<h2. _i(t)≤ d_i(t)3^4≤ 2h3^4< h2. The same argument applies to rjr_j and rkr_k. A robot that is not activated or is mobility-faulty has displacement zero, and a non-rigid interruption can only decrease the displacement. Therefore, irrespective of which subset of the three robots is activated in the round, each of them is displaced by less than h/2h/2. Suppose, for contradiction, that after these simultaneous movements the three robots become collinear on a line ℓ . Since the new position of each robot lies on ℓ and its displacement is less than h/2h/2, each of the three positions before the round is at perpendicular distance less than h/2h/2 from ℓ . Hence the entire triangle △rirjrk r_ir_jr_k before the round is contained in an open strip of width strictly smaller than h whose axis is ℓ . This is impossible: the minimum width of a triangle is equal to its minimum altitude, which is h. Thus ri,rj,rkr_i,r_j,r_k remain non-collinear after the round. Since they are non-collinear initially, induction over all Phase I rounds proves that they remain non-collinear throughout Phase I. ∎ Lemma 4. If an initial line of collinearity persists at the end of Phase I, then every robot lying on that line is mobility-faulty. Proof. By Lemma 1, every non-faulty robot initially on the line performs a positive movement in a direction different from the line and hence leaves it. Moreover, by Lemma 2, no robot initially outside the line can move onto it and become collinear with two robots initially on the line. Thus, any robot lying on an initial line at the end of Phase I must be mobility-faulty. ∎ Lemma 5. During Phase I, every newly created line of collinearity contains exactly three robot positions, all of which were collinear in the initial configuration. Moreover, at least one of these robots is terminal. Proof. Let ℒ′L be a line of collinearity created during Phase I. By Lemma 3, robots that were not collinear in the initial configuration cannot become collinear during Phase I. Hence, all robots on ℒ′L originate from the same initial line of collinearity ℒL. By Lemma 2, at most two robots of ℒL can move in the same round. Moreover, the destination construction prevents a moving robot from reaching a line already determined by two stationary robots. Therefore, ℒ′L cannot contain more than three robot positions; since it is a line of collinearity, it contains exactly three. Finally, Phase I eligibility propagates from the terminal ends of ℒL towards its interior. Thus, any new collinearity is created by the current frontier movement(s) together with a robot already exposed on one of these fronts. By the Phase I movement order, at least one of the three robots is terminal. Moreover, if all robots of the newly created collinearity are non-faulty, then at least one of them belongs to the unprocessed part of the corresponding propagation front and has not yet performed its Phase I movement. ∎ Lemma 6. Every newly created line of collinearity that persists at the end of Phase I contains at least one mobility-faulty robot. Proof. Let ℒ′L be a newly created line of collinearity that persists at the end of Phase I. By Lemma 5, ℒ′L contains exactly three robots originating from the same initial line of collinearity ℒL, and at least one of them is terminal. Suppose, for contradiction, that all three robots on ℒ′L are non-faulty. Phase I eligibility on ℒL propagates from its terminal ends towards the interior. Hence, when an all-non-faulty new collinearity ℒ′L is created by the current frontier movement(s), at least one robot r on ℒ′L belongs to the unprocessed part of the corresponding frontier and has not yet performed its Phase I movement. The robots preceding r on that frontier eventually display a Phase I completion color. Consequently, r either becomes terminal or satisfies the friend-pair eligibility condition. Since r is non-faulty and the scheduler is fair, it is eventually activated while eligible and performs its positive Phase I movement. By the destination construction, its movement direction does not coincide with its current line of collinearity; hence r leaves ℒ′L . Therefore, ℒ′L cannot persist until the end of Phase I, a contradiction. Thus, if a newly created line of collinearity persists at the end of Phase I, at least one of its robots must be mobility-faulty. ∎ Lemma 7. At the end of Phase I, all non-faulty non-terminal robots are mutually visible. Proof. Suppose, for contradiction, that two non-faulty non-terminal robots rir_i and rjr_j are not mutually visible at the end of Phase I. Then some robot rkr_k lies in the interior of rirj¯ r_ir_j, and hence ri,rk,rjr_i,r_k,r_j lie on a line of collinearity ℒL. The line ℒL cannot be a persisting initial line of collinearity, since by Lemma 5 every robot lying on such a line at the end of Phase I is mobility-faulty, whereas rir_i and rjr_j are non-faulty. Hence, ℒL must be a newly created line of collinearity. By Lemma 4, ℒL contains exactly three robots and at least one of them is terminal. However, rir_i and rjr_j are non-terminal by assumption, and rkr_k is also non-terminal since it lies in the interior of rirj¯ r_ir_j. Thus all three robots on ℒL are non-terminal, contradicting Lemma 5. Therefore, every pair of non-faulty non-terminal robots is mutually visible at the end of Phase I. ∎ Lemma 8. If two non-faulty terminal robots are not mutually visible at the end of Phase I, then there is a faulty non-terminal robot that lies in between them. Proof. Let rir_i and rjr_j be two non-faulty terminal robots that are not mutually visible at the end of Phase I, and let rkr_k lie between them. By Lemma 4, their line cannot be a persisting initial line of collinearity; hence it is newly created. By Lemma 5, this line contains exactly three robots, and by Lemma 6, at least one of them is mobility-faulty. Since rir_i and rjr_j are non-faulty, rkr_k must be mobility-faulty. Moreover, as rkr_k lies between rir_i and rjr_j, it is non-terminal. ∎ Phase I (Only non-faulty non-terminal robots move): During this phase, every non-faulty non-terminal robot moves to break the newly created collinearities during Phase I. Let us consider a non-faulty non-terminal robot rir_i on a line of collinearity ℒL. Then, by Lemmas 5– 6 above, ℒL is a new line of collinearity created in Phase I, and at least one of its friends on ℒL is a faulty robot. If the other friend is a terminal robot or a faulty non-terminal robot, then if it moves, it breaks the collinearity on ℒL, since terminal robots do not move in this phase. Now, if the other friend is a non-faulty non-terminal robot, then this robot and rir_i move simultaneously in the same round, and rir_i may remain collinear after the movements. If these robots are part of any cyclic dependency, then this process may continue. In order to break a cyclic dependency, we move robots in some order. If robots move in some order, then the cyclic dependency breaks down, and further movements of the robots will break the remaining dependencies in that cycle (this part is achieved during Phase I). We obtain a partial ordering of the movements of the non-faulty non-terminal robots using their radial distances ρi(t) _i(t) from the reference point P∗P^*, and move the farthest eligible non-terminal robot first among those that have not yet completed their Phase I movement. We obtain a partial ordering of movements of the non-faulty non-terminal robots (faulty robots may not see all faulty non-terminal robots) by using their relative distances from the reference point, and we move the farthest non-terminal robot first among the non-terminal robots that have not moved yet in Phase I. Robots use their lights to communicate whether they have moved in Phase I or not (see below). The Phase I ordering does not require all non-faulty non-terminal robots to observe the same global set of candidates. It is sufficient to compare robots that are directly dependent. In particular, two consecutive critical non-terminal robots of a cyclic dependency are friends on a common line of collinearity and hence are mutually visible. Therefore, if two such robots rir_i and rjr_j have ‖ri−P∗‖>‖rj−P∗‖,\|r_i-P^*\|>\|r_j-P^*\|, then rjr_j cannot be eligible while rir_i still has light moved-NT-1, since rjr_j observes the farther unprocessed robot rir_i. Hence, simultaneously eligible dependent robots must have the same distance from P∗P^*. Now consider the case when all the non-terminal robots in a cyclic dependency are at the same distance l from P∗P^*. Then these points lie on a circle of radius l centered at P∗P^*(see Fig. 3(a)). Now, according to our distance rule, all of these robots are eligible to move in the same round. If they all move in the same round, their cyclic dependency may remain intact even after their movements. We move them along the line segment joining their respective current position and P∗P^* (this helps us in Phase I). However, due to these movements, one of the following will happen: either a non-terminal robot becomes terminal (when it and its friend move the same distance)(see Fig. 3(b)) or they remain cyclic dependent without all lying on the same new circle having P∗P^* as center. In the second case, it can be easily shown that all these robots are at distinct distances from P∗P^*(see Fig. 3(c)), and in Phase I, these robots move one by one according to their distances from P∗P^*, and non-faulty non-terminal robots become terminal robots at the end of Phase I. During the Phase I, a non-terminal robot uses three colors for their lights: (i) moving-2 to indicate that it has completed its movement in Phase I, (i) if after the movement in Phase I, it remains non-terminal, it uses moved-NT-2 to indicate that after the movement in Phase I, they are still non-terminals, and (i) if after the movement in Phase I, it becomes a terminal robot, it uses moved-T-2 to indicate that after the movement in Phase I, it has become terminal. In Phase I, only the robots with light moved-NT-2 move. During Phase I, each eligible non-faulty non-terminal robot rir_i moves towards the destination desti(t)dest_i(t) lying in the interior of the line segment joining ri(t)r_i(t) and P∗P^*, as defined in Section 3.1. We formally define the movement rules for the non-terminal robots as follows: rir_i is a robot with light moved-NT-1: 1. If rir_i is currently terminal, it changes its light to moved-T-2 without moving. 2. If rir_i is currently non-terminal and is farthest from P∗P^* among all the visible robots with light moved-NT-1, then it changes its light to moving-2 and moves toward its computed destination point on the line segment joining rir_i and P∗P^*. 3. If rir_i has light moving-2, then, upon its next activation, it changes its light to moved-T-2 if it is currently terminal, and to moved-NT-2 otherwise. In all other cases, rir_i does nothing. After completing its Phase I action, a robot has light either moved-T-2 or moved-NT-2. Lemma 9. After all Phase-I actions associated with a cyclic dependency have completed, either the dependency is broken or every pair of consecutive non-faulty critical non-terminal robots remaining in the dependency have distinct distances from P∗P^*. Proof. Consider two consecutive non-faulty critical robots that remain dependent after completing their Phase-I actions. They are friend robots on their common line of collinearity. When the later of the two completes its Phase-I movement and remains non-terminal, Lemma 14 implies that its distance from P∗P^* differs from that of each of its friends, in particular from the other critical robot. Hence every consecutive remaining critical pair has distinct distances from P∗P^*. If no such pair remains, the dependency has been broken. ∎ Figure 3: An illustration of resolving an equal-distance cyclic dependency. (a) The critical non-terminal robots lie on a common circle centered at P∗P^*. (b) If the robots move equal distances toward P∗P^*, the existing collinearities are broken. (c) If they move unequal distances due to non-rigid movement, the collinearities are also broken, and the robots attain distinct distances from P∗P^*, inducing an order for Phase I. Phase I (Only non-faulty non-terminal robots move): After the relevant Phase-I actions have completed, consecutive non-faulty critical robots that remain in the same dependency have distinct distances from P∗P^*. Hence, the radial-distance ordering prevents directly dependent robots from remaining simultaneously eligible in Phase I. Since after Phase I, the non-faulty non-terminal robots belonging to the same cyclic or non-cyclic dependencies are at different distances from P∗P^*, we can move them one by one. Since from each line of collinearity exactly one robot (among the three) moves, the remaining collinearities involving non-faulty non-terminal robots gradually break one by one. However, some collinearities may remain from Phase I involving a faulty non-terminal robot and at least one non-faulty terminal robot (for example when an initial line of collinearity ℒ′L passes through P∗P^* two robots from ℒ′L may move in the two opposite sides of ℒ′L and they may become collinear on a new line with another faulty robot lying on ℒ′L in between). In this case, we handle the case in Phase IV. During the Phase I, a non-terminal robot uses three colors for their lights: (i) moving-3 to indicate that it has completed its movement in Phase I, (i) if after the movement in Phase I, it remains non-terminal, it uses moved-NT-3 to indicate that after the movement in Phase I, it is still a non-terminal robot (in case of faulty robots), and (i) if after the movement in Phase I, it becomes a terminal robot, it uses moved-T-3 to indicate that after the movement in Phase I, it has become a terminal robot. During Phase I, each eligible non-faulty non-terminal robot rir_i moves towards the destination desti(t)dest_i(t) lying in the interior of the line segment joining ri(t)r_i(t) and P∗P^*, as defined in Section 3.1. A robot with light moved-NT-2 becomes eligible for its Phase I action only when none of its friend robots on its current dependency lines has light moved-NT-1 or moving-2. Thus, a Phase I action cannot overtake an unfinished Phase I action on the same dependency, and no global Phase I completion test is required. r_i is a robot with light moved-NT-2: 1. If rir_i is the farthest from the point P∗P^* among all the visible non-terminal robots with light moved-NT-2, then it changes its light to moving-3 and moves towards the computed destination point. 2. If rir_i is a terminal robot and its light is moving-3, then rir_i changes its light to moved-T-3 and does not move. 3. If rir_i is a non-terminal robot and its light is moving-3, then rir_i changes its light to moved-NT-3 and does not move. In this case, robot rir_i is a faulty non-terminal robot. In all remaining cases, robot rir_i does nothing. At the end of Phase I, every non-faulty robot has a light either moved-T-1, moved-T-2, moved-T-3, or moved-NT-3. Moreover, all cyclic dependencies among the robots with light moved-NT-2 are eliminated, and the non-faulty robots can identify the completion of this phase. Phase IV (Only terminal robots with light moved-T-1, moved-T-2, or moved-T-3 move): Phase IV is necessary because a terminal non-faulty robot may still have its visibility obstructed by a mobility-faulty non-terminal robot. Such a configuration may arise after an earlier simultaneous movement, while the faulty robot remains immobile. Therefore, terminal robots with light moved-T-1, moved-T-2, or moved-T-3 perform one final radial movement toward P∗P^*. During Phase IV, each eligible non-faulty terminal robot rir_i moves towards the destination desti(t)dest_i(t) lying in the interior of the line segment joining ri(t)r_i(t) and P∗P^*, as defined in Section 3.1. rir_i is a physically terminal robot with light moved-T-1, moved-T-2, or moved-T-3: 1. Upon its Phase-IV activation, rir_i changes its light to moving-4 and moves toward its radial destination desti(t)dest_i(t). 2. If rir_i has light moving-4, then upon its next activation it changes its light to moved-T-4 and does not move. 3. If rir_i has light moved-T-4, it performs no further action. Termination: If every robot visible to rir_i, including rir_i itself, has light either moved-T-4 or moved-NT-3, then rir_i terminates without changing its current light color. 3.3 Correctness Due to space constraints, we mainly state the lemmas that are essential to prove the correctness of our algorithm, Mutual-Visibility-Mobility-Fault(). Lemma 10. During the whole execution of Mutual-Visibility-Mobility-Fault(), each robot moves at most four times. Proof. A robot performs at most one movement in each of Phases I, I, I, and IV. The light-state transitions prevent it from becoming eligible for a second movement within the same phase. Therefore, every robot performs at most four movements during the entire execution. ∎ Lemma 11. Let ri,rj,rkr_i,r_j,r_k be three robots that are non-collinear in the initial configuration. Then they remain non-collinear throughout the execution of algorithm Mutual-Visibility-Mobility-Fault(). Proof. Since ri,rj,rkr_i,r_j,r_k are non-collinear before the considered round, the current configuration is non-linear; hence the non-linear case of the displacement rule applies. We prove the claim by induction over the SSYNC rounds. Suppose that ri,rj,rkr_i,r_j,r_k are non-collinear immediately before a round, and let h>0h>0 be the minimum altitude of the triangle △rirjrk r_ir_jr_k at that time. Since these three robots are non-collinear, the current robot configuration is non-linear. We first show that every robot among ri,rj,rkr_i,r_j,r_k that moves in the round is displaced by less than h/2h/2. Consider rir_i. If both rjr_j and rkr_k are visible to rir_i, then the corresponding triangle altitudes are considered in the computation of di(t)d_i(t), and hence di(t)≤hd_i(t)≤ h. Therefore, by the displacement rule, σi(t)≤di(t)34<h2. _i(t)≤ d_i(t)3^4< h2. Otherwise, let r^j r_j and r^k r_k be the first visible robots from rir_i on the segments rirjr_ir_j and rirkr_ir_k, respectively. If h h denotes the minimum altitude of △rir^jr^k r_i r_j r_k, then, as in the proof of Lemma 4, h^≤2h. h≤ 2h. Since the altitudes of △rir^jr^k r_i r_j r_k are considered in computing di(t)d_i(t), di(t)≤h^≤2h,d_i(t)≤ h≤ 2h, and consequently σi(t)≤di(t)34≤2h34<h2. _i(t)≤ d_i(t)3^4≤ 2h3^4< h2. The same argument applies to rjr_j and rkr_k. A robot that is not activated or is mobility-faulty has displacement zero, while a non-rigid interruption can only reduce the executed displacement. Thus, irrespective of which subset of the three robots moves simultaneously in the round, every robot is displaced by less than h/2h/2. Suppose, for contradiction, that after the simultaneous movements the three robots become collinear on a line ℓ . Since each new position lies on ℓ and each displacement is less than h/2h/2, each pre-round position lies at perpendicular distance less than h/2h/2 from ℓ . Hence the triangle △rirjrk r_ir_jr_k before the round is contained in an open strip of width strictly smaller than h whose axis is ℓ . This is impossible because the minimum width of a triangle equals its minimum altitude, which is h. Therefore, ri,rj,rkr_i,r_j,r_k remain non-collinear after the round. Induction over all SSYNC rounds proves the claim throughout the execution. ∎ Lemma 12. Let ri∈ℛr_i . If, during the execution of the algorithm, the movement of rir_i creates a new line of collinearity ℒL, then all robots lying on ℒL originally belonged to a single line of collinearity from the initial configuration. Moreover, ℒL contains exactly three robot positions. Proof. Suppose that after the movement of rir_i, the new line ℒL contains rir_i and two robots rjr_j and rkr_k. If ri,rj,rkr_i,r_j,r_k were not collinear before the movement, Lemma 12 would prevent them from becoming collinear. Therefore, every robot participating in the new collinearity must originate from a line of collinearity through rir_i. Assume that robots originating from two distinct lines in ℒi0L_i^0 lie on the same newly created line. Then at least one triple consisting of rir_i and robots originating from these two distinct initial lines was initially non-collinear, contradicting Lemma 12. Hence, all robots on the new line originate from a single line L∗∈ℒi0.L^* _i^0. During Phase I, at most two robots of an initial line move in one round, and the movement directions are chosen so that a moving robot does not move along an existing robot-to-robot line. The distance bound also prevents the moving trajectory from intersecting two different lines determined by stationary robots. Thus a new line can contain only the moving robot and at most two robots originating from ℒ∗L^*. Consequently, every newly created line of collinearity contains exactly three robot positions. ∎ Lemma 13. During Phase I, only non-faulty non-terminal robots are eligible to move. Moreover, every non-faulty robot that remains non-terminal eventually becomes eligible to move. Proof. The Phase I movement rule applies only to a physically non-terminal robot whose light is moved-NT-1. Hence terminal robots are not eligible. A mobility-faulty robot may satisfy the logical eligibility condition and change its light, but it cannot execute a displacement. Therefore, every robot that actually moves in Phase I is non-faulty and non-terminal. Let rir_i be a non-faulty robot that remains non-terminal. All non-faulty non-terminal robots are mutually visible at the end of Phase I, by Lemma 8, and therefore observe the same set of Phase I candidates and their distances from P∗P^*. At least one candidate has maximum distance from P∗P^* and is eligible. After every such candidate completes its Phase I action, its light is no longer moved-NT-1. Thus the number of unprocessed candidates strictly decreases. Fairness guarantees that an eligible non-faulty candidate is eventually activated. Repeating this argument shows that rir_i eventually becomes eligible. ∎ Lemma 14. Let rir_i be a non-faulty robot that performs a Phase I movement. After completing the movement, either rir_i becomes terminal or, if it remains non-terminal, its distance from P∗P^* is different from the distance of each of its friend robots from P∗P^*. Proof. Robot rir_i moves along the segment joining its current position to P∗P^*. Thus its distance from P∗P^* strictly decreases by the distance actually traversed. If only rir_i moves on a line of collinearity, the old collinearity is broken and rir_i becomes terminal with respect to that line. The only relevant case in which rir_i can remain non-terminal is when one or more dependent friend robots are activated in the same round. If the movements produce equal new radial distances and preserve the local dependency, the involved segments toward P∗P^* have equal executed lengths; the geometry of the three-robot line then makes one of the participating robots terminal. Otherwise, non-rigid interruptions yield unequal executed lengths, and therefore unequal final distances from P∗P^*. Hence, whenever rir_i remains non-terminal, its distance from P∗P^* is different from that of each friend involved in its remaining collinearities. ∎ Lemma 15. If non-faulty robots form a cyclic-dependency relation during Phase I and are simultaneously eligible to move, then all such robots are equidistant from P∗P^*. Consequently, they lie on a common circle centered at P∗P^*. Proof. Let rir_i and rjr_j be two consecutive critical non-terminal robots of the cyclic dependency. Since they are directly dependent on a common line of collinearity, they are mutually visible. Suppose that both are simultaneously eligible in Phase I. If ‖ri−P∗‖>‖rj−P∗‖,\|r_i-P^*\|>\|r_j-P^*\|, then rjr_j observes the farther unprocessed robot rir_i with light moved-NT-1, and hence rjr_j cannot satisfy the Phase I farthest condition, a contradiction. Similarly, ‖rj−P∗‖>‖ri−P∗‖\|r_j-P^*\|>\|r_i-P^*\| is impossible. Therefore, ‖ri−P∗‖=‖rj−P∗‖.\|r_i-P^*\|=\|r_j-P^*\|. Applying the same argument to every pair of consecutive critical robots around the cyclic dependency yields ‖r1−P∗‖=‖r2−P∗‖=⋯=‖rk−P∗‖.\|r_1-P^*\|=\|r_2-P^*\|=·s=\|r_k-P^*\|. Hence all simultaneously eligible critical robots lie on a common circle centered at P∗P^*. ∎ Lemma 16. Every non-faulty robot with light moved-NT-1 eventually changes its light to either moved-T-2 or moved-NT-2. Proof. Let rir_i be a non-faulty robot with light moved-NT-1. If rir_i becomes terminal before its Phase I movement, then at its next activation it changes directly to moved-T-2. Otherwise, rir_i remains non-terminal. On every current dependency line, its friend robots are visible. Once these friends have completed their Phase I actions, the Phase I eligibility rule applies. Among any finite set of visible unprocessed candidates, at least one has maximum distance from P∗P^*. By fairness, an eligible non-faulty robot is eventually activated and completes its Phase I action. After completing the action it no longer has light moved-NT-1. Repeating the argument eliminates all non-faulty robots with light moved-NT-1 in finite time. ∎ Lemma 17. Every cyclic-dependency relation among non-faulty robots is eventually eliminated during Phase I. Proof. At the end of Phase I, either a cyclic dependency has already been broken or its remaining non-faulty critical robots have pairwise distinct distances from P∗P^*, by Lemma 16. Phase I activates the farthest remaining robot with light moved-NT-2. Therefore, among the non-faulty critical robots of a dependency, at least one robot is selected before its dependent neighbors. The selected robot moves toward P∗P^*. On each incident line of the cyclic dependency, it is the only selected critical robot at that stage. Its movement consequently breaks at least one dependency edge. By Lemma 12, this movement does not introduce a collinearity involving robots that were previously non-collinear. After completing the movement, the robot changes its light and is not selected again in Phase I. Hence every effective movement strictly decreases the number of unresolved dependency edges. Because the number of such edges is finite, every cyclic dependency is eventually eliminated. ∎ Lemma 18. Every non-faulty robot that is non-terminal at the beginning of Phase I eventually becomes terminal. Proof. Let rir_i be a non-faulty non-terminal robot at the beginning of Phase I. It has light moved-NT-2. By the distance ordering, the farthest unprocessed non-terminal robot is eligible in every non-terminal configuration. After its movement, that robot either immediately becomes terminal or breaks at least one incident dependency. Lemma 17 guarantees that cyclic dependencies cannot persist. Once the cyclic parts are eliminated, the remaining dependencies form a finite non-cyclic chains. Such a chain has an endpoint non-terminal robot whose movement breaks its incident collinearity and makes it terminal. Removing this endpoint shortens the chain. Induction on the number of robots in the dependency chain shows that every non-faulty non-terminal robot eventually becomes terminal. Fairness ensures that each eligible robot is activated after finitely many rounds. ∎ Lemma 19. Every non-faulty robot with light moved-NT-2 eventually performs its Phase I action and leaves the state moved-NT-2. Proof. A robot with light moved-NT-2 waits only for unfinished Phase I actions on its current dependency lines. These dependencies involve visible friend robots. By Lemma 16, every non-faulty such friend eventually leaves its Phase I state; a mobility-faulty robot can still update its light and therefore also eventually records completion of its Phase I action. Hence the local waiting condition eventually disappears. The distance ordering then makes at least one remaining robot eligible for Phase I, and fairness guarantees its activation. Thus every non-faulty robot eventually leaves moved-NT-2. ∎ Lemma 20. During Phase IV, every non-faulty terminal robot can see every robot in the system. Proof. At the beginning of Phase IV, Lemma 18 and Lemma 19 implies that every non-faulty robot is terminal. Thus any remaining visibility obstruction for a non-faulty robot must be caused by a faulty robot lying between two terminal robots. Let rir_i be an eligible non-faulty terminal robot that does not see any other robots. It moves toward a destination on the ray from rir_i toward P∗P^*. The Phase IV construction guarantees that the current line of collinearity through rir_i does not contain P∗P^*. Hence, the radial movement of rir_i leaves that line immediately and remove the obstruction. By Lemma 12 and the definition of di(t)d_i(t), this movement does not create a collinearity with robots that were previously non-collinear. After the movement, rir_i changes its light to moved-T-4 and does not move again. Since every remaining obstructed non-faulty terminal robot eventually becomes eligible and is activated by fairness, all such obstructions are removed in finite time. Therefore, every non-faulty terminal robot eventually sees every robot, including the mobility-faulty robots. ∎ Lemma 21. The movements of the robots are collision-free. Proof. Consider an arbitrary SSYNC round starting at time t, and let λi(t) _i(t) denote the distance actually traversed by robot rir_i during this round; set λi(t)=0 _i(t)=0 if rir_i does not move. By the destination construction, λi(t)≤σi(t)≤Di(t)34. _i(t)≤ _i(t)≤ D_i(t)3^4. Consider any two distinct robots rir_i and rjr_j, and let dij(t)=‖ri(t)−rj(t)‖.d_ij(t)=\|r_i(t)-r_j(t)\|. If rir_i sees rjr_j, then, by the definition of Di(t)D_i(t), Di(t)≤dij(t).D_i(t)≤ d_ij(t). If rir_i does not see rjr_j, opacity implies that some robot lies in the open segment ri(t)rj(t)¯ r_i(t)r_j(t). Let rkr_k be the first such robot visible from rir_i. Then Di(t)≤‖ri(t)−rk(t)‖<dij(t).D_i(t)≤\|r_i(t)-r_k(t)\|<d_ij(t). Thus, in either case, λi(t)≤dij(t)34. _i(t)≤ d_ij(t)3^4. The same argument gives λj(t)≤dij(t)34. _j(t)≤ d_ij(t)3^4. Consequently, λi(t)+λj(t)≤2dij(t)34<dij(t). _i(t)+ _j(t)≤ 2d_ij(t)3^4<d_ij(t). Suppose, for contradiction, that the two executed movement segments intersect at a point x. Since x lies on both executed segments, dij(t)≤‖ri(t)−x‖+‖x−rj(t)‖≤λi(t)+λj(t)<dij(t),d_ij(t)≤\|r_i(t)-x\|+\|x-r_j(t)\|≤ _i(t)+ _j(t)<d_ij(t), a contradiction. This argument also covers the case in which one robot is stationary, by taking its displacement to be zero. Hence, the executed trajectories of every pair of robots are disjoint in every SSYNC round. Non-rigid interruption only shortens an executed segment and therefore cannot create a collision. Thus, all movements are collision-free. ∎ Lemma 22. The proposed algorithm Mutual-Visibility-Mobility-Fault() solves the problem in O(n)O(n) epochs. Proof. In Phase I, every non-faulty robot performs exactly one Phase-I movement, and eligibility propagates from the terminal robots toward the interior of each dependency. Hence, by fairness, at least one previously unprocessed robot completes its Phase-I action within a constant number of epochs. Since there are at most n robots, Phase I requires O(n)O(n) epochs. In Phase I, every completed action removes one robot from the set with light moved-NT-1; similarly, in Phase I, every completed action removes one robot from the set with light moved-NT-2. Since each such set contains at most n robots and an eligible robot completes its action within a constant number of epochs, each of Phases I and I requires O(n)O(n) epochs. Finally, every eligible terminal robot performs at most one Phase-IV movement, so Phase IV also requires O(n)O(n) epochs. Therefore, the four phases together complete in O(n)O(n) epochs. ∎ Lemma 23. During the execution of Mutual-Visibility-Mobility-Fault, the total Euclidean distance traversed by every robot is at most its prescribed movement budget B. Proof. For every movement of rir_i, σi(t)≤Bi(t)34<Bi(t), _i(t)≤ B_i(t)3^4<B_i(t), and only the actually traversed distance is deducted from the remaining budget. If ℓi(q) _i^(q) is the distance traversed in the q-th movement, then Bi(q+1)=Bi(q)−ℓi(q)≥0.B_i^(q+1)=B_i^(q)- _i^(q)≥ 0. Therefore, by telescoping, ∑qℓi(q)=B−Bi(final)≤B. _q _i^(q)=B-B_i^(final)≤ B. Hence, every robot respects its prescribed movement budget. ∎ Theorem 1. There exists a collision-free deterministic algorithm that solves the mutual visibility problem in O(n)O(n) epochs for SSYNC robots with non-rigid, budget-constrained movements under the FALL light model using only 1212 light colors and tolerating an arbitrary number of mobility faults. Proof. By Lemmas 16–20, every non-faulty robot eventually attains unobstructed visibility of every robot in the system, including the mobility-faulty robots. Lemma 21 guarantees collision-free movements, Lemma 22 establishes the O(n)O(n)-epoch complexity, and Lemma 23 shows that every robot respects its prescribed movement budget. The algorithm uses only twelve light colors. Hence Mutual-Visibility-Mobility-Fault() satisfies all requirements of the budget-constrained strong fault-tolerant mutual visibility problem. ∎ 4 Conclusion We studied the mutual visibility problem under the budget-constrained mobility fault model for opaque luminous robots operating in the SSYNC model with non-rigid movements. Unlike existing algorithms, our solution neither relies on convex-hull decomposition nor assumes one-axis agreement. Instead, we showed that access to a common fixed external reference beacon is sufficient to coordinate the robots without requiring axis agreement. We presented the first deterministic non-convex-hull-based algorithm for this model that guarantees collision-free mutual visibility from every admissible initial robot configuration satisfying the reference-beacon assumption while respecting the prescribed movement budget and tolerating an arbitrary number of mobility faults. The algorithm uses only 12 light colors and terminates in O(n)O(n) epochs. Future work includes extending the proposed algorithm to the ASYNC model and investigating whether the mutual visibility problem can be solved under the budget-constrained mobility fault model without assuming a common fixed reference point and any form of local axes agreement. References [1] R. Adhikary, K. Bose, M. K. Kundu, and B. Sau (2022) Mutual visibility on grid by asynchronous luminous robots. Theoretical Computer Science 922, p. 218–247. External Links: Document Cited by: §1.1. [2] A. Aljohani and G. Sharma (2018) Complete visibility for mobile robots with lights tolerating faults. International Journal of Networking and Computing 8 (1), p. 32–52. Cited by: §1.1. [3] S. Bhagat, S. G. Chaudhuri, and K. Mukhopadhyaya (2016) Formation of general position by asynchronous mobile robots under one-axis agreement. In WALCOM: Algorithms and Computation, Lecture Notes in Computer Science, Vol. 9627, p. 80–91. External Links: Document Cited by: §1.1, §1.1. [4] S. Bhagat, K. Mukhopadhyaya, and R. Ray (2025) The min-move mutual visibility problem for disoriented asynchronous robots. Theoretical Computer Science 1035, p. 115125. Cited by: §1.1, §1.1. [5] S. Bhagat and K. Mukhopadhyaya (2017) Optimum algorithm for mutual visibility among asynchronous robots with lights. In Stabilization, Safety, and Security of Distributed Systems, Lecture Notes in Computer Science, Vol. 10616, p. 341–355. External Links: Document Cited by: §1.1, §1.1. [6] S. Bhagat and K. Mukhopadhyaya (2019) Mutual visibility by robots with persistent memory. In Frontiers in Algorithmics, Lecture Notes in Computer Science, Vol. 11458, p. 144–155. External Links: Document Cited by: §1.1. [7] S. Bhagat (2020) Optimum algorithm for the mutual visibility problem. In WALCOM: Algorithms and Computation, Lecture Notes in Computer Science, p. 31–42. External Links: Document Cited by: §1.1. [8] K. Bose, A. Chakraborty, and K. Mukhopadhyaya (2023) Mutual visibility by fat robots with slim omnidirectional camera. Journal of Parallel and Distributed Computing 180, p. 104716. External Links: Document Cited by: §1.1. [9] G. Di Luna, P. Flocchini, F. Poloni, N. Santoro, G. Viglietta, et al. (2014) The mutual visibility problem for oblivious robots. In 26th Canadian Conference on Computational Geometry, CCCG 2014, Cited by: §1.1, §1.1. [10] G. A. Di Luna, P. Flocchini, S. G. Chaudhuri, F. Poloni, N. Santoro, and G. Viglietta (2017) Mutual visibility by luminous robots without collisions. Information and Computation 254, p. 392–418. Cited by: §1.1, §1.1. [11] Y. Kim, Y. Katayama, and K. Wada (2025) Complete visibility algorithms of luminous robots with two-color lights on grid. Concurrency and Computation: Practice and Experience 37 (2), p. e8323. External Links: Document Cited by: §1.1. [12] P. Poudel, A. Aljohani, and G. Sharma (2021) Fault-tolerant complete visibility for asynchronous robots with lights under one-axis agreement. Theoretical Computer Science 850, p. 116–134. Cited by: §1.1, §1.1, Table 1. [13] S. Pramanick, S. Jana, A. Bhattacharya, and P. S. Mandal (2024) Mutual visibility of luminous robots despite angular inaccuracy. Theoretical Computer Science 1011, p. 114723. External Links: Document Cited by: §1.1. [14] S. Pramanick, S. Jana, and P. S. Mandal (2025) Fault-tolerant mutual visibility without any axis agreement in presence of mobility failure. Theoretical Computer Science 1025, p. 114970. External Links: Document Cited by: §1.1, §1.1, §1.1. [15] S. Pramanick, S. Jana, and P. S. Mandal (2026) Asynchronous fault-tolerant mutual visibility. In International Colloquium on Structural Information and Communication Complexity, p. 470–488. Cited by: §1.1, §1.1, Table 1. [16] G. Sharma, R. Alsaedi, C. Busch, and S. Mukhopadhyay (2018) The complete visibility problem for fat robots with lights. In Proceedings of the 19th International Conference on Distributed Computing and Networking (ICDCN), p. 21:1–21:4. External Links: Document Cited by: §1.1, §1.1. [17] G. Sharma, C. Busch, and S. Mukhopadhyay (2015) Bounds on mutual visibility algorithms. In Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG), p. 268–274. Cited by: §1.1. [18] G. Sharma, C. Busch, and S. Mukhopadhyay (2015) Mutual visibility with an optimal number of colors. In International Symposium on Algorithms and Experiments for Wireless Sensor Networks, p. 196–210. Cited by: §1.1, §1.1. [19] G. Sharma, C. Busch, and S. Mukhopadhyay (2018) How to make fat autonomous robots see all others fast?. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), p. 3730–3735. External Links: Document Cited by: §1.1, §1.1. [20] G. Sharma, C. Busch, and S. Mukhopadhyay (2019) Complete visibility for oblivious robots in (N)O(N) time. In Networked Systems, Lecture Notes in Computer Science, Vol. 11028, p. 67–84. External Links: Document Cited by: §1.1. [21] G. Sharma, R. Vaidyanathan, J. L. Trahan, C. Busch, and S. Rai (2016) Complete visibility for robots with lights in o (1) time. In International Symposium on Stabilization, Safety, and Security of Distributed Systems, p. 327–345. Cited by: §1.1, §1.1. [22] G. Sharma, R. Vaidyanathan, and J. L. Trahan (2021) Constant-time complete visibility for robots with lights: the asynchronous case. Algorithms 14 (2), p. 56. Cited by: §1.1, §1.1. [23] G. Sharma (2018) Mutual visibility for robots with lights tolerating light faults. In IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPS Workshops), p. 829–836. Cited by: §1.1. [24] R. Vaidyanathan, C. Busch, J. L. Trahan, G. Sharma, and S. Rai (2015) Logarithmic-time complete visibility for robots with lights. In 2015 IEEE International Parallel and Distributed Processing Symposium, p. 375–384. Cited by: §1.1, §1.1.