next up previous contents
Next: Ein randomisierter Approximationsalgorithmus für Up: Die optimale nächste Scanposition Previous: Problemdefinition


Das Kunstausstellungsproblem

Ein mit einer 2D-Karte seiner Umgebung ausgestatteter Roboter soll so gesteuert werden, dass er die gesamte 2D-Umgebung sieht. Gesucht ist also eine Menge von Positionen, von denen die gesamte Karte überblickt werden kann. Fährt der Roboter diese nacheinander an und führt dort Sensoroperationen aus, ist dadurch die Karte verifiziert. Das Berechnen der notwendigen Positionen heißt Kunstausstellungsproblem (engl.: art gallery problem). Die Analogie liegt auf der Hand: Sei die gegebene 2D-Karte der Grundriss einer Kunstausstellung. Dann entsprechen die Positionen den Orten, wo Wachpersonen postiert werden sollten, um alle Teile der Ausstellung einsehen und beschützen zu können4.1.

Die 2D-Karte wird als Polygon $ {\cal P}$ repräsentiert, das als eine Menge von $ n$ Eckpunkten $ v_1, v_2,\ldots,\linebreak v_n$, und $ n$ Kanten $ v_1v_2, v_2v_3,\ldots, v_{n-1}v_n, v_nv_1$ (Kantenzug) definiert ist. Es handelt sich also um eine geschlossene, endliche, verbundene Region einer Ebene, die vom genannten Kantenzug umschlossen ist. Ein so definiertes Polygon besitzt keine Löcher. Alle nun folgenden Aussagen beziehen sich auf diesen Fall. Am Ende des Kapitels werden die Resultate für Polygone vorgestellt, die durch Kantenzüge begrenzt sind. Man sagt, ein Punkt $ x \in \mathbbm{R}^2$ sieht Punkt $ y \in
\mathbbm{R}^2$, wenn das Liniensegment $ xy$ vollständig in $ {\cal P}$ liegt ( $ xy
\subset {\cal P}$).

Für das Kunstausstellungsproblem gibt folgender Satz eine Obergrenze für die Anzahl der benötigten Wachpersonen. Die Wachposten haben ein 360$ ^\circ$-Blickfeld und können unbegrenzt weit schauen [55].

Satz 2 (Art Gallery Theorem)   Eine Kunstausstellung kann immer von $ \left\lfloor \frac{n}{3}
\right\rfloor$ Wachposten bewacht werden [55].

Beweis:Bezeichne $ g({\cal P})$ die Anzahl der benötigten Wachleute. Damit beweisen folgende Teilaussagen den Satz:

$ \Box$

Der letzte Satz liefert eine Obergrenze für das Kunstausstellungsproblem bzw. für den vorliegenden Fall der Robotik ein oberes Limit für die Anzahl der Sensoroperationen zum vollständigen Erfassen der 2D-Umgebung bei gegebener Karte. Ziel ist es, die Anzahl der benötigten Sensoroperationen gering zu halten, also im Kunstausstellungsfall möglichst wenig Wachpersonen einzusetzen. Wächter überschauen so genannte Sternpolygone; jeder Punkt dieses Polygons lässt sich mittels einer Linie, die die Kanten des Polygons nicht schneidet, mit dem Wachposten (auch Kern genannt) verbinden. Die einzelnen Sternpolygone dürfen sich dabei überlappen. Es ist folglich nicht nach einer Partition gesucht.

Formal lässt sich das Kunstausstellungsproblem auf diese Weise definieren:

StarC:

Instanz:
Ein Polygon $ {\cal P}$ und eine positive Konstante $ K$.
Frage:
Gibt es eine Überdeckung von $ {\cal P}$ mit $ K$ oder mit weniger als $ K$ Sternpolygonen, d.h. existieren Sternpolygone $ {\cal S}_1, {\cal S}_2,\ldots,
{\cal S}_k$ mit $ k \leq K$, so dass $ {\cal S}_1 \cup {\cal S}_2 \cup \ldots
\cup {\cal S}_k = {\cal P}$?

Im weiteren Verlauf wird gezeigt, dass dieses Problem NP-hart ist. Für den Nachweis der NP-Härte wird nachfolgend das Problem 3-SAT definiert und danach auf StarC reduziert. Cook hat 1971 gezeigt, dass das 3-SAT NP-vollständig ist [47].

3-SAT:

Instanz:
Eine Menge von boolschen Variablen $ U = \{\mathsf{u}_1, \mathsf{u}_2,\ldots, \mathsf{u}_n\}$ und eine Menge von Klauseln (Disjunktion von Literalen) $ C = \{\mathsf{c}_1,
\mathsf{c}_2,\ldots,\mathsf{c}_m \}$, definiert über der Menge $ U$. Jede Klausel ist eine Disjunktion von 3 Literalen.
Frage:
Gibt es eine erfüllende Belegung von $ C$, d.h. gibt es eine Belegung der $ n$ Variablen, so dass $ \mathsf{c}_1 {\wedge}\mathsf{c}_2 {\wedge}\cdots {\wedge}\mathsf{c}_m$ wahr wird?

Satz 3 (Art Gallery is NP-hard)   StarC ist NP-hart [55].

Beweis:3-SAT wird in polynomieller Zeit auf StarC reduziert (3-SAT$ \leq_p$StarC). Für jede
mögliche 3-SAT Formel lässt sich ein Polygon konstruieren, wobei eine Lösung des StarC Problems, also die Postierung der Wachposten beim Kunstausstellungsproblem, einer Lösung von 3-SAT entspricht.

Der vollständige Beweis befindet sich in Anhang A.4.$ \Box$

Da das Kunstausstellungsproblem NP-hart ist, ist dieses Problem und somit auch die Berechnung einer minimalen Menge von Sensorpositionen nach dem heutigen Wissensstand nicht in polynomieller Zeit zu lösen. Der folgende Abschnitt beschreibt eine Approximation der Berechnung von minimal notwendigen Sensorpositionen.



Unterabschnitte
next up previous contents
Next: Ein randomisierter Approximationsalgorithmus für Up: Die optimale nächste Scanposition Previous: Problemdefinition
Andreas Nüchter
2002-07-10