×

On the power of bounded asynchrony: convergence by autonomous robots with limited visibility. (English) Zbl 07909897

Summary: A distributed algorithm \(\mathcal{A}\) solves the Point Convergence task if an arbitrarily large collection of entities, starting in an arbitrary configuration, move under the control of \(\mathcal{A}\) to eventually form and thereafter maintain configurations in which the separation between all entities is arbitrarily small. This fundamental task in the standard \(\mathcal{O}BLOT\) model of autonomous mobile entities has been previously studied in a variety of settings, including full visibility, exact measurements (including distances and angles), and synchronous activation of entities. Our study concerns the minimal assumptions under which entities, moving asynchronously with limited and unknown visibility range and subject to limited imprecision in measurements, can be guaranteed to converge in this way. We present an algorithm operating under these constraints that solves Point Convergence, for entities moving in two or three dimensional space, with any bounded degree of asynchrony. We also prove that under similar realistic constraints, but unbounded asynchrony, Point Convergence in the plane is not possible in general, contingent on the natural assumption that algorithms maintain the (visible) connectivity among entities present in the initial configuration. This variant, that we call Cohesive Convergence, serves to distinguish the power of bounded and unbounded asynchrony in the control of autonomous mobile entities, settling a long-standing question whether in the Euclidean plane synchronously scheduled entities are more powerful than asynchronously scheduled entities.

MSC:

68M14 Distributed systems
68W15 Distributed algorithms

References:

