Abstract
We consider the task of exploring graphs with anonymous nodes by a team of non-cooperative robots modeled as finite automata. These robots have no a priori knowledge of the topology of the graph, or of its size. Each edge has to be traversed by at least one robot. We first show that, for any set of q non-cooperative K-state robots, there exists a graph of size O(qK) that no robot of this set can explore. This improves the O(K O(q)) bound by Rollik (1980). Our main result is an application of this improvement. It concerns exploration with stop, in which one robot has to explore and stop after completing exploration. For this task, the robot is provided with a pebble, that it can use to mark nodes. We prove that exploration with stop requires Ω(log n) bits for the family of graphs with at most n nodes. On the other hand, we prove that there exists an exploration with stop algorithm using a robot with O(D log Δ) bits of memory to explore all graphs of diameter at most D and degree at most Δ.
This work has been supported by the projects: INRIA “Grand Large”, “PairAPair” of the ACI “Masses de Données”, “FRAGILE” of the ACI “Sécurité et Informatique,” LAFMI (Franco-Mexican lab in Computer Science), and PAPIIT-UNAM.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Bender, M., Fernandez, A., Ron, D., Sahai, A., Vadhan, S.: The power of a pebble: Exploring and mapping directed graphs. Information and Computation 176, 1–21 (2002); Prel. Version in STOC 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)
Budach, L.: Automata and labyrinths. Math. Nachrichten, 195–282 (1978)
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)
Dudek, G., Jenkins, M., Milios, E., Wilkes, D.: Robotic Exploration as Graph Construction. IEEE Transaction on Robotics and Automation 7(6), 859–865 (1991)
Fraigniaud, P., Ilcinkas, D., Peer, G., Pelc, A., Peleg, D.: Graph Exploration by a Finite Automaton. In: Fiala, J., Koubek, V., Kratochvíl, J. (eds.) MFCS 2004. LNCS, vol. 3153, pp. 451–462. Springer, Heidelberg (2004)
Rollik, H.-A.: Automaten in planaren graphen. Acta Informatica 13, 287–298 (1980)
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
© 2005 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Fraigniaud, P., Ilcinkas, D., Rajsbaum, S., Tixeuil, S. (2005). Space Lower Bounds for Graph Exploration via Reduced Automata. In: Pelc, A., Raynal, M. (eds) Structural Information and Communication Complexity. SIROCCO 2005. Lecture Notes in Computer Science, vol 3499. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11429647_13
Download citation
DOI: https://doi.org/10.1007/11429647_13
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-26052-3
Online ISBN: 978-3-540-32073-9
eBook Packages: Computer ScienceComputer Science (R0)Springer Nature Proceedings Computer Science