Circle Formation of Weak Mobile Robots

by Yoann Dieudonne, Ouiddad Labbani-Igbida, & Franck Pet arXiv.org E-print Archive, 12 Jul 2006 The contribution is twofold. We first show the validity of the conjecture of D´efago and Konagaya, i.e., there exists no deterministic oblivious algorithm solving the Uniform Transformation Problem for any number of robots. Next, a protocol which solves deterministically the Circle Formation Problem in finite time for any number n of weak robots -- n /∈ {4, 6, 8} -- is proposed. The robots are assumed to be uniform, anonymous, oblivious, and they share no kind of coordinate system nor common sense of direction. Read more