{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T10:58:16Z","timestamp":1769857096202,"version":"3.49.0"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2009,1,1]],"date-time":"2009-01-01T00:00:00Z","timestamp":1230768000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001700","name":"Ministry of Education, Culture, Sports, Science, and Technology","doi-asserted-by":"publisher","award":["Nr. 18680007"],"award-info":[{"award-number":["Nr. 18680007"]}],"id":[{"id":"10.13039\/501100001700","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Auton. Adapt. Syst."],"published-print":{"date-parts":[[2009,1]]},"abstract":"<jats:p>Reaching agreement among a set of mobile robots is one of the most fundamental issues in distributed robotic systems. This problem is often illustrated by the gathering problem, where the robots must self-organize and meet at some location not determined in advance, and without the help of some global coordinate system. While very simple to express, this problem has the advantage of retaining the inherent difficulty of agreement, namely the question of breaking symmetry between robots. In previous works, it has been proved that the gathering problem is solvable in asynchronous model with oblivious (i.e., memory-less) robots and limited visibility, as long as the robots share the knowledge of some direction, as provided by a compass. However, the problem has no solution in the semi-synchronous model when robots do not share a compass, or when they cannot detect multiplicity.<\/jats:p>\n          <jats:p>In this article, we define a model in which compasses may be unreliable, and study the solvability of gathering oblivious mobile robots with limited visibility in the semi-synchronous model. In particular, we give an algorithm that solves the problem in finite time in a system where compasses are unstable for some arbitrary long periods, provided that they stabilize eventually. In addition, we show that our algorithm solves the gathering problem for at most three robots in the asynchronous model. Our algorithm is intrinsically self-stabilizing.<\/jats:p>","DOI":"10.1145\/1462187.1462196","type":"journal-article","created":{"date-parts":[[2009,2,10]],"date-time":"2009-02-10T16:42:19Z","timestamp":1234284139000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":57,"title":["Using eventually consistent compasses to gather memory-less mobile robots with limited visibility"],"prefix":"10.1145","volume":"4","author":[{"given":"Samia","family":"Souissi","sequence":"first","affiliation":[{"name":"Japan Advanced Institute of Science and Technology (JAIST), Ishikawa, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xavier","family":"D\u00e9fago","sequence":"additional","affiliation":[{"name":"Japan Advanced Institute of Science and Technology (JAIST), Ishikawa, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Masafumi","family":"Yamashita","sequence":"additional","affiliation":[{"name":"Kyushu University, Fukuoka, Japan"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,2,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/050645221"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.795787"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/70.736776"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of the International Symposium on Distributed Autonomous Robotic Systems (DARS'92)","author":"Beni G."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.5555\/554879"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/226643.226647"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24698-5_60"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the International Colloquium on Automata, Languages and Programming (ICALP'03)","author":"Cieliebak M."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-27796-5_8"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/060665257"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11945529_25"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/11864219_4"},{"key":"e_1_2_1_13_1","doi-asserted-by":"crossref","unstructured":"Dolev S. 2000. Self-Stabilization. MIT Press.   Dolev S. 2000. Self-Stabilization. MIT Press.","DOI":"10.7551\/mitpress\/6156.001.0001"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/42282.42283"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24592-6_23"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/646342.689384"},{"key":"e_1_2_1_17_1","volume-title":"Proceedings of the 8th International Colloquium on Structural Information and Communication Complexity (SIROCCO'01)","author":"Flocchini P."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.01.001"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2003.11.010"},{"key":"e_1_2_1_20_1","volume-title":"Proceedings of the 1st Workshop on Theoretical Computer Science. 43--46","author":"Imazu H."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69355-0_3"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-75142-7_24"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-72951-8_22"},{"key":"e_1_2_1_24_1","first-page":"833","article-title":"A principle of distributed decision making of cellular robotic system (cebot). In Proceedings of the IEEE International Conference on Robotics and Automation","volume":"3","author":"Kawauchi Y.","year":"1993","journal-title":"Lecture Notes in Computer Science"},{"key":"e_1_2_1_25_1","doi-asserted-by":"crossref","unstructured":"Krieger M. J. B. Billeter J.-B. and Keller L. 2000. Ant-like task allocation and recruitment in cooperative robots. Nature 406 6799 992--995.  Krieger M. J. B. Billeter J.-B. and Keller L. 2000. Ant-like task allocation and recruitment in cooperative robots. Nature 406 6799 992--995.","DOI":"10.1038\/35023164"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the 4th Symposium on Experimental Robotics. 3--10","author":"Martinoli A."},{"key":"e_1_2_1_27_1","first-page":"275","article-title":"From local interactions to collective intelligence. In Proceedings of Biology and Technology of Intelligent Autonomous Agents","volume":"144","author":"Matari\u0107 M. J.","year":"1995","journal-title":"Lecture Notes in Computer Science"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/11603771_1"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/646293.687244"},{"key":"e_1_2_1_30_1","volume-title":"Proceedings of the 4th European Research Seminar on Advances in Distributed Systems and Dependable Systems (ERSADS'01)","author":"Prencipe G.","year":"2001"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/11429647_20"},{"key":"e_1_2_1_32_1","unstructured":"Souissi S. 2007. Fault-resilient cooperation of autonomous mobile robots with unreliable compass sensors. Japan Advanced Institute of Science and Technology.  Souissi S. 2007. Fault-resilient cooperation of autonomous mobile robots with unreliable compass sensors. Japan Advanced Institute of Science and Technology."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/11945529_24"},{"key":"e_1_2_1_34_1","first-page":"471","article-title":"Using eventually consistent compasses to gather oblivious mobile robots with limited visibility. In Proceedings of the 8th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS'06)","volume":"4280","author":"Souissi S.","year":"2006","journal-title":"Lecture Notes in Computer Science"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/S009753979628292X"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008855018923"},{"key":"e_1_2_1_37_1","volume-title":"Proceedings of the 1st International Conference on Robot Communication and Coordination (ROBOCOMM'07)","author":"Yamashita M."}],"container-title":["ACM Transactions on Autonomous and Adaptive Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1462187.1462196","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1462187.1462196","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:30:15Z","timestamp":1750253415000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1462187.1462196"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,1]]},"references-count":37,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,1]]}},"alternative-id":["10.1145\/1462187.1462196"],"URL":"https:\/\/doi.org\/10.1145\/1462187.1462196","relation":{},"ISSN":["1556-4665","1556-4703"],"issn-type":[{"value":"1556-4665","type":"print"},{"value":"1556-4703","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,1]]},"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":"2009-02-09","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}