Mobility Matters
Home›Mobile robots in the plane›Formation problems›Pattern formation›Mutual visibility

Mutual visibility

Opaque robots must reach positions where no three are collinear, so that every robot sees every other.

Problem statement and measuresexpand

\(n\) opaque point robots (or unit discs) start at distinct points: a robot hides the robots behind it on the same line of sight. They must reach a configuration in which every robot sees every other (no three collinear), without collisions.

Measures: Time, rounds (FSYNC, SSYNC) or epochs (ASYNC) until the task is done; "finite" when only solvability is known; Colours, colours of the light per robot (0 for oblivious robots).

Lights, mobility faults, SSYNC, non-rigid

verified
Time: unknownColours: tight

With any number of mobility faults, luminous robots without axis agreement reach mutual visibility in non-rigid SSYNC in \(O(n)\) epochs with 12 colours, if they all see a common fixed reference point.

Assumed (added on the last edge are outlined)

+Bodypoint robots+Visibilityunlimited+Faultsup to \(f\) robots may crash+Schedulersemi-synchronous (SSYNC)+Lights (persistent memory)full light (LUMI): every robot sees all lights, including its own

Not assumed

Opacityopaque: collinear robots hide each otherAgreement on coordinatesno agreement on local coordinate systemsMovementnon-rigid: the adversary may stop a move after some minimum distance \(\delta\)Multiplicity detectionnone: a point with several robots looks like one robotRandomnessdeterministicIdentifiersanonymous: all robots are identical
Formal definitions of this setting
Body: point
Each robot is a point of the plane: several robots may share a point (multiplicity), and a robot hides only what lies exactly behind it on a line of sight.
Visibility: unlimited visibility
A robot sees all robots (subject to opacity).
Opacity: opaque
Robots are points that obstruct sight: \(r\) sees \(s\) iff no third robot lies on the open segment \(\overline{rs}\).
Faults: crash faults
Up to \(f\) robots stop forever at adversarial times and remain visible at their last position.
Scheduler: SSYNC
SSYNC: time is divided into rounds; in each round a non-empty subset of robots, chosen by a fair adversary, executes one atomic Look–Compute–Move cycle. Called Atom by Prencipe Prencipe 2007.
Lights (persistent memory): lights (LUMI)
LUMI: each robot has a light with \(c\) colours, set at the end of Compute, visible to all robots including itself; it is both memory and communication. Also called luminous robots, or a full light.
Agreement on coordinates: disoriented
Each robot \(r\) observes in its own coordinate system, obtained from the global one by an unknown similarity (translation, rotation, uniform scaling, and possibly reflection); systems may differ between robots and, in some models, between cycles. Papers that call robots disoriented do not always mean this: Défago and Souissi use the word while assuming chirality Défago & Souissi 2008. Some papers also let the adversary change a robot's rotation, reflection and unit at every Look (variable disorientation) Flocchini et al. 2023 Wada et al. 2026.
Movement: non-rigid
In a Move phase the adversary may stop a robot before its destination, but only after it has travelled at least \(\delta>0\) (a constant unknown to the robots) or reached the destination.
Multiplicity detection: no multiplicity detection
A snapshot is a set of points: a point occupied by several robots looks like a single robot.
Randomness: deterministic
The destination computed in a cycle is a function of the snapshot (and the light, if any).
Identifiers: anonymous
Robots are indistinguishable and run the same algorithm.

Statement for this variant

Any number \(f\) of robots, unknown to the robots, may suffer a mobility fault at any time: a faulty robot never moves again, but keeps performing Look and Compute and changing its light, and cannot tell that it is faulty. The non-faulty robots must reach, without collisions, a configuration in which every non-faulty robot sees every other robot, faulty or not Shukla et al. 2026a. (A weaker goal, used by Poudel et al. 2021 in ASYNC, asks only that no three non-faulty robots be collinear and that no faulty robot lie between two non-faulty ones.)

