@InProceedings{ABRS95,
  author = 	 { Baruch Awerbuch and Margrit Betke and Ronald L. Rivest and Mona Singh },
  title = 	 { Piecemeal graph exploration by a mobile robot (extended abstract) },
  pages = 	 { 321--328 },
  acmid =        { 225337 },  
  doi =          { 10.1145/225298.225337 },                
  acm =          { 77463 },                  
  booktitle =    { Proceedings Eighth Annual Conference on Computational Learning Theory },
  editor = 	 { Wolfgang Maas },
  publisher =    { ACM },
  isbn =         { 0-89791-723-5 },
  date =         { 1995-07 },                  
  OPTyear = 	 { 1995 },
  OPTmonth = 	 { July 5--8 },
  eventtitle =   { COLT'95 },
  eventdate =    { 1995-07-05/1995-07-08 },
  venue =        { Santa Cruz, California },
  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 point (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 it has already explored. \par
        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 + 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.   \par
        We also give an application of piecemeal learning to the
        problem of searching a graph for a ``treasure''.                  
                 },                  
}