Abstract
An n-node tree has to be explored by a group of k mobile robots deployed initially at the root. Robots traverse the edges of the tree until all nodes are visited. We would like to minimize maximal distance traveled by each robot (e.g. to preserve the battery power). First, we assume that a tree is known in advance. For this NP-hard problem we present a 2-approximation. Moreover, we present an optimal algorithm for a case where k is constant.
From the 2-approximation algorithm we develop a fast 8-competitive online algorithm, which does not require a previous knowledge of the tree and collects information during the exploration. Furthermore, our online algorithm is distributed and uses only a local communication. We show a lower bound of 1.5 for the competitive ratio of any deterministic online algorithm.
This research is partially supported by the DFG-Sonderforschungsbereich SPP 1183: “Organic Computing. Smart Teams: Local, Distributed Strategies for Self-Organizing Robotic Exploration Teams”.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Borodin, A., El-Yaniv, R.: Online computation and competitive analysis. Cambridge University Press, New York (1998)
Fraigniaud, P., Gasieniec, L., Kowalski, D., Pelc, A.: Collective tree exploration. In: Farach-Colton, M. (ed.) LATIN 2004. LNCS, vol. 2976, pp. 141–151. Springer, Heidelberg (2004)
Rao, N., Kareti, S., Shi, W., Iyenagar, S.: Robot navigation in unknown terrains: Introductory survey of non-heuristic algorithms. Technical report (1993)
Bender, M., Fernández, A., Ron, D., Sahai, A., Vadhan, S.: The power of a pebble: exploring and mapping directed graphs. In: Proc. 30th Symp. Theory of Computing, pp. 269–278. ACM, New York (1998)
Awerbuch, B., Betke, M., Rivest, R., Singh, M.: Piecemeal graph exploration by a mobile robot. Information and Computation 152(2), 155–172 (1999)
Dessmark, A., Pelc, A.: Optimal graph exploration without good maps. In: Möhring, R.H., Raman, R. (eds.) ESA 2002. LNCS, vol. 2461, p. 374. Springer, Heidelberg (2002)
Panaite, P., Pelc, A.: Exploring unknown undirected graphs. In: SODA 1998. Proceedings of the ninth annual ACM-SIAM symposium on Discrete algorithms, Philadelphia, PA, USA, Society for Industrial and Applied Mathematics, pp. 316–322 (1998)
Bender, M., Slonim, D.: The power of team exploration: two robots can learn unlabeleddirected graphs. In: Proc. FOCS 1994, pp. 75–85 (1994)
Averbakh, I., Berman, O.: (p - 1)/(p + 1)-approximate algorithms for p-traveling salesmen problems on a tree with minmax objective. Discrete Applied Mathematics 75(3), 201–216 (1997)
Nagamochi, H., Okada, K.: A faster 2-approximation algorithm for the minmax p-traveling salesmen problem on a tree. Discrete Applied Mathematics 140(1-3), 103–114 (2004)
Averbakh, I., Berman, O.: A heuristic with worst-case analysis for minimax routing of two traveling salesmen on a tree. Discrete Applied Mathematics 68, 17–32 (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Dynia, M., Korzeniowski, M., Schindelhauer, C. (2006). Power-Aware Collective Tree Exploration. In: Grass, W., Sick, B., Waldschmidt, K. (eds) Architecture of Computing Systems - ARCS 2006. ARCS 2006. Lecture Notes in Computer Science, vol 3894. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11682127_24
Download citation
DOI: https://doi.org/10.1007/11682127_24
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-32765-3
Online ISBN: 978-3-540-32766-0
eBook Packages: Computer ScienceComputer Science (R0)