COMPETITIVE STRATEGIES FOR AUTONOMOUS SYSTEMS

Abstract

A strategy for working with incomplete information is called competitive if it solves each problem instance at a cost not exceeding the cost of an optimal solution (with full information available), times a constant. This paper strives to demonstrate why competitive strategies are useful for the design of autonomous robots. They guarantee a good worst-case behaviour, they are easy to implement, and they allow to deal with some problems whose optimal solution would be NP-hard. We survey competitive strategies for the following problems. How to find a door in a long wall, how to find a goal in an unknown environment, how to find a point from which an unknown environment is fully visible, and how to determine a robot's location on a known map from local visibility. Keywords. Competitive, doubling strategy, localization, kernel, polygon, robot, street, visibility. 1 Introduction Suppose there is a very long wall, and at some point at the wall a mobile robot is located. Its ta...