TY - GEN

T1 - Piecemeal graph exploration by a mobile robot

AU - Awerbuch, Baruch

AU - Betke, Margrit

AU - Rivest, Ronald L.

AU - Singh, Mona

N1 - Funding Information:
*We gratefully acknowledge support from NSF grant CCR-9310888, ARO grant DAAL03-86-K0171, NSF grant 9z171)41.ASC, Air Force Contract TN DGAFOSR.86.0078, ARPA/Army contract DABT63-93-C-0038, NSF contract 9114440 -CCR, DARPA contract NOOO14-J-9Z.1799, ARPA/ONR contract Nooo I4-92-J-131o, the Siemens Corporation, and a special grant from IBM. The authors can be reached at barucht!blaze. cs. jhu. ectu, margrit@lcs .mit. edu, rivest@theory. lcs .mit. edu, and monat?theory. lcs .mit . edu. t Also at Johns Hopkins University,
Publisher Copyright:
© 1995 ACM.

PY - 1995/7/5

Y1 - 1995/7/5

N2 - 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 (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 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 + V1+0(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 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 (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 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 + V1+0(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=84923103437&partnerID=8YFLogxK

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

M3 - Conference contribution

AN - SCOPUS:84923103437

T3 - Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995

SP - 321

EP - 328

BT - Proceedings of the 8th Annual Conference on Computational Learning Theory, COLT 1995

PB - Association for Computing Machinery, Inc

T2 - 8th Annual Conference on Computational Learning Theory, COLT 1995

Y2 - 5 July 1995 through 8 July 1995

ER -