×

Computing without communicating: ring exploration by asynchronous oblivious robots. (English) Zbl 1272.68399

Summary: We consider the problem of exploring an anonymous unoriented ring by a team of \(k\) identical, oblivious, asynchronous mobile robots that can view the environment but cannot communicate. This weak scenario is standard when the spatial universe in which the robots operate is the two-dimensional plane, but (with one exception) has not been investigated before for networks. Our results imply that, although these weak capabilities of robots render the problem considerably more difficult, ring exploration by a small team of robots is still possible.{ }We first show that, when \(k\) and \(n\) are not co-prime, the problem is not solvable in general, e.g., if \(k\) divides \(n\) there are initial placements of the robots for which gathering is impossible. We then prove that the problem is always solvable provided that \(n\) and \(k\) are co-prime, for \(k \geq 17\), by giving an exploration algorithm that always terminates, starting from arbitrary initial configurations. Finally, we consider the minimum number \(\rho(n)\) of robots that can explore a ring of size \(n\). As a consequence of our positive result we show that \(\rho(n)\) is \(O(\log n)\). We additionally prove that \(\Omega(\log n)\) robots are necessary for infinitely many \(n\).

MSC:

68T40 Artificial intelligence for robotics
68Q25 Analysis of algorithms and problem complexity

References:

