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 measurescollapse
Start: hidden robots on hull edges and insideCorner robots cut in and set their light to VertexFinal: all see each other; the robots stop
Mutual visibility: opaque robots at distinct points, where a robot hides those behind it, must reach a configuration with no three robots collinear, so that every robot sees every other, without collisions. Shown: the Shrink idea of Di Luna et al. 2017 in SSYNC rounds with rigid moves: a ringed (activated) robot that is at a corner of the convex hull (dashed) of the robots it sees moves a little into the triangle with its two hull neighbours, staying at a corner, and sets its light to Vertex (green); hidden robots become corner robots in turn.

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

A first look

the basic problem, a simple algorithm and why some things cannot be done, for a newcomer

Picture people at a party who want every pair of them to be able to see each other, but bodies block the view: you cannot see someone directly behind another person. There are \(n\) robots, points at distinct places in the plane; their positions form the configuration. The robots are opaque: robot \(r\) sees robot \(s\) only if no third robot lies on the straight segment between them. Each robot repeats a Look–Compute–Move cycle: it takes a snapshot of the robots it sees (Look), decides on a destination point (Compute) and moves towards it (Move). Each robot carries a light showing one of \(c\) colours, which all robots can see and which persists between cycles; otherwise robots remember nothing. In the basic version the scheduler, an adversary, is SSYNC: time runs in rounds, and in each round it decides the activation of some robots, each of which performs one cycle; every move is a rigid move (a robot always reaches its destination). The robots must reach, without two of them ever colliding, a configuration in which no three are on a line, so all see each other, and then stop.

1AlgorithmShrink: only corner robots move, cutting corners of the convex hull Lights, SSYNC, rigid → Di Luna et al. 2017

The convex hull is the shape of a rubber band stretched around all robots; its corner points are its corners, and a robot at one of them is a corner robot. Lights have two colours, Off and Vertex (meaning: I am at a corner), all starting Off.

  1. A robot that is not at a corner of the convex hull of the robots it sees does nothing.
  2. A corner robot sets its light to Vertex, finds its two neighbours \(a\) and \(b\) along the hull, and moves a little into the triangle formed by itself, \(a\) and \(b\), cutting off its corner.
  3. The move is kept inside a smaller safe triangle, so that robots moving at the same time cannot collide, and the robot stops on the nearest line parallel to \(ab\) through another robot, so that it stays at a corner.
  4. A robot that sees only robots with light Vertex knows that it sees everybody, and stops.
Why it works and what it costs. Each cut shrinks the hull and can turn a robot that was hidden on an edge or inside into a new corner robot; eventually all robots are at the corners of a convex polygon, and then nobody blocks anybody. Some configurations need an inside robot to move: in a centrally symmetric configuration with a robot at the centre, symmetric robots can be made to move symmetrically forever, and the central robot keeps hiding pairs; the paper handles such cases separately. Di Luna, Flocchini, Gan Chaudhuri, Poloni, Santoro and Viglietta prove that this solves the problem in rigid SSYNC with 2 colours, which is optimal, and with no lights if \(n\) is known Di Luna et al. 2017. In ASYNC, \(O(1)\) epochs (intervals in which every robot completes a cycle) are achievable with more colours Sharma et al. 2021.

Why it matters. It introduced the luminous-robot approach to obstructed visibility, and its output (all robots on a convex polygon) is a starting point for other tasks on opaque robots.

2Lower boundWithout lights, a robot cannot know when to stop Lights, SSYNC, rigid → Di Luna et al. 2017

Suppose robots have no lights (one colour) and do not know \(n\). A robot sees, say, four other robots at the vertices of a square. Maybe that is everybody, and it should stop. Or maybe a fifth robot hides exactly behind one of the four, on the same line of sight, and the robots must still move. The two situations give the robot the same snapshot, and stopping cannot be undone, so whatever it decides is wrong in one of them.

Why it holds. Hence at least 2 colours are needed when \(n\) is unknown and robots must stop (Section 7 of Di Luna et al. 2017), and Shrink shows that 2 suffice in rigid SSYNC. If \(n\) is known, a robot can count the robots it sees and stop when it sees \(n - 1\) others, so no light is needed. The authors note that if robots only need to stand still forever, without explicitly stopping, this argument does not apply.

Why it matters. It shows that the cost of detecting completion, not of reaching it, is what forces memory.

What is known

The best upper bound against the best lower bound in each catalogued setting. Open a setting for its results, proofs and notes, or see the progress map with the branch points.

