Exploring unknown environments
Albers, Susanne
Henzinger, Monika H
directed graph
exploration algorithm
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.
Society for Industrial and Applied Mathematics
2000
info:eu-repo/semantics/article
doc-type:article
text
http://purl.org/coar/resource_type/c_6501
https://research-explorer.ista.ac.at/record/11694
Albers S, Henzinger MH. Exploring unknown environments. <i>SIAM Journal on Computing</i>. 2000;29(4):1164-1188. doi:<a href="https://doi.org/10.1137/s009753979732428x">10.1137/s009753979732428x</a>
eng
info:eu-repo/semantics/altIdentifier/doi/10.1137/s009753979732428x
info:eu-repo/semantics/altIdentifier/issn/0097-5397
info:eu-repo/semantics/altIdentifier/issn/1095-7111
info:eu-repo/semantics/closedAccess