Technical Report No. 97, April 1998 - Zusammenfassung

Sven Schuierer, Ines Semrau:
Eine optimale Suchstrategie für Straßen

Wir untersuchen das Problem eines Roboters, ein Ziel in einem unbekannten Polygon nur unter Zuhilfenahme der bereits erlangten Sichtbarkeitsinformation zu finden. Eine Straße ist ein Polygon mit Start- und Zielpunkt, so daß auf jedem Weg vom Start zum Ziel das gesamte Polygon eingesehen werden kann. Für diese bereits intensiv untersuchte Polygonklasse stellen wir eine optimal On-line-Suchstrategie vor. Diese findet einen Weg zum Ziel, der höchstens sqrt(2)-mal so lang ist wie der kürzeste Weg.