In the area of mobile robot environment learning, we introduce the problem of piecemeal learning of an unknown environment: the robot must return to its starting point after each piece of exploration. We give linear time algorithms for exploring environments modeled as grid-graphs with rectangular obstacles. Our best algorithm for piecemeal learning of arbitrary undirected graphs runs in almost linear time. (This is joint work with R. Rivest, M. Singh (MIT), and B. Awerbuch (JHU).)