×

Embedded pattern formation by asynchronous robots without chirality. (English) Zbl 1432.68025

Summary: We consider the Embedded Pattern Formation (epf) problem introduced in [N. Fujinaga et al., SIAM J. Comput. 44, No. 3, 740–785 (2015; Zbl 1325.68230)]. Given a set \(F\) of distinct points in the Euclidean plane (called here fixed-points) and a set \(R\) of robots such that \(|R|=|F|\), the problem asks for a distributed algorithm that moves robots so as to occupy all points in \(F\). Initially, each robot occupies a distinct position. When active, a robot operates in standard Look-Compute-Move cycles. In one cycle, a robot perceives the current configuration in terms of the robots’ positions and the fixed-points (Look) according to its own coordinate system, decides whether to move toward some direction (Compute), and in the positive case it moves (Move). Cycles are performed asynchronously for each robot. Robots are oblivious, anonymous, silent and execute the same deterministic algorithm. In the mentioned paper, the problem has been investigated by endowing robots with chirality, that is they share a common left-right orientation. Here we consider epf without chirality, and we fully characterize when it can be solved by designing a deterministic distributed algorithm that works for all configurations but those identified as unsolvable. The algorithm has been designed according to a rigorous approach, characterized by the use of logical predicates associated to each move used by the robots. This induces a greater level of detail that provides us rigorous bases to state the correctness of the algorithm.

MSC:

68M14 Distributed systems
68T40 Artificial intelligence for robotics
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68W15 Distributed algorithms

Citations:

Zbl 1325.68230
Full Text: DOI

References:

