{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,4,7]],"date-time":"2024-04-07T02:49:44Z","timestamp":1712458184550},"reference-count":17,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Auton. Adapt. Syst."],"published-print":{"date-parts":[[2008,11]]},"abstract":"\n We consider distributed systems made of\n weak mobile<\/jats:italic>\n robots, that is, mobile devices, equipped with sensors, that are\n anonymous<\/jats:italic>\n ,\n autonomous<\/jats:italic>\n ,\n disoriented<\/jats:italic>\n , and\n oblivious<\/jats:italic>\n . The\n Circle Formation Problem<\/jats:italic>\n (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\n regular n-gon<\/jats:italic>\n \u2014the robots take place on the circumference of a circle\n C<\/jats:italic>\n with equal spacing between any two adjacent robots on\n C<\/jats:italic>\n .\n <\/jats:p>\n \n CFP is known to be unsolvable by arranging the robots evenly along the circumference of a circle\n C<\/jats:italic>\n without leaving\n C<\/jats:italic>\n \u2014that is, starting from a configuration where the robots are on the boundary of\n C<\/jats:italic>\n . We circumvent this impossibility result by designing a scheme based on\n concentric circles<\/jats:italic>\n . 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 n<\/jats:italic>\n \u2265 5 of robots.\n <\/jats:p>","DOI":"10.1145\/1452001.1452006","type":"journal-article","created":{"date-parts":[[2008,12,10]],"date-time":"2008-12-10T15:32:31Z","timestamp":1228923151000},"page":"1-20","update-policy":"http:\/\/dx.doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":36,"title":["Circle formation of weak mobile robots"],"prefix":"10.1145","volume":"3","author":[{"given":"Yoann","family":"Dieudonn\u00e9","sequence":"first","affiliation":[{"name":"MIS Laboratory, Universit\u00e9 de Picardie Jules Verne, Amiens, France"}]},{"given":"Ouiddad","family":"Labbani-Igbida","sequence":"additional","affiliation":[{"name":"MIS Laboratory, Universit\u00e9 de Picardie Jules Verne, Amiens, France"}]},{"given":"Franck","family":"Petit","sequence":"additional","affiliation":[{"name":"MIS Laboratory, Universit\u00e9 de Picardie Jules Verne, Amiens, France"}]}],"member":"320","published-online":{"date-parts":[[2008,12,12]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"Proceedings of the 3rd International Workshop on Experimental and Efficient Algorithms (WEA). Lecture Notes in Computer Science","volume":"3059","author":"Chatzigiannakis I.","unstructured":"Chatzigiannakis , I. , Markou , M. , and Nikoletseas , S . 2004. Distributed circle formation for anonymous oblivious robots . In Proceedings of the 3rd International Workshop on Experimental and Efficient Algorithms (WEA). Lecture Notes in Computer Science , vol. 3059 , Springer, Berlin, Germany. 159--174. Chatzigiannakis, I., Markou, M., and Nikoletseas, S. 2004. Distributed circle formation for anonymous oblivious robots. In Proceedings of the 3rd International Workshop on Experimental and Efficient Algorithms (WEA). Lecture Notes in Computer Science, vol. 3059, Springer, Berlin, Germany. 159--174."},{"key":"e_1_2_1_2_1","first-page":"115","article-title":"Remark about self-stabilizing systems","volume":"38","author":"Debest X. A.","year":"1995","unstructured":"Debest , X. A. 1995 . Remark about self-stabilizing systems . Commun. ACM , 38 , 2, 115 -- 117 . Debest, X. A. 1995. Remark about self-stabilizing systems. Commun. ACM, 38, 2, 115--117.","journal-title":"Commun. ACM"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/584490.584509"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2008.01.050"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the 8th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS). Lecture Notes in Computer Science","volume":"4280","author":"Dieudonn\u00e9 Y.","unstructured":"Dieudonn\u00e9 , Y. Labbani-Igbida , O. , and Petit , F . 2006. Circle formation of weak mobile robots . In Proceedings of the 8th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS). Lecture Notes in Computer Science , vol. 4280 . Springer, Berlin, Heidelberg, New York, 262--275. Dieudonn\u00e9, Y. Labbani-Igbida, O., and Petit, F. 2006. Circle formation of weak mobile robots. In Proceedings of the 8th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS). Lecture Notes in Computer Science, vol. 4280. Springer, Berlin, Heidelberg, New York, 262--275."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.09.008"},{"key":"e_1_2_1_7_1","volume-title":"Proceedings of the 11th International Conference On Principles of Distributed Systems (OPODIS). Lecture Notes in Computer Science","volume":"4878","author":"Dieudonn\u00e9 Y.","unstructured":"Dieudonn\u00e9 , Y. and Petit , F . 2007b. Deterministic leader election in anonymous sensor networks without common coordinated system . In Proceedings of the 11th International Conference On Principles of Distributed Systems (OPODIS). Lecture Notes in Computer Science , vol. 4878 . Springer, Berlin, Germany, 132--142. Dieudonn\u00e9, Y. and Petit, F. 2007b. Deterministic leader election in anonymous sensor networks without common coordinated system. In Proceedings of the 11th International Conference On Principles of Distributed Systems (OPODIS). Lecture Notes in Computer Science, vol. 4878. Springer, Berlin, Germany, 132--142."},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 14th International Colloquium on Structural Information and Communication Complexity (SIROCCO). Lecture Notes in Computer Science","volume":"4474","author":"Dieudonn\u00e9 Y.","unstructured":"Dieudonn\u00e9 , Y. and Petit , F . 2007c. Swing words to make circle formation quiescent . In Proceedings of the 14th International Colloquium on Structural Information and Communication Complexity (SIROCCO). Lecture Notes in Computer Science , vol. 4474 . Springer, Berlin, Germany, 169--179. Dieudonn\u00e9, Y. and Petit, F. 2007c. Swing words to make circle formation quiescent. In Proceedings of the 14th International Colloquium on Structural Information and Communication Complexity (SIROCCO). Lecture Notes in Computer Science, vol. 4474. Springer, Berlin, Germany, 169--179."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/11963271_6"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the IEEE Intelligent Vehicle Symposium (IV). IEEE Computer Society","author":"Flocchini P.","unstructured":"Flocchini , P. , Prencipe , G. , Santoro , N. , and Widmayer , P . 2000. Distributed coordination of a set of autonomous mobile robots . In Proceedings of the IEEE Intelligent Vehicle Symposium (IV). IEEE Computer Society , Los Alamitos, CA, 480--485. Flocchini, P., Prencipe, G., Santoro, N., and Widmayer, P. 2000. Distributed coordination of a set of autonomous mobile robots. In Proceedings of the IEEE Intelligent Vehicle Symposium (IV). IEEE Computer Society, Los Alamitos, CA, 480--485."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11429647_16"},{"key":"e_1_2_1_12_1","volume-title":"Combinatorics on Words","author":"Lothaire M.","unstructured":"Lothaire , M. 1983. Combinatorics on Words . Addison-Wesley . Lothaire, M. 1983. Combinatorics on Words. Addison-Wesley."},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of the 4th European Research Seminar on Advances in Distributed Systems (ERSADS). 185--190","author":"Prencipe G.","year":"2001","unstructured":"Prencipe , G. 2001 . Corda: distributed coordination of a set of autonomous mobile robots . In Proceedings of the 4th European Research Seminar on Advances in Distributed Systems (ERSADS). 185--190 . Prencipe, G. 2001. Corda: distributed coordination of a set of autonomous mobile robots. In Proceedings of the 4th European Research Seminar on Advances in Distributed Systems (ERSADS). 185--190."},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the IFIP International Conference on Theoretical Computer Science (TCS). Springer","author":"Prencipe G.","unstructured":"Prencipe , G. and Santoro , N . 2006. Distributed algorithms for autonomous mobile robots . In Proceedings of the IFIP International Conference on Theoretical Computer Science (TCS). Springer , Berlin, Germany, 47--62. Prencipe, G. and Santoro, N. 2006. Distributed algorithms for autonomous mobile robots. In Proceedings of the IFIP International Conference on Theoretical Computer Science (TCS). Springer, Berlin, Germany, 47--62."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1097-4563(199603)13:3<127::AID-ROB1>3.0.CO;2-U"},{"key":"e_1_2_1_17_1","volume-title":"Intelligent Robots: Sensing, Modeling and Planning","author":"Suzuki I.","year":"1996","unstructured":"Suzuki , I. and Yamashita , M . 1996 . Agreement on a common x−y coordinate system by a group of mobile robots. Intelligent Robots: Sensing, Modeling and Planning . World Scientific Press , 305--321. Suzuki, I. and Yamashita, M. 1996. Agreement on a common x−y coordinate system by a group of mobile robots. Intelligent Robots: Sensing, Modeling and Planning. World Scientific Press, 305--321."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979628292X"}],"container-title":["ACM Transactions on Autonomous and Adaptive Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1452001.1452006","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,29]],"date-time":"2022-12-29T08:58:52Z","timestamp":1672304332000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1452001.1452006"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,11]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2008,11]]}},"alternative-id":["10.1145\/1452001.1452006"],"URL":"https:\/\/doi.org\/10.1145\/1452001.1452006","relation":{},"ISSN":["1556-4665","1556-4703"],"issn-type":[{"value":"1556-4665","type":"print"},{"value":"1556-4703","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,11]]},"assertion":[{"value":"2007-02-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-12-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}