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).)