TY - GEN
T1 - Piecemeal graph exploration by a mobile robot
AU - Awerbuch, Baruch
AU - Betke, Margrit
AU - Rivest, Ronald L.
AU - Singh, Mona
N1 - 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 -