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).
\(k\) equal groups, no common orientation, deterministic
verifiedWithout any common orientation no deterministic algorithm partitions robots into \(k > 1\) groups, already in FSYNC.
Assumed (added on the last edge are outlined)
Not assumed
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: transparent
- Robots do not obstruct each other's view.
- Faults: no faults
- All robots follow the algorithm forever.
- Scheduler: FSYNC
- FSYNC: every robot executes one atomic cycle in every round.
- Lights (persistent memory): oblivious
- OBLOT: a robot's computation depends only on the current snapshot; nothing persists across cycles.
- Agreement on coordinates: disoriented
- Each robot \(r\) observes in its own coordinate system, obtained from the global one by an unknown similarity (translation, rotation, uniform scaling, and possibly reflection); systems may differ between robots and, in some models, between cycles. Papers that call robots disoriented do not always mean this: Défago and Souissi use the word while assuming chirality Défago & Souissi 2008. Some papers also let the adversary change a robot's rotation, reflection and unit at every Look (variable disorientation) Flocchini et al. 2023 Masuzawa et al. 2026.
- 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.
Statement for this variant
Partition\((n,k)\) of Efrima and Peleg: \(k\) is given to the robots, every group has exactly \(n/k\) robots (\(\lfloor n/k\rfloor\) or \(\lfloor n/k\rfloor + 1\) when \(k\) does not divide \(n\)), robots in one group converge (for every \(\varepsilon\) they are eventually within \(\varepsilon\) of each other) and groups stay more than \(2\eta\) apart, for some fixed \(\eta > 0\). Robots start at distinct points and can count the robots at a point.
What is known
- Proposition 3.3: deterministic, \(k > 1\)
- robots start at the vertices of a regular \(n\)-gon and always make the same move
- holds even in FSYNC, hence in SSYNC and ASYNC
- with common axes but no orientation, still unsolvable for some \(n, k\) (Proposition 3.4)
Results, in order of publication
No result recorded yet.
Open questions
None recorded for this variant.
Notes
In a companion paper the same authors show that the problem becomes solvable in ASYNC without a compass if the start is asymmetric, if one robot is identifiable, or, randomized against a non-adaptive adversary, with one bit of memory and communication (as stated in Efrima & Peleg 2009). Checked against the full text.
Know a better result for this setting, or found a mistake? Suggest a result · Report an error. Accepted contributions are acknowledged.