2001 · 39 citations · 15 references
ComputingComputer ScienceAlgorithmsOptimizationRoboticsAutonomous ExplorationCombinatorial OptimizationExploration-exploitation TradeoffGraph AlgorithmsHeuristic SearchNetwork OptimizationExplorationFuel Tank ConfigurationFuel Tank DesignGraph Exploration
We address the problem of exploring an unknown graph G = (V; E) from a given start node s with either a tethered robot or a robot with a fuel tank of limited capacity, the former being a tighter constraint. In both varaitations of the problem, the robot can only move along the edges of the graph, i.e, it cannot jump between non-adjacent vertices. In the tethered robot case, if the tether (rope) has length l, then the robot must remain within distance l from the start node s. In the second variation, a fuel tank of capacity C forces the robot to return to s after traversing C edges. The eciency of algorithms for both variations of the problem is measured by the number of edges traversed during the exploration. We present an algorithm for a tethered robot which explores the graph in O(jEj) edge traversals. The problem of exploration using a robot with a limited fuel tank capacity can be solved with a simple reduction from the tethered robot case and also yields a O(jEj) algorithm...
15
V. J. Rayward‐Smith, Thomas H. Cormen, Charles E. Leiserson et al. · Journal of the Operational Research Society · 1991 · 17K citations
Michael A. Bender, Antonio Fernández Anta, Dana Ron et al. · 1998 · 226 citations