Kamphans, T: Models and Algorithms for Online Exploration an

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, so we deal with online algorithms.First, we consider a special kind of environments that we call cellular environments, where the robot's surrounding is subdivided by an integer grid. The robot's task is to visit every cell in this grid at least once. We distinguish between simple grid polygons (i.e., polygons with no obstacles inside) and general grid polygons. We show that no online exploration strategy is able to achieve a competitive factor better than 7/6 for simple grid polygons and better than 2 for general grid polygons. That is, the path of an online exploration strategy is in the worst case at least 7/6 times (2 times, respectively) longer than the optimal path that was computed with full knowledge of the environment. For both cases we develop exploration strategies and show upper bounds on their performance. More precisely, for environments without obstacles we provide a strategy that produces tours of length S = C + E/2 - 3, and for environments with obstacles we provide a strategy that is bound by S = C + E/2 + 3H + W - 2, where C denotes the number of cells-the area-, E denotes the number of boundary edges-the perimeter-, H is the number of obstacles, and W is a measure for the sinuosity of the given environment. Moreover, we show that the strategy for simple grid polygons is 4/3-competitive; that is, the path generated by our strategy is never longer than 4/3 times the optimal path.Second, we consider search tasks with error-prone robots and give performance results that take the robot's errors into account. The first search task is to leave an unknown environment using the well-known Pledge algorithm. We give sufficient conditions that ensure a successful application with an error-prone robot. The second task is the