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›fat, + unlimited visibility, + no faults›+ FSYNC, + lights (LUMI), + rigid

Fat robots, FSYNC, rigid

verified

Time: unknownColours: tight

In FSYNC, fat robots without chirality reach mutual visibility in \(O(n)\) rounds with 2 colours, which is optimal.

Assumed (added on the last edge are outlined)

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

Not assumed

Bodyfat robots (unit discs)Opacityopaque: collinear robots hide each otherAgreement 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: fat: Each robot is a closed disc of radius 1 (unit disc). Discs may not overlap, so robots cannot share a point and must avoid collisions; a disc hides what lies behind it from other robots. Gathering then asks for a configuration whose union of discs is connected and in which every robot sees all others Czyzowicz et al. 2009.
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: FSYNC: FSYNC: every robot executes one atomic cycle in every round.
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.