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

Circle formation

Robots must reach positions on a common circle.

Problem statement and measurescollapse
Start: the smallest enclosing circle is fixedInner robots move out along their raysFinal: all robots on the circle
Circle formation: robots at distinct points must place themselves at distinct points of one common circle and stay there; the spacing need not be uniform Défago & Konagaya 2002. Shown: the first phase of Flocchini et al. 2017 in SSYNC rounds: every robot computes the smallest enclosing circle (dashed), which never changes; a ringed (activated) robot inside moves out along the ray from the centre, possibly stopping early; the robot at the centre first steps off it.

\(n\) robots start at distinct points and must reach a configuration in which all of them lie on one circle, at distinct points, and stay there. Uniform circle formation additionally asks for a regular \(n\)-gon.

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

Think of dancers who must spread out on one common circle, each at a different spot on it, without anyone drawing the circle first. 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 (origin, axes, unit of length and handedness). A scheduler (an adversary) decides the activation of robots, that is, when each performs a cycle; in the basic version it is ASYNC, so each phase may take any finite time, and every move is a non-rigid move: the adversary may stop a robot after it has travelled some minimum distance \(\delta\). The robots must reach a configuration in which all of them lie on one circle, at distinct points (not necessarily evenly spaced), and stay there.

1AlgorithmUse the smallest enclosing circle and walk out to it Circle formation → Flocchini et al. 2017
  1. Every robot computes the smallest enclosing circle (SEC) of all robots. It is unique and does not depend on any local coordinate system, so all robots compute the same circle.
  2. A robot already on the circle stays where it is.
  3. A robot inside the circle moves straight outwards, along the ray from the centre through itself, to the circle.
  4. A robot exactly at the centre has no ray; it first steps a little away from the centre.
  5. If several robots lie on the same ray, only the outermost one moves out; the others first step sideways onto free rays, so that no two robots ever land on the same point.
Why it works and what it costs. Robots that move from inside onto the circle never change the smallest enclosing circle, so the circle stays fixed while robots move at different speeds and act on outdated snapshots. Each robot inside needs only finitely many moves, since each move covers at least \(\delta\) or reaches the circle. This is the first phase of the uniform circle algorithm of Flocchini, Prencipe, Santoro and Viglietta, which forms even a regular \(n\)-gon (hence a circle) in ASYNC without chirality (agreement on the clockwise direction) Flocchini et al. 2017, the catalogue's current best. Steps 4 and 5 are simplified here; the paper handles robots at the centre and robots on a common ray as separate cases.

Why it matters. The smallest enclosing circle is the standard common reference for disoriented robots, reused in pattern formation, gathering and leader election.

2AlgorithmMove only inside your own zone, then slide along the circle Circle formation, SSYNC → Défago & Souissi 2008
  1. Compute the smallest enclosing circle and use its centre as the origin of polar coordinates.
  2. A robot at the centre steps off it, by less than the distance of any other robot from the centre.
  3. Otherwise, find your two neighbours in angular order around the centre and draw the rays halfway (by angle) to each of them. The region between these two rays is your exclusive zone for this cycle: no other robot will move into it.
  4. A robot inside the circle moves outwards within its zone towards the circle; a robot on the circle slides along it towards the angle halfway between its neighbours, without ever leaving an empty arc larger than a half circle (which would shrink the circle).
Why it works and what it costs. Exclusive zones guarantee that two robots never end up at the same point. That matters: two robots on one point get the same snapshot, so a scheduler that always activates them together, with suitable local coordinate systems, can keep them together forever. Défago and Souissi show that in SSYNC the robots reach the circle and then converge towards even spacing without necessarily reaching it Défago & Souissi 2008; reaching exactly even spacing needed later work (see uniform circle formation).

Why it matters. It introduced the exclusive-zone trick for avoiding inseparable robots and the "slide towards the middle of your neighbours" rule for even spacing.

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
Circle formation standard
Robots must place themselves on a common circle, not necessarily evenly spaced; solved in ASYNC without chirality through uniform circle formation.
unknown \(\text{finite}\) vs —
tight \(0\) vs —
Circle formation, SSYNC
In SSYNC the first algorithms formed a circle and then converged towards a uniform one.
unknown \(\text{finite}\) vs —
tight \(0\) vs —

What the community started looking at

Circle formation was first proposed as a way to reach a uniform circle by oblivious robots without a common orientation Défago & Konagaya 2002; the first algorithms formed a circle and only converged towards uniformity Défago & Souissi 2008. The question was whether disoriented, oblivious robots can form a circle at all, under which scheduler.

Special case of Pattern formation

A circle is a family of patterns; forming some circle is easier than forming a given pattern, and it is the precursor of uniform circle formation Feletti et al. 2024.

Related problems

Uniform 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 (2 settings, 1 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.