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›+ FSYNC, + lights (LUMI), + chirality

Lights, FSYNC, chirality

draft

Time: unknownColours: tight

In FSYNC with chirality, complete visibility takes \(O(\log n)\) rounds with 12 colours.

Assumed (added on the last edge are outlined)

+Bodypoint robots+Visibilityunlimited+Faultsno faults+Schedulerfully synchronous (FSYNC)+Lights (persistent memory)full light (LUMI): every robot sees all lights, including its own+Agreement on coordinatescommon chirality (same clockwise orientation)

Not assumed

Opacityopaque: collinear robots hide each otherMovementnon-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: 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: chirality: All local coordinate systems have the same handedness (clockwise orientation): no reflection. Also called handedness. Prencipe uses chirality for agreement on North and East, i.e. a compass Prencipe 2007.
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.

What is known

Time · rounds (FSYNC, SSYNC) or epochs (ASYNC) until the task is done; "finite" when only solvability is known

unknown

\(O(1)\) is known in SSYNC with rigid moves Sharma et al. 2016, which needs no chirality but is not a weaker setting on every axis.

lower boundnone known

introductory—

current best

\(O(\log n)\)

Vaidyanathan et al. 2015

Colours · colours of the light per robot (0 for oblivious robots)

tight

\(\Theta(1)\).

lower boundnone known

introductory—

current best

\(12\)

Vaidyanathan et al. 2015

Results, in order of publication

Vaidyanathan et al. 2015 current best

Time \(O(\log n)\)Colours \(12\)

Introductory and current best; robot paths may cross. Abstract only.

Open questions

None recorded for this variant.

Notes

Unverified: read from the abstract only.

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

Lights, SSYNC, non-rigid

Time \(\text{finite}\)Colours \(3\)

Lower bounds from stronger settings hold here

No catalogued stronger setting.

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