Budget-Constrained Fault-Tolerant Mutual Visibility for Autonomous Robots under the Mobility Fault Model

Budget-Constrained Fault-Tolerant Mutual Visibility for Autonomous Robots under the Mobility Fault Model Prakhar Shukla, Animesh Maiti∗, Shivam Kumar, Subhash Bhagat

arXiv:2610.04402v1 [cs.DC] 3 Oct 2026

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

Abstract We investigate the mutual visibility problem for a swarm of n ≥ 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 ∗

Corresponding author: p22ma201@iitj.ac.in

1

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 ∗ 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. [4] 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. [18] analyzed bounds on existing mutual-visibility algorithms, while subsequent work improved the running time for oblivious robots; in particular, Sharma et al. [21] obtained an 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. [19] 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. [23] further reduced the running time to 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 2

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 [3], 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. [17] studied complete visibility for fat luminous robots, whereas Sharma et al. [20] 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 [16], 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. [7] 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, 23, 19, 22, 17, 20, 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 [4, 5, 7]. 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 3

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 ∗ lying outside the convex hull of the initial configuration. The point 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 ∗ 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 12 light colors, and terminates in 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 SchedulerAxis/assumption

Colors Time

Approach

Poudel et al. [12] Pramanick et al. [15]

f f

ASYNC One-axis agreement ASYNC No axis agreement

3 35

O(n) O(n)

Non-convex hull 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 R = {r1 , r2 , . . . , rn } 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∥ denote the Euclidean distance between x and y. • Computation Model: Robots execute the Look–Compute–Move cycle under the semisynchronous (SSYNC) model with a fair scheduler. Robot movements are non-rigid. There exists a 4

