Advanced

Optimal graph exploration without good maps

Dessmark, Anders LU and Pelc, A (2004) In Theoretical Computer Science 326(1-3). p.343-362
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, or-in one case-close to smallest, overhead. While for the class of all graphs, depth-first 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, depth-first 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:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
robot, traversal, map, graph, algorithm, exploration
in
Theoretical Computer Science
volume
326
issue
1-3
pages
343 - 362
publisher
Elsevier
external identifiers
  • wos:000224601400017
  • scopus:5144223747
ISSN
0304-3975
DOI
10.1016/j.tcs.2004.07.031
language
English
LU publication?
yes
id
4cc44e45-0bbe-45fc-bda4-95249f467220 (old id 262633)
date added to LUP
2007-10-23 13:34:52
date last changed
2017-07-30 04:29:20
@article{4cc44e45-0bbe-45fc-bda4-95249f467220,
  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, or-in one case-close to smallest, overhead. While for the class of all graphs, depth-first 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, depth-first 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         = {0304-3975},
  keyword      = {robot,traversal,map,graph,algorithm,exploration},
  language     = {eng},
  number       = {1-3},
  pages        = {343--362},
  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},
}