Distributed k-Circle Formation by Mobile Robots

Abstract

The k-circle formation problem asks a group of robots to form disjoint circles. Each circle is restricted to being centered at one of the pre- xed points given in the plane, and each circle should have exactly k distinct robot positions. In this thesis, we investigate the solvability of the k-circle formation by a swarm of mobile robots in a deterministic manner. The robots are autonomous, and they execute Look-Compute-Move (LCM) cycle under a fair asynchronous scheduler. They are anonymous, i.e., they do not have any unique idenit er, and homogeneous, i.e., they execute the same deterministic algorithm. The robots are assumed to be oblivious and silent or may have limited persistent memory. We begin by investigating the k-circle formation problem in a setting where the robots have global agreement on the y-axis. In this setting, all the initial con gurations and values of k for which the k-circle formation problem is deterministically unsolvable are characterized. For the remaining con gurations and values of k, a deterministic distributed algorithm is proposed that solves the k-circle formation problem within nite time. It is shown that if the k-circle formation problem is deterministically solvable, then the k-EPF problem (a generalized version of the embedded pattern formation problem) can also be solved deterministically. We proceed by dropping the assumption of global y-axis agreement, where we assume that the robots do not have any agreement on the orientations and directions of any of the axes of a global coordinate system. In this setting, we provide a deterministic solution for the k-circle formation problem by characterizing all the deterministically unsolvable con gurations. If the robots are opaque, when three robots are collinear, then the terminal robots cannot see one another. In this setup, we consider two cases, namely, complete knowledge of xed points and zero knowledge of xed points. When the robots have complete knowledge of xed points, a distributed algorithm is proposed that solves k-circle formation problem for oblivious and silent robots in a deterministic manner. For robots with zero knowledge of xed points, a deterministic distributed solution is presented by assuming that the robots have one bit of persistent memory. In the real world, a robot cannot be dimensionless. We study the k-circle formation problem for unit disk robots. We propose a deterministic distributed solution under the assumption of global y-axis agreement. We conclude this thesis by discussing some future research directions related to the k-circle formation problem.