{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,7]],"date-time":"2026-10-07T06:49:21Z","timestamp":1791355761632,"version":"4.3.1"},"reference-count":30,"publisher":"MDPI AG","issue":"2","license":[{"start":{"date-parts":[[2021,2,18]],"date-time":"2021-02-18T00:00:00Z","timestamp":1613606400000},"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>For a given positive integer k, the k-circle formation problem asks a set of autonomous, asynchronous robots to form disjoint circles having k robots each at distinct locations, centered at a set of fixed points in the Euclidean plane. The robots are identical, anonymous, oblivious, and they operate in Look\u2013Compute\u2013Move cycles. This paper studies the k-circle formation problem and its relationship with the k-epf problem, a generalized version of the embedded pattern formation problem, which asks exactly k robots to reach and remain at each fixed point. First, the k-circle formation problem is studied in a setting where the robots have an agreement on the common direction and orientation of one of the axes. We have characterized all the configurations and the values of k, for which the k-circle formation problem is deterministically unsolvable in this setting. For the remaining configurations and the values of k, a deterministic distributed algorithm has been proposed, in order to solve the problem. It has been proved that for the initial configurations with distinct robot positions, if the k-circle formation problem is deterministically solvable then the k-epf problem is also deterministically solvable. It has been shown that by modifying the proposed algorithm, the k-epf problem can be solved deterministically.<\/jats:p>","DOI":"10.3390\/a14020062","type":"journal-article","created":{"date-parts":[[2021,2,18]],"date-time":"2021-02-18T20:56:21Z","timestamp":1613681781000},"page":"62","update-policy":"https:\/\/doi.org\/10.3390\/mdpi_crossmark_policy","source":"Crossref","is-referenced-by-count":13,"title":["k-Circle Formation and k-epf by Asynchronous Robots"],"prefix":"10.3390","volume":"14","author":[{"given":"Subhash","family":"Bhagat","sequence":"first","affiliation":[{"name":"Indian Association for the Cultivation of Science, Kolkata 700108, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bibhuti","family":"Das","sequence":"additional","affiliation":[{"name":"Advanced Computing and Microelectronics Unit, Indian Statistical Institute, Kolkata 700108, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Abhinav","family":"Chakraborty","sequence":"additional","affiliation":[{"name":"Advanced Computing and Microelectronics Unit, Indian Statistical Institute, Kolkata 700108, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Krishnendu","family":"Mukhopadhyaya","sequence":"additional","affiliation":[{"name":"Advanced Computing and Microelectronics Unit, Indian Statistical Institute, Kolkata 700108, India"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"1968","published-online":{"date-parts":[[2021,2,18]]},"reference":[{"key":"ref_1","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."},{"key":"ref_2","doi-asserted-by":"crossref","unstructured":"Bouzid, Z., Das, S., and Tixeuil, S. (2013, January 8\u201311). Gathering of mobile robots tolerating multiple crash faults. Proceedings of the 2013 IEEE 33rd International Conference on Distributed Computing Systems, Philadelphia, PA, USA.","DOI":"10.1109\/ICDCS.2013.27"},{"key":"ref_3","doi-asserted-by":"crossref","unstructured":"D\u00e9fago, X., Gradinariu, M., Messika, S., and Raipin-Parv\u00e9dy, P. (2006, January 18\u201320). Fault-tolerant and self-stabilizing mobile robots gathering. Proceedings of the 20th International Symposium on Distributed Computing, Stockholm, Sweden.","DOI":"10.1007\/11864219_4"},{"key":"ref_4","doi-asserted-by":"crossref","unstructured":"Flocchini, P., Santoro, N., Viglietta, G., and Yamashita, M. (2013, January 1\u20133). Rendezvous of two robots with constant memory. Proceedings of the International Colloquium on Structural Information and Communication Complexity, Ischia, Italy.","DOI":"10.1007\/978-3-319-03578-9_16"},{"key":"ref_5","doi-asserted-by":"crossref","first-page":"276","DOI":"10.1137\/060665257","article-title":"Convergence of autonomous mobile robots with inaccurate sensors and movements","volume":"38","author":"Cohen","year":"2008","journal-title":"SIAM J. Comput."},{"key":"ref_6","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."},{"key":"ref_7","unstructured":"Cieliebak, M., and Prencipe, G. (2002, January 10\u201312). Gathering Autonomous Mobile Robots. Proceedings of the 9th International Colloquium on Structural Information and Communication Complexity, Andros, Greece."},{"key":"ref_8","doi-asserted-by":"crossref","first-page":"56","DOI":"10.1137\/050645221","article-title":"Fault-tolerant gathering algorithms for autonomous mobile robots","volume":"36","author":"Agmon","year":"2006","journal-title":"SIAM J. Comput."},{"key":"ref_9","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1016\/j.jda.2015.10.005","article-title":"Fault-tolerant gathering of asynchronous oblivious mobile robots under one-axis agreement","volume":"36","author":"Bhagat","year":"2016","journal-title":"J. Discret. Algorithms"},{"key":"ref_10","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_11","doi-asserted-by":"crossref","first-page":"412","DOI":"10.1016\/j.tcs.2008.07.026","article-title":"Arbitrary pattern formation by asynchronous, anonymous, oblivious robots","volume":"407","author":"Flocchini","year":"2008","journal-title":"Theor. Comput. Sci."},{"key":"ref_12","doi-asserted-by":"crossref","unstructured":"Fujinaga, N., Yamauchi, Y., Kijima, S., and Yamashita, M. (2012, January 16\u201318). Asynchronous pattern formation by anonymous oblivious mobile robots. Proceedings of the International Symposium on Distributed Computing, Salvador, Brazil.","DOI":"10.1007\/978-3-642-33651-5_22"},{"key":"ref_13","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1007\/s00446-018-0325-7","article-title":"Asynchronous arbitrary pattern formation: The effects of a rigorous approach","volume":"32","author":"Cicerone","year":"2019","journal-title":"Distrib. Comput."},{"key":"ref_14","doi-asserted-by":"crossref","unstructured":"Fujinaga, N., Ono, H., Kijima, S., and Yamashita, M. (2010, January 14\u201317). Pattern Formation through Optimum Matching by Oblivious CORDA Robots. Proceedings of the Principles of Distributed Systems\u201414th International Conference, OPODIS 2010, Tozeur, Tunisia.","DOI":"10.1007\/978-3-642-17653-1_1"},{"key":"ref_15","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1007\/s00446-018-0333-7","article-title":"Embedded pattern formation by asynchronous robots without chirality","volume":"32","author":"Cicerone","year":"2019","journal-title":"Distrib. Comput."},{"key":"ref_16","doi-asserted-by":"crossref","unstructured":"Bhagat, S., and Mukhopadhyaya, K. (2018). Optimum circle formation by autonomous robots. Advanced Computing and Systems for Security, Springer.","DOI":"10.1007\/978-981-10-8180-4_10"},{"key":"ref_17","doi-asserted-by":"crossref","unstructured":"Datta, S., Dutta, A., Chaudhuri, S.G., and Mukhopadhyaya, K. (2013, January 5\u20138). Circle Formation by Asynchronous Transparent Fat Robots. Proceedings of the Distributed Computing and Internet Technology, 9th International Conference, ICDCIT 2013, Bhubaneswar, India.","DOI":"10.1007\/978-3-642-36071-8_15"},{"key":"ref_18","doi-asserted-by":"crossref","first-page":"97","DOI":"10.1016\/j.tcs.2008.01.050","article-title":"Non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformity","volume":"396","author":"Souissi","year":"2008","journal-title":"Theor. Comput. Sci."},{"key":"ref_19","doi-asserted-by":"crossref","unstructured":"Dutta, A., Chaudhuri, S.G., Datta, S., and Mukhopadhyaya, K. (2012, January 2\u20134). Circle Formation by Asynchronous Fat Robots with Limited Visibility. Proceedings of the 8th International Conference on Distributed Computing and Internet Technology (ICDCIT-2012), Bhubaneswar, India.","DOI":"10.1007\/978-3-642-28073-3_8"},{"key":"ref_20","doi-asserted-by":"crossref","first-page":"413","DOI":"10.1007\/s00446-016-0291-x","article-title":"Distributed computing by mobile robots: Uniform circle formation","volume":"30","author":"Flocchini","year":"2017","journal-title":"Distrib. Comput."},{"key":"ref_21","doi-asserted-by":"crossref","unstructured":"Mondal, M., and Chaudhuri, S.G. (2020, January 9\u201312). Uniform Circle Formation by Swarm Robots Under Limited Visibility. Proceedings of the International Conference on Distributed Computing and Internet Technology, Bhubaneswar, India.","DOI":"10.1007\/978-3-030-36987-3_28"},{"key":"ref_22","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/s00446-017-0293-3","article-title":"Gathering of robots on meeting-points: Feasibility and optimal resolution algorithms","volume":"31","author":"Cicerone","year":"2018","journal-title":"Distrib. Comput."},{"key":"ref_23","doi-asserted-by":"crossref","unstructured":"Bhagat, S., Chakraborty, A., Das, B., and Mukhopadhyaya, K. (2020, January 13\u201315). Gathering over Meeting Nodes in Infinite Grid. Proceedings of the Conference on Algorithms and Discrete Applied Mathematics, Hyderabad, India.","DOI":"10.1007\/978-3-030-39219-2_26"},{"key":"ref_24","doi-asserted-by":"crossref","first-page":"1355","DOI":"10.1016\/j.tcs.2008.04.042","article-title":"Distributed algorithms for partitioning a swarm of autonomous mobile robots","volume":"410","author":"Efrima","year":"2009","journal-title":"Theor. Comput. Sci."},{"key":"ref_25","doi-asserted-by":"crossref","first-page":"138","DOI":"10.1016\/j.tcs.2020.10.015","article-title":"Arbitrary pattern formation by asynchronous opaque robots with lights","volume":"849","author":"Bose","year":"2021","journal-title":"Theor. Comput. Sci."},{"key":"ref_26","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1016\/j.tcs.2020.02.016","article-title":"Arbitrary pattern formation on infinite grid by asynchronous oblivious robots","volume":"815","author":"Bose","year":"2020","journal-title":"Theor. Comput. Sci."},{"key":"ref_27","doi-asserted-by":"crossref","unstructured":"D\u00e9fago, X., and Konagaya, A. (2002, January 30\u201331). Circle formation for oblivious anonymous mobile robots with no common sense of orientation. Proceedings of the Second ACM International Workshop on Principles of Mobile Computing, Toulouse, France.","DOI":"10.1145\/584490.584509"},{"key":"ref_28","doi-asserted-by":"crossref","unstructured":"Feletti, C., Mereghetti, C., and Palano, B. (2018, January 4\u20137). Uniform Circle Formation for Swarms of Opaque Robots with Lights. Proceedings of the Stabilization, Safety, and Security of Distributed Systems, Tokyo, Japan.","DOI":"10.1007\/978-3-030-03232-6_21"},{"key":"ref_29","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.tcs.2018.01.009","article-title":"Team assembling problem for asynchronous heterogeneous mobile robots","volume":"721","author":"Liu","year":"2018","journal-title":"Theor. Comput. Sci."},{"key":"ref_30","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 auf der Heide, F.M. (2011, January 4\u20138). A new approach for analyzing convergence algorithms for mobile robots. Proceedings of the International Colloquium on Automata, Languages, and Programming, Z\u00fcrich, Switzerland.","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\/62\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,11]],"date-time":"2025-10-11T05:25:37Z","timestamp":1760160337000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.mdpi.com\/1999-4893\/14\/2\/62"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,2,18]]},"references-count":30,"journal-issue":{"issue":"2","published-online":{"date-parts":[[2021,2]]}},"alternative-id":["a14020062"],"URL":"https:\/\/doi.org\/10.3390\/a14020062","relation":{},"ISSN":["1999-4893"],"issn-type":[{"value":"1999-4893","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,2,18]]}}}