{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,12]],"date-time":"2025-10-12T01:48:42Z","timestamp":1760233722120,"version":"build-2065373602"},"reference-count":38,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2021,2,9]],"date-time":"2021-02-09T00:00:00Z","timestamp":1612828800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithms"],"abstract":"<jats:p>We consider the distributed setting of N autonomous mobile robots that operate in Look-Compute-Move (LCM) cycles and use colored lights (the robots with lights model). We assume obstructed visibility where a robot cannot see another robot if a third robot is positioned between them on the straight line segment connecting them. In this paper, we consider the problem of positioning N autonomous robots on a plane so that every robot is visible to all others (this is called the Complete Visibility problem). This problem is fundamental, as it provides a basis to solve many other problems under obstructed visibility. In this paper, we provide the first, asymptotically optimal, O(1) time, O(1) color algorithm for Complete Visibility in the asynchronous setting. This significantly improves on an O(N)-time translation of the existing O(1) time, O(1) color semi-synchronous algorithm to the asynchronous setting. The proposed algorithm is collision-free, i.e., robots do not share positions, and their paths do not cross. We also introduce a new technique for moving robots in an asynchronous setting that may be of independent interest, called Beacon-Directed Curve Positioning.<\/jats:p>","DOI":"10.3390\/a14020056","type":"journal-article","created":{"date-parts":[[2021,2,9]],"date-time":"2021-02-09T23:43:16Z","timestamp":1612914196000},"page":"56","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":9,"title":["Constant-Time Complete Visibility for Robots with Lights: The Asynchronous Case"],"prefix":"10.3390","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4930-4609","authenticated-orcid":false,"given":"Gokarna","family":"Sharma","sequence":"first","affiliation":[{"name":"Department of Computer Science, Kent State University, Kent, OH 44242, USA"}]},{"given":"Ramachandran","family":"Vaidyanathan","sequence":"additional","affiliation":[{"name":"Electrical Engineering and Computer Science, Louisiana State University, Baton Rouge, LA 70803, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4160-0013","authenticated-orcid":false,"given":"Jerry L.","family":"Trahan","sequence":"additional","affiliation":[{"name":"Electrical Engineering and Computer Science, Louisiana State University, Baton Rouge, LA 70803, USA"}]}],"member":"1968","published-online":{"date-parts":[[2021,2,9]]},"reference":[{"key":"ref_1","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_2","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/j.tcs.2015.09.018","article-title":"Autonomous mobile robots with lights","volume":"609","author":"Das","year":"2016","journal-title":"Theor. Comput. Sci."},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"Peleg, D. (2005). Distributed Coordination Algorithms for Mobile Robot Swarms: New Directions and Challenges. International Workshop on Distributed Computing, Springer.","DOI":"10.1007\/11603771_1"},{"key":"ref_4","unstructured":"Vaidyanathan, R., Sharma, G., and Trahan, J.L. (2021, January 18). On Fast Pattern Formation by Autonomous Robots. Available online: https:\/\/www.sciencedirect.com\/science\/article\/abs\/pii\/S0890540121000146."},{"key":"ref_5","doi-asserted-by":"crossref","unstructured":"Di Luna, G.A., Flocchini, P., Chaudhuri, S.G., Santoro, N., and Viglietta, G. (2014). Robots with Lights: Overcoming Obstructed Visibility Without Colliding. Symposium on Self-Stabilizing Systems, Springer.","DOI":"10.1007\/978-3-319-11764-5_11"},{"key":"ref_6","doi-asserted-by":"crossref","first-page":"392","DOI":"10.1016\/j.ic.2016.09.005","article-title":"Mutual visibility by luminous robots without collisions","volume":"254","author":"Flocchini","year":"2017","journal-title":"Inf. Comput."},{"key":"ref_7","doi-asserted-by":"crossref","unstructured":"Sharma, G., Busch, C., and Mukhopadhyay, S. (2015). Mutual Visibility with an Optimal Number of Colors. International Symposium on Algorithms and Experiments for Wireless Sensor Networks, Springer.","DOI":"10.1007\/978-3-319-28472-9_15"},{"key":"ref_8","doi-asserted-by":"crossref","unstructured":"Vaidyanathan, R., Busch, C., Trahan, J.L., Sharma, G., and Rai, S. (2017, January 25\u201329). Logarithmic-Time Complete Visibility for Robots with Lights. Proceedings of the 2015 IEEE International Parallel and Distributed Processing Symposium, Hyderabad, India.","DOI":"10.1109\/IPDPS.2015.52"},{"key":"ref_9","doi-asserted-by":"crossref","unstructured":"Sharma, G., Vaidyanathan, R., Trahan, J.L., Busch, C., and Rai, S. (2016). Complete Visibility for Robots with Lights in O(1) Time. International Symposium on Stabilization, Safety, and Security of Distributed Systems, Springer.","DOI":"10.1007\/978-3-319-49259-9_26"},{"key":"ref_10","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, Montreal, QC, Canada.","DOI":"10.1145\/2484239.2484266"},{"key":"ref_11","doi-asserted-by":"crossref","unstructured":"Sharma, G., Alsaedi, R., Busch, C., and Mukhopadhyay, S. (2018, January 4\u20137). The Complete Visibility Problem for Fat Robots with Lights. Proceedings of the 19th International Conference on Distributed Computing and Networking, Varanasi, India.","DOI":"10.1145\/3154273.3154319"},{"key":"ref_12","unstructured":"Sharma, G., Busch, C., and Mukhopadhyay, S. (2018, January 9\u201311). Complete Visibility for Oblivious Robots in O(N) Time. Proceedings of the Networked Systems-6th International Conference, NETYS 2018, Essaouira, Morocco."},{"key":"ref_13","doi-asserted-by":"crossref","unstructured":"Sharma, G., Vaidyanathan, R., Trahan, J.L., Busch, C., and Rai, S. (2017, January 25\u201329). Logarithmic-Time Complete Visibility for Asynchronous Robots with Lights. Proceedings of the 2015 IEEE International Parallel and Distributed Processing Symposium, Hyderabad, India.","DOI":"10.1109\/IPDPS.2015.52"},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Sharma, G., Vaidyanathan, R., and Trahan, J.L. (2017). Constant-Time Complete Visibility for Asynchronous Robots with Lights. International Symposium on Stabilization, Safety, and Security of Distributed Systems, Springer.","DOI":"10.1109\/IPDPS.2017.51"},{"key":"ref_15","unstructured":"Di Luna, G.A., Flocchini, P., Poloni, F., Santoro, N., and Viglietta, G. (2014, January 11\u201313). The Mutual Visibility Problem for Oblivious Robots. Proceedings of the Canadian Conference on Computational Geometry, Halifax, NS, Canada."},{"key":"ref_16","first-page":"32","article-title":"Complete Visibility for Mobile Robots with Lights Tolerating Faults","volume":"8","author":"Aljohani","year":"2018","journal-title":"Int. J. Netw. Comput."},{"key":"ref_17","doi-asserted-by":"crossref","first-page":"116","DOI":"10.1016\/j.tcs.2020.10.033","article-title":"Fault-tolerant complete visibility for asynchronous robots with lights under one-axis agreement","volume":"850","author":"Poudel","year":"2021","journal-title":"Theor. Comput. Sci."},{"key":"ref_18","doi-asserted-by":"crossref","unstructured":"Bhagat, S., Chaudhuri, S.G., and Mukhopadhyaya, K. (2016). Formation of General Position by Asynchronous Mobile Robots Under One-Axis Agreement. International Workshop on Algorithms and Computation, Springer.","DOI":"10.1007\/978-3-319-30139-6_7"},{"key":"ref_19","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1016\/j.tcs.2008.10.005","article-title":"Gathering Few Fat Mobile Robots in the Plane","volume":"410","author":"Czyzowicz","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"ref_20","doi-asserted-by":"crossref","unstructured":"Adhikary, R., Bose, K., Kundu, M.K., and Sau, B. (2018). Mutual Visibility by Asynchronous Robots on Infinite Grid. International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, Springer.","DOI":"10.1007\/978-3-030-14094-6_6"},{"key":"ref_21","first-page":"607","article-title":"Optimal Randomized Complete Visibility on a Grid for Asynchronous Robots with Lights","volume":"11","author":"Sharma","year":"2021","journal-title":"Int. J. Netw. Comput."},{"key":"ref_22","doi-asserted-by":"crossref","unstructured":"Hector, R., Vaidyanathan, R., Sharma, G., and Trahan, J.L. (2020, January 18\u201322). Optimal Convex Hull Formation on a Grid by Asynchronous Robots with Lights. Proceedings of the 2020 IEEE International Parallel and Distributed Processing Symposium, New Orleans, LA, USA.","DOI":"10.1109\/IPDPS47924.2020.00111"},{"key":"ref_23","doi-asserted-by":"crossref","first-page":"169","DOI":"10.1016\/j.entcs.2016.03.012","article-title":"Synchronous Robots vs Asynchronous Lights-Enhanced Robots on Graphs","volume":"322","author":"Frigioni","year":"2016","journal-title":"Electr. Notes Theor. Comput. Sci."},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"71","DOI":"10.1016\/j.tcs.2008.02.007","article-title":"Local Spreading Algorithms for Autonomous Robot Systems","volume":"399","author":"Cohen","year":"2008","journal-title":"Theor. Comput. Sci."},{"key":"ref_25","doi-asserted-by":"crossref","unstructured":"Dutta, A., Chaudhuri, S.G., Datta, S., and Mukhopadhyaya, K. (2012). Circle Formation by Asynchronous Fat Robots with Limited Visibility. International Conference on Distributed Computing and Internet Technology, Spring.","DOI":"10.1007\/978-3-642-28073-3_8"},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"171","DOI":"10.1016\/j.jda.2015.04.001","article-title":"Leader election and gathering for asynchronous fat robots without common chirality","volume":"33","author":"Mukhopadhyaya","year":"2015","journal-title":"J. Discrete Algorithms"},{"key":"ref_27","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/j.tcs.2014.08.004","article-title":"Gathering fat mobile robots with slim omnidirectional cameras","volume":"557","author":"Honorat","year":"2014","journal-title":"Theor. Comput. Sci."},{"key":"ref_28","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."},{"key":"ref_29","doi-asserted-by":"crossref","unstructured":"Ando, H., Suzuki, I., and Yamashita, M. (1995, January 10\u201313). Formation and agreement problems for synchronous mobile robots with limited visibility. Proceedings of the International Conference on Distributed Computing and Internet Technology, Bhubaneswar, India.","DOI":"10.21236\/ADA296911"},{"key":"ref_30","doi-asserted-by":"crossref","unstructured":"Prencipe, G. (2013). Autonomous Mobile Robots: A Distributed Computing Perspective. International Symposium on Algorithms and Experiments for Sensor Systems, Wireless Networks and Distributed Robotics, Spring.","DOI":"10.1007\/978-3-642-45346-5_2"},{"key":"ref_31","doi-asserted-by":"crossref","first-page":"2433","DOI":"10.1016\/j.tcs.2010.01.037","article-title":"Characterizing geometric patterns formable by oblivious anonymous mobile robots","volume":"411","author":"Yamashita","year":"2010","journal-title":"Theor. Comput. Sci."},{"key":"ref_32","doi-asserted-by":"crossref","unstructured":"Abshoff, S., Cord-Landwehr, A., Fischer, M., Jung, D., and Meyer auf der Heide, F. (2016, January 23\u201327). Gathering a Closed Chain of Robots on a Grid. Proceedings of the 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS), Chicago, IL, USA.","DOI":"10.1109\/IPDPS.2016.51"},{"key":"ref_33","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.","DOI":"10.1145\/2935764.2935789"},{"key":"ref_34","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.","DOI":"10.1145\/1989493.1989515"},{"key":"ref_35","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, Santorini, Greece."},{"key":"ref_36","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.","DOI":"10.1145\/2312005.2312009"},{"key":"ref_37","doi-asserted-by":"crossref","unstructured":"Izumi, T., Potop-Butucaru, M.G., and Tixeuil, S. (2010). Connectivity-preserving Scattering of Mobile Robots with Limited Visibility. Symposium on Self-Stabilizing Systems, Springer.","DOI":"10.1007\/978-3-642-16023-3_27"},{"key":"ref_38","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). A New Approach for Analyzing Convergence Algorithms for Mobile Robots. International Colloquium on Automata, Languages, and Programming, Springer.","DOI":"10.1007\/978-3-642-22012-8_52"}],"container-title":["Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/2\/56\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:22:02Z","timestamp":1760160122000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/2\/56"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,9]]},"references-count":38,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2021,2]]}},"alternative-id":["a14020056"],"URL":"https:\/\/doi.org\/10.3390\/a14020056","relation":{},"ISSN":["1999-4893"],"issn-type":[{"type":"electronic","value":"1999-4893"}],"subject":[],"published":{"date-parts":[[2021,2,9]]}}}