Teil III

Erfors chen von G raphen und Umgebungen

Martin L¨ ohnertz, Andr´ e Weilert

1 Einleitung

Der folgende Beitrag versucht, einen Einblick in graphentheoretische und geometrische Problemstellungen und L¨ osungsstrategien zu geben, die im Rahmen der Online-Problematik auftreten. Die Erkenntnisse, die in diesem Gebiet gewonnen wurden, sind, obwohl man annehmen sollte, daß die Probleme in modi�zierter Form schon seit Jahrhunderten bestehen, ¨ uberwiegend j¨ ungeren Datums, was dazu f¨ uhrt, daß es weder eine einheitliche Theorie noch einen systematischen Ansatz zur Klassi�zierung gibt. Einerseits inspiriert durch grundlegende Arbeiten wie z.B. [24] andererseits aus der Praxis, i.e. der Robotik oder sogar aus der Automatentheorie heraus ([6]) motiviert wurden zahlreiche Verfahren entwickelt, die aufgrund der Unterschiedlichkeit der Anforderungen, aber auch der analytischen Methoden bzw. der als solche deklarierten Variablen und Konstanten teilweise unvergleichbar sind. So �nden sich in [21] Algorithmen zum ¨ Uberwinden von Hindernissen, die in der L¨ ange des Randes dieser Hindernisse kompetetiv sind, w¨ ahrend z.B. [17] kompetetiv bez¨ uglich der zur¨ uckgelegten Wegstrecke und [22] kompetetiv bez¨ uglich der Zahl der Hindernisse bleibt. Bei den Graphen besteht immerhin noch ein Zusammenhang zu den theoretisch besser erschlossenen ”Greedy”- Verfahren auf diesen (Matroide etc.); dieser wurde aber in keiner der von uns betrachteten Literaturstellen verwandt. Dementsprechend beginnt der Beitrag mit einem kurzen Systematisierungsversuch, geht dann auf die Rahmenbedingungen ein und besteht im Hauptteil aus zwei getrennten Beitr¨ agen zu Graphen^{1} und Hindernisparcours ^{2}, in denen der Versuch unternommen wird, einige der wichtigsten Ergebnisse und Strategien vorzustellen.

2 De�nitionen

In der Literatur �ndet sich keine einheitliche Terminologie zur Beschreibung der Problematiken mit formalen Methoden. Um eine Klassi�zierung der Problemstellungen vornehmen zu k¨ onnen, und allgemein eing¨ angigere Formulierungen zu erzielen, ist es daher sinnvoll, zun¨ achst einige Vereinbarungen vorzunehmen. Um eine unn¨ otige Verkomplizierung der Situation, die sich durch eine allgemeine De�nition h¨ au�g ergibt, zu vermeiden, unterscheiden wir allerdings zwischen der f¨ ur dieses Referat notwendigen, und der tats¨ achlich zu verlangenden Notation. D.h. bei Verweisen auf Probleme, die sich mit der nun gegebenen De�nition nicht darstellen lassen, wird die entsprechende Erweiterung angegeben, wobei diese aber im allgemeinen nur die Schritte der Mengen-, bzw. Potenzmengenbildung verlangt.

1haupts¨ achlich Andr´ e Weilert

2haupts¨ achlich Martin L¨ ohnertz

2.1 Graphen

De�nition 2.1.1 (Online Graphenproblem) Ein Online Graphenproblem ist ein 8-Tupel OG := (V, E, C, 𝔒, K_{0}, K_{fin}, κ, Υ), wobei:

• G = (V, E) der zu betrachtende (Multi-)Graph ist.

• C ist eine Menge von sonstigen Informationen, die mit Knoten oder Kanten assoziiert werden. Z. B. eine Kostenfunktion auf den Kanten.

• 𝔒 : 2^{V} × 2^{E} → 2^{V} × 2^{E} × 2^{C} wird im folgenden als Online-Begrenzungsfun-ktion bezeichnet. Sie ordnet den vollzogenen Aktionen die dadurch gewonnene Information zu.

• K_{0} ist die Startkon�guration

• K_{fin} die Menge der Endkon�gurationen

• κ : K ∪ K^{2} → ℝ die Kostenfunktion

• Υ : K_{fin} → ℝ die Zielfunktion

De�nition 2.1.2 (Kon�guration) Eine Kon�guration beschreibt einen Zustand w¨ ahrend der Berechnung. Sie wird dargestellt durch ein 3-Tupel K_{i} = (W̃_{i}, F̃_{i}, p_{i})

• W̃ := ”Menge der besuchten Ecken”

• F̃ := ”Menge der besuchten Kanten”

• p ist der ”Aufenthaltsort” nach Schritt i Entsprechend ergibt sich die Menge K aller m¨ oglichen Kon�gurationen, mit K_{0} ∈ K ⊃ K_{fin} Als weitere Abk¨ urzungen seien vereinbart:

• Ŵ := 𝔒_{W} (W̃ , F̃) := π_{1} ∘ 𝔒(W̃ , F̃) ”Menge der bekannten Ecken”

• F̂ := 𝔒_{F} (W̃ , F̃) := π_{2} ∘ 𝔒(W̃ , F̃) ”Menge der bekannten Kanten”

• Ĉ := 𝔒_{C}(W̃ , F̃) := π_{3} ∘ 𝔒(W̃ , F̃) ”Menge der bekannten sonstigen Informa-

tionen” Diese Darstellung der Problematik schließt z.B. das Erhalten der Informationen aus anderen Quellen aus (s. vgl 5.4 auf Seite III-9).

2.2 Hindernisparcours

De�nition 2.2.1 (Online Environment) Ein Online Environment (Hindernisparcours) ist ein 8-Tupel OE = (A, H, M, 𝔒, K_{0}, K_{fin}, κ, Υ)

mit

• Polygon P : (p_{j})_{j∈J} ∀j ∈ J : p_{j} ∈ ℝ^{2} (Kanten ¨ uberschneiden einander nicht)^{3}

• Umschließendes Polygon A ⊂ ℝ^{2} oder A = ℝ^{2}

• Hindernisse (Polygone) (H_{i})_{i∈I} ∀i : H_{i} ⊂ A

• M := Menge von ”interessanten” Punkten

• H̃ := ”Menge der besuchten Positionen”

• Online-Begrenzungsfunktion: 𝔒 : 2^{ℝ^{2}} → 2^{ℝ^{2}} , 𝔒(H̃) = (Ŵ , F̂)

• Kon�gurationen : K_{i} = (H̃_{i}, p_{i}) ∈ 2^{ℝ^{2}} × ℝ^{2}, s.o.

Des weiteren scheinen folgende Vereinbarungen sinnvoll, auch wenn wir die Begriffe nur implizit benutzen:

• VisibilityGraph G_{OE} = (V, E);

V = {p|∃i : H_{i} = (⋯, p, ⋯) ∨ A = (⋯, p, ⋯) ∨ p ∈ M}

Kanten:

(u, w) ∈ E ⇔ ∀λ ∈ (0, 1) : λw + (1 − λ)u ∈ A\ (⋃_{i∈I} H_{i})

• Identi�kationsf¨ ahigkeit ℑ : 2^{ℝ^{2}} → 2^{V_{OE}} × 2^{E_{OE}} , ℑ ∘ 𝔒(X̄) = (Ŵ , F̂)

2.2.1 Gegner und Begrenzungsfunktion

Bei der Konzipierung der De�nitionen wurde in Anbetracht der Tatsache, daß in der Praxis vorkommende Gegner meist von Typ OBLIVIOUS sind eine eher statische Beschreibung der Probleme gew¨ ahlt, was darin Ausdruck �ndet, daß die Mengen nicht von den Entscheidungen des Algorithmus abh¨ angen. Es sei daher an dieser Stelle darauf hingewiesen, daß wir die obigen Vereinbarungen in erster Linie in analytischen Zusammenh¨ angen einsetzen wollen. D.h. nachdem der Algorithmus abgelaufen ist, wird sein Verhalten anhand des hierbei erstellten Graphen analysiert. In diesem Zusammenhang erscheint eine ehemalige Entscheidung eines Gegners als Entdeckung einer bestehenden Tatsache. In den meisten F¨ allen ist es allerdings so, daß tats¨ achlich von festen Graphen oder Umgebungen ausgegangen wird, die der Gegner als Ganzes erzeugt.

