SCIENCE@home

Circle formation of weak mobile robots

Yoann Dieudonné,O. Labbani-Igbida,F. Petit

Published 2006 in TAAS

ABSTRACT

We consider distributed systems made of <i>weak mobile</i> robots, that is, mobile devices, equipped with sensors, that are <i>anonymous</i>, <i>autonomous</i>, <i>disoriented</i>, and <i>oblivious</i>. The <i>Circle Formation Problem</i> (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 <i>regular n-gon</i>—the robots take place on the circumference of a circle <i>C</i> with equal spacing between any two adjacent robots on <i>C</i>. CFP is known to be unsolvable by arranging the robots evenly along the circumference of a circle <i>C</i> without leaving <i>C</i>—that is, starting from a configuration where the robots are on the boundary of <i>C</i>. We circumvent this impossibility result by designing a scheme based on <i>concentric circles</i>. 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 <i>n</i> ≥ 5 of robots.

PUBLICATION RECORD

CITATION MAP

EXTRACTION MAP

CLAIMS

  • No claims are published for this paper.

CONCEPTS

  • No concepts are published for this paper.

REFERENCES

Showing 1-20 of 20 references · Page 1 of 1

CITED BY

Showing 1-73 of 73 citing papers · Page 1 of 1