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\\Omega\\Gamma p n)-competitive, solving an open problem by Deng, Kameda and Papadimitriou [5]. 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, Rivest and Singh [3] and implies that the robot has to return 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 obstacles. 1 Introduction In robot exploration problems, a...