Abstract
For a set of robots disposed on the Euclidean plane, Mutual Visibility is often desirable. The requirement is to move robots without collisions so as to achieve a placement where no three robots are collinear. For robots moving on graphs, we consider the Geodesic Mutual Visibility (\(\textrm{GMV}\)) problem. Robots move along the edges of the graph, without collisions, so as to occupy some vertices that guarantee they become pairwise geodesic mutually visible. This means that there is a shortest path (i.e., a “geodesic”) between each pair of robots along which no other robots reside. We study this problem in the context of square grids for robots operating under the standard Look-Compute-Move model. We add the further requirement to obtain a placement of the robots so as that the final bounding rectangle enclosing all the robots is of minimum area. This leads to the \(\mathrm {GMV\!}_{\textsf{area}}\) version of the problem. We show that \(\mathrm {GMV\!}_{\textsf{area}}\) can be solved by a time-optimal distributed algorithm for synchronous robots sharing chirality.
The work has been supported in part by project SICURA – CUP C19C200005200004, and by the Italian National Group for Scientific Computation (GNCS-INdAM).
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Adhikary, R., Bose, K., Kundu, M.K., Sau, B.: Mutual visibility by asynchronous robots on infinite grid. In: Gilbert, S., Hughes, D., Krishnamachari, B. (eds.) ALGOSENSORS 2018. LNCS, vol. 11410, pp. 83–101. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-14094-6_6
Aljohani, A., Poudel, P., Sharma, G.: Complete visitability for autonomous robots on graphs. In: International Parallel and Distributed Processing Symposium (IPDPS), pp. 733–742. IEEE (2018)
Bhagat, S.: Optimum algorithm for the mutual visibility problem. In: Rahman, M.S., Sadakane, K., Sung, W.-K. (eds.) WALCOM 2020. LNCS, vol. 12049, pp. 31–42. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-39881-1_4
Bhagat, S., Gan Chaudhuri, S., Mukhopadhyaya, K.: Mutual visibility for asynchronous robots. In: Censor-Hillel, K., Flammini, M. (eds.) SIROCCO 2019. LNCS, vol. 11639, pp. 336–339. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-24922-9_24
Bhagat, S., Mukhopadhyaya, K.: Optimum algorithm for mutual visibility among asynchronous robots with lights. In: Spirakis, P., Tsigas, P. (eds.) SSS 2017. LNCS, vol. 10616, pp. 341–355. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-69084-1_24
Bhagat, S., Mukhopadhyaya, K.: Mutual visibility by robots with persistent memory. In: Chen, Y., Deng, X., Lu, M. (eds.) FAW 2019. LNCS, vol. 11458, pp. 144–155. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-18126-0_13
Cicerone, S., Di Fonso, A., Di Stefano, G., Navarra, A.: Arbitrary pattern formation on infinite regular tessellation graphs. Theor. Comput. Sci. 942, 1–20 (2023)
Cicerone, S., Di Fonso, A., Di Stefano, G., Navarra, A.: The geodesic mutual visibility problem for oblivious robots: the case of trees. In: Proceedings of the 24th International Conference on Distributed Computing and Networking (ICDCN), pp. 150–159. ACM (2023)
Cicerone, S., Di Stefano, G., Klavzar, S.: On the mutual visibility in cartesian products and triangle-free graphs. Appl. Math. Comput. 438, 127619 (2023)
Cicerone, S., Di Stefano, G., Navarra, A.: Solving the pattern formation by mobile robots with chirality. IEEE Access 9, 88177–88204 (2021)
Cicerone, S., Di Stefano, G., Navarra, A.: A structured methodology for designing distributed algorithms for mobile entities. Inf. Sci. 574, 111–132 (2021)
D’Angelo, G., Di Stefano, G., Klasing, R., Navarra, A.: Gathering of robots on anonymous grids and trees without multiplicity detection. Theor. Comput. Sci. 610, 158–168 (2016)
Di Luna, G.A., Flocchini, P., Chaudhuri, S.G., Poloni, F., Santoro, N., Viglietta, G.: Mutual visibility by luminous robots without collisions. Inf. Comput. 254, 392–418 (2017)
Di Stefano, G.: Mutual visibility in graphs. Appl. Math. Comput. 419, 126850 (2022)
Flocchini, P., Prencipe, G., Santoro, N. (eds.): Distributed Computing by Mobile Entities, Current Research in Moving and Computing, LNCS, vol. 11340. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-11072-7
Poudel, P., Aljohani, A., Sharma, G.: Fault-tolerant complete visibility for asynchronous robots with lights under one-axis agreement. Theor. Comput. Sci. 850, 116–134 (2021)
Sharma, G., Busch, C., Mukhopadhyay, S.: Mutual visibility with an optimal number of colors. In: Bose, P., Gąsieniec, L.A., Römer, K., Wattenhofer, R. (eds.) ALGOSENSORS 2015. LNCS, vol. 9536, pp. 196–210. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-28472-9_15
Sharma, G., Vaidyanathan, R., Trahan, J.L.: Optimal randomized complete visibility on a grid for asynchronous robots with lights. Int. J. Netw. Comput. 11(1), 50–77 (2021)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2023 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Cicerone, S., Di Fonso, A., Di Stefano, G., Navarra, A. (2023). Time-Optimal Geodesic Mutual Visibility of Robots on Grids Within Minimum Area. In: Dolev, S., Schieber, B. (eds) Stabilization, Safety, and Security of Distributed Systems. SSS 2023. Lecture Notes in Computer Science, vol 14310. Springer, Cham. https://doi.org/10.1007/978-3-031-44274-2_29
Download citation
DOI: https://doi.org/10.1007/978-3-031-44274-2_29
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-44273-5
Online ISBN: 978-3-031-44274-2
eBook Packages: Computer ScienceComputer Science (R0)