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 measuresexpand

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

Progress map

tight near-optimal polynomial gap unknown impossible· rows follow the assumption tree; each cell: best upper bound vs lower bound, and what forces the lower bound

Setting

Time

Colours

No assumptions

—

Faults + point, + unlimited visibility, + transparent

—

Scheduler + crash faults

—

\(k\) groups of equal size ASYNC, + compass

0 open · 1 results

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

tight \(0\) vs —

\(k\) equal groups, randomized, SSYNC + SSYNC, + randomized

1 open · 1 results

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

tight \(0\) vs —

\(k\) equal groups, no common orientation, deterministic + no faults, + FSYNC

0 open · 0 results

impossible — vs \(\text{impossible}\) symmetry breaking

tight — vs —

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