Im Zuge des AIAV Use Cases Pfadplanung für autonome Systeme haben wir uns bereits mit Suchen befasst und einen Suchalgorithmus auf ein Pfadplanungsproblem angewandt (siehe AIAV Video Suchen). Neben der Suche selbst haben wir uns dabei auch damit beschäftigt, wie der Roboter die Umwelt Schritt für Schritt auf einer internen Karte erfassen kann. Diese Karte wurde dabei durch Knotenpunkte und Verbindungen zwischen den Knotenpunkten beschrieben, damit der A* (A Stern) Suchalgorithmus den bestmöglichen Weg zum Ziel finden kann. Da die Länge des bereits zurückgelegten Wegs, sowie die Entfernung zum Ziel bei der Suche berücksichtigt wurden, spricht man bei dieser Art von Suchalgorithmen auch von informierter Suche (siehe AIAV Fähigkeit SUCHE).
Neben Pfadplanung können aber auch andere Arten von Planungsproblemen mittels Suchalgorithmen gelöst werden; so ein Problem ist Scheduling. Beim Scheduling soll entschieden werden, wo und in welcher Reihenfolge Teilaufgaben getätigt werden, um eine größere Aufgabe zu erledigen.
Ein Beispiel für so ein Scheduling Problem ist die Beladung von Containerschiffen (siehe Abbildung 1). Dabei soll ein Kran Container auf ein Frachtschiff befördern. Die Container sind alle gleich groß und in mehrere Gewichtsklassen (a-d) unterteilt; es ist vorab bekannt, wie viele Container jeder Gewichtsklasse zu beladen sind. Damit das Schiff nicht kippt, darf sich sein Schwerpunkt während des Beladens aber nicht zu weit von der Schiffsmitte entfernen. Die Ladung muss also gleichmäßig verteilt beladen werden. Unser Scheduling Problem besteht nun darin, in welcher Reihenfolge Container aus jeder Gewichtsklasse an welche freien Positionen auf dem Schiff verladen werden.
Abbildung 1: Ein Containerschiff soll in unserem Scheduling Problem mit Containern verschiedener Gewichtsklassen beladen werden. Dabei müssen die Container aber in der richtigen Reihenfolge an bestimmten freien Positionen abgelegt werden, sodass das Schiff nicht kippt.
Suche auf einem Graphen
Um ein Problem mittels Suchen lösen zu können, müssen wir dieses in eine Form bringen, die ein Suchalgorithmus verarbeiten kann. Wir beschreiben das Problem durch einen Graphen, welcher aus Knotenpunkten (Nodes) und Verbindungen zwischen diesen (Edges) besteht. Ausgehend von der Start-Node werden dann alle Verbindungen und Folgeknoten abgesucht, bis die Ziel-Node gefunden wurde. Dabei bestimmt der verwendete Suchalgorithmus die Reihenfolge, in der die Nodes und Edges verarbeitet werden. Was Nodes und Edges nun in der realen Welt darstellen, hängt von der Art des zu lösenden Problems ab. Allgemein beschreibt eine Node den Zustand der Umwelt, während die Edges Veränderungen dieses Zustands bewirken.
Ein Beispiel für so eine Darstellung ist das Labyrinth im Use Case Pfadplanung für autonome Systeme. Hier wird das Labyrinth durch einen Graphen dargestellt, indem alle Knotenpunkte mögliche Roboterpositionen repräsentieren. Diese Positionen werden durch Edges verbunden, um die Verzweigungen im Labyrinth darzustellen.
Abhängig von der Komplexität des Problems kann es sein, dass das komplette Erstellen des Graphen vor der Suche, z.B. durch zu lange Rechendauer, nicht durchführbar ist. In diesem Fall bietet es sich an, während der Generierung des Graphen bereits die Suche durchzuführen und abzubrechen, wenn ein Ziel gefunden wurde (siehe Abbildung 2). Nicht alle Suchalgorithmen eignen sich für diese explizite Form der Suche, da Teile der Suche auf einem unvollständigen Graphen durchgeführt werden müssen.
Abbildung 2: Das Problem wird als Graph dargestellt, um es für einen Suchalgorithmus lösbar zu machen. Da der vollständige Graph zu Umfangreich für die Weiterverarbeitung ist, wird bereits beim Erstellen des Graphs gesucht. Die Erstellung wird abgebrochen, sobald ein Zielzustand gefunden wurde.
Breiten- und Tiefensuche
Die Generierung eines kompletten Graphen mit allen möglichen Zuständen des Containerschiffs wäre bei wachsender Schiffsgröße sehr rechenintensiv. Deshalb wird die Suche während der Generierung des Graphen durchgeführt und frühzeitig abgebrochen, wenn eine mögliche Lösung gefunden wurde. Zur Suche wurden hier Breiten- und Tiefensuche eingesetzt, da sich die beiden Verfahren für diese explizite Form der Suche eignen.
Bei Breiten- und Tiefensuche wird jeweils auf einem baumförmigen Graphen von einem Startknoten aus gesucht. Die beiden Algorithmen suchen dabei nach und nach benachbarte Knotenpunkte ab und überprüfen, ob es sich beim Nachbarn um den Zielknoten handelt. Wurde der Zielknoten gefunden, wird die Suche abgebrochen und eine Liste der bereits abgesuchten Knoten zurückgegeben. Aus dieser Liste kann dann der Pfad von Start zum Ziel ermittelt werden.
Der Unterschied zwischen Breitensuche und Tiefensuche liegt dabei in der Reihenfolge, in der Nachbarknoten überprüft werden (siehe Abbildung 3). Breitensuche geht, wie der Name schon sagt, zuerst in die Breite und sucht nach und nach alle Ebenen des Baums ab. Tiefensuche sucht hingegen in die Tiefe; hier werden nach und nach alle Äste überprüft. Dadurch, dass die beiden Algorithmen Knoten in unterschiedlichen Reihenfolgen abarbeiten, können sie bei Problemen mit mehreren Lösungen unterschiedliche Lösungen finden. Je nach Aufbau des Graphen kann auch einer der Algorithmen wesentlich schneller zu einer Lösung finden als der Andere.
Abbildung 3: Breiten- und Tiefensuche eignen sich zum Absuchen von baumförmigen Graphen. Dabei überprüfen sie die Nachbarknoten jeder Node in einer unterschiedlichen Reihenfolge (siehe die Nummerierung der Knoten).
Praktische Implementierung
Die praktische Implementierung wurde anhand des in Hamburg gebauten Conceiver Feederschiffs (siehe Abbildung 4) durchgeführt. Auf diesem können die Container aus verschiedenen Gewichtsklassen auf sechs mal sechs möglichen Positionen abgeladen werden. Jede Node repräsentiert dabei einen möglichen Zustand des Schiffs. Das heißt, dass es für jede Kombination aus zu verladenen Containern und möglichen Positionen auf dem Schiff einen Knoten gibt, der dieser Kombination eindeutig zuordenbar ist. Dieses Konzept kann in der Praxis einfach umgesetzt werden, indem man den Schiffszustand als Ziffernfolge darstellt und diese Ziffernfolge den Namen der Node darstellt. So entspricht z.B. die Node "aa " einem Schiff mit vier Plätzen für Container (siehe die zwei Leerzeichen). Auf zwei dieser Plätze sind Container der Gewichtsklasse a verladen, während die anderen beiden frei sind.
Abbildung 4: Wir verwenden das Conceiver Feederschiff mit 6x6 Containerplätzen für unsere Implementierung des Schedulings (Bildquelle: Das Container-Zubringeschiff (Feeder) Conceiver auf der Außenelbe mit Kurs Hamburg).
Da wir ermitteln wollen, in welcher Reihenfolge die Container auf das Schiff beladen werden sollen, gehen wir zunächst von einem leeren Schiff aus. Alle möglichen Folgezustände werden als Knoten generiert. Dabei wird die Reihenfolge, in der die Zustände erstellt werden, vom Suchalgorithmus abhängig gemacht. Tiefensuche geht zuerst in die Tiefe, während Breitensuche zuerst in die Breite geht. Wird nun ein Ziel (also ein Schiffszustand, bei welchem alle Container verladen sind) gefunden, wird die Suche abgebrochen und die zum Ziel führenden Zustände zurückgegeben.
Um das Schiff während der Beladung im Gleichgewicht zu halten, dürfen bei der Generierung nur Zustände in Betracht gezogen werden, bei welchen sich das Schiff durch die Ladung nicht mehr als 5 Grad entlang seiner Länge neigt. Dafür wurde eine Methode in die Graphgenerierung eingebaut, welche den Schwerpunkt der Ladung und den Auftriebsschwerpunkt des Schiffs annähert und überprüft, ob der maximale Winkel in einem der Folgezustände überschritten wird. Resultiert der Folgezustand in einem zu großen Winkel, wird er übersprungen. So simulieren wir fiktive Beladungen in der Reihenfolge, die der Suchalgorithmus vorschlägt.
Abbildung 5 zeigt den Ablauf der Schiffsbeladung mittels Tiefensuche (links) und Breitensuche (rechts). Dabei wird eine Ebene des Schiffs mit einer zufällig generierten Anzahl an Containern aus jeder Gewichtsklasse (a-d) beladen. Wir simulieren für jede Ebene den vom Suchalgorithmus vorgesehenen Beladungsschritt und überprüfen, ob dieser das Schiff zu weit neigen würde.
Dadurch, dass die Suchalgorithmen in einer unterschiedlichen Reihenfolge vorgehen, resultieren sie in verschiedenen Lösungen für das gleiche Problem.
Abbildung 5: Um das unterschiedliche Vorgehen der Suchalgorithmen zu zeigen, werden Tiefensuche (links) und Breitensuche(rechts) gleichzeitig zur Ermittlung der Beladungsreihenfolge des Schiffes eingesetzt. Dabei Repräsentieren die verschiedenen Farben der Container die definierten Gewichtsklassen.
Fazit
Um ein Problem mittels Suche zu lösen, werden Zustände als Knotenpunkte und Zustandsänderungen als Verbindungen zwischen den Knotenpunkten gespeichert. Der resultierende Graph erlaubt es Suchalgorithmen Pfade zwischen Knoten zu finden und so das Problem zu lösen. Breiten- und Tiefensuche sind dabei einfach implementierbare Suchalgorithmen, welche eine Lösung finden, aber nicht abschätzen können, welche von mehreren Lösungen die günstigste ist. Um z.B. die Ladung so gleichmäßig wie möglich zu verteilen, könnte die Implementierung um einen informierten Suchalgorithmus erweitert werden, welcher die gefundenen Lösungen bewertet und sich die Beste aussucht.