Damit sich ein Roboter autonom durch ein Produktionsumfeld bewegen kann, muss er einen Pfad von seiner aktuellen Position zu einer Zielposition finden. Bei einem Linienfolger ist dieser Pfad statisch und bereits vorgegeben und erlaubt nur das wiederholte Abfahren. Ein anderer, flexibler Ansatz ist es, den Pfad anhand einer Karte zu planen. Dieses Vorgehen erlaubt es dem Roboter, verschiedene Stationen in unterschiedlicher Reihenfolge anzufahren. Da die abgefahrenen Pfade bei diesem Ansatz aber unterschiedlich sind, müssen diese erst vom Roboter geplant werden. Das passiert in der Regel anhand einer Karte. Diese kann dabei vorab bekannt sein oder dynamisch anhand von Sensordaten aufgebaut werden. Wie können Bewegungen also auf einer Karte geplant werden? Das Pfadplanungsproblem wird so dargestellt, dass es durch einen Suchalgorithmus gelöst werden kann (siehe AIAV Video Suchen). Dazu erfasst der Roboter seine Umgebung, erstellt sich aus Sensordaten eine Karte und bestimmt seine derzeitige Position. Der Suchalgorithmus sucht dann nach einem Pfad von der derzeitigen Position des Roboters zum Ziel. Befahrbare Wegpunkte werden dabei als Knotenpunkte, sogenannte "Nodes", dargestellt. Die Nodes sind durch einen oder mehrere Pfade miteinander verbunden. Das aus den Nodes und Pfaden resultierende Netzwerk nennt man Graph. Dieser bildet alle bekannten Verzweigungen und Pfade ab. Abbildung 1 zeigt ein Beispiel für so einen Graphen. Abbildung 1 zeigt ein Beispiel für so einen Graphen. Die Nodes (z.B. Stationen oder Kreuzungen) sind durch Linien miteinander verbunden. Diese Linien stellen mögliche Verbindungen zwischen den Nodes dar. Jede der Linien ist mit einer Zahl (den Kosten) bemessen. Diese Kosten beschreiben wie "schwierig" das Abfahren einer Verbindung ist. Sie können zum Beispiel vom Abstand zwischen den Nodes oder von der benötigten Zeit zum Zurücklegen der Verbindung abhängig sein. Mit einem Beispiel ist das ganze gleich anschaulicher: Wir haben eine Station für unseren Roboter und eine Kreuzung. Zwischen Station und Kreuzung gibt es einen drei Meter langen Gang. Also stellen wir sowohl die Station, als auch die Kreuzung als Nodes dar und verbinden diese mit einem Pfad und Kosten in der Höhe von "3".
Abbildung 1: Die Nodes (N1-N5) stellen Punkte in der echten Welt, wie z.B. eine Station oder Kreuzung, dar. Jeder Verbindungspfad ist mit einer Zahl (den Kosten für den "Transit") bemessen.
Suchalgorithmen suchen einen Weg zwischen zwei Knotenpunkten auf dem Graphen. Beispiele für Suchalgorithmen sind Breiten- und Tiefensuche, sowie Dijkstra's und A* (A Stern). Abhängig von der Art des Suchalgorithmus wird dabei unterschiedlich vorgegangen und Knoten in einer unterschiedlichen Reihenfolge durchsucht - siehe Fähigkeit SUCHEN. In diesem Use-Case wurde der A*-Suchalgorithmus implementiert. Die Idee hinter diesem Algorithmus ist es, systematisch den kürzesten Weg zu bekannten Nodes zu finden. Dafür werden Nodes vom Startpunkt aus abgesucht bis die Ziel-Node erreicht wird. Die Reihenfolge, in welcher abgesucht wird, hängt dabei von der sogenannten Heuristik ab. Diese wird für jeden Knotenpunkt als Summe aus den Kosten, um den Punkt zu erreichen, und der Entfernung zum Zielknoten berechnet. Da durch die Heuristik sowohl der zurückgelegte Weg als auch die Entfernung zum Ziel berücksichtigt werden, müssen potentiell weniger Knoten durchsucht werden als bei anderen Suchalgorithmen. Ein weiterer Vorteil dieses Vorgehens ist, dass der optimale Pfad zum Ziel gefunden wird. Voraussetzung dabei ist, dass der Pfad existiert und eine gültige Heuristik eingesetzt wird. Die Suche wird mittels zwei Listen durchgeführt: einer offenen und einer geschlossenen. Der Ablauf des Algorithmus ist wie folgt: Zunächst wird der Startknoten auf die offene Liste gelegt und aufgeklappt. Beim Aufklappen einer Node werden alle mit ihr verbundenen Knoten der offenen Liste hinzugefügt, sofern der jeweilige Knoten noch nicht auf der offenen oder geschlossenen Liste vorhanden ist. Die Nodes auf der offenen Liste werden anhand der Heuristik sortiert. Die Node mit dem niedrigsten Wert für die Heuristik wird von der offenen Liste in die geschlossene Liste abgelegt und wiederum aufgeklappt. Nun wird so lange neu sortiert und aufgeklappt, bis der Zielknoten erreicht wird oder die offene Liste leer wird. Sobald dies eintritt, bricht der Algorithmus ab, da keine Lösung existiert. Wurde der Zielknoten jedoch erreicht, wird abschließend der optimale Pfad vom Zielknoten – basierend auf den bekannten Nodes in der geschlossenen Liste – konstruiert.
Abbildung 2: Beispielhafter Ablauf des A*-Algorithmus auf einem Graphen
Im Zuge der praktischen Implementierung des Use-Cases wird ein mobiler Roboter in einem zufällig generierten Labyrinth platziert. Das Ziel des Roboters ist, einen Pfad vom Eingang links unten zum Ausgang rechts oben zu finden. Die Struktur des Labyrinths ist dem Roboter dabei unbekannt – das heißt, dass der Graph erst aufgebaut werden muss.
Jetzt wenden wir die Idee des Graphen auf ein "echtes" Umfeld - also unser Labyrinth - an. Der Graph besteht aus einem Gitter aus Nodes (siehe Abbildung 3). Alle Pfade zwischen den Nodes sind 1,8 Meter lang, damit jede Zelle des Labyrinths einer Node entspricht. Die Pfade zwischen den Nodes signalisieren offene Durchgänge und werden anhand der Laserscan-Sensoren am Roboter ermittelt. Der Laserscan liefert den Abstand bis zur nächsten Wand rund um den Roboter. Mithilfe der Position des Roboters am Graphen und den Laserscan-Daten wird der Graph so lange aktualisiert, bis das komplette Labyrinth bekannt ist oder das Ziel erreicht wurde.
Abbildung 3: Das Labyrinth wird als Graph dargestellt, damit der Roboter mittels A* navigieren kann
Im folgenden Video wird der Aufbau der Karte gezeigt. Dabei fährt der Roboter alle aufgeklappten Nodes ab und erweitert anhand der Sensordaten so lange die Liste der bekannten Nodes, bis das Ziel gefunden wurde.
Im folgenden Video wird das Abfahren der Karte gezeigt. Hier hat sich der Roboter erfolgreich eine Karte aufgebaut. Auf dieser wird mittels A*-Algorithmus ein Pfad zwischen Start und Ziel ermittelt. Dieser ist im rechten Fenster grün eingezeichnet. Sobald der Pfad erfolgreich ermittelt wurde, fährt ihn der Roboter ab.
Da der Roboter das Labyrinth anfangs noch nicht kennt, werden zunächst alle Nodes angefahren, die vom A*-Algorithmus aufklappt werden. Dabei wird der Graph so lange aus den Sensordaten aufgebaut, bis die Zielnode aufgeklappt und erreicht wurde. Danach wird der optimale Pfad zwischen Start und Ziel mithilfe der kompletten geschlossenen Liste ermittelt. Abschließend fährt der Roboter auf diesem Pfad zurück zum Start.