Top

Published in:

2019 | OriginalPaper | Chapter

Mutual Visibility by Asynchronous Robots on Infinite Grid

Authors : Ranendu Adhikary, Kaustav Bose, Manash Kumar Kundu, Buddhadeb Sau

Published in: Algorithms for Sensor Systems

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Consider a set of autonomous, identical, opaque point robots in the Euclidean plane. The Mutual Visibility problem asks the robots to reposition themselves, without colliding, to a configuration where they all see each other, i.e., no three of them are collinear. In this paper, we consider the problem in a grid based terrain where the movements of the robots are restricted only along grid lines and only by a unit distance in each step. We consider the luminous robots model, in which each robot is equipped with an externally visible light which can assume a constant number of predefined colors. These colors serve both as internal memory and as a form of communication. The robots operate in Look-Compute-Move cycles under a fully asynchronous scheduler. The robots do not have any common global coordinate system or chirality and do not have the knowledge of the total number of robots. Our proposed distributed algorithm solves the problem for any arbitrary initial configuration and guarantees collision-free movements.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Average Case - Worst Case Tradeoffs for Evacuating 2 Robots from the Disk in the Face-to-Face Model

next chapter Optimal Gathering by Asynchronous Oblivious Robots in Hypercubes

Available only for authorised users

Agathangelou, C., Georgiou, C., Mavronicolas, M.: A distributed algorithm for gathering many fat mobile robots in the plane. In: ACM Symposium on Principles of Distributed Computing, PODC 2013, 22–24 July 2013, Montreal, QC, Canada, pp. 250–259 (2013). https://doi.org/10.1145/2484239.2484266

Aljohani, A., Sharma, G.: Complete visibility for mobile robots with lights tolerating faults. Int. J. Netw. Comput. 8(1), 32–52 (2018). http://www.ijnc.org/index.php/ijnc/article/view/166CrossRef

Barberá, H.M., Quiñonero, J.P.C., Zamora-Izquierdo, M.A., Gómez-Skarmeta, A.F.: i-fork: a flexible AGV system using topological and grid maps. In: Proceedings of the 2003 IEEE International Conference on Robotics and Automation, ICRA 2003, 14–19 September 2003, Taipei, Taiwan, pp. 2147–2152 (2003). https://doi.org/10.1109/ROBOT.2003.1241911

Bhagat, S., Mukhopadhyaya, K.: Optimum algorithm for mutual visibility among asynchronous robots with lights. In: Proceedings of 19th International Symposium Stabilization, Safety, and Security of Distributed Systems, SSS 2017, 5–8 November 2017, Boston, MA, USA, pp. 341–355 (2017). https://doi.org/10.1007/978-3-319-69084-1_24

Bose, K., Adhikary, R., Chaudhuri, S.G., Sau, B.: Crash tolerant gathering on grid by asynchronous oblivious robots. CoRR abs/1709.00877 (2017). http://arxiv.org/abs/1709.00877

D’Angelo, G., Stefano, G.D., Klasing, R., Navarra, A.: Gathering of robots on anonymous grids and trees without multiplicity detection. Theor. Comput. Sci. 610, 158–168 (2016). https://doi.org/10.1016/j.tcs.2014.06.045MathSciNetCrossRef

Fischer, M., Jung, D., Meyer auf der Heide, F.: Gathering anonymous, oblivious robots on a grid. In: Fernández Anta, A., Jurdzinski, T., Mosteiro, M.A., Zhang, Y. (eds.) ALGOSENSORS 2017. LNCS, vol. 10718, pp. 168–181. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-72751-6_13CrossRef

Luna, G.A.D., Flocchini, P., Chaudhuri, S.G., Poloni, F., Santoro, N., Viglietta, G.: Mutual visibility by luminous robots without collisions. Inf. Comput. 254, 392–418 (2017). https://doi.org/10.1016/j.ic.2016.09.005MathSciNetCrossRef

Luna, G.A.D., Flocchini, P., Poloni, F., Santoro, N., Viglietta, G.: The mutual visibility problem for oblivious robots. In: Proceedings of the 26th Canadian Conference on Computational Geometry, CCCG 2014, Halifax, Nova Scotia, Canada (2014). http://www.cccg.ca/proceedings/2014/papers/paper51.pdf

10.

Peleg, D.: Distributed coordination algorithms for mobile robot swarms: new directions and challenges. In: Pal, A., Kshemkalyani, A.D., Kumar, R., Gupta, A. (eds.) IWDC 2005. LNCS, vol. 3741, pp. 1–12. Springer, Heidelberg (2005). https://doi.org/10.1007/11603771_1CrossRef

11.

Poudel, P., Sharma, G.: Universally optimal gathering under limited visibility. In: Spirakis, P., Tsigas, P. (eds.) SSS 2017. LNCS, vol. 10616, pp. 323–340. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-69084-1_23CrossRef

12.

Sharma, G., Alsaedi, R., Busch, C., Mukhopadhyay, S.: The complete visibility problem for fat robots with lights. In: Proceedings of the 19th International Conference on Distributed Computing and Networking, ICDCN 2018, 4–7 January 2018, Varanasi, India, pp. 21:1–21:4 (2018). https://doi.org/10.1145/3154273.3154319

13.

Sharma, G., Busch, C., Mukhopadhyay, S.: Bounds on mutual visibility algorithms. In: Proceedings of the 27th Canadian Conference on Computational Geometry, CCCG 2015, 10–12 August 2015, Kingston, Ontario, Canada (2015). http://research.cs.queensu.ca/cccg2015/CCCG15-papers/43.pdf

14.

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_15CrossRef

15.

Sharma, G., Vaidyanathan, R., Trahan, J.L., Busch, C., Rai, S.: Complete visibility for robots with lights in O(1) time. In: Bonakdarpour, B., Petit, F. (eds.) SSS 2016. LNCS, vol. 10083, pp. 327–345. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-49259-9_26CrossRef

16.

Sharma, G., Vaidyanathan, R., Trahan, J.L., Busch, C., Rai, S.: O(log n)-time complete visibility for asynchronous robots with lights. In: 2017 IEEE International Parallel and Distributed Processing Symposium, IPDPS 2017, 29 May–2 June 2017, Orlando, FL, USA, pp. 513–522 (2017). https://doi.org/10.1109/IPDPS.2017.51

17.

Stefano, G.D., Navarra, A.: Gathering of oblivious robots on infinite grids with minimum traveled distance. Inf. Comput. 254, 377–391 (2017). https://doi.org/10.1016/j.ic.2016.09.004MathSciNetCrossRefMATH

Title: Mutual Visibility by Asynchronous Robots on Infinite Grid
Authors: Ranendu Adhikary
Kaustav Bose
Manash Kumar Kundu
Buddhadeb Sau
Publisher: Springer International Publishing
Book: Algorithms for Sensor Systems
Print ISBN: 978-3-030-14093-9

Electronic ISBN: 978-3-030-14094-6

Copyright Year: 2019
DOI: https://doi.org/10.1007/978-3-030-14094-6_6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner