nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Dispersion of Mobile Robots: The Power of Randomness

verfasst von : Anisur Rahaman Molla, William K. Moses Jr.

Erschienen in: Theory and Applications of Models of Computation

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

We consider cooperation among insects, modeled as cooperation between mobile robots on a graph. Within this setting, we consider the problem of mobile robot dispersion on graphs. The study of mobile robots on a graph is an interesting paradigm with many interesting problems and applications. The problem of dispersion in this context, introduced by Augustine and Moses Jr. [4], asks that n robots, initially placed arbitrarily on an n node graph, work together to quickly reach a configuration with exactly one robot at each node. Previous work on this problem has looked at the trade-off between the time to achieve dispersion and the amount of memory required by each robot. However, the trade-off was analyzed for deterministic algorithms and the minimum memory required to achieve dispersion was found to be \(\varOmega (\log n)\) bits at each robot. In this paper, we show that by harnessing the power of randomness, one can achieve dispersion with \(O(\log \varDelta )\) bits of memory at each robot, where \(\varDelta \) is the maximum degree of the graph. Further, we show a matching lower bound of \(\varOmega (\log \varDelta )\) bits for any randomized algorithm to solve dispersion. We further extend the problem to a general k-dispersion problem where \(k> n\) robots need to disperse over n nodes such that at most \(\lceil k/n \rceil \) robots are at each node in the final configuration.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

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!

Jetzt informieren

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!

Jetzt informieren

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!

Jetzt informieren

Vorheriges Kapitel Watson-Crick Jumping Finite Automata

Nächstes Kapitel Building Resource Auto-scaler with Functional-Link Neural Network and Adaptive Bacterial Foraging Optimization

Note that all \(\log \)’s that appear in this paper are to the base 2.

Notice that our algorithms require only O(1) bits memory at each robot on paths, rings, grids and any constant degree graphs, whereas the previous deterministic algorithms require \(O(\log n)\) bits.

The robot’s memory restricts it to only use a subset of the available ports when determining which port to move through. Importantly, the robot does not know that there are more ports than it is seeing. Thus it cannot purposely choose which subset of ports to see. We call this lack of control “by nature”.

This does not necessarily give a \(\varOmega (\log \varDelta )\) memory lower bound for dispersion. We discuss this further in the lower bound section (Sect. 9).

This can be considered a realistic assumption when the time taken for a robot to move through an edge is significantly more than the time taken for either local message exchange or local computation.

It is possible for the robot at u to differentiate x from just another robot executing phase one of the DFS because x has changed its status to reflect that the second phase has begun.

It is required that Local-Leader-Election works without issue in that setting. This is the case.

Since ports are ordered, each robot can determine which port is last in the order. Furthermore, this ordering is unique to each node, so different robots will see the same ordering at each node.

For 3 sets of phases a, b, and c, sequence is: phase one of a, phase one of b, phase two of a, phase one of c, phase two of b, phase two of c. This sequence can be easily seen now for more sets.

Aldous, D.J.: Lower bounds for covering times for reversible Markov chains and random walks on graphs. J. Theor. Probab. 2(1), 91–100 (1989)MathSciNetMATH

Aleliunas, R., Karp, R.M., Lipton, R.J., Lovász, L., Rackoff, C.: Random walks, universal traversal sequences, and the complexity of maze problems. In: Proceedings of the 20th Annual Symposium on Foundations of Computer Science (FOCS), pp. 218–223 (1979)

Ambühl, C., Gąsieniec, L., Pelc, A., Radzik, T., Zhang, X.: Tree exploration with logarithmic memory. ACM Trans. Algorithms (TALG) 7(2), 17 (2011)MathSciNetMATH

Augustine, J., Moses Jr., W.K.: Dispersion of mobile robots: a study of memory-time trade-offs. In: Proceedings of the 19th International Conference on Distributed Computing and Networking, ICDCN 2018, Varanasi, India, 4–7 January 2018, pp. 1:1–1:10. ACM (2018)

Augustine, J., Moses Jr., W.K.: Dispersion of mobile robots: a study of memory-time trade-offs. CoRR abs/1707.05629 (v4) (2018). arxiv.org/abs/1707.05629

Baldoni, R., Bonnet, F., Milani, A., Raynal, M.: On the solvability of anonymous partial grids exploration by mobile robots. In: Baker, T.P., Bui, A., Tixeuil, S. (eds.) OPODIS 2008. LNCS, vol. 5401, pp. 428–445. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-92221-6_27

Barriere, L., Flocchini, P., Mesa-Barrameda, E., Santoro, N.: Uniform scattering of autonomous mobile robots in a grid. Int. J. Found. Comput. Sci. 22(03), 679–697 (2011)MathSciNetMATH

Bodlaender, H.L., van Leeuwen, J.: Distribution of Records on a Ring of Processors. Department of Computer Science, University of Utrecht (1986)