3Dies l¨ aßt sich nat¨ urlich auf den ℝ^{n} verallgemeinern.

Zudem l¨ aßt sich die De�nition der Gegnertypen der Literatur zu diesem Thema hier nicht vollst¨ andig ¨ ubertragen und ist auch nicht konsistent zur allgemeinen De�nition der Online-Thematik, wie z.B. List-Update o.¨ a. . So z.B. wird im Environment-Kontext ein Gegner als OBLIVIOUS bezeichnet, dem zwar unbekannt ist, wie der Algorithmus zu einem speziellen Zeitpunkt entschieden hat, der aber ¨ uber den jeweils aktuellen Standort informiert ist.

3 Komplexit¨ at

Vor dem Versuch geeignete Probleml¨ osungen �nden zu wollen, sollte man den Rahmen abstecken, in dem diese liegen k¨ onnen. Viele Graphenprobleme sind NP-hart, was die Existenz eines guten ”Greedy”-Algorithmus von vornherein ausschließt. Da die Laufzeit bei der Bestimmung des optimalen Of�ine-Algorithmus aber keine Rolle spielt m¨ ussen die Online-Algorithmen sozusagen gegen die ”vielleicht existente” polynomielle L¨ osung der NP-vollst¨ andigen Probleme^{4} antreten, was sich am folgenden Beispiel am besten verdeutlichen l¨ aßt: Gesucht: ein kompetetiver Algorithmus f¨ ur das Problem des Handlungsreisenden. D.h. die L¨ osung darf nur um einen konstanten Faktor c von der optimalen L¨ osung abweichen. Gewichtet man aber bei einem beliebigen einfachen Graphen alle existenten Kanten mit 1 und f¨ ugt die nichtexistenten hinzu und gewichtet diese mit (|V | + 1) ∗ c, so w¨ urde obiger Algorithmus hamiltonsche Kreise in diesem Graphen aufsp¨ uren, da die Verwendung einer einzigen nicht existente Kante einen Weg liefern w¨ urde dessen L¨ ange um mehr als das c-fache von einer optimalen L¨ osung (so existent) abweichen w¨ urde. Da aber die einzige Methode einen HC zu �nden (Annahme, P ≠ N P) im Durchtesten aller Varianten besteht, kann es keinen Greedy-Algorithmus und somit auch keinen Online-Algorithmus geben. Die folgende Abbildung zeigt z.B. einen Graphen, bei dem man bereits bei der ersten Kante die Entscheidung ¨ uber das Gelingen trifft, ohne die notwenigen Informationen besitzen zu k¨ onnen.

Abbildung 3.0.1 (OnlineHamiltongraph)

Konkret kann man f¨ ur einige besonders einfache Probleme zeigen, daß das Finden einer L¨ osung in PSPACE (und somit in EXPTIME) ist^{5}:

4d.h. zur Zeit gegen ein Backtracking Verfahren

5nach einer Beweisidee von [24]

Man betrachte die folgende Variante das ”Canadian Traveling Salesman problem” In einem gerichteten Graphen seien die Kantengewichte in dem Sinne unbekannt, daß bei einigen Kanten zwei ausgehende Kanten vorhanden sind f¨ ur die zwei Gewichte bekannt sind, man aber nicht weiß, welche der Kanten welches der Gewichte tr¨ agt. Diese Information erh¨ alt man, wenn man einen Vater des entsprechenden Knotens besucht. Ziel ist es, m¨ oglichst billig vom Knoten s zum Knoten t zu gelangen. d.h:

𝔒_{W} (M, N) = W ∧ 𝔒_{F} (M, N) = F ∀M ⊂ V, N ⊂ E

𝔒_{C}(M, N) = {(a, b)|a ∈ F, b ∈ w_{1a}, w_{2a}, a = (v_{1}, v_{2}), ∃v_{0} ∈ M : (v_{0}, v_{1}) ∈ E}

K_{0} = {∅, ∅, v_{0}}K_{fin} = {K|K = (a, b, p), p = t}
κ = w((P_{K_{1}}, P_{K_{2}}))(Kantengewicht)

Mit Hilfe folgender Konstruktion l¨ aßt sich zeigen, daß das Finden einer kompetetiven Strategie dazu verwandt werden kann eine L¨ osung f¨ ur Q-Sat (Quanti�ed Sat), was selbst PSPACE-complete ist, zu �nden:

Abbildung 3.0.2 (PSPACE)

Zu einer gegebenen Zielkompetetivit¨ at r > 1 seien m und M seien wie folgt gew¨ ahlt: m sei so groß, daß \frac{m+|V |}{m} < r und \frac{M}{m+|V |} > r. Die K¨ astchen entsprechen den Klauseln, und jedem der dick dargestellten Vierecke ist eine Variable zugeordnet. Die jeweils untere Ecke ist mit einer Klausel genau dann verbunden, wenn die entsprechende Variable in der Klausel negiert vorkommt, die obere, wenn sie nicht negiert vorkommt. Der Sucher kann von S aus nicht senkrecht nach unten gehen, da der Gegner die Kosten f¨ ur diesen Weg auf M setzen und selber ¨ uber den gleich beschriebenen Weg mit Kosten ≤ m + |V | zum Ziel gelangen kann. Dieser Weg (A) steht also nur dem Gegner offen, und kostet diesen 1. Jede dick dargestellte Gabelung ohne Wertangabe entspricht einem Existenzquantor: Der Sucher kann sich den Weg aussuchen. Jede dick dargestellte Gabelung mit Wertangabe entspricht einem All-Quantor. Hier kann der Gegner durch geeignetes Zuweisen der Werte die Entscheidung des Suchers festlegen. Ist eine derartige Entscheidung getroffen, kann der Sucher von einem der mit 0 oder 1 markierten Knoten aus den ”Ausgang” aller Klauseln (K¨ astchen) sehen, die die entsprechende Variable mit der entsprechenden Belegung beinhalten. Schließt der Gegner diese nicht, so hat der Sucher einen Weg der L¨ ange ≤ m + |V | gefunden, der nach Wahl von m r-kompetetiv ist. Kann der Sucher auf diese Weise alle Klauseln erreichen, muß der Gegner alle Ausg¨ ange schließen, wodurch der k¨ urzeste Of�ine-Weg eine L¨ ange ≥ M erh¨ alt, der Algorithmus also ebenfalls kompetetiv ist. Bleibt aber eine Klausel unerreicht und werden die anderen geschlossen, so kann der Gegner ¨ uber Weg A mit Kosten ≤ m + |V | t erreichen, w¨ ahrend der Sucher ≥ M ben¨ otigt. Es gibt offenbar genau dann eine allgemein kompetetive Strategie, wenn der Sucher an jeder Existenz-Entscheidung so entscheiden kann, daß egal, wie die ∀-Entscheidungen getroffen werden, alle Klauseln erreicht werden k¨ onnen, d.h. genau dann, wenn es eine L¨ osung des korrespondierenden Q-SAT-Ausdrucks gibt.

4 Erforschen von Graphen

Andre’s Kram

5 Erforschen von Hindernisparcours

5.1 De�nitionen und Vereinbarungen

De�nition 5.1.1 (Aspect Ratio) Unter der ”Aspect Ratio” α eines allgemeinen Polygons versteht man das Verh¨ altnis von Umkreis- zu Inkreisradius.

De�nition 5.1.2 (Aspect Ratio eines Rechtecks) Bei einem Rechteck bezeichnet man als Aspect Ratio das Verh¨ altnis der l¨ angeren Seite zur k¨ urzeren.

• Sucher: Die aktuelle Suchposition. z.B. ein Robot

