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›Byzantine, + SSYNC, + lights (LUMI), + compass, + rigid

Lights, one Byzantine robot

verified

Time: impossibleColours: impossible

With one Byzantine robot among three, mutual visibility is impossible.

Assumed (added on the last edge are outlined)

+Bodypoint robots+Visibilityunlimited+Schedulersemi-synchronous (SSYNC)+Lights (persistent memory)full light (LUMI): every robot sees all lights, including its own+Agreement on coordinatesagreement on both axes (common compass)+Movementrigid: every move reaches its destination

Not assumed

Opacityopaque: collinear robots hide each otherFaultsup to \(f\) Byzantine robotsMultiplicity 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: Byzantine: Up to \(f\) robots move arbitrarily (adversarially); with lights, they may also set arbitrary colours.
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: compass: All robots agree on the directions and orientations of both axes (a common compass); they may still disagree on origin and unit. Called full compass by Efrima and Peleg, who also use half compass (both axis directions, the positive sense of one axis, no chirality), direction-only and axes-only Efrima & Peleg 2009. Agreement on one axis together with common chirality is equivalent: the orientation of the second axis then follows from handedness.
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

impossible

For \(n = 3\).

lower bound

\(\text{impossible}\) Aljohani & Sharma 2018

bottleneckindistinguishable Byzantine agents

holds when

\(n = 3\) with one Byzantine robot

introductory—

current best—

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

impossible

For \(n = 3\).

lower boundnone known

introductory—

current best—

Results, in order of publication

No result recorded yet.

Open questions

None recorded for this variant.

Notes

Checked against the full text.

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, one crash, SSYNC, rigid, compass

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