tight near-optimal polynomial gap unknown impossible· one row per catalogued setting, in tree order; each cell: best upper bound vs lower bound, and what forces the lower bound
Setting
Time
Colours
Lights, SSYNC, non-rigid
With non-rigid moves, 3 colours suffice in SSYNC, and 2 if \(\delta\) or \(n\) is known.
unknown \(\text{finite}\) vs —
tight \(3\) vs \(2\) memory
Lights, SSYNC, rigid
Opaque luminous robots reach mutual visibility in rigid SSYNC with 2 colours, which is optimal; oblivious robots suffice if \(n\) is known.
tight \(\text{finite}\) vs —
tight \(2\) vs \(2\) memory
Lights, ASYNC, rigid
In rigid ASYNC, 3 colours suffice, and \(O(1)\) epochs are achievable with 47 colours.
tight \(O(1)\) vs \(\Omega(1)\) trivial
tight \(47\) vs \(2\) memory
Lights, ASYNC, non-rigid, one axis
With non-rigid moves, 3 colours suffice in ASYNC if robots agree on one axis; without axis agreement the problem is open.
unknown \(\text{finite}\) vs —
tight \(3\) vs \(2\) memory
Lights, FSYNC, chirality
In FSYNC with chirality, complete visibility takes \(O(\log n)\) rounds with 12 colours.
unknown \(O(\log n)\) vs —
tight \(12\) vs —
Lights, one crash, SSYNC, rigid, compass
With one crash fault, robots that share a compass reach mutual visibility in rigid SSYNC with 3 colours.
unknown \(\text{finite}\) vs —
tight \(3\) vs —
Lights, one Byzantine robot
With one Byzantine robot among three, mutual visibility is impossible.
impossible — vs \(\text{impossible}\) indistinguishable Byzantine agents
impossible — vs —
Fat robots, ASYNC, one axis
Fat robots that agree on one axis reach mutual visibility in ASYNC in \(O(n)\) epochs with \(O(1)\) colours.
unknown \(O(n)\) vs —
tight \(O(1)\) vs —
Fat robots, FSYNC, rigid
In FSYNC, fat robots without chirality reach mutual visibility in \(O(n)\) rounds with 2 colours, which is optimal.
unknown \(O(n)\) vs —
tight \(2\) vs \(2\) memory

Open questions 6

Lights, SSYNC, non-rigid

  1. Does the 2-colour algorithm work in non-rigid SSYNC without knowing \(\delta\) Di Luna et al. 2017?

Lights, ASYNC, rigid

  1. Fewer colours with \(O(1)\) epochs Sharma et al. 2021.
  2. Time bounds with non-rigid moves.

Lights, ASYNC, non-rigid, one axis

  1. Mutual visibility in non-rigid ASYNC without axis agreement, ideally with 2 colours Di Luna et al. 2017.

Lights, one crash, SSYNC, rigid, compass

  1. Tolerating three or more crashes, and using 2 colours Aljohani & Sharma 2018.

Fat robots, ASYNC, one axis

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

What the community started looking at

Mutual visibility arose from obstructed visibility: before opaque robots can coordinate they must see each other. The first questions were feasibility and the number of colours Di Luna et al. 2017 Sharma et al. 2015; then time with \(O(1)\) colours Vaidyanathan et al. 2015 Sharma et al. 2021, and fat robots Sharma et al. 2018 Bhagat et al. 2024.

Special case of Pattern formation

Mutual visibility asks for any pattern in general position, a family of patterns; it is the usual first step of pattern formation for opaque robots.

Perspectives

  • Weak robots in the plane Why the theory of robots in the plane starts from oblivious, anonymous, disoriented points; how formation problems became its testbed and the scheduler its adversary; and how a light with a few colours turned into memory, communication and a measure.
  • When agents fail A node that destroys visitors, a robot that stops, an agent that lies, a searcher that misses the target: the papers motivate each fault by the hardware or the network, and each kind of fault changes a different measure, from team size to feasibility to an exact constant.

All settings

The assumption tree (9 settings, 5 branch points)

The root assumes nothing. Going down, each edge adds the assumptions on its chips (+blue); a grey chip names the branch that leaves that axis unassumed while a sibling assumes something. Solid nodes are catalogued variants with their status per measure (Time, Colours); dashed nodes are branch points with no catalogued variant, named after the axis on which their branches differ. Axis order: Body › Visibility › Opacity › Faults › Scheduler › Lights (persistent memory) › Agreement on coordinates › Movement › Multiplicity detection › Randomness › Identifiers.

tight near-optimal polynomial gap unknown impossible no variant

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