|
Abstract : |
We study how a mobile robot can piecemeal learn an unknown environment. The robot's goal is to learn a complete map of its environment, while satisfying the constraint that it must return every so often to its starting position s (for refueling, say). The environment is modelled as an arbitrary, undirected graph, which is initially unknown to the robot. We assume that the robot can distinguish vertices and edges which it has already explored. We present a surprisingly efficient algorithm for piecemeal learning an unknown undirected graph G = (V; E) in which the robot explores every vertex and edge in G by traversing at most O(E + V 1+o(1)) edges. This nearly linear algorithm improves on the best previous algorithm, in which the robot traverses at most O(E + V 2) edges. We also address the related problem of searching a graph for a particular distinguished location or treasure. If this treasure is likely to be near s, then the robot should explore in a breadth-first manner. We show how the robot can explore while never being much further than ffi away from s, where ffi is the shortest path distance from s of the unvisited vertex nearest to s. We show that if the robot is never more than ffi away from s (as in traditional BFS), then there are graphs for which the robot traverses \Omega\Gamma, |
