Worst-case robot navigation in deterministic environments

We design and analyze algorithms for the following two robot navigation problems: (1) TARGET SEARCH. Given a robot located at a point s in the plane, how will a robot navigate to a goal t in the presence of unknown obstacles? (2) LOCALIZATION. A robot is "lost" in an environment with a map of its surroundings. How will it find its true location by traveling the minimum distance?;Since efficient algorithms for these two problems will make a robot completely autonomous, they have held the interest of both robotics and computer science communities.;Previous work has focussed mainly on designing competitive algorithms where the robot's performance is compared to that of an omniscient adversary. For example, a competitive algorithm for target search will compare the distance traveled by the robot with the shortest path from s to t.;We analyze these problems from the worst-case perspective, which, in our view, is a more appropriate measure. Our results are: (1) For target search, we analyze an algorithm called Dynamic A*. The robot continuously moves to the goal on the shortest path which it recomputes on the discovery of obstacles. A variant of this algorithm has been employed in Mars Rover prototypes. We show that D* takes O( n log n) time on planar graphs and also show an O(n log2 n) bound on arbitrary graphs. Thus, our results show that D* combines the optimistic possibility of reaching the goal very soon while competing with depth-first search within a logarithmic factor. (2) For the localization problem, worst-case analysis compares the performance of the robot with the optimal decision tree over the set of possible locations.;No approximation algorithm has been known. We give an O(log 3 n)-approximation algorithm and also show a O(log 2--epsilon n) lower bound for the grid graphs commonly used in practice. The key idea is to plan travel on a "majority-rule map" which eliminates uncertainty and permits a link to the ½-Group Steiner problem. We also extend the problem to polygonal maps by discretizing the domain using novel geometric techniques.