The Minimum Algorithm Size of k-Grouping by Silent Oblivious Robots

Consider a set of mobile computational elements, called robots, that are viewed as points, and operate in the Euclidean plane in synchronous rounds. The robots are oblivious (they forget all computations performed in previous rounds), silent (unable of direct communication), and anonymous (indistinguishable from the outside). Each robot is provided with a private coordinate system, and can determine the position of the other robots (performing a Look operation); it has an algorithm, which it executes (performing a Compute operation) to determine a destination point; and it can move towards the destination (performing a Move operation). The k-Grouping problem requires the robots, starting from an arbitrary initial configuration in the plane, to gather at k distinct locations, not chosen in advance, by performing Look-Compute-Move cycles, and no longer move. This simple problem is however unsolvable if all the robots execute the same algorithm. It has been recently shown that, were different subgroups of the robots to execute different algorithms, the problem remains still unsolvable if the number of the algorithms is less than k. In this paper we prove that this number is minimum: we design k distinct algorithms and prove that, if each is executed by an arbitrary non-empty subset of the robots, they will collectively be able to solve the problem; furthermore, they are able to do so under a weak assumption on the level of agreement among the local coordinate systems. We further prove that, without any agreement, the problem becomes unsolvable even with \(k+1\) different algorithms. However, if an unbounded number of algorithms are allowed such that each robot has a unique algorithm, then we can solve k-Grouping without any agreement.