Mobility Matters
Home›Mobile robots in the plane›Formation problems›Pattern formation›k-grouping

k-grouping

Robots must form \(k\) distinct groups, each group at its own point.

Problem statement and measurescollapse
Start: n=9, k=3; blocks of 3 by x-orderActivated robots move to their block's centreFinal: 3 groups, each converging on its own point
\(k\)-grouping: \(n\) robots must split into exactly \(k\) groups, each gathered at (or converging to) its own point, the points distinct. Shown: the algorithm of Efrima & Peleg 2009 with a common compass, \(n = 9\), \(k = 3\), in SSYNC rounds: robots are cut into blocks of \(n/k\) by \(x\)-order (colours), and each ringed (activated) robot moves towards the centre of gravity (star) of its block, possibly stopping early; blocks never mix.

\(n\) robots must form exactly \(k\) distinct groups, each group gathered at its own point or converging towards one, and stay apart. The number of groups \(k\) is given; the group sizes are free unless the variant fixes them. With \(k = 1\) this is gathering (or convergence).

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 swarm that must split into \(k\) teams of equal size, each team clustering in its own place, far from the others. In the problem the members of the swarm are \(n\) robots, points at distinct places in the plane, and the teams are groups; \(k\) divides \(n\). The positions of all robots form the configuration. Each robot reads positions in its own local coordinate system (its private axes, unit of length and handedness) and 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). Robots are identical, silent and oblivious (no memory between cycles). In the basic version robots share a compass (all local coordinate systems agree on north and east, though not on origin or unit of length); the scheduler, which decides the activation of robots (when each starts a cycle) and how long each phase takes, is ASYNC (each phase may take any finite time); and some robots may crash (stop forever). The robots must split into \(k\) groups of \(n/k\) robots each, every group converging towards its own point, with the groups staying a fixed distance apart; with \(k = 1\) this is just convergence.

1AlgorithmSort by the compass, cut into blocks, converge within each block \(k\) groups of equal size → Efrima & Peleg 2009
  1. Sort the robots from west to east, and robots on one north-south line from south to north. All robots get the same order, because they share north and east.
  2. Cut the order into \(k\) consecutive blocks of \(n/k\) robots: the first \(n/k\) robots, the next \(n/k\), and so on. Each robot finds its own block.
  3. Move towards the centre of gravity of your block, the average of the positions of its robots.
Why it works and what it costs. The region spanned by a block's robots and their destinations never grows when they move to their centre of gravity (Lemma 2.5 of Efrima & Peleg 2009, from Cohen and Peleg). The blocks start in disjoint regions ordered from west to east, so two robots of different blocks can never swap order, and the blocks cut in step 2 stay the same forever, even though robots forget them. Each block therefore converges on its own, and a crashed robot simply stays inside its block's region, so any number of crashes is tolerated (Proposition 2.7 of Efrima & Peleg 2009). This is the catalogue's introductory and current best result.

Why it matters. It shows a clean way to make oblivious robots keep an agreement forever: choose it so that the motion itself preserves it.

2ImpossibilityNo compass: the regular polygon cannot be split \(k\) equal groups, no common orientation, deterministic → Efrima & Peleg 2009

Start the \(n\) robots on the corners of a regular \(n\)-gon, with local coordinate systems that are copies of each other turned around the centre. Every robot sees the same snapshot, so in every round of the fully synchronous scheduler FSYNC (a step of time in which every robot performs one full cycle) all robots make the same move up to rotation, and the configuration stays a regular polygon (or a single point). But \(k \ge 2\) groups of several robots each, far apart, never look like a regular polygon or a point. So the groups never form.

Why it holds. This is Proposition 3.3 of Efrima & Peleg 2009: deterministic robots without a compass cannot partition themselves into \(k > 1\) groups, already in FSYNC and therefore in SSYNC and ASYNC. Agreeing only on the axis lines but not their directions is still not enough for some \(n\) and \(k\) (a symmetric square with \(n = 4\), \(k = 2\); Proposition 3.4).

Why it matters. It shows that partitioning, unlike gathering, needs a way to break symmetry.

3AlgorithmA coin flip breaks the tie \(k\) equal groups, randomized, SSYNC → Efrima & Peleg 2009

Without a compass, the trouble is sets of robots that look exactly alike. Randomness helps: a robot in such a tied set chooses its direction of motion at random. Two robots that would otherwise mirror each other forever now choose differently with probability at least \(1/2\) in each attempt, so the tie is broken after a few attempts on average, and the robots then proceed with the deterministic method.

Why it works and what it costs. Efrima and Peleg give a randomized algorithm, of the kind that always ends correctly and is only random in its running time, that partitions robots without any common orientation in FSYNC and SSYNC and tolerates crashes Efrima & Peleg 2009. The description above is simplified: in the paper the random choice is used only to separate robots that lie on the same line.

Why it matters. It is the standard illustration that randomness breaks the symmetry that defeats deterministic robots.

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
\(k\) groups of equal size standard
Robots split into \(k\) groups of \(n/k\) that converge apart; with a full compass a deterministic crash-tolerant algorithm works in ASYNC.
unknown \(\text{finite}\) vs —
tight \(0\) vs —
\(k\) equal groups, randomized, SSYNC
With randomness, robots without any common orientation partition in SSYNC, tolerating crashes.
unknown \(\text{finite}\) vs —
tight \(0\) vs —
\(k\) equal groups, no common orientation, deterministic
Without any common orientation no deterministic algorithm partitions robots into \(k > 1\) groups, already in FSYNC.
impossible — vs \(\text{impossible}\) symmetry breaking
tight — vs —

Open questions 1

\(k\) equal groups, randomized, SSYNC

  1. Partitioning in ASYNC without a common orientation, by a randomized algorithm with no extra memory.

What the community started looking at

Splitting a swarm into a given number of groups was asked as solvability under each timing model and amount of orientation Efrima & Peleg 2009, who called it partitioning and required equal group sizes. Team assembling of heterogeneous robots, where the composition of each team is prescribed, is a related task Liu et al. 2018.

Special case of Pattern formation

When the groups sit at points, \(k\)-grouping forms a pattern of \(k\) points; which points, and how many robots each holds, is up to the robots. Gathering is its special case \(k = 1\). Splitting needs symmetry breaking Efrima & Peleg 2009.

Derived problems

Gathering: Gathering is \(k\)-grouping with \(k = 1\), a single group of all \(n\) robots, that is, point formation: the pattern consisting of one point of multiplicity \(n\) Flocchini et al. 2017 Flocchini et al. 2026. General pattern formation algorithms usually exclude it, because multiplicity points need detection Bramas & Tixeuil 2016.

Related problems

Partitioning: \(k\)-grouping fixes the number of groups; partitioning fixes the size of each group. With equal sizes the two coincide: \(k\) groups of \(n/k\) robots.

Separation: 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.

All settings

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