• Gegner: Wenn nicht anders angegeben, handelt es sich um einen OBLIVIOUS Gegner, der den Algorithmus nicht kennt und dem die Aktionen seines Gegners bis zum jeweiligen Zeitpunkt seiner Entscheidung bekannt sind; dies ist kein OB-LIVIOUS Gegner in dem Sinn, wie er im allgemeinen Online-Bereich verwandt wird, sondern eine eingeschr¨ ankte Variante eines adaptiven of�ine-Gegners, diese Art der Bezeichnung scheint sich im Umgebungskontext aber durchgesetzt zu haben [24].

5.2 Ver¨ anderungen gegen¨ uber der Graphenproblematik

Betrachtet man den Visibility-Graphen eines Online-Environmentproblems (s. 2.2), so kann der Eindruck entstehen, daß durch Verwenden der f¨ ur Graphen entwickelten Methoden s¨ amtliche Online-Environment Probleme gel¨ ost werden k¨ onnen. Dies ist aber nicht der Fall, da durch die Abstrahierung mit Graphen wesentliche Strukturinformationen verlorengehen[6]. Insbesondere erzeugen die Kenntnis des Zielpunktes und das Wissen, wann man einen Kreis geschlossen hat, so wie Beschr¨ ankungen die den Kanten durch ihre Lage im ℝ^{2} auferlegt werden, eine v¨ ollig neue Gewichtung der Kanten. Diese l¨ aßt sich allerdings nicht so intuitiv, wie man vermuten m¨ ochte zur Modi�kation der Strategien einsetzen. Hierzu m¨ oge folgendes Gegenbeispiel aus [23] als Anschauungshilfe dienen:

Abbildung 5.2.1 (Gegenbeispiel)

Offenbar w¨ urde ein Algorithmus, der der Strategie folgt, das Skalarprodukt zwischen dem Bewegungsvektor und dem zum Ziel zeigenden Vektor zu maximieren,in bestimmten F¨ allen nicht terminieren.

5.3 Einige grundlegende Ergebnisse

Das wohl grundlegenste Problem aus diesem Bereich besteht darin, auf einer Geraden einen konkreten Punkt in unbekannter Entfernung zu �nden (nach [1]).

Abbildung 5.3.1 (Dimension:1)

Zur L¨ osung dieses Problemes verwendet man eine ”Verdopplungsstrategie”: Man gehe zun¨ achst k Schritte nach links, von dort 3k Schritte nach rechts, dann 6 Schritte nach links usw. , so daß der Abstand von der Anf¨ anglichen Startposition im iten Schritt 2^{i} ist.

Behauptung 5.3.1 (Verdopplung) Die obige Strategie ist 9-kompetetiv, und dies ist optimal.

Es ergibt sich kanonisch das Problem, einen Punkt auf mehreren Geraden zu suchen, das sog. Cow-Path-Problem:

Abbildung 5.3.2 (Cow-Path)

Hier verdoppelt man bei jedem Wegwechsel (zyklisch) die zur¨ uckgelegte Strecke. Angewandt auf das Problem einen Zielpunkt in einem nichtkonvexen Polyeder zu �nden (nach [5]), ergibt sich sofort, daß es hierf¨ ur keinen in der Anzahl der Hindernisse (hier 1) kompetetiven Algorithmus f¨ ur dieses Problem geben kann.

Abbildung 5.3.3 (Nichtkonvexe Hindernisse)

Hier geht man dann zur Anzahl der Ecken des jeweiligen Polyeders ¨ uber, und erh¨ alt, daß f¨ ur einen randomisierten Algorithmus eine Kompetetivit¨ at von \frac{|V |}{8} nicht unterschritten werden kann ([5]).

5.4 ¨ Ubersicht ¨ uber die Problemstellungen und Begr¨ undung der Auswahl

Aufgrund der (wenn auch eher zuk¨ unftigen) Anwendungsrelevanz dieses Themas gibt es viele Auspr¨ agungen der Problematik. Des weiteren f¨ uhrt die generelle oder praktische Unl¨ osbarkeit allgemeiner Problemstellungen (s.vgl. 5.5.1 auf Seite III-11) dazu, daß man verschiedene F¨ alle mit verschiedenen Einschr¨ ankungen betrachten muß, um L¨ osungsstrategien f¨ ur m¨ oglichst viele Situationen zu entwickeln. Wie auch bei den Graphen ist hier eine Klassi�zierung nach Endzust¨ anden und Online-Begrenzungs-funktionen m¨ oglich: Man �ndet in der Literatur ¨ uberwiegend zwei F¨ alle:

• FIND: K_{fin} = {K = (W̃ , F̃, p)|p = t_{0} ∈ R^{2}}, d.h. das Ziel ist es, einen konkreten Zielpunkt (Target) zu erreichen.