Brass, P., Cabrera-Mora, F., Gasparri, A., Xiao, J.: Multirobot tree and graph exploration. IEEE Trans. Rob. 27(4), 707–717 (2011)

10.

Brass, P., Vigan, I., Xu, N.: Improved analysis of a multirobot graph exploration strategy. In: 2014 13th International Conference on Control Automation Robotics & Vision (ICARCV), pp. 1906–1910. IEEE (2014)

11.

Broder, A.Z., Karlin, A.R.: Bounds on the cover time. J. Theor. Probab. 2(1), 101–120 (1989)MathSciNetMATH

12.

Cohen, R., Fraigniaud, P., Ilcinkas, D., Korman, A., Peleg, D.: Label-guided graph exploration by a finite automaton. ACM Trans. Algorithms (TALG) 4(4), 42 (2008)MathSciNetMATH

13.

Cybenko, G.: Dynamic load balancing for distributed memory multiprocessors. J. Parallel Distrib. Comput. 7(2), 279–301 (1989)

14.

Datta, A.K., Lamani, A., Larmore, L.L., Petit, F.: Enabling ring exploration with myopic oblivious robots. In: Parallel and Distributed Processing Symposium Workshop (IPDPSW), pp. 490–499. IEEE (2015)

15.

Dereniowski, D., Disser, Y., Kosowski, A., Pająk, D., Uznański, P.: Fast collaborative graph exploration. Inf. Comput. 243, 37–49 (2015)MathSciNetMATH

16.

Devismes, S., Lamani, A., Petit, F., Raymond, P., Tixeuil, S.: Optimal grid exploration by asynchronous oblivious robots. In: Richa, A.W., Scheideler, C. (eds.) SSS 2012. LNCS, vol. 7596, pp. 64–76. Springer, Heidelberg (2012). https://doi.org/10.1007/978-3-642-33536-5_7

17.

Diks, K., Fraigniaud, P., Kranakis, E., Pelc, A.: Tree exploration with little memory. In: Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 588–597. Society for Industrial and Applied Mathematics (2002)

18.

Dynia, M., Kutyłowski, J., auf der Heide, F.M., Schindelhauer, C.: Smart robot teams exploring sparse trees. In: Královič, R., Urzyczyn, P. (eds.) MFCS 2006. LNCS, vol. 4162, pp. 327–338. Springer, Heidelberg (2006). https://doi.org/10.1007/11821069_29

19.

Elor, Y., Bruckstein, A.M.: Uniform multi-agent deployment on a ring. Theor. Comput. Sci. 412(8–10), 783–795 (2011)MathSciNetMATH

20.

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

21.

Kshemkalyani, A.D., Ali, F.: Efficient dispersion of mobile robots on graphs. arXiv preprint arXiv:1805.12242 (2018)

22.

Lamani, A., Potop-Butucaru, M.G., Tixeuil, S.: Optimal deterministic ring exploration with oblivious asynchronous robots. In: Patt-Shamir, B., Ekim, T. (eds.) SIROCCO 2010. LNCS, vol. 6058, pp. 183–196. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13284-1_15

23.

Lovász, L.: Random walks on graphs: a survey. In: Combinatorics, Paul Erdős is Eighty, vol. 2, pp. 1–46 (1993)

24.

Muthukrishnan, S., Ghosh, B., Schultz, M.H.: First-and second-order diffusive methods for rapid, coarse, distributed load balancing. Theor. Comput. Syst. 31(4), 331–354 (1998)MathSciNetMATH

25.

Ortolf, C., Schindelhauer, C.: A recursive approach to multi-robot exploration of trees. In: Halldórsson, M.M. (ed.) SIROCCO 2014. LNCS, vol. 8576, pp. 343–354. Springer, Cham (2014). https://doi.org/10.1007/978-3-319-09620-9_26

26.

Peleg, D., Van Gelder, A.: Packet distribution on a ring. J. Parallel Distrib. Comput. 6(3), 558–567 (1989)

27.

Reingold, O.: Undirected connectivity in log-space. J. ACM 55(4), 17:1–17:24 (2008)MathSciNetMATH

28.

Shibata, M., Mega, T., Ooshita, F., Kakugawa, H., Masuzawa, T.: Uniform deployment of mobile agents in asynchronous rings. In: Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing, pp. 415–424. ACM (2016)

29.

Subramanian, R., Scherson, I.D.: An analysis of diffusive load-balancing. In: Proceedings of the Sixth Annual ACM Symposium on Parallel Algorithms and Architectures, pp. 220–225. ACM (1994)

Titel: Dispersion of Mobile Robots: The Power of Randomness
verfasst von: Anisur Rahaman Molla
William K. Moses Jr.
Verlag: Springer International Publishing
Buch: Theory and Applications of Models of Computation
Print ISBN: 978-3-030-14811-9

Electronic ISBN: 978-3-030-14812-6

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-14812-6_30

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner