Wegfindung / Pathfinding

Im letzten Beitrag haben wir uns mit den Sensoren eines autonomen mobilen Roboters (AMR) beschäftigt und damit, wie er seine Umgebung wahrnimmt. Im heutige Beitrag gehen wir auf seine Navigation im Lager ein.

Aufgabe des AMRs ist die Übernahme von Transporten im Lager. Was muss er nun leisten, damit er für uns einen Mehrwert darstellt? Richtig, er sollte den schnellsten bzw. kürzesten Weg für seine Transporte nehmen. Es bringt uns nichts, wenn er im Lager Sightseeing betreibt und dreimal eine große Runde fährt, bevor er am Ziel ankommt.

Aber wie wird nun in der Informatik diese optimale Wegfindung realisiert? Dafür bedienen wir uns der Graphentheorie aus der Mathematik. Graphen sind Modelle für netzartige Strukturen. Diese bestehen aus Knoten und Kanten. Einen Knoten kann man sich als Kreuzungspunkt mit Abzweigungen vorstellen und eine Kante entspricht dann dem direkten Weg zwischen zwei Knoten.

Wir brauchen also eine Karte unseres Lagers, in der wir alle möglichen Knoten und Kanten eintragen. Der AMR legt dazu über eine Karte des Lagers ein kleines Gitternetz. Jeder Schnittpunkt der Gitterlinien entspricht dabei einem Knoten. Das sieht dann so aus, als ob man sein Lager in der Draufsicht auf kariertes Papier gezeichnet hat. Typische Gitterabstände liegen dabei zwischen 5 cm und 10 cm. Jeder Knoten wird mit seinen direkten Nachbarknoten über Kanten verbunden. Auf einer Fläche von 1 m² macht das bei einem 5 cm-Gitter schon 400 Knoten und 722 Kanten.  Daran sieht man, dass in einem großen Lager schon sehr viele Knoten und Kanten zusammenkommen.

Jetzt haben wir unseren Graphen. Damit wir nun am schnellsten von A nach B kommen, nutzen wir dazu das Konzept des kürzesten Pfades. Dazu werden alle möglichen Pfade zum Ziel nach verschiedenen Faktoren bewertet. Dies sind in unserem Beispiel die Entfernung je Kante und das Verkehrsaufkommen je Kante. So erhält jede Kante eine eigene numerische Gewichtung. Je höher die Zahl, desto schlechter die Kante (also ähnlich wie zu Schulzeiten).

Um nun den kürzesten Pfad zu finden, nutzen wir einen Algorithmus. Dieser ermittelt uns, welcher Pfad die kleinste Gewichtung hat. Ein Algorithmus funktioniert wie ein Kochrezept. Wenn jeder Schritt in der richtigen Reihenfolge und korrekt ausgeführt wird, sollte es schmecken bzw. ein Ergebnis liefern. Wir gehen wie folgt vor

1. Wir haben einen Graphen, in dem alle Kanten gewichtet sind. Alle Knoten sind noch ohne Zustand, ein Knoten kann einen von 3 Zuständen haben:
   1. unbesucht (farblos)
   2. provisorisch besucht (rot)
   3. permanent besucht (grün)
2. Wir wählen A als Start- und H als Zielknoten aus. Der Startknoten A enthält den Wert 0 (Maß für die Wichtung).

Folgendes Bild zeigt ein ganz einfaches Lagerlayout: 8 Regale, breite Gänge für Gabelstaplerfahrten / Kommissionierung und schmale Gänge zum reinen Kommissionnieren. Die Entfernung in Metern entspricht der Wichtung. Auf den breiten Gängen herrscht mehr Verkehr, dort wird die Entfernung mal 2 genommen. Prinzipiell haben wir auch hier das Gitternetz darübergelegt. Der Übersichtlichkeit halber haben wir aber nur die relevanten Knoten (A – H) und Kanten dargestellt.

3. Vom Knoten A besuchen wir alle benachbarten Knoten und notieren bei diesen die zurück­gelegte Kantenlänge und den Ursprungsknoten (B = (A 1) und D = (A 10)) und markieren diese als „provisorisch besucht“ (Grund: Es wurden noch nicht alle ihre Nachbarknoten besucht).
4. Knoten A wird nun als „permanent besucht“ markiert (Grund: Alle seine Nachbarknoten wurden jetzt besucht).

5. Wir wählen von allen „provisorisch besuchten“ Knoten den aus, der die kleinste Gewichtung hat (hier Knoten B mit (A 1)).
6. Wir besuchen wieder alle Nachbarn des Knoten B und notieren die Summe aus der Wichtung von B plus die zurückgelegte Kantenlänge von B dorthin (C = (B 11)) und markieren diesen als „provisorisch besucht.
7. Wir markieren B als „permanent besucht.

8. Wir wählen wieder von allen „provisorisch besuchten“ Knoten den aus, der die kleinste Wichtung hat (jetzt Knoten D mit (A 10)).
9. Wir besuchen wieder alle Nachbarn, notieren die Summe aus den Wichtungen bis dorthin und markieren diese als „provisorisch besucht“ (F = (D 30) und E = (D 21)).
10. Wir markieren D als „permanent besucht“.

Wie wir sicher schon erkannt haben, folgen wir jetzt immer den drei Schritten bis alle Knoten permanent besucht wurden:

1. Knoten mit der kleinsten Gewichtung besuchen
2. Nachbarknoten markieren
3. Heimatknoten markieren.

Zwei Fälle sind noch zu erwähnen:

Treffen wir auf einen Konten, der bereits als „provisorisch besucht“ markiert ist, aber haben von unserem neuen Pfad eine kleinere Wichtung, dann ändern wir die bestehende auf die neue Wichtung.

Falls wir einen Knoten immer nur besuchen, diesen aber nie als Heimatknoten auswählen, setzen wir diesen auf „permanent besucht“, sobald alle seine Nachbarn „permanent besucht“ wurden.

Am Ende sollten alle Knoten als „permanent besucht“ markiert (also grün) sein. Um den kürzesten Pfad zu ermitteln, gehen wir jetzt vom Zielknoten einfach rückwärts entsprechend unseren Knotenbeschriftungen.

Et voilà, wir haben unseren kürzesten Pfad von A nach H ermittelt:

• von H nach F
• von F nach C
• von C nach B
• von B nach A.

Je nach Anwendung kommen verschieden Algorithmen zum Einsatz. Für die Wegfindung werden vor allen der Dijkstra- und A*-Algorithmus verwendet, die im Grunde ähnlich dem Beschriebenen verlaufen. Eine Anwendung der Algorithmen für die Wegfindung hat wahrscheinlich auch jeder von uns schon einmal im täglichen Leben genutzt: die Routenplanung im Autonavi. Dort läuft im Grunde der gleiche Algorithmus wie in unserem AMR ab.

Jetzt haben wir uns mit der Navigation des AMR beschäftigt. Im nächsten Beitrag schauen wir uns an, wie wir eine Karte des Lagers mithilfe des AMR erstellen. Im ersten Beitrag haben wir die Sensoren behandelt, mit denen er seine Umwelt sieht. Aber am Anfang dieses Beitrags haben wir uns bereits eine fertige Karte genommen. Also fehlt uns noch ein Verbindungsschritt zwischen beiden Beitragen, und zwar die Kartenerstellung durch SLAM (Simultaneous Localization and Mapping = Simultane Positionsbestimmung und Kartenerstellung).