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 it rectang les. We show that no deterministic or randomized online algorithm, can be b etter than Omega(rootn)-competitive, solving an open problem by Deng ct al. [7]. We also generalize this bound to the problem of exploring three-dimen sional 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 define d by Betke et al [4] and implies that the robot has to return to a start no de every so often. Betke et al. gave an efficient algorithm for exploring g rids with rectangular obstacles. We present an efficient strategy for piece meal exploration of grids with arbitrary rectilinear obstacles.