Competitive Strategies for Autonomous Systems

Icking, Christian; Klein, Rolf GND

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.

Vorschau

Zitieren

Zitierform:

Icking, Christian / Klein, Rolf: Competitive Strategies for Autonomous Systems. Hagen 1995. FernUniversität in Hagen.

Zugriffsstatistik

Gesamt

Volltextzugriffe:
Metadatenansicht:

12 Monate

Volltextzugriffe:
Metadatenansicht:

Rechte

Nutzung und Vervielfältigung:
Alle Rechte vorbehalten

Export

powered by MyCoRe