Top

Published in:

2020 | OriginalPaper | Chapter

Live Exploration with Mobile Robots in a Dynamic Ring, Revisited

Authors : Subhrangsu Mandal, Anisur Rahaman Molla, William K. Moses Jr.

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

The graph exploration problem requires a group of mobile robots, initially placed arbitrarily on the nodes of a graph, to work collaboratively to explore the graph such that each node is eventually visited by at least one robot. One important requirement of exploration is the termination condition, i.e., the robots must know that exploration is completed. The problem of live exploration of a dynamic ring using mobile robots was recently introduced in [Di Luna et al., ICDCS 2016]. In it, they proposed multiple algorithms to solve exploration in fully synchronous and semi-synchronous settings with various guarantees when 2 robots were involved. They also provided guarantees that with certain assumptions, exploration of the ring using two robots was impossible. An important question left open was how the presence of 3 robots would affect the results. In this paper, we try to settle this question in a fully synchronous setting and also show how to extend our results to a semi-synchronous setting.

In particular, we present algorithms for exploration with explicit termination using 3 robots in conjunction with either (i) unique IDs of the robots and edge crossing detection capability (i.e., two robots moving in opposite directions through an edge in the same round can detect each other), or (ii) access to randomness. The time complexity of our deterministic algorithm is asymptotically optimal. We also provide complementary impossibility results showing that there do not exist any explicit termination algorithms for 2 robots even when each robot has a unique ID, edge crossing detection capability, and access to randomness. We also present an algorithm to achieve exploration with partial termination using 3 robots with unique IDs in the semi-synchronous setting.

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 On Efficient Connectivity-Preserving Transformations in a Grid

next chapter Asynchronous Filling by Myopic Luminous Robots

Here by ‘sense’ we mean the two robots can detect the edge crossing and can exchange information including IDs.

The third robot gets named C only after it meets either A or B at the end of Stage 2.

Note that even if A and C do not have shared chirality, the direction of B can be conveyed as follows. Depending on how A and C meet, C will immediately know the direction A moves in or can take a round or two to understand this based on how A and C both move in their “clockwise” direction and see if they moved to the same node or not. Once C determines the naming mechanism A uses for directions, C can understand exactly which direction B is moving in.

The expectation is easy to see. The high probability bound can be seen by applying a simple Chernoff bound.

The high probability is a result of the use of Random-Movement.

It is possible that A and B may have crossed each other several times before the adversary blocks them at adjacent nodes and the latter case occurs. In this case, C and the robot it finally interacts with will know an upper bound on n. Note that if A and B cross each other at least twice, then on expectation they will meet, leading to the former case.

Since the number of robots 3 is given to the robots, they can use it to set a value for l, e.g., \(l=2^3+12 =20\).

Agarwalla, A., Augustine, J., Moses Jr., W.K., Sankar, K.M., Sridhar, A.K.: Deterministic dispersion of mobile robots in dynamic rings. In: International Conference on Distributed Computing and Networking, ICDCN, pp. 19:1–19:4. ACM (2018)

Albers, S., Henzinger, M.R.: Exploring unknown environments. SIAM J. Comput. 29(4), 1164–1188 (2000)MathSciNetCrossRef

Das, S.: Graph explorations with mobile agents. In: Flocchini, P., Prencipe, G., Santoro, N. (eds.) Distributed Computing by Mobile Entities. Lecture Notes in Computer Science, vol. 11340, pp. 403–422. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-11072-7_16

Deng, X., Papadimitriou, C.H.: Exploring an unknown graph. J. Graph Theory 32(3), 265–297 (1999)MathSciNetCrossRef

Di Luna, G.A.: Mobile agents on dynamic graphs. In: Flocchini, P., Prencipe, G., Santoro, N. (eds.) Distributed Computing by Mobile Entities. Lecture Notes in Computer Science, vol. 11340, pp. 549–584. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-11072-7_20

Di Luna, G.A., Dobrev, S., Flocchini, P., Santoro, N.: Live exploration of dynamic rings. In: International Conference on Distributed Computing Systems, ICDCS, pp. 570–579. IEEE (2016)

