Exploring unknown environments
Albers S, Henzinger MH. 2000. Exploring unknown environments. SIAM Journal on Computing. 29(4), 1164–1188.
Download
No fulltext has been uploaded. References only!
Journal Article
| Published
| English
Scopus indexed
Author
Albers, Susanne;
Henzinger, MonikaISTA
Abstract
We consider exploration problems where a robot has to construct a complete map of an unknown environment. We assume that the environment is modeled by a directed, strongly connected graph. The robot's task is to visit all nodes and edges of the graph using the minimum number R of edge traversals. Deng and Papadimitriou [Proceedings of the 31st Symposium on the Foundations of Computer Science, 1990, pp. 356-361] showed an upper bound for R ofd O(d)m and Koutsoupias (reported by Deng and Papadimitriou) gave a lower bound of Ω≠(d2m), where m is the number of edges in the graph and d is the minimum number of edges that have to be added to make the graph Eulerian. We give the 1rst subexponential algorithm for this exploration problem, which achieves an upper bound of dO(logd)m. We also show a matching lower bound of d≠(logd)m for our algorithm. Additionally, we give lower bounds of 2≠(d)m, respectively, d≠(logd)m for various other natural exploration algorithms.
Keywords
Publishing Year
Date Published
2000-07-01
Journal Title
SIAM Journal on Computing
Publisher
Society for Industrial and Applied Mathematics
Acknowledgement
We thank Prabhakar Raghavan for bringing to our attention the literature on the s-t connectivity problem. We also thank an anonymous referee for many helpful comments which improved the presentation of the paper.
Volume
29
Issue
4
Page
1164-1188
Conference
STOC97: 29th Annual Symposium on Theory of Computing
Conference Location
El Paso, TX, United States
Conference Date
1997-05-04 – 1997-05-06
ISSN
eISSN
IST-REx-ID
Cite this
Albers S, Henzinger MH. Exploring unknown environments. SIAM Journal on Computing. 2000;29(4):1164-1188. doi:10.1137/s009753979732428x
Albers, S., & Henzinger, M. H. (2000). Exploring unknown environments. SIAM Journal on Computing. El Paso, TX, United States: Society for Industrial and Applied Mathematics. https://doi.org/10.1137/s009753979732428x
Albers, Susanne, and Monika H Henzinger. “Exploring Unknown Environments.” SIAM Journal on Computing. Society for Industrial and Applied Mathematics, 2000. https://doi.org/10.1137/s009753979732428x.
S. Albers and M. H. Henzinger, “Exploring unknown environments,” SIAM Journal on Computing, vol. 29, no. 4. Society for Industrial and Applied Mathematics, pp. 1164–1188, 2000.
Albers S, Henzinger MH. 2000. Exploring unknown environments. SIAM Journal on Computing. 29(4), 1164–1188.
Albers, Susanne, and Monika H. Henzinger. “Exploring Unknown Environments.” SIAM Journal on Computing, vol. 29, no. 4, Society for Industrial and Applied Mathematics, 2000, pp. 1164–88, doi:10.1137/s009753979732428x.