What is known

Time · rounds (FSYNC, SSYNC) or epochs (ASYNC) until the task is done; "finite" when only solvability is known
unknown
\(O(n)\) epochs; no lower bound beyond the trivial one.
lower boundnone known
introductory—
current best
\(O(n)\)
\(n \ge 3\)a common fixed reference point that every robot sees in every Look, whatever robots lie in between, and that lies outside the convex hull of the initial configuration; it gives no common directiona faulty robot keeps changing its light: the fault stops only its movementevery robot travels a total distance of at most a budget \(B > 0\), the same for all, and knows how much of it remains
Colours · colours of the light per robot (0 for oblivious robots)
tight
\(\Theta(1)\): between 2 and 12 colours.
lower bound
bottleneckmemory
holds when
  • fault-free bound (no robot faulty): one colour does not suffice when \(n\) is unknown and robots must terminate (Section 7 of Di Luna et al. 2017)
introductory—
current best
\(12\)
\(n \ge 3\)a common fixed reference point that every robot sees in every Look, whatever robots lie in between, and that lies outside the convex hull of the initial configuration; it gives no common directiona faulty robot keeps changing its light: the fault stops only its movementevery robot travels a total distance of at most a budget \(B > 0\), the same for all, and knows how much of it remains

Results, in order of publication

Shukla et al. 2026a preprint current best
Time \(O(n)\)Colours \(12\)
\(n \ge 3\)a common fixed reference point that every robot sees in every Look, whatever robots lie in between, and that lies outside the convex hull of the initial configuration; it gives no common directiona faulty robot keeps changing its light: the fault stops only its movementevery robot travels a total distance of at most a budget \(B > 0\), the same for all, and knows how much of it remains

Theorem 1: \(O(n)\) epochs (Lemma 22), 12 colours, collision-free (Lemma 21), and each robot moves at most four times (Lemma 10); the robots are not sent to corners of a convex hull. A preprint; several proofs are only sketched.

Open questions

  1. Can mobility-fault-tolerant mutual visibility under a movement budget be solved without the common reference point and without any axis agreement Shukla et al. 2026a?

  2. Does the budget-constrained algorithm extend to ASYNC Shukla et al. 2026a?

Notes

Shukla, Maiti, Kumar and Bhagat add a movement budget: each robot may travel a total distance of at most \(B\), so robots cannot be sent to the corners of a distant convex hull. Their algorithm moves robots by small steps, at most a fixed fraction of the distances to the other robots it sees and to the lines through them, in four phases encoded by the light colours (Section 3): every non-faulty robot first makes one step off the lines through it, the robots at the ends of each line before those between them; then robots that are still between two others step towards the reference point, the farthest from it first, which breaks cyclic dependencies; finally robots at the ends of lines make one step towards it, to get past faulty robots. Their goal is stronger than that of Poudel et al. 2021: a non-faulty robot must also see every faulty robot. As reported by Shukla et al. 2026a (Section 1.1 and Table 1), Pramanick, Jana and Mandal solve mobility-fault-tolerant mutual visibility without axis agreement and without a reference point: for one fault in SSYNC and ASYNC and any number in FSYNC (TCS 2025), and for any number of faults in ASYNC with 35 colours in \(O(n)\) epochs (SIROCCO 2026); neither paper is in the bibliography and neither was read. An algorithm for ASYNC would carry over to this setting. Checked against the full text of Shukla et al. 2026a (arXiv v1: model in Section 2, Theorem 1, Lemmas 10 and 21–23) and Section 7 of Di Luna et al. 2017.

What carries over from neighbouring settings

Read off the order of assumptions, not checked case by case: results may carry extra assumptions (shown on their pages), and asynchronous time is measured in epochs.

Algorithms from weaker settings work here

No catalogued weaker setting.

Lower bounds from stronger settings hold here

Branches from here

Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.