{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,17]],"date-time":"2025-11-17T21:39:13Z","timestamp":1763415553214,"version":"build-2065373602"},"reference-count":31,"publisher":"MDPI AG","issue":"11","license":[{"start":{"date-parts":[[2021,10,27]],"date-time":"2021-10-27T00:00:00Z","timestamp":1635292800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Information"],"abstract":"<jats:p>We consider the distributed setting of N autonomous mobile robots that operate in Look-Compute-Move (LCM) cycles following the well-celebrated classic oblivious robots model. We study the fundamental problem of gathering N autonomous robots on a plane, which requires all robots to meet at a single point (or to position within a small area) that is not known beforehand. We consider limited visibility under which robots are only able to see other robots up to a constant Euclidean distance and focus on the time complexity of gathering by robots under limited visibility. There exists an O(DG) time algorithm for this problem in the fully synchronous setting, assuming that the robots agree on one coordinate axis (say north), where DG is the diameter of the visibility graph of the initial configuration. In this article, we provide the first O(DE) time algorithm for this problem in the asynchronous setting under the same assumption of robots\u2019 agreement with one coordinate axis, where DE is the Euclidean distance between farthest-pair of robots in the initial configuration. The runtime of our algorithm is a significant improvement since for any initial configuration of N\u22651 robots, DE\u2264DG, and there exist initial configurations for which DG can be quadratic on DE, i.e., DG=\u0398(DE2). Moreover, our algorithm is asymptotically time-optimal since the trivial time lower bound for this problem is \u03a9(DE).<\/jats:p>","DOI":"10.3390\/info12110448","type":"journal-article","created":{"date-parts":[[2021,10,27]],"date-time":"2021-10-27T22:00:23Z","timestamp":1635372023000},"page":"448","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":6,"title":["Time-Optimal Gathering under Limited Visibility with One-Axis Agreement"],"prefix":"10.3390","volume":"12","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0709-9600","authenticated-orcid":false,"given":"Pavan","family":"Poudel","sequence":"first","affiliation":[{"name":"Department of Computer Science, Kent State University, Kent, OH 44240, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4930-4609","authenticated-orcid":false,"given":"Gokarna","family":"Sharma","sequence":"additional","affiliation":[{"name":"Department of Computer Science, Kent State University, Kent, OH 44240, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"1968","published-online":{"date-parts":[[2021,10,27]]},"reference":[{"key":"ref_1","doi-asserted-by":"crossref","first-page":"1347","DOI":"10.1137\/S009753979628292X","article-title":"Distributed Anonymous Mobile Robots: Formation of Geometric Patterns","volume":"28","author":"Suzuki","year":"1999","journal-title":"SIAM J. Comput."},{"key":"ref_2","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-031-02008-7","article-title":"Distributed Computing by Oblivious Mobile Robots","volume":"3","author":"Flocchini","year":"2012","journal-title":"Synth. Lect. Distrib. Comput. Theory"},{"key":"ref_3","doi-asserted-by":"crossref","first-page":"222","DOI":"10.1016\/j.tcs.2007.04.023","article-title":"Impossibility of Gathering by a Set of Autonomous Mobile Robots","volume":"384","author":"Prencipe","year":"2007","journal-title":"Theor. Comput. Sci."},{"unstructured":"Izumi, T., Kawabata, Y., and Kitamura, N. (2021, October 18). Toward Time-Optimal Gathering for Limited Visibility Model. Available online: https:\/\/sites.google.com\/site\/micromacfrance\/abstract-tasuke.","key":"ref_4"},{"unstructured":"Cieliebak, M., Flocchini, P., Prencipe, G., and Santoro, N. (July, January 30). Solving the Robots Gathering Problem. Proceedings of the 30th International Colloquium on Automata, Languages, and Programming, Eindhoven, The Netherlands.","key":"ref_5"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"147","DOI":"10.1016\/j.tcs.2005.01.001","article-title":"Gathering of Asynchronous Robots with Limited Visibility","volume":"337","author":"Flocchini","year":"2005","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Prencipe, G. (2013, January 5\u20136). Autonomous Mobile Robots: A Distributed Computing Perspective. Proceedings of the 9th International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, Sophia Antipolis, France.","key":"ref_7","DOI":"10.1007\/978-3-642-45346-5_2"},{"doi-asserted-by":"crossref","unstructured":"Souissi, S., D\u00e9fago, X., and Yamashita, M. (2006, January 12\u201315). Gathering Asynchronous Mobile Robots with Inaccurate Compasses. Proceedings of the 10th on Principles of Distributed Systems, Bordeaux, France.","key":"ref_8","DOI":"10.1007\/11945529_24"},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"829","DOI":"10.1137\/100796534","article-title":"Distributed Computing by Mobile Robots: Gathering","volume":"41","author":"Cieliebak","year":"2012","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Agathangelou, C., Georgiou, C., and Mavronicolas, M. (2013, January 22\u201324). A Distributed Algorithm for Gathering Many Fat Mobile Robots in the Plane. Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, Montr\u00e9al, QC, Canada.","key":"ref_10","DOI":"10.1145\/2484239.2484266"},{"doi-asserted-by":"crossref","unstructured":"Degener, B., Kempkes, B., and Meyer auf der Heide, F. (2010, January 13\u201315). A Local O(n2) Gathering Algorithm. Proceedings of the Twenty-Second Annual ACM Symposium on Parallelism in Algorithms and Architectures, Thira, Greece.","key":"ref_11","DOI":"10.1145\/1810479.1810523"},{"doi-asserted-by":"crossref","unstructured":"Degener, B., Kempkes, B., Langner, T., Meyer auf der Heide, F., Pietrzyk, P., and Wattenhofer, R. (2011, January 4\u20136). A Tight Runtime Bound for Synchronous Gathering of Autonomous Robots with Limited Visibility. Proceedings of the Twenty-Third Annual ACM Symposium on Parallelism in Algorithms and Architectures, San Jose, CA, USA.","key":"ref_12","DOI":"10.1145\/1989493.1989515"},{"doi-asserted-by":"crossref","unstructured":"Kempkes, B., Kling, P., and Meyer auf der Heide, F. (2012, January 25\u201327). Optimal and Competitive Runtime Bounds for Continuous, Local Gathering of Mobile Robots. Proceedings of the Twenty-Fourth Annual ACM Symposium on Parallelism in Algorithms and Architectures, Pittsburgh, PA, USA.","key":"ref_13","DOI":"10.1145\/2312005.2312009"},{"doi-asserted-by":"crossref","unstructured":"Cord-Landwehr, A., Fischer, M., Jung, D., and Meyer auf der Heide, F. (2016, January 11\u201313). Asymptotically Optimal Gathering on a Grid. Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures, Pacific Grove, CA, USA.","key":"ref_14","DOI":"10.1145\/2935764.2935789"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"289","DOI":"10.1016\/j.tcs.2020.02.018","article-title":"Gathering Anonymous, Oblivious Robots on a Grid","volume":"815","author":"Castenow","year":"2020","journal-title":"Theor. Comput. Sci."},{"doi-asserted-by":"crossref","unstructured":"Poudel, P., and Sharma, G. (2017). Universally Optimal Gathering Under Limited Visibility, Springer. Lecture Notes in Computer Science.","key":"ref_16","DOI":"10.1007\/978-3-319-69084-1_23"},{"doi-asserted-by":"crossref","unstructured":"Flocchini, P., Prencipe, G., and Santoro, N. (2019). Distributed Computing by Mobile Entities, Current Research in Moving and Computing, Springer. Lecture Notes in Computer Science.","key":"ref_17","DOI":"10.1007\/978-3-030-11072-7"},{"doi-asserted-by":"crossref","unstructured":"Ando, H., Suzuki, I., and Yamashita, M. (1995, January 27\u201329). Formation and Agreement Problems for Synchronous Mobile Robots with Limited Visibility. Proceedings of the Tenth International Symposium on Intelligent Control, Monterey, CA, USA.","key":"ref_18","DOI":"10.21236\/ADA296911"},{"doi-asserted-by":"crossref","unstructured":"Kirkpatrick, D., Kostitsyna, I., Navarra, A., Prencipe, G., and Santoro, N. (2021). Separating Bounded and Unbounded Asynchrony for Autonomous Robots: Point Convergence with Limited Visibility. Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing, ACM.","key":"ref_19","DOI":"10.1145\/3465084.3467910"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1007\/s00446-015-0248-5","article-title":"Getting Close Without Touching: Near-gathering for Autonomous Mobile Robots","volume":"28","author":"Pagli","year":"2015","journal-title":"Distrib. Comput."},{"doi-asserted-by":"crossref","unstructured":"Bhagat, S., Mukhopadhyaya, K., and Mukhopadhyaya, S. (2019). Computation Under Restricted Visibility. Distributed Computing by Mobile Entities: Current Research in Moving and Computing, Springer International Publishing.","key":"ref_21","DOI":"10.1007\/978-3-030-11072-7_7"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"3:1","DOI":"10.1145\/3056460","article-title":"Tight Analysis of a Collisionless Robot Gathering Algorithm","volume":"12","author":"Sharma","year":"2017","journal-title":"ACM Trans. Auton. Adapt. Syst."},{"doi-asserted-by":"crossref","unstructured":"Lukovszki, T., and auf der Heide, F.M. (2014, January 16\u201319). Fast Collisionless Pattern Formation by Anonymous, Position-Aware Robots. Proceedings of the 18th Principles of Distributed Systems, Cortina d\u2019Ampezzo, Italy.","key":"ref_23","DOI":"10.1007\/978-3-319-14472-6_17"},{"doi-asserted-by":"crossref","unstructured":"Cord-Landwehr, A., Degener, B., Fischer, M., H\u00fcllmann, M., Kempkes, B., Klaas, A., Kling, P., Kurras, S., M\u00e4rtens, M., and Meyer auf der Heide, F. (2011, January 22\u201328). Collisionless Gathering of Robots with an Extent. Proceedings of the 37th Conference on Current Trends in Theory and Practice of Computer Science, Nov\u00fd Smokovec, Slovakia.","key":"ref_24","DOI":"10.1007\/978-3-642-18381-2_15"},{"key":"ref_25","first-page":"63","article-title":"Local Gathering of Mobile Robots in Three Dimensions","volume":"Volume 12156","author":"Braun","year":"2020","journal-title":"SIROCCO"},{"unstructured":"Di Stefano, G., and Navarra, A. (October, January 28). Optimal Gathering on Infinite Grids. Proceedings of the 16th Symposium on Self-Stabilizing Systems, Paderborn, Germany.","key":"ref_26"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1007\/s00446-016-0278-7","article-title":"Optimal gathering of oblivious robots in anonymous graphs and its application on trees and rings","volume":"30","author":"Navarra","year":"2017","journal-title":"Distrib. Comput."},{"unstructured":"D\u2019Angelo, G., Stefano, G.D., Klasing, R., and Navarra, A. (July, January 30). Gathering of Robots on Anonymous Grids without Multiplicity Detection. Proceedings of the 19th International Colloquium on Structural Information and Communication Complexity, Reykjavik, Iceland.","key":"ref_28"},{"doi-asserted-by":"crossref","unstructured":"Cord-Landwehr, A., Degener, B., Fischer, M., H\u00fcllmann, M., Kempkes, B., Klaas, A., Kling, P., Kurras, S., M\u00e4rtens, M., and Meyer auf der Heide, F. (2011, January 4\u20138). A New Approach for Analyzing Convergence Algorithms for Mobile Robots. Proceedings of the 38th International Colloquium on Automata, Languages, and Programming, Zurich, Switzerland.","key":"ref_29","DOI":"10.1007\/978-3-642-22012-8_52"},{"key":"ref_30","doi-asserted-by":"crossref","first-page":"1516","DOI":"10.1137\/S0097539704446475","article-title":"Convergence Properties of the Gravitational Algorithm in Asynchronous Robot Systems","volume":"34","author":"Cohen","year":"2005","journal-title":"SIAM J. Comput."},{"doi-asserted-by":"crossref","unstructured":"Izumi, T., Potop-Butucaru, M.G., and Tixeuil, S. (2010, January 20\u201322). Connectivity-preserving Scattering of Mobile Robots with Limited Visibility. Proceedings of the 12th Symposium on Self-Stabilizing Systems, New York, NY, USA.","key":"ref_31","DOI":"10.1007\/978-3-642-16023-3_27"}],"container-title":["Information"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/2078-2489\/12\/11\/448\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T07:21:37Z","timestamp":1760167297000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/2078-2489\/12\/11\/448"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,27]]},"references-count":31,"journal-issue":{"issue":"11","published-online":{"date-parts":[[2021,11]]}},"alternative-id":["info12110448"],"URL":"https:\/\/doi.org\/10.3390\/info12110448","relation":{},"ISSN":["2078-2489"],"issn-type":[{"type":"electronic","value":"2078-2489"}],"subject":[],"published":{"date-parts":[[2021,10,27]]}}}