Optimal graph exploration without good maps
(2004) In Theoretical Computer Science 326(13). p.343362 Abstract
 A robot has to visit all nodes and traverse all edges of an unknown undirected connected graph, using as few edge traversals as possible. The quality of an exploration algorithm A is measured by comparing its cost (number of edge traversals) to that of the optimal algorithm having full knowledge of the graph. The ratio between these costs, maximized over all starting nodes in the graph and over all graphs in a given class U, is called the overhead of algorithm A for the class U of graphs. We consider three scenarios, providing the robot with varying amount of information. The robot may either know nothing about the explored graph, or have an unlabeled isomorphic copy of it (an unanchored map), or have such a copy with a marked starting... (More)
 A robot has to visit all nodes and traverse all edges of an unknown undirected connected graph, using as few edge traversals as possible. The quality of an exploration algorithm A is measured by comparing its cost (number of edge traversals) to that of the optimal algorithm having full knowledge of the graph. The ratio between these costs, maximized over all starting nodes in the graph and over all graphs in a given class U, is called the overhead of algorithm A for the class U of graphs. We consider three scenarios, providing the robot with varying amount of information. The robot may either know nothing about the explored graph, or have an unlabeled isomorphic copy of it (an unanchored map), or have such a copy with a marked starting node (an anchored map). For all of the above scenarios, we construct natural exploration algorithms that have smallest, orin one caseclose to smallest, overhead. While for the class of all graphs, depthfirst search turns out to be an optimal algorithm for all scenarios, the situation for trees is much different. We show that, under the scenario without any knowledge, DFS is still optimal for trees but this is not the case if a map is available. Under the scenario with an unanchored map, we show that optimal overhead is at leastroot3 but strictly below 2 (and thus DFS is not optimal). Under the scenario with an anchored map, we construct an optimal algorithm for trees and show that its overhead is 3/2. We also consider exploration of the class of lines (simple paths). In this case, depthfirst search remains optimal for the scenario without any knowledge, with overhead 2. Under the scenario with an unanchored map, we construct an optimal algorithm and show that its overhead is root3. Finally, under the scenario with an anchored map, we construct an optimal algorithm and show that its overhead is 7/5. An important contribution of this paper is establishing lower bounds that prove optimality of these exploration algorithms. (C) 2004 Elsevier B.V. All rights reserved. (Less)
Please use this url to cite or link to this publication:
http://lup.lub.lu.se/record/262633
 author
 Dessmark, Anders ^{LU} and Pelc, A
 organization
 publishing date
 2004
 type
 Contribution to journal
 publication status
 published
 subject
 keywords
 robot, traversal, map, graph, algorithm, exploration
 in
 Theoretical Computer Science
 volume
 326
 issue
 13
 pages
 343  362
 publisher
 Elsevier
 external identifiers

 wos:000224601400017
 scopus:5144223747
 ISSN
 03043975
 DOI
 10.1016/j.tcs.2004.07.031
 language
 English
 LU publication?
 yes
 id
 4cc44e450bbe45fcbda495249f467220 (old id 262633)
 date added to LUP
 20071023 13:34:52
 date last changed
 20180107 08:47:04
@article{4cc44e450bbe45fcbda495249f467220, abstract = {A robot has to visit all nodes and traverse all edges of an unknown undirected connected graph, using as few edge traversals as possible. The quality of an exploration algorithm A is measured by comparing its cost (number of edge traversals) to that of the optimal algorithm having full knowledge of the graph. The ratio between these costs, maximized over all starting nodes in the graph and over all graphs in a given class U, is called the overhead of algorithm A for the class U of graphs. We consider three scenarios, providing the robot with varying amount of information. The robot may either know nothing about the explored graph, or have an unlabeled isomorphic copy of it (an unanchored map), or have such a copy with a marked starting node (an anchored map). For all of the above scenarios, we construct natural exploration algorithms that have smallest, orin one caseclose to smallest, overhead. While for the class of all graphs, depthfirst search turns out to be an optimal algorithm for all scenarios, the situation for trees is much different. We show that, under the scenario without any knowledge, DFS is still optimal for trees but this is not the case if a map is available. Under the scenario with an unanchored map, we show that optimal overhead is at leastroot3 but strictly below 2 (and thus DFS is not optimal). Under the scenario with an anchored map, we construct an optimal algorithm for trees and show that its overhead is 3/2. We also consider exploration of the class of lines (simple paths). In this case, depthfirst search remains optimal for the scenario without any knowledge, with overhead 2. Under the scenario with an unanchored map, we construct an optimal algorithm and show that its overhead is root3. Finally, under the scenario with an anchored map, we construct an optimal algorithm and show that its overhead is 7/5. An important contribution of this paper is establishing lower bounds that prove optimality of these exploration algorithms. (C) 2004 Elsevier B.V. All rights reserved.}, author = {Dessmark, Anders and Pelc, A}, issn = {03043975}, keyword = {robot,traversal,map,graph,algorithm,exploration}, language = {eng}, number = {13}, pages = {343362}, publisher = {Elsevier}, series = {Theoretical Computer Science}, title = {Optimal graph exploration without good maps}, url = {http://dx.doi.org/10.1016/j.tcs.2004.07.031}, volume = {326}, year = {2004}, }