Models and Algorithms for Online Exploration and Search

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 search for a door in a wall (or a point on a line). We show that a robot that is not aware of making errors is able to find its goal, if its error is not greater than 33 per cent. Further, we give an optimal-competitive strategy that takes the maximal error into account, and generalize our result to searching on m rays. Last, we examine a new cost measure for search tasks, the search ratio. The quality of a search path is determined by a worst-case target point-a point that maximizes among all target points, t, the ratio between the length of the searcher's path up to t and the shortest path to t. An optimal search path has the minimal search ratio among all search paths in the given environment. The optimal search ratio-the search ratio of the optimal search path-is an appropriate measure for the searchability of an environment. We give a general framework for approximating a path with optimal search ratio, and apply this framework to simple polygons and grid polygons. Further, we show that no constant-competitive approximation is possible for polygons with holes.