Banos et al. reduzieren das Kunstausstellungsproblem auf ein weiteres NP-vollständiges, nämlich das Set-Cover Problem [28,29,30]. Es ist wie folgt definiert [47]:
Set-Cover:
Die Reduktion auf das Set-Cover Problem geschieht randomisiert. Der Roboter ist mit einer Karte seiner Umgebung ausgestattet. Im ersten Schritt des Algorithmus erfolgt die Generierung einer relativ großen Menge von Kandidatenpositionen. Dabei werden die Positionen zufällig ermittelt. Zudem besitzt jeder Punkt innerhalb der Karte die gleiche Wahrscheinlichkeit. Anschließend wählt der Algorithmus aus dieser Menge der Kandidatenpositionen eine minimale Menge, so dass die ganze Karte überblickt wird. Damit ist das Problem auf Set-Cover reduziert, d.h. ist die Karte und die Menge enthält die Teile der Karte, die von den Kandidatenpositionen überschaut werden können. Der randomisierte Approximationsalgorithmus ist:
Schritt 2 dieses Algorithmus ermöglicht, dass Eigenschaften von realen Sensoren, wie beispielsweise minimaler und maximaler Abstand zu Objekten oder Öffnungswinkel, berücksichtigt werden können.
Im dritten Schritt muss ein NP-vollständiges Problem gelöst werden. Glücklicherweise gibt es einen Greedy-Approximationsalgorithmus dafür, der sehr gute Ergebnisse liefert. Folgende Schritte werden bei einer Eingabe von ausgeführt:
Nachdem die optimalen Scanpositionen bei gegebener Karte approximiert worden sind, müssen diese vom Roboter nacheinander angefahren werden. Dieses Problem entspricht demjenigen des Handlungsreisenden (engl.: Travelling Salesman Problem).
TSP (euklidisch):
Dieses Problem ist ebenfalls NP-vollständig, lässt sich aber auch sehr gut approximieren [14,47].
Der nächste Abschnitt beschreibt den implementierten Algorithmus zum Finden der optimalen nächsten Scanposition. Er basiert auf Ideen aus obigem Approximationsalgorithmus. Dabei werden Kandidatenpunkte in die bereits explorierte Umgebung gestreut und anschließend ähnlich dem Greedy-Verfahren der Punkt ausgewählt, der den größen Informationsgewinn verspricht. Da der Roboter aber in diesem Fall keine vollständige Karte der Umgebung hat, handelt es sich um ein Explorationsproblem. Die dreidimensionale Umgebung des Roboters soll vollständig erfasst werden.