Abstract
We study the problem of mapping an unknown environment represented as an unlabelled undirected graph. A robot (or automaton) starting at a single vertex of the graph G has to traverse the graph and return to its starting point building a map of the graph in the process. We are interested in the cost of achieving this task (whenever possible) in terms of the number of edge traversal made by the robot. Another optimization criteria is to minimize the amount of information that the robot has to carry when moving from node to node in the graph.
We present efficient algorithms for solving map construction using a robot that is not allowed to mark any vertex of the graph, assuming the knowledge of only an upper bound on the size of the graph. We also give universal algorithms (independent of the size of the graph) for map construction when only the starting location of the robot is marked. Our solutions apply the technique of universal exploration sequences to solve the map construction problem under various constraints. We also show how the solution can be adapted to solve other problems such as the gathering of two identical robots dispersed in an unknown graph.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Albers, S., Henzinger, M.R.: Exploring unknown environments. SIAM Journal on Computing 29(4), 1164–1188 (2000)
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: 20th Annual Symposium on Foundations of Computer Science (FOCS 1979), pp. 218–223 (1979)
Ando, E., Ono, H., Sadakane, K., Yamashita, M.: The space complexity of leader election in anonymous networks. International Journal of Foundations of Computer Science 21(3), 427–440 (2010)
Angluin, D.: Local and global properties in networks of processors. In: 12th Symposium on Theory of Computing (STOC 1980), pp. 82–93 (1980)
Barrière, L., Flocchini, P., Fraigniaud, P., Santoro, N.: Rendezvous and election of mobile agents: impact of sense of direction. Theory of Computing Systems 40(2), 143–162 (2007)
Baston, V., Gal, S.: Rendezvous search when marks are left at the starting points. Naval Research Logistics 48(8), 722–731 (2001)
Bender, M., Fernández, A., Ron, D., Sahai, A., Vadhan, S.: The power of a pebble: Exploring and mapping directed graphs. In: 30th ACM Symposium on Theory of Computing (STOC 1998), pp. 269–278 (1998)
Blum, M., Kozen, D.: On the power of the compass (or, why mazes are easier to search than graphs). In: 19th Annual Symposium on Foundations of Computer Science (FOCS 1978), pp. 132–142 (1978)
Boldi, P., Vigna, S.: An effective characterization of computability in anonymous networks. In: Welch, J.L. (ed.) DISC 2001. LNCS, vol. 2180, pp. 33–47. Springer, Heidelberg (2001)
Czyzowicz, J., Kosowski, A., Pelc, A.: How to meet when you forget: log-space rendezvous in arbitrary graphs. In: 29th Annual ACM Symposium on Principles of Distributed Computing (PODC 2010), pp. 450–459 (2010)
Czyzowicz, J., Labourel, A., Pelc, A.: How to meet asynchronously (almost) everywhere. In: 21st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2010), pp. 22–30 (2010)
Deng, X., Papadimitriou, C.H.: Exploring an unknown graph. Journal of Graph Theory 32(3), 265–297 (1999)
Dessmark, A., Fraigniaud, P., Kowalski, D.R., Pelc, A.: Deterministic rendezvous in graphs. Algorithmica 46(1), 69–96 (2006)
Dudek, G., Jenkin, M., Milios, E., Wilkes, D.: Robotic exploration as graph construction. Transactions on Robotics and Automation 7(6), 859–865 (1991)
Fraigniaud, P., Ilcinkas, D.: Digraphs exploration with little memory. In: Diekert, V., Habib, M. (eds.) STACS 2004. LNCS, vol. 2996, pp. 246–257. Springer, Heidelberg (2004)
Fraigniaud, P., Pelc, A.: Deterministic rendezvous in trees with little memory. In: Taubenfeld, G. (ed.) DISC 2008. LNCS, vol. 5218, pp. 242–256. Springer, Heidelberg (2008)
Fusco, E.G., Pelc, A.: How much memory is needed for leader election. In: Lynch, N.A., Shvartsman, A.A. (eds.) DISC 2010. LNCS, vol. 6343, pp. 251–266. Springer, Heidelberg (2010)
Koucký, M.: Universal traversal sequences with backtracking. Journal of Computer and System Sciences 65(4), 717–726 (2002)
Kranakis, E., Krizanc, D., Santoro, N., Sawchuk, C.: Mobile agent rendezvous in a ring. In: 23rd International Conference on Distributed Computing Systems (ICDCS 2003), pp. 592–599 (2003)
Norris, N.: Universal covers of graphs: isomorphism to depth n–1 implies isomorphism to all depths. Discrete Applied Mathematics 56(1), 61–74 (1995)
Panaite, P., Pelc, A.: Exploring unknown undirected graphs. Journal of Algorithms 33(2), 281–295 (1999)
Panaite, P., Pelc, A.: Impact of topographic information on graph exploration efficiency. Networks 36(2), 96–103 (2000)
Reingold, O.: Undirected connectivity in log-space. Journal of the ACM 55(4) (2008)
Ta-Shma, A., Zwick, U.: Deterministic rendezvous, treasure hunts and strongly universal exploration sequences. In: 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2007), pp. 599–608 (2007)
Yamashita, M., Kameda, T.: Computing on anonymous networks: Part I - characterizing the solvable cases. IEEE Transactions on Parallel and Distributed Systems 7(1), 69–89 (1996)
Yu, X., Yung, M.: Agent rendezvous: A dynamic symmetry-breaking problem. In: Meyer auf der Heide, F., Monien, B. (eds.) ICALP 1996. LNCS, vol. 1099, pp. 610–621. Springer, Heidelberg (1996)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Chalopin, J., Das, S., Kosowski, A. (2010). Constructing a Map of an Anonymous Graph: Applications of Universal Sequences. In: Lu, C., Masuzawa, T., Mosbah, M. (eds) Principles of Distributed Systems. OPODIS 2010. Lecture Notes in Computer Science, vol 6490. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-17653-1_10
Download citation
DOI: https://doi.org/10.1007/978-3-642-17653-1_10
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-17652-4
Online ISBN: 978-3-642-17653-1
eBook Packages: Computer ScienceComputer Science (R0)