Exploring Unknown Environments with Obstacles

We study exploration problems where a robot has to construct a complete map of an unknown environment using a path that is as short as possible. In the first problem setting we consider, a robot has to explore n rectangles. We show that no deterministic or randomized online algorithm can be better than Ω(sqrt n ) -competitive, solving an open problem by Deng et al. [7]. We also generalize this bound to the problem of exploring three-dimensional rectilinear polyhedra without obstacles. In the second problem setting we study, a robot has to explore a grid graph with obstacles in a piecemeal fashion. The piecemeal constraint was defined by Betke et al. [4] and implies that the robot has to return to a start node every so often. Betke et al. gave an efficient algorithm for exploring grids with rectangular obstacles. We present an efficient strategy for piecemeal exploration of grids with arbitrary rectilinear obstacles.