TY - JOUR

T1 - Piecemeal Graph Exploration by a Mobile Robot

AU - Awerbuch, Baruch

AU - Betke, Margrit

AU - Rivest, Ronald L.

AU - Singh, Mona

N1 - Funding Information:
* Most of this work was done while all authors were affiliated with the laboratory of Computer Science at the Massachusetts Institute of technology. We gratefully acknowledge support from NSF Grant CCR-9310888, ARO Grant DAAL03-86-K-0171, NSF Grant 9217041-ASC, Air Force Contract TNDGAFOSR-86-0078, ARPA Army Contract DABT63-93-C-0038, NSF Contract 9114440-CCR, DARPA Contract N00014-J-92-1799, ARPA ONR Contract N00014-92-J-1310, the Siemens Corporation and a special grant from IBM. E-mail: baruch blaze.cs.jhu.edu, betke cs.bc.edu, rivest theory. lcs.mit.edu, and mona wi.mit.edu.

PY - 1999/8/1

Y1 - 1999/8/1

N2 - We study how a mobile robot can learn an unknown environment in a piecemeal manner. 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 (for refueling, say). The environment is modeled as an arbitrary, undirected graph, which is initially unknown to the robot. We assume that the robot can distinguish vertices and edges that 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 the graph by traversing at most O(E + \/1+o(1)) edges. This nearly linear algorithm improves on the best previous algorithm, in which the robot traverses at most O(E + V2) edges. We also give an application of piecemeal learning to the problem of searching a graph for a "treasure."

AB - We study how a mobile robot can learn an unknown environment in a piecemeal manner. 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 (for refueling, say). The environment is modeled as an arbitrary, undirected graph, which is initially unknown to the robot. We assume that the robot can distinguish vertices and edges that 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 the graph by traversing at most O(E + \/1+o(1)) edges. This nearly linear algorithm improves on the best previous algorithm, in which the robot traverses at most O(E + V2) edges. We also give an application of piecemeal learning to the problem of searching a graph for a "treasure."

UR - http://www.scopus.com/inward/record.url?scp=0000151983&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0000151983&partnerID=8YFLogxK

U2 - 10.1006/inco.1999.2795

DO - 10.1006/inco.1999.2795

M3 - Article

AN - SCOPUS:0000151983

SN - 0890-5401

VL - 152

SP - 155

EP - 172

JO - Information and Computation

JF - Information and Computation

IS - 2

ER -