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

Fat robots, ASYNC, rigid, one axis

verified
Time: unknownColours: tight

Fat robots that agree on one axis reach mutual visibility in rigid ASYNC in \(O(n)\) epochs with \(O(1)\) colours.

Assumed (added on the last edge are outlined)

+Visibilityunlimited+Faultsno faults+Lights (persistent memory)full light (LUMI): every robot sees all lights, including its own+Agreement on coordinatesagreement on one axis (no common chirality)+Movementrigid: every move reaches its destination

Not assumed

Bodyfat robots (unit discs)Opacityopaque: collinear robots hide each otherSchedulerasynchronous (ASYNC)Multiplicity 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. 2009b.
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: one axis
All robots agree on the direction and orientation of one axis (e.g. North), but not necessarily on handedness: two robots may disagree on which side is East. This is how the papers use one axis agreement (e.g. robots "agree on only 'left' and 'right'" Bose et al. 2021a; robots "do not necessarily have the same handedness" Pagli et al. 2015). One axis and chirality are alternatives on this axis; together they amount to a common compass.
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
unknown
No lower bound is recorded. Bhagat et al. 2024 attribute an \(\Omega(\sqrt{n})\) lower bound to Sharma et al. 2018, but that paper (ICDCN 2018) states no lower bound.
lower boundnone known
introductory—
current best
\(O(n)\)
\(n \ge 3\)robots know their common radius
Colours · colours of the light per robot (0 for oblivious robots)
tight
\(\Theta(1)\).
lower boundnone known
introductory—
current best
\(O(1)\)
\(n \ge 3\)robots know their common radius

Results, in order of publication

Bhagat et al. 2024 current best
Time \(O(n)\)Colours \(O(1)\)
\(n \ge 3\)robots know their common radius

Introductory and current best for ASYNC (Theorem 1, Lemma 3.17): \(n \ge 3\) unit discs, collision-free, \(n\) unknown; the robots end on a semicircle.

Open questions

  1. Non-rigid moves, and SSYNC and ASYNC extensions of the 2-colour FSYNC algorithm Alsaedi et al. 2023a.

  2. Mutual visibility of fat robots in ASYNC with non-rigid moves and no axis agreement Bhagat et al. 2024.

Notes

Checked against the full text of Bhagat et al. 2024 (Section 2, Theorem 1). The variant was previously recorded without rigid moves; the paper assumes "rigid movement". Its count of colours is \(O(1)\); the phases use 3 to 5 colours each (Lemmas 3.3, 3.7 and 3.14), and the total is not stated.

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