fixed but unknown constant δ > 0 such that, if a non-faulty robot ri computes a destination di and ∥ri − di ∥ ≤ δ, then it reaches di ; otherwise, the scheduler may stop it after any displacement in [δ, ∥ri − di ∥]. 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 ∗ . 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 ri obtains the relative position of P ∗ expressed in its current local coordinate system. Thus, P ∗ provides a common geometric landmark, but does not induce a common coordinate system, axis orientation, handedness, or chirality. We assume that 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 ∗ simply as the reference point. • Movement Budget: Each robot is assigned the same finite movement budget B > 0, representing the maximum Euclidean distance it may traverse during the execution. At every activation, robot ri can locally obtain its current remaining movement budget, denoted by Bi (t). Initially, Bi (0) = B. Only the distance actually traveled is deducted from Bi (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 denotes the total distance traveled by ri , then ℓ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 ri at time t is denoted by ri (t), and its light color by ci (t). The geometric configuration at time t is R(t) = {r1 (t), r2 (t), . . . , rn (t)}. The complete robot configuration is C(t) = {(ri (t), ci (t)) : 1 ≤ i ≤ n}. Thus, R(t) describes only the robot positions, whereas 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 eL and R eN L denote, respectively, the sets of linear on a single line, and non-linear otherwise. Let R 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 ri , let L0i denote the set of initial lines of collinearity containing ri (0). • Visibility: The vision of robot ri at time t is the set Vi (t) consisting of all robot positions visible to ri , including its own position. • Adjacent and friend robots: Two robots ri and rj are said to be adjacent at time t if they are collinear and no robot lies in the open line segment joining ri (t) and rj (t). Equivalently, they are 5

Figure 1: Illustration of adjacent and friend robots. The adjacent robot pairs are (ri , rj ), (rj , rk ), and (rk , rl ). Since rj and rk are non-terminal robots, ri and rk are the friend robots of rj , whereas rj and rl are the friend robots of rk . mutually visible along the line containing them. Furthermore, let ri be a non-terminal robot on a line of collinearity L at time t, and let rj (t) and rk (t) lie on the two opposite sides of ri (t) along L, with both robots visible to ri . Then rj and rk are called the friend robots of ri 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 R = {r1 , . . . , rn }, n ≥ 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 RN F (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 ∈ RN F (T ) and every rj ∈ R \ {ri },   int ri (T )rj (T ) ∩ (R(T ) \ {ri (T ), rj (T )}) = ∅. Moreover, if ℓi is the total Euclidean distance traversed by ri , then ℓi ≤ B for every ri ∈ R. 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.

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) denote the destination of robot ri at time t. Its destination is determined by a movement direction DIRi (t) and a displacement σi (t). The construction below guarantees that the movement respects the 6

(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. 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) and rj (t) be two distinct robot positions in R(t). We denote the straight line joining these two robot positions by Lij (t). • Let ri (t), rj (t) and rk (t) be three non-collinear robot positions in R(t). We denote the perpendicular distance of the line Lij (t) from the point rk (t) by dkij (t). • For every robot position rm (t) ∈ Vi (t) \ {ri (t)}, let L∗m (t) denote the line passing through rm (t) and the reference point P ∗ . Whenever ri (t) ∈ / L∗m (t), define
∗ dPi,m (t) = dist ri (t), L∗m (t) . Suppose that R(t) ∈ RN L . Define  ∗ Di (t) = dPi,m (t) : rm (t) ∈ Vi (t) \ {ri (t)}, ri (t) ∈ / L∗m (t)  ∪ dkij (t), djik (t), dijk (t) : rj (t), rk (t) ∈ Vi (t) \ {ri (t)}, ri (t), rj (t), rk (t) are non-collinear . We define di (t) =

( min Di (t), if Di (t) ̸= ∅, +∞,

if Di (t) = ∅.

Thus, whenever finite, di (t) is the minimum perpendicular clearance induced by the relevant lines considered in the destination construction. • Let ri (t) be a robot positions. Let N Ti (t) be the set of non-terminal robot positions visible to ri such that n N Ti (t) = rk (t) ∈ Vi (t) \ {ri (t)} : rk (t) is non-terminal and o P∗ ∈ / Lik (t) . 7

For every rk (t) ∈ N Ti (t), the line Lik (t) joining ri (t) and rk (t) divides the plane into two open half-planes. Let HPik+ (t) denote the open half-plane containing P ∗ . Let HPik+ be the open half plane that contains P ∗ . Define the safe region of ri by \ Regi (t) = HPik+ (t). rk (t)∈N Ti (t)

If N Ti (t) = ∅, we set Regi (t) = R2 . For every rk (t) ∈ N Ti (t), the segment from ri (t) toward P ∗ locally enters HPik+ (t); hence a direction toward 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 II–IV. For a Phase I movement, When R(t) ∈ RN L , let xi be any point in Regi (t) such that the segment ri (t)xi does not lie on any line Lik (t), where rk (t) ∈ Vi (t) \ {ri (t)}. Define uIi (t) =

xi − ri (t) . ∥xi − ri (t)∥

If R(t) ∈ RL and L0 denotes the current line containing all robot positions, let L⊥ 0 be the line ⊥ perpendicular to L0 at ri (t), and choose an arbitrary point yi ∈ L0 \ {ri (t)}. Define uIi (t) =

yi − ri (t) . ∥yi − ri (t)∥

For every radial movement in Phases II–IV, define ρi (t) = ∥ri (t) − P ∗ ∥ and uR i (t) =

P ∗ − ri (t) . ρi (t)

∗ Thus, uR i (t) is the unit vector directed from ri (t) towards the reference point P .

The amount of displacement: Let Di (t) denote the minimum distance of any two robot positions in {ri (t), Vi (t)}. Let Bi (t) denote the remaining movement budget locally available to robot ri at time t. The amount of displacement of ri at time t is denoted by σi (t) and it is defined as follows, For a Phase I movement,  1   4 min{di (t), Di (t), Bi (t)}, R(t) ∈ RN L , σi (t) = 3   1 min{Di (t), Bi (t)}, R(t) ∈ RL . 34 For a radial movement toward P ∗ in Phases II–IV,  1   4 min{di (t), Di (t), Bi (t), ρi (t)}, R(t) ∈ RN L , σi (t) = 3   1 min{Di (t), Bi (t), ρi (t)}, R(t) ∈ RL . 34 8

The quantity σ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); hence the computed destination lies strictly in the interior of the segment joining ri (t) and P ∗ , and the robot neither reaches nor crosses the reference point. Destination point. The destination of an eligible robot ri is defined according to the phase in which it moves:  ri (t) + σi (t)uIi (t), in Phase I, desti (t) = r (t) + σ (t)uR (t), in Phases II–IV. i i i For a radial movement, σi (t) ≤

ρi (t) < ρi (t). 34

Hence,
desti (t) ∈ int ri (t)P ∗ , so the robot moves strictly towards 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 II and Phase III, 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 ri , rj , rk , rl and rm be collinear robots on a line L such that robots ri and rm are terminal, other robots are non-terminal, rj is adjacent to ri , and rl is adjacent to rm . As the terminal robots move first, initially only ri and rm are eligible to move. Without loss of generality, let us consider the following order of activations of the robots: ri is activated first, followed by rj , then rm is activated, followed by rl , and lastly rk is activated. Upon activation, robot ri turns its light moving-1 and moves. The moving-1 keeps the information that robot ri has made its initial move. In the next activation, robot ri 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 ri , robot rj may become terminal or may remain non-terminal (due to a fault in ri ). If rj becomes terminal, then it acts like ri . Otherwise, rj finds one of its friends with light move-T-1 (ri and rk are friends of rj ) has light moved-T-1. We allow robot rj 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 rj and rl are initially faulty. According to the activation schedule and moving rule, when rk becomes active, it finds both of its friends with light moved-NT-1, this let rk know that all the collinear robots on L have moved. We allow the robot rk 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: ri is a physically terminal robot: The robot ri finds itself as a physically terminal robot and 1. its light is off: it changes its light to moving-1 and moves. 9

2. its light is moving-1: it changes its light to moved-T-1 and does not move. ri is a physically non-terminal robot: Robot ri 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 ri 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 , rk 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 , rk are non-collinear immediately before some round, and let h > 0 denote the minimum altitude of the triangle △ri rj rk at that time. We first show that every robot among ri , rj , rk that moves in this round is displaced by less than h/2. Consider robot ri . If both rj and rk are visible to ri , then the three altitudes of △ri rj rk are among the distances considered in the computation of di (t). Hence, di (t) ≤ h. Since the configuration is non-linear, the destination construction gives di (t) h h σi (t) ≤ 4 ≤ 4 < . 3 3 2 Now suppose that one or both of rj , rk are not visible to ri . Let rbj and rbk be the first visible robots on the segments ri rj and ri rk , respectively; if rj (respectively, rk ) is visible, take rbj = rj (respectively, rbk = rk ). There exist α, β ∈ (0, 1] such that rbj − ri = α(rj − ri ),

rbk − ri = β(rk − ri ). 10

h be the Let A be the area of △ri rj rk , and let M = max{|ri rj |, |ri rk |, |rj rk |}. Then h = 2A . Let b M c be the length of its longest side. Since its area is αβA, minimum altitude of △ri rbj rbk , and let M 2αβA b h= M c . Furthermore,
αβM ≤ αβ |ri rj | + |ri rk | c. ≤ α|ri rj | + β|ri rk | ≤ 2M Therefore, b h ≤ 2h. Since rbj and rbk are visible to ri , the altitudes of △ri rbj rbk are considered in the computation of di (t). Thus, di (t) ≤ b h ≤ 2h, and consequently σi (t) ≤

di (t) 2h h ≤ 4 < . 4 3 3 2

The same argument applies to rj and rk . 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/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/2, each of the three positions before the round is at perpendicular distance less than h/2 from ℓ. Hence the entire triangle △ri rj rk 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 , rk 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. 11

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 ri and rj are not mutually visible at the end of Phase I. Then some robot rk lies in the interior of ri rj , and hence ri , rk , rj 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 ri and rj 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, ri and rj are non-terminal by assumption, and rk is also non-terminal since it lies in the interior of ri rj . 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 ri and rj be two non-faulty terminal robots that are not mutually visible at the end of Phase I, and let rk 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 ri and rj are non-faulty, rk must be mobility-faulty. Moreover, as rk lies between ri and rj , it is non-terminal. Phase II (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 ri 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 ri move simultaneously in the same round, and ri 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 12

dependency breaks down, and further movements of the robots will break the remaining dependencies in that cycle (this part is achieved during Phase III). We obtain a partial ordering of the movements of the non-faulty non-terminal robots using their radial distances ρi (t) from the reference point P ∗ , and move the farthest eligible non-terminal robot first among those that have not yet completed their Phase II 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 II. Robots use their lights to communicate whether they have moved in Phase II or not (see below). The Phase II 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 ri and rj have ∥ri − P ∗ ∥ > ∥rj − P ∗ ∥, then rj cannot be eligible while ri still has light moved-NT-1, since rj observes the farther unprocessed robot ri . Hence, simultaneously eligible dependent robots must have the same distance from P ∗ . Now consider the case when all the non-terminal robots in a cyclic dependency are at the same distance l from P ∗ . Then these points lie on a circle of radius l centered at 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 ∗ (this helps us in Phase III). 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 ∗ as center. In the second case, it can be easily shown that all these robots are at distinct distances from P ∗ (see Fig. 3(c)), and in Phase III, these robots move one by one according to their distances from P ∗ , and non-faulty non-terminal robots become terminal robots at the end of Phase III. During the Phase II, a non-terminal robot uses three colors for their lights: (i) moving-2 to indicate that it has completed its movement in Phase II, (ii) if after the movement in Phase II, it remains non-terminal, it uses moved-NT-2 to indicate that after the movement in Phase II, they are still non-terminals, and (iii) if after the movement in Phase II, it becomes a terminal robot, it uses moved-T-2 to indicate that after the movement in Phase II, it has become terminal. In Phase III, only the robots with light moved-NT-2 move. During Phase II, each eligible non-faulty non-terminal robot ri moves towards the destination desti (t) lying in the interior of the line segment joining ri (t) and P ∗ , as defined in Section 3.1. We formally define the movement rules for the non-terminal robots as follows: ri is a robot with light moved-NT-1: 1. If ri is currently terminal, it changes its light to moved-T-2 without moving. 2. If ri is currently non-terminal and is farthest from 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 ri and P ∗ . 3. If ri 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, ri does nothing. After completing its Phase II action, a robot has light either moved-T-2 or moved-NT-2. 13

Lemma 9. After all Phase-II 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 ∗ . Proof. Consider two consecutive non-faulty critical robots that remain dependent after completing their Phase-II actions. They are friend robots on their common line of collinearity. When the later of the two completes its Phase-II movement and remains non-terminal, Lemma 14 implies that its distance from 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 ∗ . 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 ∗ . (b) If the robots move equal distances toward 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 ∗ , inducing an order for Phase III. Phase III (Only non-faulty non-terminal robots move): After the relevant Phase-II actions have completed, consecutive non-faulty critical robots that remain in the same dependency have distinct distances from P ∗ . Hence, the radial-distance ordering prevents directly dependent robots from remaining simultaneously eligible in Phase III. Since after Phase II, the non-faulty non-terminal robots belonging to the same cyclic or non-cyclic dependencies are at different distances from 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 ∗ 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 III, a non-terminal robot uses three colors for their lights: (i) moving-3 to indicate that it has completed its movement in Phase III, (ii) if after the movement in Phase III, it remains nonterminal, it uses moved-NT-3 to indicate that after the movement in Phase III, it is still a non-terminal robot (in case of faulty robots), and (iii) if after the movement in Phase III, it becomes a terminal robot, 14

it uses moved-T-3 to indicate that after the movement in Phase III, it has become a terminal robot. During Phase III, each eligible non-faulty non-terminal robot ri moves towards the destination desti (t) lying in the interior of the line segment joining ri (t) and P ∗ , as defined in Section 3.1. A robot with light moved-NT-2 becomes eligible for its Phase III action only when none of its friend robots on its current dependency lines has light moved-NT-1 or moving-2. Thus, a Phase III action cannot overtake an unfinished Phase II action on the same dependency, and no global Phase II completion test is required. ri is a robot with light moved-NT-2: 1. If ri is the farthest from the point 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 ri is a terminal robot and its light is moving-3, then ri changes its light to moved-T-3 and does not move. 3. If ri is a non-terminal robot and its light is moving-3, then ri changes its light to moved-NT-3 and does not move. In this case, robot ri is a faulty non-terminal robot. In all remaining cases, robot ri does nothing. At the end of Phase III, 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 ∗ . During Phase IV, each eligible non-faulty terminal robot ri moves towards the destination desti (t) lying in the interior of the line segment joining ri (t) and P ∗ , as defined in Section 3.1. ri is a physically terminal robot with light moved-T-1, moved-T-2, or moved-T-3: 1. Upon its Phase-IV activation, ri changes its light to moving-4 and moves toward its radial destination desti (t). 2. If ri has light moving-4, then upon its next activation it changes its light to moved-T-4 and does not move. 3. If ri has light moved-T-4, it performs no further action. Termination: If every robot visible to ri , including ri itself, has light either moved-T-4 or moved-NT-3, then ri 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.

15

Proof. A robot performs at most one movement in each of Phases I, II, III, 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 , rk 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 , rk 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 , rk are non-collinear immediately before a round, and let h > 0 be the minimum altitude of the triangle △ri rj rk 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 , rk that moves in the round is displaced by less than h/2. Consider ri . If both rj and rk are visible to ri , then the corresponding triangle altitudes are considered in the computation of di (t), and hence di (t) ≤ h. Therefore, by the displacement rule, σi (t) ≤

di (t) h < . 4 3 2

Otherwise, let rbj and rbk be the first visible robots from ri on the segments ri rj and ri rk , respectively. h denotes the minimum altitude of △ri rbj rbk , then, as in the proof of Lemma 4, b h ≤ 2h. Since the If b b altitudes of △ri rbj rbk are considered in computing di (t), di (t) ≤ h ≤ 2h, and consequently σi (t) ≤

di (t) 2h h ≤ 4 < . 4 3 3 2

The same argument applies to rj and rk . 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/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/2, each pre-round position lies at perpendicular distance less than h/2 from ℓ. Hence the triangle △ri rj rk 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 , rk remain non-collinear after the round. Induction over all SSYNC rounds proves the claim throughout the execution. Lemma 12. Let ri ∈ R. If, during the execution of the algorithm, the movement of ri 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 ri , the new line L contains ri and two robots rj and rk . If ri , rj , rk 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 ri . Assume that robots originating from two distinct lines in L0i lie on the same newly created line. Then at least one triple consisting of ri 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∗ ∈ L0i . 16

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 II, 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 II 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 II is non-faulty and non-terminal. Let ri 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 II candidates and their distances from P ∗ . At least one candidate has maximum distance from P ∗ and is eligible. After every such candidate completes its Phase II 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 ri eventually becomes eligible. Lemma 14. Let ri be a non-faulty robot that performs a Phase II movement. After completing the movement, either ri becomes terminal or, if it remains non-terminal, its distance from P ∗ is different from the distance of each of its friend robots from P ∗ . Proof. Robot ri moves along the segment joining its current position to P ∗ . Thus its distance from P ∗ strictly decreases by the distance actually traversed. If only ri moves on a line of collinearity, the old collinearity is broken and ri becomes terminal with respect to that line. The only relevant case in which ri 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 ∗ 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 ∗ . Hence, whenever ri remains non-terminal, its distance from 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 II and are simultaneously eligible to move, then all such robots are equidistant from P ∗ . Consequently, they lie on a common circle centered at P ∗ . Proof. Let ri and rj 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 II. If ∥ri − P ∗ ∥ > ∥rj − P ∗ ∥, then rj observes the farther unprocessed robot ri with light moved-NT-1, and hence rj cannot satisfy the Phase II farthest condition, a contradiction. Similarly, ∥rj − P ∗ ∥ > ∥ri − P ∗ ∥ is impossible. Therefore, ∥ri − P ∗ ∥ = ∥rj − P ∗ ∥. Applying the same argument to every pair of consecutive critical robots around the cyclic dependency yields ∥r1 − P ∗ ∥ = ∥r2 − P ∗ ∥ = · · · = ∥rk − P ∗ ∥. Hence all simultaneously eligible critical robots lie on a common circle centered at P ∗ . 17

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 ri be a non-faulty robot with light moved-NT-1. If ri becomes terminal before its Phase II movement, then at its next activation it changes directly to moved-T-2. Otherwise, ri remains non-terminal. On every current dependency line, its friend robots are visible. Once these friends have completed their Phase I actions, the Phase II eligibility rule applies. Among any finite set of visible unprocessed candidates, at least one has maximum distance from P ∗ . By fairness, an eligible non-faulty robot is eventually activated and completes its Phase II 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 III. Proof. At the end of Phase II, either a cyclic dependency has already been broken or its remaining non-faulty critical robots have pairwise distinct distances from P ∗ , by Lemma 16. Phase III 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 ∗ . 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 III. 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 III eventually becomes terminal. Proof. Let ri be a non-faulty non-terminal robot at the beginning of Phase III. 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 III action and leaves the state moved-NT-2. Proof. A robot with light moved-NT-2 waits only for unfinished Phase II actions on its current dependency lines. These dependencies involve visible friend robots. By Lemma 16, every non-faulty such friend eventually leaves its Phase II state; a mobility-faulty robot can still update its light and therefore also eventually records completion of its Phase II action. Hence the local waiting condition eventually disappears. The distance ordering then makes at least one remaining robot eligible for Phase III, 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. 18

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 ri be an eligible non-faulty terminal robot that does not see any other robots. It moves toward a destination on the ray from ri toward P ∗ . The Phase IV construction guarantees that the current line of collinearity through ri does not contain P ∗ . Hence, the radial movement of ri leaves that line immediately and remove the obstruction. By Lemma 12 and the definition of di (t), this movement does not create a collinearity with robots that were previously non-collinear. After the movement, ri 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) denote the distance actually traversed by robot ri during this round; set λi (t) = 0 if ri does not move. By the destination construction, λi (t) ≤ σi (t) ≤ D3i4(t) . Consider any two distinct robots ri and rj , and let dij (t) = ∥ri (t) − rj (t)∥. If ri sees rj , then, by the definition of Di (t), Di (t) ≤ dij (t). If ri does not see rj , opacity implies that some robot lies in the open segment ri (t)rj (t). Let rk be the first such robot visible from ri . Then Di (t) ≤ ∥ri (t) − rk (t)∥ < dij (t). d (t) d (t) Thus, in either case, λi (t) ≤ ij34 . The same argument gives λj (t) ≤ ij34 . Consequently, λi (t) + λj (t) ≤ 2dij (t) < dij (t). 34 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), 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) 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) epochs. In Phase II, every completed action removes one robot from the set with light moved-NT-1; similarly, in Phase III, 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 II and III requires O(n) epochs. Finally, every eligible terminal robot performs at most one Phase-IV movement, so Phase IV also requires O(n) epochs. Therefore, the four phases together complete in 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 ri , σi (t) ≤ B3i (t) < Bi (t), and only the actually traversed distance is 4 (q) deducted from the remaining budget. If ℓi is the distance traversed in the q-th movement, then P (q) (q+1) (q) (q) (final) Bi = Bi − ℓi ≥ 0. Therefore, by telescoping, q ℓi = B − Bi ≤ B. Hence, every robot respects its prescribed movement budget. 19

