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önnen^4.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:

• $g({\cal P}) \geq \left\lfloor \frac{n}{3} \right\rfloor$

  Abbildung 4.1 zeigt zwei Polygone mit den jeweils notwendigen Wachposten. Wegen ihrer Form heißen die Polygone Kronen. Jede Krone benötigt je Zacke, die wiederum aus 3 Ecken besteht, einen Wachposten. Induktion beweist, dass derartige Polygone mindestens $\left\lfloor \frac{n}{3} \right\rfloor$ Wächter benötigen.

  Abbildung 4.1: Wachposten in Polygonen: (a) 6 Ecken, 2 Wachposten; (b) 14 Ecken, 4 Wachposten.

  

• $g({\cal P}) \leq \left\lfloor \frac{n}{3} \right\rfloor$

  Mit einem bemerkenswert einfachen Trick gelingt dieser Nachweis. Jedes Polygon lässt sich durch das Hinzufügen von inneren Diagonalen triangulieren (vgl. Anhang A.3). Anschließend wird die entstandene Triangulation als Graph betrachtet. Dieser Graph ist planar und kann nach dem berühmten 4-Farben-Theorem mit vier Farben eingefärbt werden. Der Beweis des 4-Farben Theorems war der erste, der vollständig vom Computer geführt wurde [45]. Einfärben des Triangulationsgraphs bedeutet, Knoten mit Farben zu beschriften, wobei keine zwei Knoten, die durch eine Kante verbunden sind, die gleiche Farbe erhalten. Anhang A.3 zeigt, dass der aus einer Triangulation entstandene Graph sich sogar mit nur 3 Farben kolorieren lässt. Abbildung 4.2 zeigt exemplarisch einen eingefärbten Triangulationsgraphen.

  Abbildung: Einfärbung einer Triangulation mittels Triangulationsgraph. 3 Farben werden benötigt.

  

  Um den Beweis zu beenden, genügt die Feststellung, dass eine der Farben nicht öfter als an $1/3$ der Ecken benutzt wird. O.B.d.A. sei diese Farbe grün. An jeder grünen Ecke postiere man eine Wache. Somit ist gezeigt, dass maximal $\left\lfloor \frac{n}{3} \right\rfloor$ Wachposten notwendig sind.

$\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.