Mobility Matters
Home›Mobile robots in the plane›Formation problems›Pattern formation›Uniform circle formation

Uniform circle formation

Robots must form a regular \(n\)-gon: a circle with equal spacing.

Problem statement and measurescollapse
Start: inner robots move out to the fixed circleAll on the circle: move to hexagon verticesFinal: a regular hexagon
Uniform circle formation: \(n\) oblivious robots at distinct points must occupy the vertices of a regular \(n\)-gon, of any position and size, and stay there Flocchini et al. 2017. Shown in SSYNC rounds (ringed robots are activated), simplified from Flocchini et al. 2017: the smallest enclosing circle (dashed) never changes; robots inside move out to it, then robots on it move to the vertices of a regular hexagon inscribed in it (hollow).

\(n\) robots start at distinct points and must reach the vertices of a regular \(n\)-gon (in any position and size) and stay there. Time is in epochs (ASYNC: intervals in which every robot completes at least one full Look–Compute–Move cycle) or rounds; colours count light colours in the luminous model.

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 guards who must stand evenly spaced around a circular fence that nobody has built: the circle and the spacing must come from the guards themselves. There are \(n\) robots, points at distinct places in the plane; their positions form the configuration. Each robot repeats a Look–Compute–Move cycle: it takes a snapshot of where the other robots are (Look), decides on a destination point (Compute) and moves towards it (Move). They are identical, silent, oblivious (no memory between cycles), and each uses its own local coordinate system, so they agree on no direction and no handedness. The scheduler (an adversary) decides the activation of robots, that is, when each performs a cycle, and is ASYNC: each phase may take any finite time. Every move is a non-rigid move: a robot may be stopped after a minimum distance \(\delta\). The robots must reach the vertices of a regular \(n\)-gon (a polygon with \(n\) equal sides and equal angles), one robot on each vertex, of any size and position, and stay there.

1AlgorithmFix the smallest enclosing circle, reach it, then let symmetric robots move as one ASYNC, oblivious, disoriented → Flocchini et al. 2017
  1. Compute the smallest enclosing circle (SEC) of all robots; every robot computes the same circle. All moves are chosen so that this circle does not change.
  2. Robots inside the circle move out to it, as in circle formation.
  3. With all robots on the circle, group them into analogy classes: two robots are analogous if some symmetry of the whole configuration maps one to the other.
  4. The scheduler could make analogous robots act identically anyway, so the algorithm makes each class always move together, deliberately and symmetrically.
  5. The robots compute the vertices of a regular \(n\)-gon on the circle and move to them class by class. Special configurations that are already close to regular (pre-regular, biangular) get their own procedure.
Why it works and what it costs. The overall plan is simple; the difficulty is that asynchronous robots act on outdated snapshots, so the analogy classes and destinations that one robot computes may already be stale. Flocchini, Prencipe, Santoro and Viglietta show that oblivious, disoriented robots with non-rigid moves form a regular \(n\)-gon in ASYNC from every initial configuration at distinct points, for every \(n\) Flocchini et al. 2017; the case \(n = 4\) is solved in Mamino & Viglietta 2016. Time is not analysed; for opaque robots with lights, \(O(1)\) epochs and \(O(1)\) colours suffice Feletti et al. 2024.

Why it matters. It closed a long-standing question and showed that, for pattern formation, asynchrony, chirality and rigid moves do not add computational power.

2ImpossibilityTwo robots on the same point can never be separated ASYNC, oblivious, disoriented → Flocchini et al. 2017

Suppose two robots start at the same point. They get exactly the same snapshot. The adversary gives them identical local coordinate systems and the scheduler always activates them together. Identical robots with identical snapshots and identical local coordinate systems compute the same destination, so they move together and are still on one point after every cycle. A regular \(n\)-gon has \(n\) distinct vertices, so it is never formed.

Why it holds. This is why the problem asks for distinct starting points; Flocchini et al. note that with two robots on one point the problem is "easily seen to be unsolvable" Flocchini et al. 2017. The same trap is the reason careful algorithms never let two robots meet while they move.