• MAP: K_{fin} = {K = (W̃ , F̃, p|W̃ = W ^{6}}

Des weiteren ergibt sich die Online-Begrenzungsfunktion kanonisch aus den Eigenschaften des ”Wahrnehmungsorgans” i.e. des Sensors der betreffenden Maschine: Hier gibt es im wesentlichen drei F¨ alle, die alle einer De�nition gen¨ ugen:

𝔒(X) = \{y|∃x ∈ X ∧ \overline{xy} ∩ ⋃_{i∈I} H_{i} = ∅ ∧ min_{x∈X} ∥y − x∥ ≤ d\}

Wobei man die beiden F¨ alle d = 0 (BOUNCE) und d = ∞ (SEE) am ausf¨ uhrlichsten behandelt hat. Man �ndet aber noch viele Spezialf¨ alle:

• Search Party Problem [16] Statt einem Sucher gibt es hier k St¨ uck. Dieses Problem wird durch die gegebenen De�nitionen nicht gedeckt (man bilde das kfache carteisische Produkt), da komplexe Kommunikationsstrukturen zwischen den Suchern gegeben sein k¨ onnen.

• Mehrfaches Suchen [3] Die selbe Suchaufgabe soll mehrfach ausgef¨ uhrt werden. Da bei jedem Suchvorgang mehr Informationen gewonnen werden k¨ onnen, kann der Weg immer weiter verbessert werden. Amortisiert ist hier zun¨ achst DFS auf dem Visibility-Graphen und dann k−1 faches Verwenden des optimalen (offline) Weges ideal. [3] zeigen aber eine Variante, diesen zu gl¨ atten. Hier treten die selben Endkon�gurationen wie bei FIND auf, aber man kann diese (zun¨ achst) wieder verlassen, und zudem ist eine Zielfunktion Υ gegeben durch

Υ(K) := L¨ ange des k¨ urzesten Pfades von s nach t in (Ŵ , F̂)

Eine weitere Differenzierung ergibt sich nach der Form der Hindernisse. Hier unterscheidet man zwischen Objekten mit beschr¨ ankter bzw unbeschr¨ ankter Aspect Ratio, zwischen konvexen und nichtkonvexen Polyedern und betrachtet zumeist rechteckige Hindernisse. Bei der Auswahl der genauer betrachteten Probleme waren wir bem¨ uht einerseits einen Querschnitt durch die Gesamtproblematik zu erzielen, und andererseits einige herausragende Ergebnisse zu pr¨ asentieren. Die folgende Tabelle gibt einen groben ¨ Uberblick. Die eingerahmten Felder werden im weiteren genauer betrachtet werden. Die angegebenen Komplexit¨ atsschranken wurden in dieser Form in der Literatur gefunden, n¨ ahere Angaben �nden sich dort. (D: deterministisch,R: randomisiert).

Abbildung 5.4.1 (Uebersicht) III-10

5.5 Bounce and Find

5.5.1 Untere Grenzen

Satz 5.5.1 (Lower Bound I) Es gibt keinen kompetetiven Algorithmus f¨ ur Bounce and Find, f¨ ur einen offensichtlichen Gegner.

Beweis: Man betrachte folgendes Beispiel: Gegeben ein Startpunkt s und eine Ziellinie t in einem ausreichend großen Gebiet A. Sei z.B. x der Nullpunkt in einem Koordinatensystem und t die Gerade x = n. Dann wartet der Gegner jeweils, bis der Sucher eine x-Koordinate zum ersten Mal erreicht und plaziert dann ein Hindernis H_{i} der H¨ ohe n vor diesem, so daß dieser einen Umweg von \frac{n}{2} machen muß, um das Hindernis zu umgehen. Zum erreichen der Ziellinie muß der Sucher also einen Weg der L¨ ange Ω(n^{2}) zur¨ ucklegen. Nach dem Schubfachprinzip gibt es aber eine y-Koordinate k im Intervall [0, n\sqrt{n}], die nur \sqrt{n} Hindernisse trifft, da jedes der n Hindernisse n ganzzahlige Koordinaten ¨ uberdecken kann. D.h. indem man zun¨ achst zum Punkt(0, k) geht, dann entlang der (z, 0)-Linie \sqrt{n} Objekte mit einem Aufwand von \frac{n}{2} umgeht, was zu einem Gesamtaufwand von O(n\sqrt{n}) f¨ uhrt, und somit einen kompetetiven Koef�zienten von O(\sqrt{n}) erzwingt.

Korollar 5.5.1 (Lower Bound I’) Das gleiche gilt nat¨ urlich f¨ ur jede Art von schmalem, hohem Hindernis

Stellt man also fest, daß der allgemeine Fall unl¨ osbar ist, so betrachte man zun¨ achst den einfachst m¨ oglichen: Quadratische Hindernisse (Aspect Ratio 1):

Korollar 5.5.2 (Lower Bound II) F¨ ur quadratische Hindernisse kann man eine Competetive Ratio von \frac{3}{2} nicht unterschreiten.

Beweis: Es gen¨ ugt dieselbe Konstruktion wie oben, es kann nun garantiert werden, daß der Sucher wenigstens die Strecke n ∗ 1.5 zur¨ ucklegen muß, w¨ ahrend der Optimale Weg die L¨ ange n + O(\sqrt{n}) hat.

5.5.2 45-Grad-Heuristik

Lemma 5.5.1 (45-Grad) Liegen Start und Zielpunkt relativ zur Ausrichtung der Hindernisse im Winkel von 45^{∘} zueinander, kann man einen kompetetiven Faktor von \sqrt{2} erreichen.

Abbildung 5.5.1 (45-Grad)

5.5.3 Bias-Heuristik

Als erstes einfaches Beispiel sei ein Verfahren angef¨ uhrt, daß (im Grenzwert) f¨ ur quadratische Hindernisse gleicher Seitenl¨ ange (o.B.d.A. 1) einen kompetetiven Faktor von 1.5 garantiert.

Algorithmus 5.5.1 (Bias-Heuristik) (Papadimitrou & Yanakis)

Zu Begin sei β := ϵ := \frac{1}{\sqrt{n}} repeat

Solange kein Hindernis ber¨ uhrt wird:

Bewegung parallel zur Start-Ziel-Linie. SONST:

Ist das n¨ aher zur Start-Ziel-Linie gelegene Ende des Hindernisses weniger als \frac{1}{2} + β entfernt, gehe zu diesem Ende und verringere β um ϵ

SONST

W¨ ahle das andere Ende und erh¨ ohe β um ϵ

until Ziellinie ist erreicht. Bewegung senkrecht zur Start-Ziel-Linie zum Zielpunkt.

Satz 5.5.2 (Bias-Heuristik) Die untere Schranke von \frac{3}{2} wird durch den ”Bias-Algo-rithmus” asymptotisch erreicht.

Beweis: Es sind folgende Bedingungen erf¨ ullt:

• An jedem der n ber¨ uhrten Hindernisse wird maximal die Strecke \frac{1}{2} + β zur¨ uckgelegt.

• Der Roboter entfernt sich maximal O(\sqrt{n}) von der Start-Ziel-Linie, da f¨ ur β = \frac{1}{2} immer die n¨ aher an der Start-Ziel-Linie gelegene Richtung gew¨ ahlt wird.

• Mit jedem Schritt, mit dem n¨ aher an die x-Achse herangehen und eine Strecke von mehr als \frac{1}{2} + ϵ zur¨ ucklegt wird, muß der Roboter sich zuvor entfernt haben, also eine Strecke von weniger als \frac{1}{2} − ϵ zur¨ uckgelegt haben. So daß bei jedem Hindernis maximal ein zus¨ atzlicher Aufwand von ϵ verbleibt.

Als Schranke f¨ ur die Gesamtstrecke erhalten wir somit:

n + \frac{1}{2}n + n ∗ \frac{1}{\sqrt{n}} + O(\sqrt{n})

Die L¨ ange eines k¨ urzesten Weges von s nach t muß aber mindestens die L¨ ange n haben, wodurch man als asymptotische Grenze 1.5 erh¨ alt.

5.5.4 Beliebig orientierte rechtwinklige Hindernisse

Im folgenden wird ein Algorithmus von Karpinski [17] wiedergegeben, der f¨ ur das Problem beliebig orientierter Rechtecke mit Breite mindestens 1 eine Schranke von n^{\frac{3}{4}} garantiert.

Algorithmus 5.5.2 (Karpinski-Grundform) (Karpinski, Berman)

Alle im folgenden angegebenen Prozeduren werden von folgender Hauptroutine aufgerufen:

set(m,l); repeat

rand.set(r)

for phase.no := 1 to m do

for attack.no :=-(m-1) to m-1 do lower := line {y = (i − 1)l} upper := line {y = (i + 1)l} central := line {y = il} attack(attack.no);

l := 2 ∗ l forever

Ein Durchlauf der ¨ außersten Schleife sei als STAGE bezeichnet, ein Durchlauf der ”phase”-Schleife als PHASE Zun¨ achst sei ein deterministischer Algorithmus f¨ ur orientierte Rechtecke betrachtet: In set(m,l) seien gew¨ ahlt: m := ⌈\sqrt{n}⌉ und l = m.

Algorithmus 5.5.3 (Karpinski I)

Attack(i):repeat Gehe bis zum n¨ achsten Hindernis. if es erstreckt sich von lower bis upper

exit. else

umgehe es um die n¨ ahere Kante zur¨ uck zu central forever

Satz 5.5.3 (Karpinski I) Durch Karpinski I wird ein kompetetiver Faktor von O(m) = \sqrt{n} erreicht.

der Satz folgt unmittelbar aus den folgenden Lemmata:

Lemma 5.5.2 (Obere Schranke) Der Weg des Suchers bis einschließlich STAGE l ist beschr¨ ankt durch O(m^{2}l).

1. Die außerhalb der Attacken zur¨ uckgelegte Strecke ist beschr¨ ankt durch O(6m^{2}l)

2. Blockiert ein Objekt mehrere Phasen, so wird abgebrochen. Ansonsten erreicht man In jedem 2l. Schritt einer Attacke (summiert ¨ uber einen ganzen loop) einen Fortschritt von mindestens 1.Es k¨ onnen also in den jeweiligen Attacken also h¨ ochstens nl = m^{2}l Schritte auftreten.

Lemma 5.5.3 (Untere Schranke) Wurde das Ziel in STAGE l nicht erreicht, so hat ein k¨ urzester Weg mindestens die L¨ ange Ω(ml)

Beweis: Fall 1: Alle PHASEN dieses STAGE wurden vom selben Hindernis aufgehalten. Dann muß dieses Hindernis die L¨ ange ml haben, jeder k¨ urzeste Weg muß also wenigstens \frac{1}{2}ml lang sein. Fall 2: Da in m Phasen das Ziel nicht erreicht wurde, muß es wenigstens m disjunkte ”Phasenbarrieren” (vgl. Abbildung) geben. Offenbar muß jeder k¨ urzeste Weg entweder die Barrieren umgehen oder jeweils eine Distanz von l zur¨ ucklegen, um eine jeweilige Barriere zu ¨ uberwinden. Da jede Barriere die H¨ ohe ml hat, und m vorhanden sind, sind hierzu mindestens ml Schritte notwendig.

Abbildung 5.5.2 (Karpinski I)

Beim ¨ Ubergang auf bliebig orientierte Rechtecke wird nun davon ausgegangen, daß der Roboter,wenn er auf ein Hindernis trifft, dessen Steigung sp¨ uren kann. Der Roboter kann sich entlang eines solchen Hindernisses dann entweder zum Ziel hin und von der momentanen ”Angriffslinie” weg oder vom Ziel weg zur momentanen Angriffslinie hin bewegen.

Abbildung 5.5.3 (Karpinski II)

Man kann nun den Wert, bei dem die Entscheidung getroffen werden soll, mit dem Zufallsgenerator so bestimmen, daß eine gute Schranke garantiert werden kann. Hierzu w¨ ahle man in set(m, l), bzw. rand.set(r):

m := ⌈n^{0.25}⌉ l := m^{3} r aus {m^{2} + 1, ⋯ 2m^{2}}

Das oben beschriebene Vorgehen wird durch folgende Subroutine realisiert:

Algorithmus 5.5.4 (Stabilize(line))

stabilize(line): repeat

if nicht an einem Hindernis

then gehe Richtung Ziel else if feel > r then

folge dem Hindernis Richtung Ziel else folge dem Hindernis Richtung line

until line ist erreicht, ein Hindernis ber¨ uhrt und feel ≤ r

Unter Verwendung dieser Routine kann man nun die neue Angriffsvariante angeben:

Attack(i): repeat

if in diesem Stage zur¨ uckgelegter Weg > cm^{4}l then exit stabilize(central); if Hindernis sperrt von lower bis upper

exit else

folge dem Hindernis um die n¨ ahere Ecke zur¨ uck zu central forever

Satz 5.5.4 (Karpinski II) der Algorithmus Karpinski II hat eine Kompetetivit¨ at von O(m^{3}) = O(n^{\frac{3}{4}} )

Beweis: Es sei L die L¨ ange des k¨ urzesten Weges.

• in STAGE l wird maximal cm^{4}l zur¨ uckgelegt.

• Wird das Ziel in STAGE l nicht erreicht und der STAGE korrekt beendet, ist der erwartete Weg l¨ anger als ml.

• Es muß also die L¨ ange der Wege abgesch¨ atzt werden, die in STAGE mit ml > L zur¨ uckgelegt werden, in denen dieses wegen eines Abbruchs nicht ”bemerkt” wurde.

• Die Wahrscheinlichkeit, daß ein STAGE nicht korrekt beendet wird, ist kleiner als \frac{1}{4}.

• F¨ ur alle diese STAGES verdoppelt sich also die erlaubte Pfadl¨ ange, w¨ ahrend die Wahrscheinlichkeit, diesen STAGE ¨ uberhaupt noch auszuf¨ uhren um den Faktor 4 sinkt (s.u.). D.h jeder weitere (wegen eines Abbruchs aufgerufene) STAGE tr¨ agt im Erwartungswert h¨ ochstens die H¨ alfte des Vorangegangenen zur erwarteten Pfadl¨ ange bei.

• Summiert ¨ uber die m¨ oglichen STAGES ergibt sich also, daß die L¨ ange des Weges, der in STAGES zur¨ uckgelegt wird, f¨ ur die abgebrochen wird, obwohl der k¨ urzeste Pfad kleiner als ml ist, als die doppelte (∑_{i=0}^{∞} \frac{1}{2} = 2) L¨ ange des letzten STAGES, in dem diese Bedingung noch erf¨ ullt war.

Im folgenden wird der Beweis, daß jeder Stage mit der Wahrscheinlichkeit \frac{3}{4} beendet wird kurz skizziert. F¨ ur den exakten Beweis siehe [17].

• Die Bewegung des Roboters ist auf das Trapezoid (−2m^{3}, ±ml), (n, ±(m + 1)ml) beschr¨ ankt. Dies ergibt sich durch Nachrechnen: In Richtung Central kann man h¨ ochstens ml zur¨ ucklegen, und dabei um rm < 2m^{3} zur¨ uckgehen. Angefangen von (−rm, ml) kann man h¨ ochstens (rm + m^{4}) nach rechts und somit (l/r)(rm + m^{4}) ≤ (1 + m)ml nach oben gehen.

• Mit Wahrscheinlichkeit 3/4 ist die Gesamtl¨ ange der Hindernisse mit feel > r durch 6m^{4}l begrenzt: Die Gesamtl¨ ange aller Hindernisse ist durch die Fl¨ ache begrenzt, da man eine Dicke der Hindernisse von wenigstens 1 voraussetzt. Der Erwartungswert ist 1.5m^{4}l, woraus mit der Chebyshevschen Ungleichung eine Abweichung um mehr als 4 mit einer Wahrscheinlichkeit ≤ 1/4 auftritt.

• Wenn man zul¨ aßt, daß der Robot Hindernissen mit feel > r im Ausmaß von 6m^{4}l begegnet, so muß er h¨ ochstens 30m^{4}l Schritte zur¨ ucklegen, um das Ziel zu erreichen. Dies ergibt sich durch eine aufwendige Fallanalyse, die in der Originalquelle nachzulesen ist.

• W¨ ahlt man also c := 30 im Programm, so ist der Satz korrekt.

Karpinski und Berman verallgemeinern ihre Ergebnisse noch auf beliebige konvexe Polyeder (s. [17]).

5.6 Map and See

5.6.1 Allgemeines und Of�ine-Fall

In diesem Kapitel soll der ”Map und See” Fall mit der zus¨ atzlichen Annahme daß I = ∅ ist, d.h. das es keine Hindernisse gibt, betrachtet werden. Aufgabe ist es, ausgehend von einem gegebenen Startpunkt am Rand die gesamte H¨ ulle des Polygons kennenzulernen, und dabei einen m¨ oglichst kurzen Weg zur¨ uckzulegen. Betrachtet man zun¨ achst einmal den Of�ine-Fall, so ergibt sich intuitiv die in der Literatur fast ¨ uberall konsistente De�nition von ”Line-Segments” und ”Essential Segments”:

De�nition 5.6.1 (Line-Segment) Verl¨ angert man eine beliebige Kante des Polygons solange, bis sie das Polygon verl¨ aßt, so bezeichnet man die abgetrennten Teile des Poygons (so vorhanden) als Line-Segmente. Muß ein solches Segment betreten werden, um alle Punkte des Polygons betrachten zu k¨ onnen, so nennt man es ein notwendiges Line-Segment

De�nition 5.6.2 (Essential Segment) Jedes notwendige Segment, daß nicht automatisch betreten werden muß, wenn man ein (bestimmtes) anderes notwendiges Segment besuchen will, wird als ”Essential Segment” bezeichnet.

In der folgenden Abbildung sind - unter der Annahme, daß s der Startpunkt ist - die notwendigen Segmente liniert, die essentiellen dunkel markiert.

Abbildung 5.6.1 (Line Segments)

Im folgenden wird der rechtwinklige Of�ine-Fall (nach [10]) anhand eines Beispiels beschrieben. Der allgemeine Fall folgt dem gleichen Prinzip, ist aber mit erh¨ ohtem technischem Aufwand verbunden.Offenbar ist eine Tour, die im Uhrzeigersinn die essentiellen Segmente besucht, optimal, da man eine Tour, die sich selbst schneidet, durch eine k¨ urzere Tour ersetzen kann, bei der dies nicht der Fall ist.

Abbildung 5.6.2 (Selfcut)

Es verbleibt also lediglich, den jeweiligen Punkt zu bestimmen, bei dem man das entsprechende Segment ber¨ uhrt. Man betrachte also das Problem, in diesem Polygon eine optimale Tour zu bestimmen.

Abbildung 5.6.3 (Problemstellung)

Zun¨ achst identi�ziert man die essentiellen Segmente, und bestimmt das Polygon, das nach deren Entfernen entsteht. Das Problem kann nun so aufgefaßt werden, daß die grau schattierten Kanten des reduzierten Polygons betrachtet werden sollen.

Abbildung 5.6.4 (Reduktion)

De�nition 5.6.3 (Essentielle Kante) Unter einer Essentiellen Kante versteht man eine Kante des Reduzierten Polygons, die an der Stelle neu entstanden ist, an der ein essentielles Segment entfernt wurde.

Die verwendete L¨ osung entspricht der Vorstellung des ”Lichtweges” in der Physik. Man spiegelt das Polygon an den zu besuchenden Kanten (im Uhrzeigersinn) und bestimmt dann einen k¨ urzesten Weg vom Startpunkt zu seinem Bild im letzten erzeugten Spiegelbild. Es ergibt sich leicht aus der geometrischen Anschauung, daß dieser Weg die notwendigen Kanten genau dort schneidet, wo sie im Ursprungsbild ber¨ uhrt werden m¨ ußten.

Abbildung 5.6.5 (Spiegelung)

Transformiert man dies wieder in das Ausgangsproblem zur¨ uck, so erh¨ alt man eine optimale Tour (auch Optimum-Watchman-Tour genannt).

Abbildung 5.6.6 (Loesung)

Bei der Verallgemeinerung auf einfache Polygone tritt zus¨ atzlich das Problem auf, daß man bei mehreren ¨ uberlappenden essentiellen Segmenten entscheiden muß, welches man besucht. Siehe hierzu [11],[9].

5.6.2 Ein \sqrt{2}-kompetetiver Algorithmus f¨ ur den rechtwinkligen Fall.

Schr¨ ankt man sich zun¨ achst auf den Fall eines rechteckigen Polygons ein, so ist ein guter Algorithmus bekannt [12],[13]. Die wesentliche Idee besteht darin, von der euklidischen (L_{2}) auf die Betragsnorm (L1) zu wechseln, da es unter dieser irrelevant ist, an welcher Stelle man auf die essentielle Kante trifft.

Abbildung 5.6.7 (L2-Norm)

Der Algorithmus verh¨ alt sich ansonsten intuitiv, d.h. er untersucht die jeweils n¨ achste unbekannte Position.

De�nition 5.6.4 (l(f), r(f)) F¨ ur einen Punkt f auf dem Rand des Polygons ist r(f) (l(f)) diejenige Kante, die f im (gegen den) Uhrzeigersinn folgt.

Algorithmus 5.6.1 (Rect) (Deng,Kameda,Papadimitriou)

Sei f derjenige Punkt des Polygons, der das (in Uhrzeigerrichtung) Ende des bekannten Teils des Polygons darstellt, das den Startpunkt enth¨ alt. Der Algorithmus folgt nun diesen drei Schritten, wobei x der momentane Ort und x_{0} der Startpunkt ist:

1. f kann von x aus gesehen werden, und ist eine 270-Grad Ecke: Gehe senkrecht auf r(f) zu, bis es oder seine Verl¨ angerung erreicht wird. Sollte dabei ein weiteres Hindernis getroffen werden, bewege man sich solange parallel zu r(f) bis die Sicht wieder hergestellt ist.

Abbildung 5.6.8 (Deng A1)

2. f ist innerer Punkt einer Kante r(f) = l(f). Dann gibt es eine die Sicht zu f blockierende Ecke b (bei mehreren w¨ ahle die n¨ achste). Man verhalte sich zu l(b) wie zu r(f) unter 1.. Sieht man dann f immer noch nicht, geht man entlang von l(b).

Abbildung 5.6.9 (Deng A2)

3. f kann von x aus nicht gesehen werden. Je nachdem ob f beim lezten Sehen gem¨ aß 1. oder 2. wahrgenommen wurde, bewege man sich (wo schon bekannt auf dem k¨ urzesten Weg) zu r(f) bzw. l(b)

Abbildung 5.6.10 (Deng A3)

Satz 5.6.1 (DKP) Der Algorithmus RECT hat eine Kompetetivit¨ at von 1 bez¨ uglich der Betragsnorm

Korollar 5.6.1 (DKP ’) RECT ist \sqrt{2}-kompetetiv bezueglich der euklidischen Norm.

Beweis des Satzes: Es wird im folgenden nur eine Beweis-Skizze gegeben. F¨ ur den vollst¨ andigen und recht umfangreichen Beweis siehe: [13] Es bleiben nach obigen Betrachtungen noch zwei Dinge zu zeigen:

1. Zwischen den Segmenten wird ein in der L_{1}-Metrik optimaler Weg gew¨ ahlt. Zun¨ achst ist nur klar, daß ein Weg gew¨ ahlt wird, der minimal oft seine Richtung ¨ andert. Man kann nun durch Induktion zeigen, daß in rechtwinkligen Polygonen ohne Hindernissen ein k¨ urzester Weg in dieser ”Link-Distanz” auch ein k¨ urzester Weg in der L_{1} Metrik ist.

2. Es werden die richtigen Segmente besucht.

• jedes Segment, das besucht wird ist notwendig, da es an der entsprechenden Stelle etwas liegen muß, was noch nicht gesehen wurde

• Alle essentiellen Segmente werden besucht, da der Algorithmus erst terminiert, wenn es keine unbekannten Stellen mehr gibt.

• Der Besuch notwendiger Segmente vergr¨ oßert (in der L_{1}-Metrik) den zur¨ uckgelegten Weg nicht, da jedes dieser Segmente entweder selbst essentiell ist, oder ein essentielles Segment enth¨ alt.

3. Die essentiellen Segmente werden in der richtigen Reihenfolge besucht. Dies ist nicht generell der Fall, denn es kann wie man in Abbildung 3 erkennt vorkommen, daß sich zwei essentielle Segmente schneiden, und somit die im reduzierten Polynom gegebene Reihenfolge, von zwei entgegengesetzt liegenden Kanten erzeugt werden, die Kanten also nach Konstruktion in umgekehrter Reihenfolge besucht werden. (Die x_{i} und die y_{i} beschreiben die beiden verschiedenen Wege.)

Abbildung 5.6.11 (Segmentschnitt)

Es ist aber der ¨ ubern¨ achste Punkt, der in beiden Reihenfolgen besucht wird wird, auf jeden Fall der Schnittpunkt der beiden Segmente, d.h.:

x_{i} ≠ y_{i} ⇒ (x_{i+1} = y_{i+1} ∧ x_{0} = y_{0}).

Es gen¨ ugt also zu zeigen, daß die Wege, die zwischen x_{i−1}und x_{i+1} bzw. y_{i−1} und y_{i+1} zur¨ uckgelegt werden gleichlang sind (in der L_{1}- Metrik). Nun kann man aber leicht sehen, daß nach Konstruktion x_{i} auf dem k¨ urzesten x_{i−1}, x_{i+1}- Weg liegt, und y_{i} auf dem k¨ urzesten y_{i−1}, y_{i+1}-Weg liegt. Damit folgt die Gleichheit der Abst¨ ande. Konstruktionen wie in [20] lassen vermuten, daß \sqrt{2} optimal ist.

5.6.3 Ein 133-kompetetiver Algorithmus f¨ ur nicht rechtwinklige einfache Polygone

Der folgende Abschnitt gibt im wesentlichen den Algorithmus aus [15] wieder. Dieser Algorithmus verzichtet auf das Aufsp¨ uren von essentiellen Kanten und strebt danach, bestimmte Ecken des Polygons zu untersuchen (wobei die zugeh¨ origen Segmente in einem untersucht werden.). Es ist klar, daß, wenn man auf einer engen Straße eine Links- und eine Rechtskurve einander folgen l¨ aßt, der k¨ urzeste Weg ¨ uber diese Strecke die beiden Ecken der Kurven miteinander verbinden muß. Will man diese Eigenschaft ausnutzen, so erweisen sich folgende De�nitionen als sinnvoll:

De�nition 5.6.5 (Links-Ecke) Eine Links (rechts) Ecke ist eine Ecke mit einem Winkel gr¨ oßer 180 Grad die vom Baum der k¨ urzesten Pfade ber¨ uhrt wird, und die von der Wurzel des Bauems aus (dem Startpunkt es Robots aus) nach links (rechts) abbiegt.

De�nition 5.6.6 (Door) Eine ”T¨ ur” ist eine Kante im K¨ urzeste-Wege-Baum, die eine Ecke vom Links(Rechts)-Typ mit ihrem ersten Nachfolger des entgegengestezten Typs verbindet.

De�nition 5.6.7 (Hinge) Eine ”Hinge” ist die im Baum h¨ oher liegende Ecke einer T¨ ur.

De�nition 5.6.8 (Right-Door) Eine Rechts-T¨ ur ist eine T¨ ur, deren Hinge eine rechts-Ecke ist.

Der folgende Algorithmus beruht darauf, das Polygon in einzelne R¨ aume zu partitionieren, die jeweils durch T¨ uren getrennt sind. Dabei ”erbt” der jeweilige Raum den Typ der T¨ ur, durch die er betreten wurde, wird aber ansonsten durch T¨ uren des entgegengesetzten Typs begrenzt. Die Partitionierung wird online vorgenommen, indem die jeweiligen T¨ uren erst dann passiert werden, wenn der Raum vollst¨ andig untersucht wurde. Nachdem ein jeweiliger Raum abgearbeitet ist, werden nacheinander alle R¨ aume untersucht, die hinter T¨ uren liegen, die nicht mit der Eingangst¨ ur identisch sind. Diese Aufgabe wird von der Procedure SAM wahrgenommen. Sie bedient sich hierbei der Scout-Funktionen, die dazu dienen, die T¨ uren aufzusp¨ uren. Da an jeder unbekannten Stelle eine T¨ ur liegen k¨ onnte wird hierbei gleichzeitig der entsprechende Raum v¨ ollig kartographiert. Die Explore-Prozeduren dienen dazu, jeweils konkrete Wege zur¨ uckzulegen.

Algorithmus 5.6.2 (SAM) (Hoffmann,Icking,Klein,Kriegel)

var HingeList; HingeList := Scout(x); forall y of HingeList in counterclockwise order do

MarchTo(y); SAM(y);

MarchTo(x);

Die folgende Abbildung veranschaulicht das Vorgehen von SAM. Die eingezeichneten Wege werden dabei von MarchTo zur¨ uckgelegt.

Abbildung 5.6.12 (SAM)

Scout dient dazu, die Hinges der jeweiligen R¨ aume zu bestimmen. Im folgenden soll davon ausgegangen werden, daß es sich um einen Rechts-Raum handelt, d.h. es wird nach Links-T¨ uren gesucht. Der andere Fall ist symmetrisch. Es geht also darum alle aufeinanderfolgenden Links-Rechts Eckenkombinationen zu bestimmen. Scout verwendet hierzu die Subroutinen Scout1 und Scout2. Die erste dient dazu, zun¨ achst alle Links-Ecken, die hinter einer Rechts-Ecke verborgen sind, zu �nden, so daß die zweite dann mit einer korrekten Liste aller Links-Ecken starten kann. Diejenigen Ecken, die von einer Prozedur zur anderen ¨ ubergeben werden sind in 5.6.3 markiert.

Algorithmus 5.6.3 (Scout)

var LList, HList; LList:=Scout1(x); Hlist:=Scout2(x,LList); return HList;

Algorithmus 5.6.4 (Scout1(x))

var RList,LList,Basepoint; insert all right-vertices visible from x into RList; whileRList ≠ ∅ do

Explore1(RList,BasePoint,LList);

MarchTo(closest point to x_{0} on Cut^{7} of First(RList)); BasePoint:=current position;

MarchTo(x); return LList

Die Funktion Scout2 ist analog aufgebaut, lediglich wird die von ihm verwendete LList (in Scout1 RList) mit der Ausgabe von Scout1 initialisiert.

Abbildung 5.6.13 (Scout)

Die beiden Explore-Routinen ¨ ubernehmen die Bewegung zwischen den einzelnen Base-Points (siehe Pseudocode). Dabei wird die n¨ achste Ecke so angegangen, daß bei Ber¨ uhren des zugeh¨ origen Segments der Abstand zum Ausgangspunkt minimiert wird. Zu diesem Zweck folgt man einem Kreis, der seinen Mittelpunkt im Mittelpunkt der Strecke vom Ausgangspunkt zur Ecke hat. Mit dem Satz des Thales ergibt sich somit, daß in dem Punkt, in dem man das Segment ber¨ uhrt ein rechter Winkel zwischen Segment und gerader Verbindung zum Basepoint entsteht. Sollten dabei Hindernisse den Weg blockieren, gehe man auf geradem auf das Ziel zu, bis das Hindernis verschwindet. Sollte sich LList w¨ ahrend des Vorgehens ver¨ andern, schwenkt man sofort auf das neue Ziel um.

Abbildung 5.6.14 (Explore)

Hier wird nun die Prozedur Explore2 beschrieben, die an der entsprechenden Stelle von Scout2 aufgerufen wird, wie explore1 in Scout1. Explore1 ist analog aufgebaut. Es erzeugt lediglich andere Listen als Explore2

Algorithmus 5.6.5 (Explore2)

MarchTo(First(LList)), until visible; repeat

Follow Circle (oben beschrieben) until First(LList) explored or right Vertex hidden by First(LList) discovered if discovered then insert First(LList) into HList; meanwhile do maintain LList

Satz 5.6.2 (HIKK) Der Algorithmus SAM ist 144-kompetetiv.

Wiederum soll nur eine Beweisskizze gegeben werden.

• Als Absch¨ atzung des von Explore zur¨ uckgelegten Weges gegen¨ uber der k¨ urzestm¨ oglichen Strecke zwischen BasePoint und Cut ergibt sich, wenn keine Hindernisse auftreten:

\frac{Halbkreis}{Durchmesser} = \frac{π}{2}

Durch Fallanalyse blockierender Hindernisse erh¨ alt man: \frac{π}{2} + 1.

• Absch¨ atzung des zur¨ uckgelegten Weges zwischen zwei Base Points gegen¨ uber dem k¨ urzesten Weg: Der Weg des Robots setzt sich zusammen aus dem von Explore zur¨ uckgelegten Weg und dem Wandern auf dem Rand des Segments (Cut). Die auf dem Schnitt zur¨ uckgelegte Strecke l¨ aßt sich wie dargestellt auf den k¨ urzesten Weg projizieren: Wegen

L(BasePoint, a) ≤ K(BasePoint, c) und |ac| < L(BasePoint, c)

gilt: \frac{L(Roboterweg)}{k¨ urzester Weg} ≤ \frac{pi}{2} + 2.

Abbildung 5.6.15 (ac)

• Absch¨ atzung des Verh¨ altnisses der L¨ ange der relativen konvexen H¨ ulle der Sequenz der BasePoints gegen¨ uber der Wegl¨ ange:

Abbildung 5.6.16 (Huelle)

Das kleine Bild am Rande zeigt, daß der ”worst case” genau f¨ ur rechtwinklige Dreiecke auftritt: Offenbar muß gelten: |c_{i−1}c_{i}| + |c_{i}c_{i+1}| ≤ \sqrt{2}|c_{i−1}c_{i+1}|.

• Vergleich der relativen Konvexen H¨ ulle mit dem k¨ urzesten Weg, der den Raum kennenlernt: ”One can show”, dieses Verh¨ altnis ist \frac{π}{2} + 1.

• Somit ist das Verh¨ altnis der von Scout1 bzw. Scout2 zur¨ uckgelegten Strecke gegen¨ uber dem k¨ urzesten Weg, der den entsprechenden Raum kennenlernt beschr¨ ankt durch

(\frac{π}{2} + 2) \sqrt{2} (\frac{π}{2} + 1) ≤ 13

• Durch eine weitere Fallanalyse erh¨ alt man: Das Verh¨ altnis der Summe der Wege zur Erkundung der einzelnen R¨ aume zur Optimum-Watchman Route (W opt) ist 5. Es �ießt z.B. ein, daß man beim Verlassen eines Raumes die Hinge nicht mehr ber¨ uhren muß.

• Die Summe der von SAM zur¨ uckgelegten Wege ist beschr¨ ankt durch 3 ∗ Wopt

Somit ergibt sich insgesamt :

WIcking ≤ ((\underbrace{2}_{Scout 1+2} ∗13 ∗ (5)) + 3)Wopt = 133 Wopt

Es ist allerdings zu vermuten, daß dieses Ergebnis noch verbessert werden kann, da der Robot z.B. im Rahmen von SAM manche Strecken mehrfach zur¨ ucklegt.

Behauptung 5.6.1 (Polynom mit Hindernissen) Da sich das Verfahren analog auf das ¨ Außere von Polyedern ¨ ubertragen l¨ aßt, kann man mit diesem Verfahren einen O(k) kompetetiven Algorithmus zur Erkundung eines Polygons mit k Hindernissen erhalten.

6 Schlußbemerkung und Ausblick

Die dargestellten Strategien vermitteln, so hoffen wir, einen exemplarischen ¨ Uberblick ¨ uber diesen Schnitt der Online-Thematik mit der Graphentheorie bzw. der algorithmischen Geometrie. Das einzige grundlegende Paradigma, daß sich bisher hier �ndet ist das der Verdopplung (5.3). Ansonsten hat jeder der Autoren seine eigenen Ideen verwandt. Hilfen f¨ ur anstehende Probleme kann man in diesem Bereich also nur in Form von Impulsen nicht aber von Methoden erhalten. So erkennt man, daß Sichtwechsel, wie sie [13] mit ihrem ¨ Ubergang zu einer anderen Metrik oder [15] mit dem vor¨ ubergehenden Außerachtlassen der Segmente vollziehen, h¨ au�g zu neuen Ergebnissen f¨ uhren k¨ onnen, aber diese Vorgehensweisen sind wohl nicht klassi�zierbar. Es bleibt zu hoffen, daß wie bei den meisten Problemgebieten mit zunehmender Erschließung eine Vereinheitlichung der Methoden erreicht werden kann, so daß Probleml¨ osungen auseinander ableitbar werden. Ansonsten droht mit dem zunehmenden Einsatz autonomer Roboter auch dieses Gebiet dem in der Informatik ¨ ublichen Problem anheimzufallen:

Einer großen Mengen von Anwendungen auf einer unterentwickelten theoretischen Basis. Die hieraus resultierenden Schwierigkeiten im allgemeinen Engineering sowie insbesondere in der Veri�kation d¨ urften sich auf die Betriebssicherheit der Automaten nicht unbedingt positiv auswirken. Ein weiteres anstehendes Problem ist die Integration der gefundenen L¨ osungen in die Planungsmodelle der k¨ unstlichen Intelligenz. Wie k¨ onnen gewonnene Erfahrungen ¨ uber andere Gebiete zur Optimierung der Suchstrategien verwandt werden? Wie kann man dennoch eine gute Kompetetivit¨ at garantieren? Wird es vielleicht m¨ oglich sein online Online-Verfahren neu zu �nden, oder ist es andererseits m¨ oglich, kognitiven Strukturen eine Bewertungsfunktion zuzuordnen, so daß man einen Kompetetiven Faktor zwischen einem online erlernten System und einem of�ine vorgegebenen bestimmen und somit vielleicht die Methoden der online-Thematik wiederum im KIbereich anwenden kann?

7 Literaturverzeichnis

Literatur

[1] R. Baeza-Yates, J. Culberson, and G. Rawlins. Searching in the plane. Information and Computation, 106(2):234–252, 1993. Preliminary version in Proc. 1st Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science 318, Springer-Verlag, Berlin, 1988, 176–189. Also Tech. Report CS-87-68, University of Waterloo, Department of Computer Science, October, 1987.

[2] Piotr Berman, Avrim Blum, Amos Fiat, Howard Karloff, Adi Rosen, and Michael Saks. Randomized robot navigation algorithms. In Proc. 7th ACM-SIAM Sympos. Discrete Algorithms, pages 75–84, 1996.

[3] A. Blum and P. Chalasani. An on-line algorithm for improving performance in navigation. In Proc. 34th Symp. of Foundations of Computer Science, pages 2–11, 1993.

[4] A. Blum, P. Raghavan, and B. Schieber. Navigating in unfamiliar geometric terrain. In Proc. 23rd Annu. ACM Sympos. Theory Comput., pages 494–503, 1991.

[5] Avrim Blum, Prabhakar Raghavan, and Baruch Schieber. Navigating in unfamiliar geometric terrain. IBM Research Report.

[6] M. Blum and D. Kozen. On the power of the compass (or, why mazes are easier to search than graphs). In Proc. 19th Annu. IEEE Sympos. Found. Comput. Sci., pages 132–142, 1978.

[7] H. L. Bodlaender. Complexity of path-forming games. Theoret. Comput. Sci., 110:215–245, 1993.

[8] Prasad Chalasani. Online Performance Improvement Algorithms. PhD thesis, School of Computer Science Carnegie Mellon University, 1994.

[9] W. Chin and S. Ntafos. Optimum watchman routes. In Proc. 2nd Annu. ACM Sympos. Comput. Geom., pages 24–33, 1986.

[10] W. Chin and S. Ntafos. Optimum watchman routes. Inform. Process. Lett., 28:39– 44, 1988.

[11] W.-P. Chin and S. Ntafos. Watchman routes in simple polygons. Discrete Comput. Geom., 6(1):9–31, 1991.

[12] X. Deng, T. Kameda, and C. Papadimitriou. How to learn an unknown environment. In Proc. 32nd IEEE Symp. Foundations of Computer Science, pages 298–303, 1991.

[13] Xiaotie Deng, Tiko Kameda, and Christos H. Papadimitriou. How to learn an unknown environment i: The rectlinear case. Technical Report CS-93-05, York University, 1993.

[14] L. Guibas, J. Hershberger, D. Leven, M. Sharir, and R. E. Tarjan. Linear time algorithms for visibility and shortest path problems inside simple polygons. In Proc. 2nd Annu. ACM Sympos. Comput. Geom., pages 1–13, 1986.

[15] Frank Hoffmann, Christian Icking, Rolf Klein, and Klaus Kriegel. A competetive strategie for learning a polygon. In Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms, 1997.

[16] B. Kalyanasundaram and K. Pruhs. A competitive analysis of nearest neighbor based algorithms for searching unknown scenes. In Proc. 9th Sympos. Theoret. Aspects Comput. Sci., volume 577 of Lecture Notes in Computer Science, pages 147–157. Springer-Verlag, 1992.

[17] Marek Karpinski and Piotr Berman. Randomized navigation to a wall through convex obstacles. CS-Report 85118-CS, University of Bonn, 1994.

[18] R. Klein. Walking an unknown street with bounded detour. In Proc. 32nd Annu. IEEE Sympos. Found. Comput. Sci., pages 304–313, 1991.

[19] J. M. Kleinberg. On-line search in a simple polygon. In Proc. of the 5th ACM-SIAM Symposium on Discrete Algorithms, pages 8–15, 1994.

[20] Alejandro L´ opez-Ortiz and Sven Schuierer. Going home through an unknown street. In Proc. 4th Workshop Algorithms Data Struct., volume 995 of Lecture Notes in Computer Science, pages 135–146. Springer-Verlag, 1995.

[21] V. J. Lumelsky and A. A. Stepanov. Path-planning strategies for a point mobile automaton moving amidst unknown obstacles of arbitrary shape. Algorithmica, 2:403–430, 1987.

[22] Aohan Mei and Yoshihide Igarashi. Ef�cient strategies for robot navigation in unknown environment. In Proceedings of ICALP, volume 820 of Lecture Notes in Computer Science, pages 630–641. Springer-Verlag, 1994.

[23] B. John Oomen, S. Sitharama Iyengar, Nageswara S.V. Rao, and R. L. Kashyap. Robot navigation in unknown terrain using learned visibility graphs. part i: The disjoint convex obstacle case. IEEE Journal on Robotics and Automation, 3(RA-3,6), 1987.

[24] C. H. Papadimitriou and M. Yannakakis. Shortest paths without a map. In 16th International Colloquium on Automata, Languages, and Programming, Lecture Notes in Computer Science vol. 372, pages 610–620. Springer-Verlag, 1989.

[25] D. Sleator and R. E. Tarjan. Amortized ef�ciency of list update and paging rules. Communications of the ACM, 28:202–208, 1985.