[1] 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
[2] Albers, S., Henzinger, M.R.: Exploring unknown environments. SIAM J. Comput. 29, 1164–1188 (2000) · Zbl 0947.68165 · doi:10.1137/S009753979732428X
[3] Ambühl, C., Gasieniec, L., Pelc, A., Radzik, T., Zhang, X.: Tree exploration with logarithmic memory. ACM Trans. Algorithms 7, article 17 (2011) · Zbl 1295.68203 · doi:10.1145/1921659.1921663
[4] Averbakh, I., Berman, O.: A heuristic with worst-case analysis for minimax routing of two traveling salesmen on a tree. Discrete Appl. Math. 68, 17–32 (1996) · Zbl 0848.90117 · doi:10.1016/0166-218X(95)00054-U
[5] Averbakh, I., Berman, O.: (p)/(p+1)-approximate algorithms for p-traveling salesmen problems on a tree with minmax objective. Discrete Appl. Math. 75, 201–216 (1997) · Zbl 0879.68077 · doi:10.1016/S0166-218X(97)89161-5
[6] Awerbuch, B., Betke, M., Rivest, R., Singh, M.: Piecemeal graph learning by a mobile robot. In: Proceedings of the 8th Annual Conference on Computational Learning Theory (COLT 1995), pp. 321–328 (1995) · Zbl 1045.68611
[7] Bender, M.A., Fernandez, A., Ron, D., Sahai, A., Vadhan, S.: The power of a pebble: exploring and mapping directed graphs. In: Proceedings of the 30th Annual ACM Symposium on the Theory of Computing (STOC 1998), pp. 269–278 (1998) · Zbl 1027.68652
[8] Bender, M.A., Slonim, D.: The power of team exploration: Two robots can learn unlabeled directed graphs. In: Proceedings of the 35th Annual Symposium on Foundations of Computer Science (FOCS 1994), pp. 75–85 (1994)
[9] Betke, M., Rivest, R., Singh, M.: Piecemeal learning of an unknown environment. Mach. Learn. 18, 231–254 (1995)
[10] Chalopin, J., Flocchini, P., Mans, B., Santoro, N.: Network exploration by silent and oblivious robots. In: Proceedings of the 36th Int. Workshop on Graph Theoretic Concepts in Computer Science (WG 2010). LNCS, vol. 6410, pp. 208–219. Springer, Berlin (2010) · Zbl 1309.68148
[11] Cieliebak, M., Flocchini, P., Prencipe, G., Santoro, N.: Solving the robots gathering problem. In: Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP 2003). LNCS, vol. 2719, pp. 1181–1196. Springer, Berlin (2003) · Zbl 1039.68129
[12] Cohen, R., Peleg, D.: Convergence properties of the gravitational algorithm in asynchronous robot systems. SIAM J. Comput. 34, 1516–1528 (2005) · Zbl 1081.68110 · doi:10.1137/S0097539704446475
[13] Cohen, R., Peleg, D.: Robot convergence via center-of-gravity algorithms. In: Proceedings of the 11th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2004). LNCS, vol. 3104, pp. 79–88. Springer, Berlin (2004) · Zbl 1085.68697
[14] Cooper, C., Klasing, R., Radzik, T.: Searching for black-hole faults in a network using multiple agents. In: Proceedings of the 10th International Conference on Principles of Distributed Systems (OPODIS 2006). LNCS, vol. 4288, pp. 320–332. Springer, Berlin (2006)
[15] Czyzowicz, J., Gasieniec, L., Pelc, A.: Gathering few fat mobile robots in the plane. Theor. Comput. Sci. 410, 481–499 (2009) · Zbl 1157.68065 · doi:10.1016/j.tcs.2008.10.005
[16] Czyzowicz, J., Kowalski, D., Markou, E., Pelc, A.: Searching for a black hole in synchronous tree networks. Comb. Probab. Comput. 16, 595–619 (2007) · Zbl 1130.68029 · doi:10.1017/S0963548306008133
[17] Das, S., Flocchini, P., Kutten, S., Nayak, A., Santoro, N.: Map construction of unknown graphs by multiple agents. Theor. Comput. Sci. 385, 34–48 (2007) · Zbl 1124.68078 · doi:10.1016/j.tcs.2007.05.011
[18] Défago, X., Souissi, S.: Non-uniform circle formation algorithm for oblivious mobile robots with convergence toward uniformity. Theor. Comput. Sci. 396, 97–112 (2008) · Zbl 1146.68462 · doi:10.1016/j.tcs.2008.01.050
[19] Deng, X., Papadimitriou, C.H.: Exploring an unknown graph. J. Graph Theory 32, 265–297 (1999) · Zbl 0941.68099 · doi:10.1002/(SICI)1097-0118(199911)32:3<265::AID-JGT6>3.0.CO;2-8
[20] Dessmark, A., Pelc, A.: Optimal graph exploration without good maps. Theor. Comput. Sci. 326, 343–362 (2004) · Zbl 1071.68081 · doi:10.1016/j.tcs.2004.07.031
[21] Devismes, S.: Optimal exploration of small rings. In: Proceedings of the 3rd International ACM SIGOPS/SIGACT Workshop on Reliability, Availability, and Security (WRAS 2010), pp. 9:1–9:6 (2010)
[22] Devismes, S., Petit, F., Tixeuil, S.: Optimal probabilistic ring exploration by semi-synchronous oblivious robots. In: Proceedings of the 16th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2009). LNCS, vol. 5869, pp. 195–208. Springer, Berlin (2009) · Zbl 1274.68566
[23] Diks, K., Fraigniaud, P., Kranakis, E., Pelc, A.: Tree exploration with little memory. J. Algorithms 51, 38–63 (2004) · Zbl 1067.68100 · doi:10.1016/j.jalgor.2003.10.002
[24] Duncan, C.A., Kobourov, S.G., Kumar, V.S.A.: Optimal constrained graph exploration. In: Proceedings of the 12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), pp. 807–814 (2001) · Zbl 0992.68160
[25] Fleischer, R., Trippen, G.: Exploring an unknown graph efficiently. In: Proceedings of the 13th European Symposium on Algorithms (ESA 2005). LNCS, vol. 3669, pp. 11–22. Springer, Berlin (2005) · Zbl 1162.68493
[26] Flocchini, P., Ilcinkas, D., Pelc, A., Santoro, N.: Remembering without memory: tree exploration by asynchronous oblivious robots. Theor. Comput. Sci. 411, 1544–1557 (2010) · Zbl 1191.68712 · doi:10.1016/j.tcs.2010.01.007
[27] Flocchini, P., Ilcinkas, D., Pelc, A., Santoro, N.: Computing without communicating: ring exploration by asynchronous oblivious robots. In: Proceedings of the 11th International Conference on Principles of Distributed Systems (OPODIS 2007). LNCS, vol. 4878, pp. 105–118. Springer, Berlin (2007) · Zbl 1272.68399
[28] Flocchini, P., Ilcinkas, D., Santoro, N.: Ping-Pong in dangerous graphs: Optimal black hole search with pure tokens. Algorithmica (2011, in press) · Zbl 1161.68335
[29] Flocchini, P., Prencipe, G., Santoro, N.: Computing by mobile robotic sensors. Chap. 3 of [37] (2011) · Zbl 1218.68047
[30] Flocchini, P., Prencipe, G., Santoro, N., Widmayer, P.: Arbitrary pattern formation by asynchronous, anonymous, oblivious robots. Theor. Comput. Sci. 407, 412–447 (2008) · Zbl 1152.68053 · doi:10.1016/j.tcs.2008.07.026
[31] Fraigniaud, P., Gasieniec, L., Kowalski, D., Pelc, A.: Collective tree exploration. Networks 48, 166–177 (2006) · Zbl 1107.68065 · doi:10.1002/net.20127
[32] Frederickson, G.N., Hecht, M.S., Kim, C.E.: Approximation algorithms for some routing problems. SIAM J. Comput. 7, 178–193 (1978) · doi:10.1137/0207017
[33] Kamei, S., Lamani, A., Ooshita, F., Tixeuil, S.: Asynchronous mobile robot gathering from symmetric configurations without global multiplicity detection. In: Proceedings of the 18th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2011). LNCS, vol. 6796, pp. 150–161. Springer, Berlin (2011)
[34] 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 · doi:10.1016/j.tcs.2010.05.020
[35] Klasing, R., Markou, E., Pelc, A.: Gathering asynchronous oblivious mobile robots in a ring. Theor. Comput. Sci. 390, 27–39 (2008) · Zbl 1134.68013 · doi:10.1016/j.tcs.2007.09.032
[36] Lamani, A., Gradinariu Potop-Butucaru, M., Tixeuil, S.: Optimal deterministic ring exploration with oblivious asynchronous robots. In: Proceedings of the 17th International Colloquium on Structural Information and Communication Complexity (SIROCCO 2010). LNCS, vol. 6058, pp. 183–196. Springer, Berlin (2010) · Zbl 1284.68563
[37] Nikoletseas, S., Rolim, J. (eds.): Theoretical Aspects of Distributed Computing in Sensor Networks. Springer, Berlin (2011) · Zbl 1207.68013
[38] Panaite, P., Pelc, A.: Exploring unknown undirected graphs. J. Algorithms 33, 281–295 (1999) · Zbl 0957.68092 · doi:10.1006/jagm.1999.1043
[39] Prencipe, G.: Impossibility of gathering by a set of autonomous mobile robots. Theor. Comput. Sci. 384, 222–231 (2007) · Zbl 1125.68124 · doi:10.1016/j.tcs.2007.04.023
[40] Ruiz, S.M.: A result on prime numbers. Math. Gaz. 81, 269 (1997) · doi:10.2307/3619207
[41] Souissi, S., Défago, X., Yamashita, M.: Gathering asynchronous mobile robots with inaccurate compasses. In: Proceedings of the 10th International Conference on Principles of Distributed Systems (OPODIS 2006). LNCS, vol. 4305, pp. 333–349. Springer, Berlin (2006)
[42] Suzuki, I., Yamashita, M.: Distributed anonymous mobile robots: formation of geometric patterns. SIAM J. Comput. 28, 1347–1363 (1999) · Zbl 0940.68145 · doi:10.1137/S009753979628292X
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.