Competitive Strategies for Autonomous Systems
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.
Nutzung und Vervielfältigung:
Alle Rechte vorbehalten