Theorem 1. There exists a collision-free deterministic algorithm that solves the mutual visibility problem in O(n) epochs for SSYNC robots with non-rigid, budget-constrained movements under the FALL light model using only 12 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)-epoch complexity, and Lemma 23 shows that every robot respects its prescribed movement budget. The algorithm uses only twelve light colors. Hence Mutual-VisibilityMobility-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) 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] Ranendu Adhikary, Kaustav Bose, Manash Kumar Kundu, and Buddhadeb Sau. Mutual visibility on grid by asynchronous luminous robots. Theoretical Computer Science, 922:218–247, 2022. [2] Aisha Aljohani and Gokarna Sharma. Complete visibility for mobile robots with lights tolerating faults. International Journal of Networking and Computing, 8(1):32–52, 2018. [3] Subhash Bhagat. Optimum algorithm for the mutual visibility problem. In WALCOM: Algorithms and Computation, Lecture Notes in Computer Science, pages 31–42. Springer, 2020. [4] Subhash Bhagat, Sruti Gan Chaudhuri, and Krishnendu Mukhopadhyaya. Formation of general position by asynchronous mobile robots under one-axis agreement. In WALCOM: Algorithms and Computation, volume 9627 of Lecture Notes in Computer Science, pages 80–91. Springer, 2016. [5] Subhash Bhagat and Krishnendu Mukhopadhyaya. Optimum algorithm for mutual visibility among asynchronous robots with lights. In Stabilization, Safety, and Security of Distributed Systems, volume 10616 of Lecture Notes in Computer Science, pages 341–355. Springer, 2017. [6] Subhash Bhagat and Krishnendu Mukhopadhyaya. Mutual visibility by robots with persistent memory. In Frontiers in Algorithmics, volume 11458 of Lecture Notes in Computer Science, pages 144–155. Springer, 2019. [7] Subhash Bhagat, Krishnendu Mukhopadhyaya, and Rajarshi Ray. The min-move mutual visibility problem for disoriented asynchronous robots. Theoretical Computer Science, 1035:115125, 2025. 20

