Home›Mobile robots in the plane›Formation problems›Pattern formation›Partitioning

Partitioning

Robots must partition themselves into \(k\) groups of exactly \(n/k\) robots each, each group at its own point.

Problem statement and measurescollapse

Partitioning (\(k\)-EPF): \(n\) robots, \(k\) dividing \(n\), must gather in groups of exactly \(n/k\) robots at the \(k\) given fixed points, each point receiving one group Bhagat et al. 2021. Shown: the simplest case \(k = 1\), one fixed point (dashed square), in SSYNC rounds; ringed robots are activated and move straight towards the point, a move possibly stopping early, until all are on it.

\(n\) robots, with \(k\) dividing \(n\), must partition themselves into \(k\) groups of exactly \(n/k\) robots, each group gathered at its own point, and stay there. The \(k\) points, and so the group size \(n/k\), are given (the papers' \(k\)-EPF and \(k\)-circle formation name the group size \(k\), which is \(n/k\) here).

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 cars that must park in equal groups at a few marked charging stations. In the problem the cars are \(n\) robots, points in the plane, and the stations are \(k\) fixed points that every robot can see; \(k\) divides \(n\). 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 and the fixed points 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 their local coordinate systems agree on the direction of one axis (say north), all robots see everything, and the scheduler, which decides when each robot acts and how long each phase takes, is ASYNC (each phase may take any finite time). The robots must end with exactly \(n/k\) robots, a group, on each fixed point, and stay there. The question is for which starting configurations (positions of all robots) and numbers \(k\) of fixed points this is possible.

1AlgorithmThe easy extreme: one fixed point for everybody Exactly \(n/k\) robots at each fixed point →

A standard approach for the simplest case, \(k = 1\), where there is only one fixed point:

Look for the fixed point.
Move straight towards it.
Once on it, stay.

Why it works and what it costs. No coordination is needed, because the fixed point is a landmark all robots recognise: every move either reaches the point or covers at least a minimum distance, so each robot arrives after finitely many cycles. With more than one fixed point the robots must agree who goes where, and robots that look alike may be unable to choose differently; Bhagat, Das, Chakraborty and Mukhopadhyaya characterise the configurations and numbers \(k\) of fixed points for which the problem is solvable with one common axis Bhagat et al. 2021, the catalogue's introductory and current best result (not described in detail here). The opposite extreme, \(k = n\), asks for one robot per fixed point.

Why it matters. It shows the role of fixed points: they are landmarks that break much of the symmetry robots cannot break themselves.

2ImpossibilityMirror twins arrive in pairs Exactly \(n/k\) robots at each fixed point →

A standard symmetry argument, for robots that cannot tell left from right. Let \(n = 6\) and \(k = 2\) (groups of \(3\)), and put both fixed points on a vertical line \(L\). Place three robots left of \(L\) and their three mirror images to the right, none on \(L\); a robot and its mirror image are mirror twins. The adversary, an imagined opponent that chooses the local coordinate systems and when robots act, gives each pair of mirror twins mirror-image local coordinate systems and always activates them together. Twins see mirror-image snapshots, so they make mirror-image moves and stay mirror images forever. A robot can reach a point of \(L\) only together with its twin, so every point of \(L\) always holds an even number of robots. It can never hold exactly 3.

Why it holds. The same parity argument rules out every odd group size \(n/k\) whenever all fixed points lie on a line of symmetry of the start that holds no robot. This is why the catalogue's setting assumes a common axis, and why the answer depends on the start; the exact characterisation is in Bhagat et al. 2021.

Why it matters. It is a compact example of how symmetry and counting combine to make a placement task impossible.

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

Exactly \(n/k\) robots at each fixed point standard

With one common axis, the configurations and numbers \(k\) of fixed points for which exactly \(n/k\) robots can gather at each of given fixed points are characterised.

unknown \(\text{finite}\) vs —

tight \(0\) vs —

Open questions 1

Exactly \(n/k\) robots at each fixed point

Partitioning into \(k\) groups of size \(n/k\) at points chosen by the robots (no fixed points given).

What the community started looking at

Partitioning into groups of a given size (\(n/k\) here; the papers write \(k\)) was first studied with the group locations fixed in advance (\(k\)-EPF), together with \(k\)-circle formation; the question was for which configurations and group sizes it is solvable when robots share only one axis Bhagat et al. 2021.

Special case of Pattern formation

A partition into \(k\) groups at points is a pattern of \(k\) points, each of multiplicity \(n/k\).

All settings

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

No assumptions · 1 branches by body Nothing is assumed on any axis.
- +point+unlimited visibility+transparent+no faults+one axis
  Exactly \(n/k\) robots at each fixed point standard setting With one common axis, the configurations and numbers \(k\) of fixed points for which exactly \(n/k\) robots can gather at each of given fixed points are characterised.

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