[1] Agmon, N., Peleg, D.: Fault-tolerant gathering algorithms for autonomous mobile robots. SIAM J. Comput. 36(1), 56-82 (2006) · Zbl 1111.68136
[2] Bérard, B., Lafourcade, P., Millet, L., Potop-Butucaru, M., Thierry-Mieg, Y., Tixeuil, S.: Formal verification of mobile robot protocols. Distrib. Comput. 29(6), 459-487 (2016) · Zbl 1410.68217
[3] Bhagat, S., Chaudhuri, S.G., Mukhopadhyaya, K.: Formation of general position by asynchronous mobile robots under one-axis agreement. In: Proceeding of 10th International ’l WS on Algorithms and Computation (WALCOM), LNCS, vol. 9627, pp. 80-91. Springer (2016) · Zbl 1475.68388
[4] Bramas, Q., Tixeuil, S.: Brief Announcement: Probabilistic asynchronous arbitrary pattern formation. In: Proceedings of 35th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC) (2016)
[5] Cicerone, S., Di Stefano, G., Navarra, A.: Asynchronous embedded pattern formation without orientation. In: Proceedings of 30th International ’l Symposium on Distributed Computing (DISC), LNCS, vol. 9888, pp. 85-98. Springer (2016) · Zbl 1393.68183
[6] Cicerone, S., Di Stefano, G., Navarra, A.: Asynchronous arbitrary pattern formation: the effects of a rigorous approach. Distrib. Comput. (2018). https://doi.org/10.1007/s00446-018-0325-7 · Zbl 1432.68024 · doi:10.1007/s00446-018-0325-7
[7] 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
[8] 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
[9] Courtieu, P., Rieg, L., Tixeuil, S., Urbain, X.: Impossibility of gathering, a certification. Inf. Process. Lett. 115(3), 447-452 (2015) · Zbl 1317.68264
[10] Courtieu, P., Rieg, L., Tixeuil, S., Urbain, X.: Brief Announcement: Certified universal gathering in \[R^2\] R2 for oblivious mobile robots. In: Proceedings of 35th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC) (2016) · Zbl 1393.68163
[11] 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) · Zbl 1332.68167
[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., 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
[14] 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
[15] Das, S., Flocchini, P., Santoro, N., Yamashita, M.: Forming sequences of geometric patterns with oblivious mobile robots. Distrib. Comput. 28(2), 131-145 (2015) · Zbl 1331.68223
[16] D’Emidio, M., Frigioni, D., Navarra, A.: Characterizing the computational power of anonymous mobile robots. In: Proceedings of 36th IEEE International ’l Conference on Distributed Computing Systems, (ICDCS), pp. 293-302. IEEE (2016)
[17] 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
[18] 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
[19] Dieudonné, Y., Labbani-Igbida, O., Petit, F.: Circle formation of weak mobile robots. TAAS 3(4), 16:1-16:20 (2008)
[20] Doan, H.T.T., Bonnet, F., Ogata, K.: Model checking of a mobile robots perpetual exploration algorithm. In: Proceedings of 6th International ’l Work on Structured Object-Oriented Formal Language and Method (SOFL+MSVL), Lecture Notes in Computer Science, vol. 10189, pp. 201-219 (2017) · Zbl 1461.68231
[21] Donald, B.R., Jennings, J.S., Rus, D.: Information invariants for distributed manipulation. I. J. Robotics Res. 16(5), 673-702 (1997)
[22] Flocchini, P., Prencipe, G., Santoro, N.: Distributed Computing by Oblivious Mobile Robots. Synthesis Lectures on Distributed Computing Theory. Morgan & Claypool Publishers, (2012) · Zbl 1286.68484
[23] Flocchini, P., Prencipe, G., Santoro, N., Viglietta, G.: Distributed computing by mobile robots: uniform circle formation. Distrib. Comput. 30, 413-457 (2017) · Zbl 1419.68029
[24] 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
[25] 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
[26] Fujinaga, N., Ono, H., Kijima, S., Yamashita, M.: Pattern formation through optimum matching by oblivious corda robots. In: Proceedings of 14th International ’l Conference on Principles of Distributed Systems (OPODIS), LNCS, vol. 6490, pp. 1-15. Springer (2010)
[27] Fujinaga, N., Yamauchi, Y., Kijima, S., Yamashita, M.: Asynchronous pattern formation by anonymous oblivious mobile robots. In: Proceedings of 26th International ’l Symposium on Distributed Computing (DISC), LNCS, vol. 7611, pp. 312-325. Springer (2012) · Zbl 1374.68584
[28] 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
[29] Ghike, S., Mukhopadhyaya, K.: A distributed algorithm for pattern formation by autonomous robots, with no agreement on coordinate compass. In: Proceedings of 6th International ’l Conference on Distributed Computing and Internet Technology, (ICDCIT), LNCS, vol. 5966, pp. 157-169. Springer (2010)
[30] Izumi, T., Katayama, Y., Inuzuka, N., Wada, K.: Gathering autonomous mobile robots with dynamic compasses: An optimal result. In: Proceedings of 21st International ’l Symposium on Distributed Computing (DISC), LNCS, vol. 4731, pp. 298-312. Springer (2007) · Zbl 1145.68549
[31] 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
[32] Mamino, M., Viglietta, G.: Square formation by asynchronous oblivious robots. In: Proceedings of the 28th Canadian Conference on Computational Geometry (CCCG), pp. 1-6 (2016)
[33] Millet, L., Potop-Butucaru, M., Sznajder, N., Tixeuil, S.: On the synthesis of mobile robots algorithms: The case of ring gathering. In: Proceedings of 16th International ’l Symposium on Stabilization, Safety, and Security of Distributed Systems (SSS), LNCS, vol. 8756, pp. 237-251. Springer (2014)
[34] Parker, L.E.: On the design of behavior-based multi-robot teams. Adv. Robot. 10(6), 547-578 (1995)
[35] Prencipe, G.: The effect of synchronicity on the behavior of autonomous mobile robot. Theory Comput. Syst. 38, 539-558 (2005) · Zbl 1086.68617
[36] Romanishin, J., Gilpin, K., Rus, D.: M-blocks: Momentum-driven, magnetic modular robots. In: Proceedings of IEEE/RSJ International ’l Conference on Intelligent Robots and Systems, pp. 4288-4295. IEEE (2013)
[37] Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: Formation of geometric patterns. SIAM J. Comput. 28(4), 1347-1363 (1999) · Zbl 0940.68145
[38] 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
[39] Yamauchi, Y., Uehara, T., Kijima, S., Yamashita, M.: Plane formation by synchronous mobile robots in the three dimensional euclidean space. In: Proceedings of 29th International ’l Symposium on Distributed Computing (DISC), LNCS, vol. 9363, pp. 92-106. Springer (2015) · Zbl 1394.68150
[40] Yamauchi, Y., Uehara, T., Yamashita, M.: Brief Announcement: Pattern formation problem for synchronous mobile robots in the three dimensional euclidean space. In: Proceedings of 35th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC) (2016) · Zbl 1374.68592
[41] Yamauchi, Y., Yamashita, M.: Randomized pattern formation algorithm for asynchronous oblivious mobile robots. In: Proceedings of 28th International ’l Symposium on Distributed Computing, (DISC), LNCS, vol. 8784, pp. 137-151. Springer (2014)
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.