[8] Kaustav Bose, Abhinav Chakraborty, and Krishnendu Mukhopadhyaya. Mutual visibility by fat robots with slim omnidirectional camera. Journal of Parallel and Distributed Computing, 180:104716, 2023. [9] G Di Luna, Paola Flocchini, Federico Poloni, Nicola Santoro, Giovanni Viglietta, et al. The mutual visibility problem for oblivious robots. In 26th Canadian Conference on Computational Geometry, CCCG 2014. Canadian Conference on Computational Geometry, 2014. [10] 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. [11] Yonghwan Kim, Yoshiaki Katayama, and Koichi Wada. Complete visibility algorithms of luminous robots with two-color lights on grid. Concurrency and Computation: Practice and Experience, 37(2):e8323, 2025. [12] Pavan Poudel, Aisha Aljohani, and Gokarna Sharma. Fault-tolerant complete visibility for asynchronous robots with lights under one-axis agreement. Theoretical Computer Science, 850:116–134, 2021. [13] Subhajit Pramanick, Saswata Jana, Adri Bhattacharya, and Partha Sarathi Mandal. Mutual visibility of luminous robots despite angular inaccuracy. Theoretical Computer Science, 1011:114723, 2024. [14] Subhajit Pramanick, Saswata Jana, and Partha Sarathi Mandal. Fault-tolerant mutual visibility without any axis agreement in presence of mobility failure. Theoretical Computer Science, 1025:114970, 2025. [15] Subhajit Pramanick, Saswata Jana, and Partha Sarathi Mandal. Asynchronous fault-tolerant mutual visibility. In International Colloquium on Structural Information and Communication Complexity, pages 470–488. Springer, 2026. [16] Gokarna Sharma. Mutual visibility for robots with lights tolerating light faults. In IEEE International Parallel and Distributed Processing Symposium Workshops (IPDPS Workshops), pages 829–836, 2018. [17] Gokarna Sharma, Rusul Alsaedi, Costas Busch, and Supratik Mukhopadhyay. The complete visibility problem for fat robots with lights. In Proceedings of the 19th International Conference on Distributed Computing and Networking (ICDCN), pages 21:1–21:4. ACM, 2018. [18] Gokarna Sharma, Costas Busch, and Supratik Mukhopadhyay. Bounds on mutual visibility algorithms. In Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG), pages 268–274, 2015. [19] Gokarna Sharma, Costas Busch, and Supratik Mukhopadhyay. Mutual visibility with an optimal number of colors. In International Symposium on Algorithms and Experiments for Wireless Sensor Networks, pages 196–210. Springer, 2015. [20] Gokarna Sharma, Costas Busch, and Supratik Mukhopadhyay. How to make fat autonomous robots see all others fast? In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pages 3730–3735. IEEE, 2018. [21] Gokarna Sharma, Costas Busch, and Supratik Mukhopadhyay. Complete visibility for oblivious robots in O(n) time. In Networked Systems, volume 11028 of Lecture Notes in Computer Science, pages 67–84. Springer, 2019. 21