Di Luna, G.A., Flocchini, P., Pagli, L., Prencipe, G., Santoro, N., Viglietta, G.: Gathering in dynamic rings. Theoret. Comput. Sci. 811, 79–98 (2020)MathSciNetCrossRef

Dieudonné, Y., Pelc, A.: Deterministic network exploration by anonymous silent agents with local traffic reports. ACM Trans. Algorithms 11(2), 10:1–10:29 (2014)MathSciNetCrossRef

Erlebach, T., Hoffmann, M., Kammer, F.: On temporal graph exploration. In: Halldórsson, M., Iwama, K., Kobayashi, N., Speckmann, B. (eds.) Automata, Languages, and Programming. ICALP 2015. Lecture Notes in Computer Science, vol. 9134, pp. 444–455. Springer, Heidelberg (2015) . https://doi.org/10.1007/978-3-662-47672-7_36

10.

Flocchini, P., Mans, B., Santoro, N.: On the exploration of time-varying networks. Theoret. Comput. Sci. 469, 53–68 (2013)MathSciNetCrossRef

11.

Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., Peleg, D.: Graph exploration by a finite automaton. Theoret. Comput. Sci. 345(2–3), 331–344 (2005)MathSciNetCrossRef

12.

Gotoh, T., Flocchini, P., Masuzawa, T., Santoro, N.: Tight bounds on distributed exploration of temporal graphs. In: International Conference on Principles of Distributed Systems, OPODIS (2019)

13.

Ilcinkas, D., Klasing, R., Wade, A.M.: Exploration of constantly connected dynamic graphs based on cactuses. In: Halldórsson, M.M. (ed.) SIROCCO 2014. LNCS, vol. 8576, pp. 250–262. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-09620-9_20CrossRef

14.

Ilcinkas, D., Wade, A.M.: On the power of waiting when exploring public transportation systems. In: Fernàndez Anta, A., Lipari, G., Roy, M. (eds.) OPODIS 2011. LNCS, vol. 7109, pp. 451–464. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-25873-2_31CrossRef

15.

Ilcinkas, D., Wade, A.M.: Exploration of the T-interval-connected dynamic graphs: the case of the ring. In: Moscibroda, T., Rescigno, A.A. (eds.) SIROCCO 2013. LNCS, vol. 8179, pp. 13–23. Springer, Cham (2013). https://doi.org/10.1007/978-3-319-03578-9_2CrossRef

16.

Kuhn, F., Lynch, N., Oshman, R.: Distributed computation in dynamic networks. In: ACM symposium on Theory of computing, STOC, pp. 513–522. ACM (2010)

17.

Kuhn, F., Oshman, R.: Dynamic networks: models and algorithms. SIGACT News 42(1), 82–96 (2011)CrossRef

18.

Mandal, S., Molla, A.R., Moses Jr., W.K.: Live exploration with mobile robots in a dynamic ring, revisited. arXiv preprint arXiv:2001.04525 (2020)

19.

Michail, O., Spirakis, P.G.: Traveling salesman problems in temporal graphs. Theoret. Comput. Sci. 634, 1–23 (2016)MathSciNetCrossRef

20.

O’Dell, R., Wattenhofer, R.: Information dissemination in highly dynamic graphs. In: Joint Workshop on Foundations of Mobile Computing, DIALM-POMC, pp. 104–110. ACM (2005)

21.

Panaite, P., Pelc, A.: Exploring unknown undirected graphs. J. Algorithms 33(2), 281–295 (1999)MathSciNetCrossRef

Title: Live Exploration with Mobile Robots in a Dynamic Ring, Revisited
Authors: Subhrangsu Mandal
Anisur Rahaman Molla
William K. Moses Jr.
Publisher: Springer International Publishing
Book: Algorithms for Sensor Systems
Print ISBN: 978-3-030-62400-2

Electronic ISBN: 978-3-030-62401-9

Copyright Year: 2020
DOI: https://doi.org/10.1007/978-3-030-62401-9_7

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