Mobility Matters
Home›Mobile robots in the plane›Symmetry breaking and spreading›Separation

Separation

Robots of different (hidden) colours must separate so that each colour class occupies its own region.

Problem statement and measurescollapse
sector 1sector 2sector 1sector 2sector 1sector 2sector 1sector 2sector 1sector 2sector 1sector 2Start: robots see the others' colours, not their ownRound 1: all move to the lower semicircleOne sector per colour; two robots are misplacedA signaller moves to point at a misplaced robotIt reads the signal and moves to its sectorSectors separated by colourFinal: one semicircle per colour
Separation: each robot carries a fixed colour that the others see but it cannot; the robots must arrange themselves so that the colour classes are separated, into parallel lines in the standard ASYNC setting Seike & Yamauchi 2023. The animation sketches the SSYNC algorithm for opaque robots Pyati et al. 2026 (read in summary only): the robots move to a semicircle, one sector per colour; a signaller points at a misplaced robot, which then moves to its sector; finally each colour class moves onto its own concentric semicircle.

Each robot has a fixed colour that the others can see but it cannot (an unconscious robot). The robots must arrange themselves so that the colour classes (the sets of robots of one colour) are separated (into points, lines or circles, depending on the variant).

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

Imagine a party where each guest wears a coloured hat they cannot see, but they can see everybody else's hat, and nobody may speak. The guests must sort themselves so that all red hats stand on one line, all blue hats on another, and so on. In the separation problem the guests are \(n\) point robots in the plane, and a hat is a robot's colour: fixed, seen by the others but not by the robot itself (an unconscious robot). Each robot repeats a Look–Compute–Move cycle: it looks at the others, computes a destination and moves there. In the basic version robots are oblivious (they forget everything after each move), see everybody, and their local coordinate systems (each robot's private axes and unit of length) agree on the direction of one axis; the scheduler, an adversary that decides when each robot acts, is asynchronous (ASYNC): a robot may look while others are still moving. They must end up separated into parallel lines, one colour class (all robots of one colour) per line.

1AlgorithmOthers tell you where to go Opaque robots, SSYNC → Pyati et al. 2026

The key difficulty is that a robot does not know its own colour, but every other robot does. One way out, used with opaque robots (robots that block the view of robots behind them) under SSYNC (time is divided into rounds, and in each round some robots each perform one full cycle):

  1. Bring all robots to the lower half of a circle, where everybody can see everybody.
  2. Divide this semicircle into sectors, one per colour.
  3. A few chosen robots act as signallers: by moving to a carefully chosen point they encode "the robot of colour \(c\) at this position should go to sector \(j\)".
  4. The robot addressed reads the signal and moves to its sector, without ever learning its colour directly.
  5. Finally each sector is moved onto its own semicircle, so colour classes lie on concentric semicircles.
Why it works and what it costs. Positions are the only way robots can pass information, so the algorithm turns positions into messages. Pyati et al. 2026 reach concentric semicircles in \(O(n)\) epochs (an epoch is an interval of time in which every robot completes at least one full cycle) without collisions and without knowing \(n\). We read only a summary of this paper's arXiv version, so the steps above give the idea, not its details. The algorithms for the standard ASYNC variant are different and are not described here.

Why it matters. Using movement as a message channel is how silent robots share information they cannot sense themselves, the same idea behind signalling with lights.

2ImpossibilityA colour with only one robot ASYNC, one common axis → Flocchini et al. 2024

Asynchronous separation into parallel lines is solvable when robots share one axis, provided no colour class has a single robot. If some robot is the only one of its colour, Flocchini et al. 2024 show that no algorithm works. The proof is a symmetry argument in the paper and is not reproduced here.

Why it holds. The catalogue records the condition but not its proof, and we have not read the full text. A student should take away the shape of the result: solvability depends on how many robots share each colour, because a robot can learn about its own colour only from what the other robots do.

Why it matters. It marks the exact boundary between possible and impossible for the asynchronous algorithm of Flocchini et al. 2024.

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, one common axis standard
Robots that carry a colour visible to others but not to themselves separate by colour into parallel lines, under ASYNC, if they share one axis.
unknown \(\text{finite}\) vs \(\text{impossible}\) symmetry
tight \(0\) vs —
Opaque robots, SSYNC
Opaque unconscious robots separate into concentric semicircles in \(O(n)\) epochs.
unknown \(O(n)\) vs —
tight \(0\) vs —

What the community started looking at

Separation of unconscious coloured robots asked whether robots that cannot see their own colour can still sort themselves by colour, first synchronously Seike & Yamauchi 2023, then asynchronously Flocchini et al. 2024 and with opaque robots Pyati et al. 2026.

Related problems

k-grouping: Both split the swarm into classes; in separation the classes are fixed by hidden colours, in \(k\)-grouping and partitioning they are chosen by the robots.

Separation of coloured particles: Robots in the plane separate by hidden colours with deterministic algorithms; here a stochastic local rule separates two visible colours.

All settings

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