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
VL - 152
SP - 155
EP - 172
JO - Information and Computation
JF - Information and Computation
SN - 0890-5401
IS - 2
ER -