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. 2021a.

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 in SSYNC, 2 colours suffice, which is optimal.
unknown \(\text{finite}\) vs —
tight \(2\) 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
Finite state, SSYNC, non-rigid
One bit of persistent memory that other robots cannot see suffices in SSYNC with non-rigid moves and no common orientation.
unknown \(\text{finite}\) vs —
tight \(2\) vs \(2\) memory
Lights, ASYNC, rigid
In rigid ASYNC, 2 colours suffice, which is optimal, 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, 2 colours suffice in ASYNC if robots agree on one axis; without axis agreement the problem is open.
unknown \(\text{finite}\) vs —
tight \(2\) vs \(2\) memory
Lights, FSYNC, rigid, chirality
In FSYNC with rigid moves and chirality, mutual visibility takes \(O(\log n)\) rounds with 12 colours.
unknown \(O(\log n)\) vs —
tight \(12\) vs —
Lights, mobility faults, SSYNC, non-rigid
With any number of mobility faults, luminous robots without axis agreement reach mutual visibility in non-rigid SSYNC in \(O(n)\) epochs with 12 colours, if they all see a common fixed reference point.
unknown \(O(n)\) vs —
tight \(12\) vs \(2\) memory
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, crash faults, ASYNC, one axis
With up to \(n\) crashed robots, robots that agree on one axis reach mutual visibility in non-rigid ASYNC in \(O(n)\) epochs with 3 colours.
unknown \(O(n)\) vs —
tight \(3\) vs \(2\) memory
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, rigid, one axis
Fat robots that agree on one axis reach mutual visibility in rigid 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 12

Finite state, SSYNC, non-rigid

  1. Solve mutual visibility with finite-state robots under ASYNC Bhagat & Mukhopadhyaya 2019.

Lights, ASYNC, rigid

  1. Fewer colours with \(O(1)\) epochs Sharma et al. 2021a.
  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, FSYNC, rigid, chirality

  1. What is the lower bound on the number of rounds, and can chirality and crossing paths be dropped Vaidyanathan et al. 2015?

Lights, mobility faults, SSYNC, non-rigid

  1. Can mobility-fault-tolerant mutual visibility under a movement budget be solved without the common reference point and without any axis agreement Shukla et al. 2026a?
  2. Does the budget-constrained algorithm extend to ASYNC Shukla et al. 2026a?

Lights, one crash, SSYNC, rigid, compass

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

Lights, crash faults, ASYNC, one axis

  1. Mutual visibility with several crashes when a crashed robot's light stops changing too, which Poudel et al. 2021 call "a major open problem".
  2. Two colours in ASYNC with crashes Poudel et al. 2021.

Fat robots, ASYNC, rigid, one axis

  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.

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. 2015b; then time with \(O(1)\) colours Vaidyanathan et al. 2015 Sharma et al. 2021a, 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.

Further reading

Papers on this problem that are not yet placed in a setting.

  • Cicerone et al. 2023c Time-Optimal Geodesic Mutual Visibility of Robots on Grids Within Minimum Area. Geodesic mutual visibility on graphs: robots on the nodes of a grid must reach nodes such that every two are joined by a shortest path through no other robot. Time-optimal algorithms for oblivious synchronous robots with chirality on finite and infinite square grids, within the minimum area (Theorem 1). Read (arXiv v1). Also in the journal paper Cicerone et al. 2023b.
  • Badri et al. 2024 An optimal algorithm for geodesic mutual visibility on hexagonal grids. Geodesic mutual visibility on finite hexagonal grids: the largest mutual-visibility sets (Theorem 1) and an optimal algorithm for synchronous oblivious robots with chirality (Theorem 2). Read (arXiv v2).
  • Cicerone et al. 2025a Mutual and total mutual visibility in hypercube-like graphs. The graph-theoretic side: mutual-visibility and total mutual-visibility numbers of hypercubes, Fibonacci cubes (journal version only), cube-connected cycles and butterflies: approximation algorithms for the first three, and exact formulae \(2^{d+1}-2\) and \(2^d\) for the butterfly of dimension \(d\). Read (arXiv v1 and the journal version).
  • Kim et al. 2023 Complete Visibility Algorithm for Autonomous Mobile Luminous Robots under an Asynchronous Scheduler on Grid Plane. Robots on the infinite grid with lights of two colours under ASYNC reach complete visibility in \(O(\Delta_0 + n)\) rounds within \(O(n^2)\) area (Theorem 1, proof sketched). Read (arXiv v1). The journal version Kim et al. 2025 proves the lemmas in full but states \(O(\Delta_0 + n^2)\) rounds.
  • Alsaedi et al. 2023b Shortest Paths of Mutually Visible Robots. A centralised motion-planning relative: move \(n\) robots inside a simple polygon along shortest paths to their targets while keeping them mutually visible; \(O(mn)\) time when starts and targets lie on two disjoint segments. Read (arXiv v2).
  • Dolev et al. 2019 Brief Announcement: Neighborhood Mutual Remainder and Its Self-Stabilizing Implementation of Look-Compute-Move Robots. A synchronisation tool for Look–Compute–Move robots: a self-stabilizing implementation of neighbourhood mutual remainder, used to make moves atomic and to simulate FSYNC with clocks of equal speed. Read (arXiv v1).
  • Bhagat et al. 2016b Formation of General Position by Asynchronous Mobile Robots Under One-Axis Agreement. ASYNC opaque robots that agree on one axis reach general position (no three collinear). Abstract read.
  • Sharma et al. 2015a Bounds on Mutual Visibility Algorithms. Runtime of Di Luna et al.'s algorithms with lights in FSYNC: Contain takes \(\Theta(n)\) rounds and Shrink \(\Omega(n^2)\); Modified Shrink takes \(O(n\log n)\) and needs \(\Omega(n)\). Abstract read.
  • Sharma et al. 2021b Optimal Randomized Complete Visibility on a Grid for Asynchronous Robots with Lights. Randomized complete visibility on the infinite grid by ASYNC robots with lights and obstructed visibility, with optimal time. Abstract read.
  • Kim et al. 2025 Complete Visibility Algorithms of Luminous Robots With Two-Color Lights on Grid. Journal version of Kim et al. 2023: ASYNC oblivious robots on the infinite grid that agree on the direction and orientation of both axes, with lights of two colours and without knowing \(n\), reach complete visibility from any configuration (Theorem 2, proved through Lemmas 1–13) in \(O(\Delta_0 + n^2)\) asynchronous rounds (their \(D\) is \(\Delta_0\) here) within the optimal area \(O(n^2)\). Read in full.
  • Cicerone et al. 2023b The geodesic mutual visibility problem: Oblivious robots on grids and trees. Poses geodesic mutual visibility: robots on distinct nodes of a graph must reach, without collisions, nodes such that every two are joined by a shortest path through no other robot. On finite grids, oblivious FSYNC robots with chirality solve it from asymmetric configurations within the smallest bounding rectangle by a time-optimal algorithm (Theorem 1), with an informal extension to infinite grids. On trees, oblivious SSYNC robots, at most one per leaf, solve it from configurations without critical nodes, where two robots would have to cross one node (Theorems 2, 3), in \(O(nD)\) epochs against \(\Omega(n + D)\), \(D\) the diameter of the tree (Lemmas 11, 12). Read in full.

All settings

The assumption tree (12 settings, 7 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.