Why it matters. It is the simplest example of a symmetry that oblivious deterministic robots can never break.

3ImpossibilityWhy only the point and the regular polygon can be formed from every initial configuration ASYNC, oblivious, disoriented → Suzuki & Yamashita 1999

Start the robots on a regular \(n\)-gon. Give every robot a local coordinate system whose \(x\)-axis points to the centre, all with the same unit. All robots get the same snapshot; if the scheduler activates all of them together, they all make the same move up to rotation, so the configuration stays a regular \(n\)-gon (or collapses to its centre). So from this initial configuration the only formable patterns are the regular \(n\)-gon and the single point.

Why it holds. Suzuki and Yamashita showed that the patterns formable from an initial configuration depend on its symmetricity, its amount of rotational symmetry Suzuki & Yamashita 1999; the regular \(n\)-gon has the most. Hence the point (gathering) and the regular \(n\)-gon (uniform circle) are the only patterns that might be formable from every initial configuration, and both are Flocchini et al. 2017.

Why it matters. It explains why the uniform circle is singled out among all patterns: it is one of only two universally formable ones.

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
ASYNC, oblivious, disoriented standard
Oblivious, disoriented, non-rigid robots form a regular \(n\)-gon from any configuration of distinct points, for every \(n\).
unknown \(\text{finite}\) vs \(\text{impossible}\) symmetry
tight \(0\) vs —
SSYNC, oblivious
The first deterministic uniform circle formation, for \(n \ge 5\) semi-synchronous robots.
unknown \(\text{finite}\) vs —
tight \(0\) vs —
Opaque robots with lights, ASYNC
With lights, opaque robots form a uniform circle in \(O(1)\) epochs with \(O(1)\) colours, which is optimal in both.
tight \(O(1)\) vs \(\Omega(1)\) trivial
tight \(O(1)\) vs \(\Omega(1)\) trivial
Opaque robots with lights, FSYNC
In FSYNC, opaque luminous robots form a uniform circle in 3 cycles with \(O(1)\) colours.
tight \(3\) vs —
tight \(O(1)\) vs —
Transparent fat robots, SSYNC
Transparent fat robots that agree on one axis form a regular \(n\)-gon of given side in SSYNC.
unknown \(\text{finite}\) vs —
tight \(0\) vs —
Opaque fat robots, ASYNC, limited visibility, compass
Opaque fat robots with limited visibility and a common coordinate system form a uniform circle of given centre and radius in ASYNC.
unknown \(\text{finite}\) vs —
tight \(0\) vs —

Open questions 3

ASYNC, oblivious, disoriented

  1. Can oblivious robots without lights form a uniform circle in \(O(1)\) epochs, with rigid or non-rigid moves? Feletti et al. 2024

Opaque robots with lights, ASYNC

  1. What is the exact minimum number of colours for \(O(1)\)-epoch uniform circle formation in ASYNC? Feletti et al. 2024
  2. Uniform circle formation with non-rigid moves in the luminous opaque model Feletti et al. 2024.

What the community started looking at

Uniform circle formation was first asked as solvability: can disoriented oblivious robots form a regular polygon? It was solved for SSYNC Dieudonné et al. 2008 and then for ASYNC without chirality or rigidity Flocchini et al. 2017 Mamino & Viglietta 2016. Only after feasibility was settled did the community turn to time and colours for luminous opaque robots Feletti et al. 2023 Pattanayak & Sharma 2024, reaching \(O(1)\) epochs with \(O(1)\) colours Feletti et al. 2024.

Special case of Pattern formation

Uniform circle formation is "an important special case of the geometric pattern formation problem" Feletti et al. 2024: the target is the regular \(n\)-gon. It is also the special case of circle formation with equal spacing; circle formation is "its precursor" Feletti et al. 2024.

Related problems

Circle formation: A uniform circle is a circle, so every uniform-circle algorithm forms a circle.

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.

All settings

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