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 measuresexpand

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

no assumptions›+ point, + unlimited visibility›opaque, + no faults, + SSYNC, + one axis

Opaque robots, SSYNC

verified
Time: unknownColours: tight

Opaque unconscious robots separate into concentric semicircles in \(O(n)\) epochs.

Assumed (added on the last edge are outlined)

+Bodypoint robots+Visibilityunlimited+Faultsno faults+Schedulersemi-synchronous (SSYNC)+Agreement on coordinatesagreement on one axis (no common chirality)

Not assumed

Opacityopaque: collinear robots hide each otherLights (persistent memory)oblivious, no light (OBLOT)Movementnon-rigid: the adversary may stop a move after some minimum distance \(\delta\)Multiplicity detectionnone: a point with several robots looks like one robotRandomnessdeterministicIdentifiersanonymous: all robots are identical
Formal definitions of this setting
Body: point
Each robot is a point of the plane: several robots may share a point (multiplicity), and a robot hides only what lies exactly behind it on a line of sight.
Visibility: unlimited visibility
A robot sees all robots (subject to opacity).
Opacity: opaque
Robots are points that obstruct sight: \(r\) sees \(s\) iff no third robot lies on the open segment \(\overline{rs}\).
Faults: no faults
All robots follow the algorithm forever.
Scheduler: SSYNC
SSYNC: time is divided into rounds; in each round a non-empty subset of robots, chosen by a fair adversary, executes one atomic Look–Compute–Move cycle. Called Atom by Prencipe Prencipe 2007.
Lights (persistent memory): oblivious
OBLOT: a robot's computation depends only on the current snapshot; nothing persists across cycles.
Agreement on coordinates: one axis
All robots agree on the direction and orientation of one axis (e.g. North), but not necessarily on handedness: two robots may disagree on which side is East. This is how the papers use one axis agreement (e.g. robots "agree on only 'left' and 'right'" Bose et al. 2021; robots "do not necessarily have the same handedness" Pagli et al. 2015). One axis and chirality are alternatives on this axis; together they amount to a common compass.
Movement: non-rigid
In a Move phase the adversary may stop a robot before its destination, but only after it has travelled at least \(\delta>0\) (a constant unknown to the robots) or reached the destination.
Multiplicity detection: no multiplicity detection
A snapshot is a set of points: a point occupied by several robots looks like a single robot.
Randomness: deterministic
The destination computed in a cycle is a function of the snapshot (and the light, if any).
Identifiers: anonymous
Robots are indistinguishable and run the same algorithm.

What is known

Time · rounds (FSYNC, SSYNC) or epochs (ASYNC) until the task is done; "finite" when only solvability is known
unknown
No lower bound recorded.
lower boundnone known
introductory—
current best
\(O(n)\)
Colours · colours of the light per robot (0 for oblivious robots)
tight
—
lower boundnone known
introductory—
current best
\(0\)

Results, in order of publication

Pyati et al. 2026 current best
Time \(O(n)\)Colours \(0\)

Collision-free; robots do not know \(n\).

Open questions

None recorded for this variant.

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