Abstract
Consider a group of autonomous mobile computational entities called robots. The robots move in the Euclidean plane and operate according to synchronous Look-Compute-Move cycles. The computational capabilities of the robots under the four traditional models \(\{ \mathcal {OBLOT},\ \mathcal {FSTA},\ \mathcal {FCOM},\ \mathcal {LUMI} \} \) have been extensively investigated both when the robots had unlimited amount of energy and when the robots were energy-constrained.
In both the above cases, the robots had full visibility. In this paper, this assumption is removed, i.e., we assume that the robots can view up to a constant radius \(V_r\) from their position (the \(V_r\) is same for all the robots) and, investigates what impact it has on its computational capabilities.
We first study whether the restriction imposed on the visibility has any impact at all, i.e., under a given model and scheduler does there exist any problem which cannot be solved by a robot having limited visibility but can be solved by a robot with full visibility. We find that the answer to the question in general turns out to be positive. Finally, we try to get an idea that under a given model, which of the two factors, Visibility or Synchronicity is more powerful and conclude that a definite conclusion cannot be drawn.
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
Ando, H., Oasa, Y., Suzuki, I., Yamashita, M.: Distributed memoryless point convergence algorithm for mobile robots with limited visibility. IEEE Trans. Robot. Autom. 15(5), 818–828 (1999). https://doi.org/10.1109/70.795787
Buchin, K., Flocchini, P., Kostitsyna, I., Peters, T., Santoro, N., Wada, K.: Autonomous mobile robots: refining the computational landscape. In: IEEE International Parallel and Distributed Processing Symposium Workshops, IPDPS Workshops 2021, Portland, OR, USA, 17–21 June 2021, pp. 576–585. IEEE (2021). https://doi.org/10.1109/IPDPSW52791.2021.00091
Buchin, K., Flocchini, P., Kostitsyna, I., Peters, T., Santoro, N., Wada, K.: On the computational power of energy-constrained mobile robots: algorithms and cross-model analysis. In: Parter, M. (ed.) Structural Information and Communication Complexity. SIROCCO 2022. LNCS, vol. 13298, pp. 42–61. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-09993-9_3
Das, S., Flocchini, P., Prencipe, G., Santoro, N., Yamashita, M.: The power of lights: synchronizing asynchronous robots using visible bits. In: 2012 IEEE 32nd International Conference on Distributed Computing Systems, Macau, China, 18–21 June 2012, pp. 506–515. IEEE Computer Society (2012). https://doi.org/10.1109/ICDCS.2012.71
Das, S., Flocchini, P., Prencipe, G., Santoro, N., Yamashita, M.: Autonomous mobile robots with lights. Theor. Comput. Sci. 609, 171–184 (2016). https://doi.org/10.1016/j.tcs.2015.09.018
Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Gathering of asynchronous robots with limited visibility. Theor. Comput. Sci. 337(1–3), 147–168 (2005). https://doi.org/10.1016/j.tcs.2005.01.001
Flocchini, P., Santoro, N., Viglietta, G., Yamashita, M.: Rendezvous with constant memory. Theor. Comput. Sci. 621, 57–72 (2016). https://doi.org/10.1016/j.tcs.2016.01.025
Flocchini, P., Santoro, N., Wada, K.: On memory, communication, and synchronous schedulers when moving and computing. In: Felber, P., Friedman, R., Gilbert, S., Miller, A. (eds.) 23rd International Conference on Principles of Distributed Systems, OPODIS 2019, December 17–19, 2019, Neuchâtel, Switzerland. LIPIcs, vol. 153, pp. 25:1–25:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019). https://doi.org/10.4230/LIPIcs.OPODIS.2019.25
Goswami, P., Sharma, A., Ghosh, S., Sau, B.: Time optimal gathering of myopic robots on an infinite triangular grid. In: Devismes, S., Petit, F., Altisen, K., Di Luna, G.A., Fernandez Anta, A. (eds.) Stabilization, Safety, and Security of Distributed Systems. SSS 2022. LNCS, vol. 13751, pp. 270–284. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-21017-4_18
Poudel, P., Sharma, G.: Time-optimal gathering under limited visibility with one-axis agreement. Inf. 12(11), 448 (2021). https://doi.org/10.3390/info12110448
Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28(4), 1347–1363 (1999). https://doi.org/10.1137/S009753979628292X
Acknowledgement
The second author is supported by West Bengal State Government Fellowship scheme. The third and fourth authors are supported by UGC, Govt. of India.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2024 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Das, A., Ghosh, S., Sharma, A., Goswami, P., Sau, B. (2024). The Computational Landscape of Autonomous Mobile Robots: The Visibility Perspective. In: Devismes, S., Mandal, P.S., Saradhi, V.V., Prasad, B., Molla, A.R., Sharma, G. (eds) Distributed Computing and Intelligent Technology. ICDCIT 2024. Lecture Notes in Computer Science, vol 14501. Springer, Cham. https://doi.org/10.1007/978-3-031-50583-6_6
Download citation
DOI: https://doi.org/10.1007/978-3-031-50583-6_6
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-031-50582-9
Online ISBN: 978-3-031-50583-6
eBook Packages: Computer ScienceComputer Science (R0)