Paper Info
Title
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 op- timal 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 nd a door in a long wall, how to nd a goal in an unknown environment, how to nd 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.
Year
Venue
Keywords
1994
Modelling and Planning for Sensor Based Intelligent Robot Systems
polygon,doubling strategy,localization,street,robot,kernel,visibility.,. competitive,incomplete information,competitive strategy
Field
DocType
Citations 
Visibility,Mathematical optimization,Computer science,Control engineering,Autonomous system (Internet),Robot,Complete information
Conference
16
PageRank 
References 
Authors
1.26
12
2
Name
Order
Citations
PageRank
Christian Icking136433.17
Rolf Klein223719.69