Abstract
A finite automaton, simply referred to as a robot, has to explore a graph whose nodes are unlabeled and whose edge ports are locally labeled at each node. The robot has no a priori knowledge of the topology of the graph or of its size. Its task is to traverse all the edges of the graph. We first show that, for any K-state robot and any d≥ 3, there exists a planar graph of maximum degree d with at most K+1 nodes that the robot cannot explore. This bound improves all previous bounds in the literature. More interestingly, we show that, in order to explore all graphs of diameter D and maximum degree d, a robot needs Ω(Dlogd) memory bits, even if we restrict the exploration to planar graphs. This latter bound is tight. Indeed, a simple DFS at depth D+1 enables a robot to explore any graph of diameter D and maximum degree d using a memory of size O(Dlogd) bits. We thus prove that the worst case space complexity of graph exploration is Θ(Dlogd) bits.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Albers, S., Henzinger, M.R.: Exploring unknown environments. SIAM J. Computing 29, 1164–1188 (2000)
Antelmann, H., Budach, L., Rollik, H.A.: On universal traps. Elektronische Informationsverarbeitung und Kybernetic, EIK 15(3), 123–131 (1979)
Asser, G.: Bemerkungen zum Labyrinth-Problem. Elektronische Informationsverarbeitung und Kybernetic, EIK 13(4-5), 203–216 (1977)
Awerbuch, B., Betke, M., Rivest, R., Singh, M.: Piecemeal graph learning by a mobile robot. In: 8th Conf. on Comput. Learning Theory, pp. 321–328 (1995)
Bar-Eli, E., Berman, P., Fiat, A., Yan, R.: On-line navigation in a room. J. Algorithms 17, 319–341 (1994)
Bar-Noy, A., Borodin, A., Karchmer, M., Linial, N., Werman, M.: Bounds on universal sequences. SIAM J. Computing 18(2), 268–277 (1989)
Bender, M., Fernandez, A., Ron, D., Sahai, A., Vadhan, S.: The power of a pebble: Exploring and mapping directed graphs. In: 30th Ann. Symp. on Theory of Computing (STOC), pp. 269–278 (1998)
Bender, M., Slonim, D.: The power of team exploration: Two robots can learn unlabeled directed graphs. In: 35th Ann. Symp. on Foundations of Computer Science (FOCS), pp. 75–85 (1994)
Blum, A., Raghavan, P., Schieber, B.: Navigating in unfamiliar geometric terrain. SIAM J. Computing 26, 110–137 (1997)
Blum, M., Kozen, D.: On the power of the compass (or, why mazes are easier to search than graphs). In: 19th Symposium on Foundations of Computer Science (FOCS), pp. 132–142 (1978)
Blum, M., Sakoda, W.: On the capability of finite automata in 2 and 3 dimensional space. In: 18th Ann. Symp. on Foundations of Computer Science (FOCS), pp. 147–161 (1977)
Betke, M., Rivest, R., Singh, M.: Piecemeal learning of an unknown environment. Machine Learning 18, 231–254 (1995)
Budach, L.: On the solution of the labyrinth problem for finite automata. Elektronische Informationsverarbeitung und Kybernetic, EIK 11(10-12), 661–672 (1975)
Budach, L.: Environments, labyrinths and automata. In: Karpinski, M. (ed.) FCT 1977. LNCS, vol. 56, pp. 54–64. Springer, Heidelberg (1977)
Budach, L.: Automata and labyrinths. Math. Nachrichten, 195–282 (1978)
Coy, W.: Automata in labyrinths. In: Karpinski, M. (ed.) FCT 1977. LNCS, vol. 56, pp. 65–71. Springer, Heidelberg (1977)
Deng, X., Kameda, T., Papadimitriou, C.H.: How to learn an unknown environment I: the rectilinear case. J. ACM 45, 215–245 (1998)
Deng, X., Papadimitriou, C.H.: Exploring an unknown graph. J. Graph Theory 32, 265–297 (1999)
Diks, K., Fraigniaud, P., Kranakis, E., Pelc, A.: Tree Exploration with Little Memory. In: 13th Annual ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 588–597 (2002)
Döpp, K.: Automaten in Labyrinthen. Elektronische Informationsverarbeitung und Kybernetic, EIK 7(2), 79–94 & 7(3), 167–190 (1971)
Dudek, G., Jenkins, M., Milios, E., Wilkes, D.: Robotic Exploration as Graph Construction. IEEE Transaction on Robotics and Automation 7(6), 859–865 (1991)
Duncan, C., Kobourov, S., Kumar, V.: Optimal constrained graph exploration. In: 12th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), pp. 807–814 (2001)
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)
Fraigniaud, P., Ilcinkas, D.: Directed Graphs Exploration with Little Memory. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol. 2996, pp. 246–257. Springer, Heidelberg (2004)
Hemmerling, A.: Labyrinth Problems: Labyrinth-Searching Abilities of Automata. Teubner-Texte zur Mathematik, vol. 114. B. G. Teubner Verlagsgesellschaft, Leipzig (1989)
Hoffmann, F.: One pebble does not suffice to search plane labyrinths. In: Gecseg, F. (ed.) FCT 1981. LNCS, vol. 117, pp. 433–444. Springer, Heidelberg (1981)
Kozen, D.: Automata and planar graphs. Fund. Computat. Theory (FCT), 243–254 (1979)
López-Ortiz, A., Schuierer, S.: On-line parallel heuristics and robot searching under the competitive framework. In: 8th Scandinavian Workshop on Algorithm Theory, SWAT (2002)
Müller, H.: Endliche Automaten und Labyrinthe. Elektronische Informationsverarbeitung und Kybernetic, EIK 7/4, 261–264 (1971)
Müller, H.: Automata catching labyrinths with at most three components. Elektronische Informationsverarbeitung und Kybernetic, EIK 15(1-2), 3–9 (1979)
Panaite, P., Pelc, A.: Exploring unknown undirected graphs. J. Algorithms 33, 281–295 (1999)
Rabin, M.O.: Maze threading automata. Seminar talk presented at the University of California at Berkeley (October 1967)
Rao, N., Kareti, S., Shi, W., Iyengar, S.: Robot navigation in unknown terrains: Introductory survey of length,non-heuristic algorithms. Tech. Report ORNL/TM-12410, Oak Ridge National Lab. (1993)
Rollik, H.A.: Automaten in planaren Graphen. OPAALS 2010 13, 287–298 (1980), also in LNCS 67, pp. 266–275 (1979)
Shannon, C.E.: Presentation of a maze-solving machine. In: 8th Conf. of the Josiah Macy Jr. Found (Cybernetics), pp. 173–180 (1951)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., Peleg, D. (2004). Graph Exploration by a Finite Automaton. In: Fiala, J., Koubek, V., Kratochvíl, J. (eds) Mathematical Foundations of Computer Science 2004. MFCS 2004. Lecture Notes in Computer Science, vol 3153. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-28629-5_34
Download citation
DOI: https://doi.org/10.1007/978-3-540-28629-5_34
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22823-3
Online ISBN: 978-3-540-28629-5
eBook Packages: Springer Book Archive