This work considers some algorithmic aspects of exploration and search, two tasks that arise, for example, in the field of motion planning for autonomous mobile robots. We assume that the environment is not known to the robot in advance,...