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).

no assumptions›+ point, + unlimited visibility›+ no faults›ASYNC, + lights (LUMI)›disoriented, + rigid

Lights, ASYNC, rigid

verified
Time: tightColours: tight

In rigid ASYNC, 3 colours suffice, and \(O(1)\) epochs are achievable with 47 colours.

Assumed (added on the last edge are outlined)

+Bodypoint robots+Visibilityunlimited+Faultsno faults+Lights (persistent memory)full light (LUMI): every robot sees all lights, including its own+Movementrigid: every move reaches its destination

Not assumed

Opacityopaque: collinear robots hide each otherSchedulerasynchronous (ASYNC)Agreement on coordinatesno agreement on local coordinate systemsMultiplicity 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: no faults
All robots follow the algorithm forever.
Scheduler: ASYNC
ASYNC: each robot's Look, Compute and Move phases take finite but unbounded, adversarially chosen time; a robot may look while others move, and compute on an outdated snapshot. Time is counted in epochs: an epoch is an interval of time in which every robot completes at least one full Look–Compute–Move cycle; it need not be the shortest such interval. The execution is divided into consecutive epochs, and a bound of \(X\) epochs holds for every such division. In FSYNC and SSYNC time is counted in rounds. Called Corda by Prencipe Prencipe 2007. Intermediate variants restrict interleavings: LC-atomic (no Look by another robot between a robot's Look and its Compute), Move-atomic (no Look during another robot's Move) and CM-atomic Flocchini et al. 2023.
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 Masuzawa et al. 2026.
Movement: rigid
Every Move phase ends at the computed 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.

What is known

Time · rounds (FSYNC, SSYNC) or epochs (ASYNC) until the task is done; "finite" when only solvability is known
tight
\(\Theta(1)\) epochs.
lower bound
\(\Omega(1)\) Sharma et al. 2021
bottlenecktrivial
holds when
  • at least one epoch
introductory
\(\text{finite}\)
current best
\(O(1)\)
Colours · colours of the light per robot (0 for oblivious robots)
tight
\(\Theta(1)\); 2 or 3 colours for finite time, 47 for \(O(1)\) epochs.
lower bound
\(2\) Di Luna et al. 2017
bottleneckmemory
holds when
  • Section 7: one colour does not suffice when \(n\) is unknown and robots must terminate
introductory
\(3\)
current best
\(47\)

Results, in order of publication

Di Luna et al. 2017 introductory
Time \(\text{finite}\)Colours \(3\)

Collision-free.

Sharma et al. 2015 also
Time \(\text{finite}\)Colours \(2\)

Claimed optimal colours; later papers disagree on its setting, and the paper was not read.

Sharma et al. 2017 also
Time \(O(\log n)\)Colours \(O(1)\)

Abstract only.

Sharma et al. 2021 current best
Time \(O(1)\)Colours \(47\)

Theorem 1: \(O(1)\) epochs, collision-free; first appeared in 2017. Its conclusion says 60 colours.

Open questions

  1. Fewer colours with \(O(1)\) epochs Sharma et al. 2021.

  2. Time bounds with non-rigid moves.

Notes

Unverified: Sharma et al. 2015 and Sharma et al. 2017 were not read in full.

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

Lights, SSYNC, rigid
Colours \(2\)

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