Uniform Circle Formation by Asynchronous Robots: A Fully-Distributed Approach

Recent advances in robotics technology have made it practical to deploy a large number of inexpensive robots in a wide range of application domains. In many of those applications, a group of autonomous robots is required to form a predefined geometric shape such as a line or a circle. This problem, namely pattern formation, is one of the most important coordination problems in multi-robot systems. A particular pattern extensively studied in literature is the uniform circle, and the corresponding problem is called uniform circle formation. In uniform circle formation, a set of simple mobile robots (asynchronous, autonomous), starting from arbitrary positions on the plane, have to arrange themselves on the vertices of a regular polygon eventually. Towards addressing the problem, existing works usually make conveniently strong assumptions, i.e., the robots are regarded as mass points and have unlimited sensing and communication range. The question of whether the robots with actual size and limited sensing and communication range could form a uniform circle, to our knowledge, has remained open. In this paper, we propose a new approach towards addressing this issue. Three phases, consensus on the circle, circle formation, and uniform transformation, constitute our approach. We propose novel distributed algorithms for convex hull construction and cardinality estimation. Simulation results, theoretical analysis, and successful deployment have shown the effectiveness and practicability of our approach.