Find in Library

For a given positive integer <i>k</i>, the <i>k</i>-circle formation problem asks a set of autonomous, asynchronous robots to form disjoint circles having <i>k</i> robots each at distinct locations, centered at a set of fixed points in the Euclidean plane. The robots are identical, anonymous, oblivious, and they operate in Look–Compute–Move cycles. This paper studies the <i>k</i>-circle formation problem and its relationship with the <i>k</i>-epf problem, a generalized version of the embedded pattern formation problem, which asks exactly <i>k</i> robots to reach and remain at each fixed point. First, the <i>k</i>-circle formation problem is studied in a setting where the robots have an agreement on the common direction and orientation of one of the axes. We have characterized all the configurations and the values of <i>k</i>, for which the <i>k</i>-circle formation problem is deterministically unsolvable in this setting. For the remaining configurations and the values of <i>k</i>, a deterministic distributed algorithm has been proposed, in order to solve the problem. It has been proved that for the initial configurations with distinct robot positions, if the <i>k</i>-circle formation problem is deterministically solvable then the <i>k</i>-epf problem is also deterministically solvable. It has been shown that by modifying the proposed algorithm, the <i>k</i>-epf problem can be solved deterministically.