Circle formation of weak mobile robots
Yoann Dieudonné, Ouiddad Labbani-Igbida, Franck Petit · ACM Transactions on Autonomous and Adaptive Systems · 2008
We consider distributed systems made of weak mobile robots, that is, mobile devices, equipped with sensors, that are anonymous , autonomous , disoriented , and oblivious . The Circle Formation Problem (CFP) consists of the design of a protocol insuring that, starting from an initial arbitrary configuration where no two robots are at the same position, all the robots eventually form a regular n-gon —the robots take place on the circumference of a circle C with equal spacing between any two adjacent robots on C . CFP is known to be unsolvable by arranging the robots evenly along the circumference of a circle C without leaving C —that is, starting from a configuration where the robots are on the boundary of C . We circumvent this impossibility result by designing a scheme based on concentric circles . This is the first scheme that deterministically solves CFP. We present our method with two different implementations working in the semi-synchronous system (SSM) for any number n ≥ 5 of robots.