×

zbMATH — the first resource for mathematics

Characterizing the computational power of mobile robots on graphs and implications for the Euclidean plane. (English) Zbl 1407.68531
Summary: In this paper we study the computational power of mobile robots without global coordination.
A comprehensive evaluation of the computational power of robots moving within the Euclidean plane has been proposed by S. Das et al. in [Theor. Comput. Sci. 609, Part 1, 171–184 (2016; Zbl 1331.68082)]. In their work, the authors study the relations between classic synchronization models, namely fully-synchronous, semi-synchronous, and asynchronous, and variations of them where robots are endowed with a visible light, i.e. they are luminous.
Here we are interested in similar settings but for robots moving on graphs. In particular, we first prove computational relationships among classic models on graphs. To this respect, we investigate the gathering problem and disprove conjectures previously posed in the literature. Second, we compare classic models against luminous models.
Third, we highlight the differences among different luminous models. Finally, we compare our results with those holding in the Euclidean plane.

MSC:
68W15 Distributed algorithms
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
68R10 Graph theory (including graph drawing) in computer science
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Aljohani, A.; Poudel, P.; Sharma, G., Fault-tolerant complete visibility for asynchronous robots with lights under one-axis agreement, (Rahman, M. S.; Sung, W.; Uehara, R., Proceedings of 12th International Conference on Algorithms and Computation (WALCOM), Lect. Notes Comput. Sci., vol. 10755, (2018), Springer), 169-182 · Zbl 06889928
[2] Alonso-Mora, J.; Naegeli, T.; Siegwart, R.; Beardsley, P. A., Collision avoidance for aerial vehicles in multi-agent scenarios, Auton. Robots, 39, 1, 101-121, (2015)
[3] Aminof, B.; Murano, A.; Rubin, S.; Zuleger, F., Verification of asynchronous mobile-robots in partially-known environments, (Chen, Q.; Torroni, P.; Villata, S.; Hsu, J.; Omicini, A., PRIMA 2015: Principles and Practice of Multi-Agent Systems, Cham, 2015, (2015), Springer International Publishing), 185-200
[4] Aminof, B.; Murano, A.; Rubin, S.; Zuleger, F., Automatic verification of multi-agent systems in parameterised grid-environments, (Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems, AAMAS ’16, (2016), International Foundation for Autonomous Agents and Multiagent Systems), 1190-1199
[5] Bouzid, Z.; Das, S.; Tixeuil, S., Gathering of mobile robots tolerating multiple crash faults, (Proceedings of 33rd International Conference on Distributed Computing Systems (ICDCS), (2013)), 337-346
[6] Cai, J.; Flocchini, P.; Santoro, N., Decontaminating a network from a black virus, Int. J. Netw. Comput., 4, 1, 151-173, (2014)
[7] Chalopin, J.; Godard, E.; Naudin, A., Anonymous graph exploration with binoculars, (Proceedings of 29th International Symposium Distributed Computing (DISC), Lect. Notes Comput. Sci., vol. 9363, (2015), Springer), 107-122 · Zbl 1394.68012
[8] Chatterjee, A.; Chaudhuri, S. G.; Mukhopadhyaya, K., Gathering asynchronous swarm robots under nonuniform limited visibility, (Proceedings of 11th International Conference on Distributed Computing and Internet Technology (ICDCIT), Lect. Notes Comput. Sci., vol. 8956, (2015), Springer), 174-180
[9] Cicerone, S.; Di Stefano, G.; Navarra, A., Gathering of robots on meeting-points: feasibility and optimal resolution algorithms, Distrib. Comput., 31, 1, 1-50, (2018) · Zbl 1425.68413
[10] Cooper, C.; Klasing, R.; Radzik, T., Locating and repairing faults in a network with mobile agents, Theor. Comput. Sci., 411, 14-15, 1638-1647, (2010) · Zbl 1191.68722
[11] Czyzowicz, J.; Kosowski, A.; Pelc, A., How to meet when you forget: log-space rendezvous in arbitrary graphs, Distrib. Comput., 25, 2, 165-178, (2012) · Zbl 1284.68066
[12] D’Angelo, G.; Di Stefano, G.; Navarra, A., Gathering on rings under the look-compute-move model, Distrib. Comput., 27, 4, 255-285, (2014) · Zbl 1320.68046
[13] D’Angelo, G.; Di Stefano, G.; Navarra, A., Gathering six oblivious robots on anonymous symmetric rings, J. Discret. Algorithms, 26, 16-27, (2014) · Zbl 1298.68270
[14] D’Angelo, G.; Di Stefano, G.; Navarra, A.; Nisse, N.; Suchan, K., Computing on rings by oblivious robots: a unified approach for different tasks, Algorithmica, 72, 4, 1055-1096, (2015) · Zbl 1319.68025
[15] D’Angelo, G.; Navarra, A.; Nisse, N., A unified approach for gathering and exclusive searching on rings under weak assumptions, Distrib. Comput., 30, 1, 17-48, (2017) · Zbl 1404.68018
[16] Das, S.; Flocchini, P.; Prencipe, G.; Santoro, N.; Yamashita, M., Autonomous mobile robots with lights, Theor. Comput. Sci., 609, 171-184, (2016) · Zbl 1331.68082
[17] Das, S.; Flocchini, P.; Santoro, N.; Yamashita, M., On the computational power of oblivious robots: forming a series of geometric patterns, (Proceedings of 29th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC), (2010), ACM), 267-276 · Zbl 1315.68249
[18] Datta, A. K.; Lamani, A.; Larmore, L. L.; Petit, F., Ring exploration by oblivious agents with local vision, (Proceedings of 33rd International Conference on Distributed Computing Systems (ICDCS), (2013)), 347-356
[19] Degener, B.; Kempkes, B.; Langner, T.; auf der Heide, F. Meyer; Pietrzyk, P.; Wattenhofer, R., A tight runtime bound for synchronous gathering of autonomous robots with limited visibility, (Proceedings of 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), (2011), ACM), 139-148
[20] D’Emidio, M.; Frigioni, D.; Navarra, A., Exploring and making safe dangerous networks using mobile entities, (12th International Conference on Ad Hoc Networks and Wireless (ADHOC-NOW), Lect. Notes Comput. Sci., vol. 7960, (2013), Springer), 136-147
[21] D’Emidio, M.; Frigioni, D.; Navarra, A., Explore and repair graphs with black holes using mobile entities, Theor. Comput. Sci., 605, 129-145, (2015) · Zbl 1330.68222
[22] D’Emidio, M.; Frigioni, D.; Navarra, A., Characterizing the computational power of anonymous mobile robots, (Proceedings of 36th IEEE International Conference on Distributed Computing Systems (ICDCS), (2016)), 293-302
[23] D’Emidio, M.; Frigioni, D.; Navarra, A., Synchronous robots vs asynchronous lights-enhanced robots on graphs, (Proceedings of 16th Italian Conference on Theoretical Computer Science (ICTCS), Electron. Notes Theor. Comput. Sci., vol. 322, (2016), Elsevier), 169-180 · Zbl 1345.68257
[24] D’Emidio, M.; Khan, I., Multi-robot task allocation problem: current trends and new ideas, (Joint Proceedings of the 18th Italian Conference on Theoretical Computer Science and the 32nd Italian Conference on Computational Logic (ICTCS/CILC), CEUR Workshop Proc., vol. 1949, (2017)), 99-103
[25] D’Emidio, M.; Stefano, G. D.; Frigioni, D.; Navarra, A., Improved protocols for luminous asynchronous robots, (Bilò, V.; Caruso, A., Proceedings of the 17th Italian Conference on Theoretical Computer Science, Lecce, Italy, September 7-9, 2016, CEUR Workshop Proc., vol. 1720, (2016)), 136-148
[26] Devismes, S.; Petit, F.; Tixeuil, S., Optimal probabilistic ring exploration by semi-synchronous oblivious robots, (Proceedings of 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO), Lect. Notes Comput. Sci., vol. 5869, (2009)), 195-208 · Zbl 1274.68566
[27] Di Stefano, G.; Montanari, P.; Navarra, A., About ungatherability of oblivious and asynchronous robots on anonymous rings, (Proceedings of 26th International Workshop on Combinatorial Algorithms (IWOCA), Lect. Notes Comput. Sci., vol. 9538, (2015), Springer), 136-147 · Zbl 06562480
[28] Di Stefano, G.; Navarra, A., Gathering of oblivious robots on infinite grids with minimum traveled distance, Inf. Comput., 254, 377-391, (2017) · Zbl 1370.68286
[29] Di Stefano, G.; Navarra, A., Optimal gathering of oblivious robots in anonymous graphs and its application on trees and rings, Distrib. Comput., 30, 2, 75-86, (2017) · Zbl 1419.68184
[30] Dieudonné, Y.; Petit, F.; Villain, V., Leader election problem versus pattern formation problem, (Proceedings of 24th International Symposium on Distributed Computing (DISC), Lect. Notes Comput. Sci., vol. 6343, (2010), Springer), 267-281 · Zbl 1290.68021
[31] Dobrev, S.; Flocchini, P.; Královic, R.; Santoro, N., Exploring an unknown dangerous graph using tokens, Theor. Comput. Sci., 472, 28-45, (2013) · Zbl 1259.68159
[32] Efrima, A.; Peleg, D., Distributed models and algorithms for mobile robot systems, (Proceedings of 33rd Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), Lect. Notes Comput. Sci., vol. 4362, (2007), Springer), 70-87 · Zbl 1131.68556
[33] Flocchini, P., Computations by luminous robots, (Proceedings of 14th International Conference on Ad-hoc, Mobile, and Wireless Networks (ADHOC-NOW), Lect. Notes Comput. Sci., vol. 9143, (2015), Springer), 238-252
[34] Flocchini, P.; Ilcinkas, D.; Pelc, A.; Santoro, N., Remembering without memory: tree exploration by asynchronous oblivious robots, Theor. Comput. Sci., 411, 14-15, 1583-1598, (2010) · Zbl 1191.68712
[35] Flocchini, P.; Ilcinkas, D.; Pelc, A.; Santoro, N., Computing without communicating: ring exploration by asynchronous oblivious robots, Algorithmica, 65, 3, 562-583, (2013) · Zbl 1272.68399
[36] Flocchini, P.; Prencipe, G.; Santoro, N., Distributed computing by oblivious mobile robots, Synth. Lect. Distributed Computing Theory, 3, 2, 1-185, (2012)
[37] Flocchini, P.; Prencipe, G.; Santoro, N.; Widmayer, P., Gathering of asynchronous robots with limited visibility, Theor. Comput. Sci., 337, 147-168, (2005) · Zbl 1108.68120
[38] Flocchini, P.; Prencipe, G.; Santoro, N.; Widmayer, P., Arbitrary pattern formation by asynchronous, anonymous, oblivious robots, Theor. Comput. Sci., 407, 1-3, 412-447, (2008) · Zbl 1152.68053
[39] Fujinaga, N.; Ono, H.; Kijima, S.; Yamashita, M., Pattern formation through optimum matching by oblivious corda robots, (Proceedings of 14th International Conference on Principles of Distributed Systems (OPODIS), Lect. Notes Comput. Sci., vol. 6490, (2010), Springer), 1-15
[40] Fujinaga, N.; Yamauchi, Y.; Kijima, S.; Yamashita, M., Asynchronous pattern formation by anonymous oblivious mobile robots, (Distributed Computing, Lect. Notes Comput. Sci., vol. 7611, (2012), Springer), 312-325 · Zbl 1374.68584
[41] Fujinaga, N.; Yamauchi, Y.; Ono, H.; Kijima, S.; Yamashita, M., Pattern formation by oblivious asynchronous mobile robots, SIAM J. Comput., 44, 3, 740-785, (2015) · Zbl 1325.68230
[42] Haba, K.; Izumi, T.; Katayama, Y.; Inuzuka, N.; Wada, K., On gathering problem in a ring for 2n autonomous mobile robots, (Proceedings of the 10th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), (2008)), poster
[43] Huus, E.; Kranakis, E., Rendezvous of many agents with different speeds in a cycle, (Proceedings of 14th International Conference on Ad-hoc, Mobile, and Wireless Networks (ADHOC-NOW), Lect. Notes Comput. Sci., vol. 9143, (2015), Springer), 195-209
[44] Izumi, T.; Izumi, T.; Kamei, S.; Oshita, F., Randomized gathering of mobile robots with local-multiplicity detection, (Proceedings 11th International Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), Lect. Notes Comput. Sci., vol. 5873, (2009), Springer), 384-398
[45] Kamei, S.; Lamani, A.; Ooshita, F.; Tixeuil, S., Gathering an even number of robots in an odd ring without global multiplicity detection, (Proceedings of 37th International Symposium on Mathematical Foundations of Computer Science (MFCS), (2012), Springer), 542-553 · Zbl 1365.68421
[46] Klasing, R.; Kosowski, A.; Navarra, A., Taking advantage of symmetries: gathering of many asynchronous oblivious robots on a ring, Theor. Comput. Sci., 411, 3235-3246, (2010) · Zbl 1195.68099
[47] Klasing, R.; Markou, E.; Pelc, A., Gathering asynchronous oblivious mobile robots in a ring, Theor. Comput. Sci., 390, 1, 27-39, (2008) · Zbl 1134.68013
[48] Koren, M., Gathering small number of mobile asynchronous robots on ring, Zesz. Nauk. Wydz. ETI Politech. Gdan. Technol. Inform., 18, 325-331, (2010)
[49] Kosowski, A.; Navarra, A., Graph decomposition for memoryless periodic exploration, Algorithmica, 63, 1-2, 26-38, (2012) · Zbl 1241.05114
[51] Peleg, D., Distributed coordination algorithms for mobile robot swarms: new directions and challenges, (Proceedings of 7th International Workshop on Distributed Computing (IWDC), Lect. Notes Comput. Sci., vol. 3741, (2005), Springer), 1-12 · Zbl 1170.68614
[52] Santoro, N., Design and Analysis of Distributed Algorithms, Wiley Ser. Parallel Distrib. Comput., (2007), Wiley-Interscience · Zbl 1115.68166
[54] Suzuki, I.; Yamashita, M., Distributed anonymous mobile robots: formation of geometric patterns, SIAM J. Comput., 28, 4, 1347-1363, (1999) · Zbl 0940.68145
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.