[22] Gokarna Sharma, Ramachandran Vaidyanathan, and Jerry L Trahan. Constant-time complete visibility for robots with lights: the asynchronous case. Algorithms, 14(2):56, 2021. [23] Gokarna Sharma, Ramachandran Vaidyanathan, Jerry L Trahan, Costas Busch, and Suresh Rai. Complete visibility for robots with lights in o (1) time. In International Symposium on Stabilization, Safety, and Security of Distributed Systems, pages 327–345. Springer, 2016. [24] Ramachandran Vaidyanathan, Costas Busch, Jerry L Trahan, Gokarna Sharma, and Suresh Rai. Logarithmic-time complete visibility for robots with lights. In 2015 IEEE International Parallel and Distributed Processing Symposium, pages 375–384. IEEE, 2015.

22

Related documents

• Budget-Constrained Fault-Tolerant Mutual Visibility for Autonomous Robots under the Mobility Fault Model#1200053
• Patrolling by Robots Equipped with Visibility#296951
• mmAlert: A Simultaneous Device Localization and Target Tracking System via Cooperative Passive Sensing#246472
• Power in Numbers: Primitive Algorithm for Swarm Robot Navigation in Unknown Environments#149194
• Robust Fault Tolerant Control for Highly Automated Vehicle Equipped With Steer-By-Wire System With Multiple Actuator Faults#677089