[1] Kirkpatrick, D., Kostitsyna, I., Navarra, A., Prencipe, G., Santoro, N.: Separating bounded and unbounded asynchrony for autonomous robots: point convergence with limited visibility. In: 40th ACM Symposium on Principles of Distributed Computing (PODC), pp. 9-19 (2021) · Zbl 07824178
[2] Flocchini, P.; Prencipe, G.; Santoro, N., Distributed Computing by Oblivious Mobile Robots, 2012, Williston: Morgan & Claypool, Williston · doi:10.1007/978-3-031-02008-7
[3] Braun, M., Castenow, J., Heide, F.M.: Local gathering of mobile robots in three dimensions. CoRR abs/2005.07495 (2020)
[4] Bhagat, S., Chaudhuri, S.G., Mukhopadyaya, K.: Gathering of opaque robots in 3D space. In: 19th International ACM Conference on Distributed Computing and Networking (ICDCN), pp. 1-10 (2018)
[5] Yamauchi, Y., Uehara, T., Yamashita, M.: Brief announcement: pattern formation problem for synchronous mobile robots in the three dimensional Euclidean space. In: Giakkoupis, G. (ed.) Proceedings of the ACM Symposium on Principles of Distributed Computing (PODC), pp. 447-449 (2016). doi:10.1145/2933057.2933063 · Zbl 1374.68592
[6] Yamauchi, Y.; Uehara, T.; Kijima, S.; Yamashita, M., Plane formation by synchronous mobile robots in the three-dimensional Euclidean space, J. ACM, 64, 3, 16-11643, 2017 · Zbl 1426.68278 · doi:10.1145/3060272
[7] Bose, K.; Kundu, MK; Adhikary, R.; Sau, B., Arbitrary pattern formation by asynchronous opaque robots with lights, Theor. Comput. Sci., 849, 138-158, 2021 · Zbl 1464.68437 · doi:10.1016/j.tcs.2020.10.015
[8] Cicerone, S.; Di Stefano, G.; Navarra, A., Asynchronous arbitrary pattern formation: the effects of a rigorous approach, Distrib. Comput., 32, 2, 91-132, 2019 · Zbl 1432.68024 · doi:10.1007/s00446-018-0325-7
[9] Cicerone, S.; Di Stefano, G.; Navarra, A., Solving the pattern formation by mobile robots with chirality, IEEE Access, 9, 88177-88204, 2021 · doi:10.1109/ACCESS.2021.3089081
[10] Flocchini, P.; Prencipe, G.; Santoro, N.; Widmayer, P., Arbitrary pattern formation by asynchronous oblivious robots, Theor. Comput. Sci., 407, 1-3, 412-447, 2008 · Zbl 1152.68053 · doi:10.1016/j.tcs.2008.07.026
[11] Kasuya, M.; Ito, N.; Inuzuka, N.; Wada, K., A pattern formation algorithm for a set of autonomous distributed robots with agreement on orientation along one axis, Syst. Comput. Japan, 37, 10, 89-100, 2006 · doi:10.1002/scj.20331
[12] Agmon, N.; Peleg, D., Fault-tolerant gathering algorithms for autonomous mobile robots, SIAM J. Comput., 36, 56-82, 2006 · Zbl 1111.68136 · doi:10.1137/050645221
[13] Bouzid, Z., Das, S., Tixeuil, S.: Gathering of mobile robots tolerating multiple crash faults. In: 33rd International Conference on Distributed Computing Systems (ICDCS), pp. 337-346 (2013)
[14] 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 · doi:10.1007/s00446-017-0293-3
[15] Cieliebak, M.; Flocchini, P.; Prencipe, G.; Santoro, N., Distributed computing by mobile robots: gathering, SIAM J. Comput., 41, 4, 829-879, 2012 · Zbl 1286.68484 · doi:10.1137/100796534
[16] Czyzowicz, J.; Gasieniec, L.; Pelc, A., Gathering few fat mobile robots in the plane, Theor. Comput. Sci., 410, 6-7, 481-499, 2009 · Zbl 1157.68065 · doi:10.1016/j.tcs.2008.10.005
[17] Izumi, T.; Souissi, S.; Katayama, Y.; Inuzuka, N.; Defago, X.; Wada, K.; Yamashita, M., The gathering problem for two oblivious robots with unreliable compasses, SIAM J. Comput., 41, 1, 26-46, 2012 · Zbl 1242.68178 · doi:10.1137/100797916
[18] Izumi, T., Katayama, Y., Inuzuka, N., Wada, K.: Gathering autonomous mobile robots with dynamic compasses: an optimal result. In: 21st International Symposium on Distributed Computing (DISC), pp. 298-312 (2007) · Zbl 1145.68549
[19] Lin, J.; Morse, AS; Anderson, BDO, The multi-agent rendezvous problem. Part 2: the asynchronous case, SIAM J. Control Optim., 46, 6, 2120-2147, 2007 · Zbl 1149.93024 · doi:10.1137/040620564
[20] Prencipe, G., Impossibility of gathering by a set of autonomous mobile robots, Theor. Comput. Sci., 384, 2-3, 222-231, 2007 · Zbl 1125.68124 · doi:10.1016/j.tcs.2007.04.023
[21] 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 · doi:10.1109/70.795787
[22] Bar-Lev, A., Cohen, R.: Convergence of asynchronous autonomous mobile robots with inaccurate sensors. In: Algorithms and Experiments for Wireless Networks (ALGOSENSORS). Springer, Berlin, Heidelberg (2020) (under review)
[23] Bouzid, Z., Potop-Butucaru, M.G., Tixeuil, S.: Byzantine convergence in robot networks: the price of asynchrony. In: Proceedings of 13th International Conference Principles of Distributed Systems (OPODIS), pp. 54-70 (2009)
[24] Cord-Landwehr, A., Degener, B., Fischer, M., Hüllmann, M., Kempkes, B., Klaas, A., Kling, P., Kurras, S., Märtens, M., Heide, F., Raupach, C., Swierkot, K., Warner, D., Weddemann, C., Wonisch, D.: A new approach for analyzing convergence algorithms for mobile robots. In: Automata, Languages and Programming (ICALP). Lecture Notes in Computer Science, vol. 6756, pp. 650-661. Springer (2011) · Zbl 1334.68227
[25] Cohen, R.; Peleg, D., Convergence properties of the gravitational algorithm in asynchronous robot systems, SIAM J. Comput., 34, 6, 1516-1528, 2005 · Zbl 1081.68110 · doi:10.1137/S0097539704446475
[26] Cohen, R.; Peleg, D., Convergence of autonomous mobile robots with inaccurate sensors and movements, SIAM J. Comput., 38, 1, 276-302, 2008 · Zbl 1178.68594 · doi:10.1137/060665257
[27] Katreniak, B.: Convergence with limited visibility by asynchronous mobile robots. In: Structural Information and Communication Complexity (SIROCCO). Lecture Notes in Computer Science, vol. 6796, pp. 125-137. Springer (2011)
[28] Pattanayak, D., Mondal, K., Mandal, P.S., Schmid, S.: Convergence of even simpler robots without position information. In: El Abbadi, A., Garbinato, B. (eds.) Networked Systems (NETYS). Lecture Notes in Computer Science, vol. 10299, pp. 69-85. Springer (2017)
[29] Pattanayak, D.; Mondal, K.; Mandal, PS; Schmid, S., Area convergence of monoculus robots with additional capabilities, Comput. J. (COMPJ), 2021 · doi:10.1093/comjnl/bxaa182
[30] Yamamoto, K.; Izumi, T.; Katayama, Y.; Inuzuka, N.; Wada, K., The optimal tolerance of uniform observation error for mobile robot convergence, Theor. Comput. Sci., 444, 77-86, 2012 · Zbl 1243.68302 · doi:10.1016/j.tcs.2012.04.038
[31] Degener, B., Kempkes, B., Langner, T., Heide, F.M., Pietrzyk, P., Wattenhofer, R.: A tight runtime bound for synchronous gathering of autonomous robots with limited visibility. In: Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 139-148 (2011)
[32] Flocchini, P.; Prencipe, G.; Santoro, N.; Widmayer, P., Gathering of asynchronous robots with limited visibility, Theor. Comput. Sci., 337, 1-3, 147-168, 2005 · Zbl 1108.68120 · doi:10.1016/j.tcs.2005.01.001
[33] Souissi, S., Défago, X., Yamashita, M.: Using eventually consistent compasses to gather memory-less mobile robots with limited visibility. ACM Trans. Auton. Adapt. Syst. 4(1), 1-27 (2009)
[34] Yamauchi, Y., Yamashita, M.: Pattern formation by mobile robots with limited visibility. In: 20th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2013). Lecture Notes in Computer Science, vol. 8179, pp. 201-212. Springer. doi:10.1007/978-3-319-03578-9_17 (2013) · Zbl 1374.68593
[35] Suzuki, I.; Yamashita, M., Distributed anonymous mobile robots: formation of geometric patterns, SIAM J. Comput., 28, 4, 1347-1363, 1999 · Zbl 0940.68145 · doi:10.1137/S009753979628292X
[36] Yamashita, M.; Suzuki, I., Characterizing geometric patterns formable by oblivious anonymous mobile robots, Theor. Comput. Sci., 411, 26-28, 2433-2453, 2010 · Zbl 1208.68222 · doi:10.1016/j.tcs.2010.01.037
[37] Yamauchi, Y.: Symmetry of anonymous robots. Chapter 8 of: P. Flocchini, G. Prencipe, N. Santoro (eds.), Distributed Computing by Mobile Entities. Springer (2019)
[38] Flocchini, P.; Prencipe, G.; Santoro, N.; Viglietta, G., Distributed computing by mobile robots: uniform circle formation, Distrib. Comput., 30, 6, 413-457, 2017 · Zbl 1419.68029 · doi:10.1007/s00446-016-0291-x
[39] Bhagat, S.; Chaudhuri, SG; Mukhopadyaya, K., Fault-tolerant gathering of asynchronous oblivious mobile robots under one-axis agreement, J. Discrete Algorithms, 36, 50-62, 2016 · Zbl 1351.68290 · doi:10.1016/j.jda.2015.10.005
[40] Défago, X., Potop-Butucaru, M., Parvédy, P.R.: Self-stabilizing gathering of mobile robots under crash or byzantine faults. Distrib. Comput. 33(5), 393-421 (2020) · Zbl 1460.68015
[41] Cicerone, S.; Di Stefano, G.; Navarra, A., Embedded pattern formation by asynchronous robots without chirality, Distrib. Comput., 32, 4, 291-315, 2019 · Zbl 1432.68025 · doi:10.1007/s00446-018-0333-7
[42] Das, S.; Flocchini, P.; Santoro, N.; Yamashita, M., Forming sequence of geometric patterns with oblivious mobile robots, Distrib. Comput., 28, 131-145, 2015 · Zbl 1331.68223 · doi:10.1007/s00446-014-0220-9
[43] Pagli, L.; Prencipe, G.; Viglietta, G., Getting close without touching: near-gathering for autonomous mobile robots, Distrib. Comput., 28, 5, 333-349, 2015 · Zbl 1341.68280 · doi:10.1007/s00446-015-0248-5
[44] Flocchini, P., Prencipe, G., Santoro, N.: Moving and computing models: robots. In: Distributed Computing by Mobile Entities, Current Research in Moving and Computing. Lecture Notes in Computer Science, Springer, vol. 11340, pp. 3-14 (2019). doi:10.1007/978-3-030-11072-7_1
[45] 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), pp. 250-259 (2013) · Zbl 1323.68547
[46] Chaudhuri, SG; Mukhopadhyaya, K., Leader election and gathering for asynchronous fat robots without common chirality, J. Discrete Algorithms, 33, 171-192, 2015 · Zbl 1337.68039 · doi:10.1016/j.jda.2015.04.001
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.