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

Scattering

Robots that may start at shared points must move to pairwise distinct points.

Problem statement and measurescollapse
H T TT TT TT TT TH TH TH322Start: points of multiplicity 3, 2 and 1Round 1: active robots flip coins; heads moveRound 2: tails everywhere, nobody movesRound 3: one heads separates a pairRound 4: the last pair separatesFinal: all positions distinct
Scattering: robots start at points of the plane, several possibly at the same point (multiplicities shown as numbers), and must reach distinct positions and stay there; deterministically this is impossible Dieudonné & Petit 2009. The animation runs the randomized SSYNC algorithm of Dieudonné & Petit 2009: in each round the adversary activates some robots (coin shown under their point), and a robot that gets heads moves to a point of its own Voronoi cell (thin lines), so robots on different points never meet again.

\(n\) robots start at points of the plane, several possibly at the same point (a multiplicity). They must reach a configuration in which all positions are distinct, and stay there.

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 box of marbles that were all tipped onto the same spot of a table, and you want them to roll apart so that no two touch the same point. In the scattering problem the marbles are \(n\) robots: they start in the plane, several possibly at the same point (a multiplicity), and must reach a configuration (the positions of all robots) in which all positions are distinct, and then stay distinct. Robots are oblivious (they forget everything after each move) and work in Look–Compute–Move cycles: take a snapshot of everyone, compute a destination, move. In each round an adversary (an opponent who controls everything the algorithm does not) chooses which robots act, and each of them performs one full cycle; this is the SSYNC scheduler. In the basic catalogued version robots may flip coins (randomized), and a robot can see how many robots share each point (strong multiplicity detection).

1ImpossibilityTwo robots on one spot can never be told apart Randomized, SSYNC, strong multiplicity detection → Dieudonné & Petit 2009

Start with all robots on the same point, give them all the same local coordinate system (the axes, unit and handedness in which a robot reads its snapshot), and let the adversary activate all of them in every round. Each robot sees exactly the same snapshot, so a deterministic rule (one without coin flips) sends every robot to the same destination. After the move they are again all on one point, with identical snapshots, and so on forever.

Why it holds. By induction, there is an execution in which the robots never separate, so no deterministic algorithm solves scattering Dieudonné & Petit 2009. The argument does not care whether robots remember the past or can count robots at a point: the robots' memories are equal as well, so their histories never differ. Only randomness can make two robots on the same point behave differently.

Why it matters. It is the cleanest example of why some robot problems need randomness at all, and it explains why scattering is studied only with coin flips.

2AlgorithmFlip a coin, then move inside your own Voronoi cell Randomized, SSYNC, strong multiplicity detection → Dieudonné & Petit 2009

Each time a robot is activated:

  1. Look at the occupied points and compute the Voronoi diagram: the Voronoi cell of an occupied point is the set of places strictly closer to it than to any other occupied point.
  2. Flip a fair coin.
  3. Heads: move to some point of your own cell other than where you stand. Tails: stay.
Why it works and what it costs. Robots on different points never collide again, because each moves only inside its own cell and the cells do not overlap. Two robots on the same point are separated in a round where exactly one of them moves; if both are active this happens with probability \(1/2\), so with probability 1 they eventually separate Dieudonné & Petit 2009. If all movers from a point pick the same destination, a crowd of \(q\) robots is at best split in two per round, so about \(\log_2 q\) rounds are needed; robots that can count the robots on their point scatter in \(O(1)\) expected rounds Clement et al. 2010, and with weaker counting \(O(\log\log n)\) rounds, which is optimal for algorithms that use the fewest random bits Bramas & Tixeuil 2017.

Why it matters. Moving only inside your own Voronoi cell is a reusable trick for keeping already separated robots apart, and randomized scattering is used to break symmetry before running deterministic algorithms such as pattern formation.

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
Randomized, SSYNC, strong multiplicity detection standard
Deterministic scattering is impossible; with randomness and strong multiplicity detection robots scatter in \(O(1)\) expected rounds.
tight \(O(1)\) vs \(\text{impossible}\) symmetry
tight \(0\) vs —
Randomized, SSYNC, weak multiplicity detection
Without strong multiplicity detection no algorithm scatters in \(O(1)\) expected rounds; with an optimal number of random bits \(O(\log\log n)\) rounds suffice.
tight \(O(\log\log n)\) vs \(\text{not } O(1)\) symmetry breaking
tight \(0\) vs —
Randomized, ASYNC
Scattering in ASYNC is open in peer-reviewed work.
unknown — vs —
unknown — vs —
Limited visibility, connectivity preserving
Robots with limited visibility scatter without ever disconnecting their visibility graph, in \(O(\min\{n, g^2+\log n\})\) expected rounds, \(g\) the diameter of the initial visibility graph.
tight \(O(\min\{n,g^2+\log n\})\) vs \(\Omega(n)\) distance
tight \(0\) vs —

Open questions 1

Randomized, ASYNC

  1. Solve scattering in ASYNC; Bramas and Tixeuil call it "the open problem of ASYNC scattering" Bramas & Tixeuil 2016 Bramas & Tixeuil 2017. A 2019 preprint by Léchine and Tixeuil (arXiv 1905.09177, not peer reviewed) solves it with vision and weak local multiplicity detection (its Theorem 4), and leaves open the plane with vision and no multiplicity detection.

What the community started looking at

Scattering was first a feasibility question: it cannot be solved deterministically, so randomness is needed Dieudonné & Petit 2009. The measures then became expected rounds and random bits Clement et al. 2010 Bramas & Tixeuil 2017, and keeping the swarm connected under limited visibility Izumi et al. 2018.

Related problems

Gathering: Scattering is the opposite task: gathering creates a multiplicity point, scattering removes all of them. Pattern formation from configurations with multiplicities needs scattering first Bramas & Tixeuil 2016.

Uniform deployment on a ring: Both spread robots out; scattering only needs distinct positions, deployment needs equal spacing.

Scattering of particles: Robots in the plane scatter to distinct points; particles must scatter so that no two are neighbours.

Perspectives

  • Symmetry is the adversary Identical agents running the same deterministic program can be kept in lockstep forever. Across graphs, the plane and programmable matter, the papers break this symmetry with identifiers, with randomness, with asymmetric starts, or with the scheduler, and leader election keeps reappearing as the common core.
  • The most consequential open problems Ten open questions ranked by how far a solution would propagate through the atlas, with the chain of problems each one feeds.

All settings

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