Wir haben eine Startkonfiguration in diesem Konfigurationsraum und
eine Zielkonfiguration, die wir erreichen wollen.
Und wir suchen eine Trajektorie, zum Beispiel Tau, mit den
Bedienungen, dass Tau natürlich zum Zeitpunkt 0, dass der Roboter an
der Startkonfiguration Q-Start ist und am Ende Tau bei T gleich 1 am
Ziel ist.
Und natürlich müssen wir dabei eine ganze Menge von Bedienungen
berücksichtigen.
Wir müssen zum Beispiel Zwangsbedienungen, die durch den Roboter
selbst vorgegeben sind, berücksichtigen.
Das ist notwendig, wie wir wissen, Gelenkwinkel grenzen.
Bestimmte Lösungen der Inversion Kinematik sind nicht gültig, weil sie
sind außerhalb der Bahnsteuerungsvorlesung.
...freie Bewegung, das ist natürlich die Hauptbedienung, die wir
berücksichtigen müssen.
Aber zusätzlich das, was hier nochmal steht.
Wir suchen nicht unbedingt irgendwelche Trajektorien, sondern
vielleicht eine Trajektorie, die gute Kriterien oder
Optimalitätskriterien erfüllt.
Zum Beispiel die Trajektorie mit der kürzesten Dauer oder die
Trajektorie, die mit dem geringsten Energieverbrauch verbunden ist
oder die Trajektorie, die den großen Abstand zu Hindernissen hat.
Und dann natürlich andere Neben- und Randbedienungen müssen
berücksichtigt werden, dass wir entlang der Trajektorie zum Beispiel
eine Tasse in der Hand in der aufrechten Position halten müssen, damit
wir zum Beispiel die Flüssigkeit nicht schütten.
Wie man sieht, ist es gar keine einfache Sache.
Also natürlich Kollisionen vermeiden.
Aber wie wir sehen werden in dieser Vorlesung, wir werden auch einige
Methoden kennenlernen, die mit solchen Bedienungen, mit diesen
Nebenzwangsbedienungen beziehungsweise auch guten Kriterien umgehen
können.
Und ganz vereinfacht unseren einfachen Roboterarm mit drei Gelenken
hier, dargestellt im Arbeitsraum, das ist zum Beispiel der
karthesische Raum R6.
Und wir wissen, dass der Endeffektor wird immer mit TCP, also Tool
Center Point hier bezeichnet.
Und wenn wir jetzt eine Trajektorie von dieser Startposition zu dieser
Endposition berechnen, kann man auch Konfiguration dazu sagen, aber
das wäre jetzt eine Konfiguration im Arbeitsraum.
Also gegeben durch die 6D-Pose zum Beispiel von dem Tool Center Point,
dann wäre das eine gültige kollisionsfreie Trajektorie.
Diese Trajektorie sieht natürlich im Konfigurationsraum anders aus,
weil in dem Konfigurationsraum müssen wir zunächst mal dieses
Hindernis hier, dieses quadratisch praktische Hindernis hier abbilden
in dem Konfigurationsraum.
Und der Konfigurationsraum wird aufgespannt von den drei Gelenken.
Uppsala.
Muss man hier kollisionsfrei laufen können.
Von den drei Gelenken Theta 0, Theta 1 und Theta 2.
Also die sind nicht alle 0 hier, die sollen 1 und 2 und 3 sein.
Und wie man sieht, das ist die Abbildung von diesem Hindernis, was wir
vorher gesehen haben im Konfigurationsraum, im Arbeitsraum, in den
Konfigurationsraum.
Und unsere Trajektorie, die blaue Trajektorie hier im Arbeitsraum,
beziehungsweise ist diese gelbe Trajektorie im Konfigurationsraum.
Das heißt, wir haben ein N-Dimensional im Konfigurationsraum.
Man nennt das auch im Englischen C-Space, also Configuration Space.
Wir haben den Freiraum.
Und zwar, das sind alle kollisionsfreien Konfigurationen.
Also alles, was weiß ist hier in diesem dreidimensionalen Raum,
dreidimensionalen Konfigurationsraum.
Und wir haben den Hindernisraum.
Und der Hindernisraum, das sind alle roten Teile.
Das heißt, alle Konfigurationen, die zu einer Kollision führen.
Und wie man sieht, natürlich der komplette Konfigurationsraum, also
alle möglichen Kombinationen von Täter 0, Täter 1, Täter 2, ist nichts
anderes als die Vereinigung vom Freiraum und vom Hindernisraum.
Und wie man sich vielleicht vorstellen kann, ist die Berechnung von
diesem Hindernisraum alles andere als trivial.
Da werden wir gleich hier ein Beispiel dazu sehen.
Aber die Beziehungen hier zwischen Konfigurations- und Arbeitsraum
kann man am besten anhand von diesem Beispiel hier sehen.
Also nehmen wir mal an, wir wollen hier dieses grüne Objekt
manipulieren.
Und da sieht man eigentlich, dass man mit keiner Konfiguration von
diesem dreiachsigen Roboter hier bis zum grünen Objekt kommt oder
kommen kann, ohne dass es zu Kollisionen kommt.
Der Konfigurationsraum momentan sieht so aus.
Also das ist die Abbildung von all diesen Hindernissen in den Raum,
der von den Gelenken Täter 1, Täter 2 und Täter 3 aufgespannt wird.
Also das sind ja die Gelenke hier von diesem Roboterarm.
Der hat auch ein drittes Gelenk, wie man sieht hier am Handgelenk.
Und das letzte Mal... Ups, Entschuldigung.
Das war zu schnell.
Und das nächste Mal haben wir gesehen, wie sich das alles verändert.
Das schalten wir mal aus.
Das heißt, wenn wir jetzt hier dieses grüne Objekt manipulieren
wollen, dann müssen wir natürlich den Weg frei machen.
Das ist sehr naheliegend natürlich im Arbeitsraum.
Jeder von euch kann sich vorstellen, was man machen muss, also welche
Sequenz von Aktionen notwendig ist, um den Weg frei zu machen zum
Zielobjekt.
Aber im Konfigurationsraum sieht die Sache natürlich ein bisschen
komplizierter aus, weil in dieser anfänglichen Situation hier, wenn
das grüne Objekt komplett blockiert ist, befindet sich dieses Ziel,
also das grüne Objekt, im Hindernisraum.
Das heißt, da gibt es keine Chance, dass man dort rankommt ohne
Kollisionen mit anderen Objekten.
Während wenn wir diese Sequenz von Aktionen ausgeführt haben, z.B.
das rote Objekt und das blaue Objekt zur Seite geschoben haben, dann
sieht man hier, dass wir eine kleine Passage geschafft haben vom
Start, also Start ist dieser grüne Punkt hier, zum Ziel, um
kollisionsfrei dorthin zu kommen.
Das heißt, wir haben jetzt ein paar Konfigurationen vom Roboterarm
gefunden, mit denen wir das Zielobjekt greifen können, ohne dass wir
mit anderen Objekten hier kollidieren.
Und natürlich, jede Änderung im Arbeitsraum hat auch oder ändert den
Konfigurationsraum.
Also man sieht hier die Situation, der Konfigurationsraum hier in
dieser Situation sieht wie folgt aus.
Das sind nur Täter 1 und Täter 2, jetzt nur ein Ausschnitt von dem
Konfigurationsraum.
Und wenn wir hier das rote Objekt verschoben haben und das blaue auch
ein bisschen mehr nach hinten verschoben, dann sieht man, dass sogar
diese Passage ein bisschen breiter ist, um vielleicht nicht nur
irgendeine Trajektorie, sondern eine Trajektorie, die im Sinne von
irgendeinem Optimalitätskriterium günstiger ist, berechnen können.
So, einige Definitionen.
Also mit Konfiguration Q wollen wir den Zustand eines Roboters und
zwar als Gelenkwinkelvektor im Gelenkwinkelraum bezeichnen.
Also wenn wir von Konfiguration reden, dann werden wir immer im
Konfigurationsraum sein.
Also nicht im Arbeitsraum, sondern im Gelenkwinkelraum des Roboters.
Also im Gegensatz zu dem, was auf der Folie stand bei der letzten
Vorlesung übrigens.
Konfigurationsraum C eines Roboters ist der Raum aller möglichen
Konfigurationen der Gelenkwinkel.
Und manchmal, nicht oft eigentlich, es soll hier manchmal heißen,
werden Bewegungen auch im Arbeitsraum geplant.
Dann spricht man in dem Fall auch vom Konfigurationsraum, weil für
einen mobilen Roboter plant man natürlich in XY und Alpha die
Orientierung und nicht vielleicht in dem Raum der Umdrehungen der
einzelnen Räder.
Könnte man das machen?
Beziehungsweise bei einer Drohne plant man natürlich auch in XYZ und
nicht in den Umdrehungen der einzelnen Rotoren von der Drohne.
Aber in dem Fall spricht man tatsächlich in der Literatur manchmal von
Konfiguration und diese Konfiguration wäre in dem Fall Position und
Orientierung vom Roboter.
Im zweidimensionalen bei einem mobilen Roboter oder im
dreidimensionalen oder sechsdimensionalen Raum, zum Beispiel bei einer
Drohne.
Der Arbeitsraumhindernis ist das eigentlich, ist dieser Block, dieser
rote Block hier.
Das heißt, es ist der Raum, welcher von einem Objekt im Arbeitsraum
angenommen wird.
Also zum Beispiel diese Schachtel hier könnte ein Hindernis hier
darstellen und dann habe ich ein Hindernis im Arbeitsraum.
Der Konfigurationsraumhindernis, das Konfigurationsraumhindernis sieht
anders aus und zwar die Abbildung von diesem Arbeitsraumhindernis in
den Konfigurationsraum.
Also es sind alle Konfigurationen des Armes, die zu einer Kollision
mit dem Objekt führen.
Der Hindernisraum, beziehungsweise Obstakelraum, deshalb C OBS, ist
die Menge aller Konfigurationsraumhindernisse, also die Vereinigung
aller Konfigurationsraumhindernisse ergibt dann den Hindernisraum.
Weitere Definitionen der Freiraum ist klar.
Der Freiraum ist der gesamte Konfigurationsraum abgezogen
Hindernisraum, beziehungsweise alle Konfigurationen, die zu keiner
Kollision führen.
Und der Aufwand für diese Berechnung von dem Freiraum ist ziemlich
hoch.
Also die ist exponentiell in der Anzahl von den Freiheitsgraden des
Roboters.
Also wenn N Anzahl der Freiheitsgrade des Roboters, zum Beispiel 8 und
M Anzahl der Hindernisse, dann haben wir M hoch 8 als Komplexität für
die Berechnung vom Freiraum.
Und bei komplexeren Kinematiken, also wenn wir eine große Anzahl von
Freiheitsgraden bei dem Roboter oder Freiheitsgrade, die sehr komplex
zueinander angeordnet sind, dann kann man diesen Freiraum nicht so
effizient berechnen.
Aber man muss natürlich beachten, dass dieser Freiraum der Grundlage
für die Berechnung aller kollisionsfreien Trajektorien ist, weil wir
Sequenzen von Konfigurationen in diesem Raum suchen.
Das heißt, für jede Aufgabe müssen wir diesen Freiraum berechnen.
Und dieser Freiraum ändert sich, wie die Objekte in der Szene sind.
Das heißt, wenn wir ein Objekt von A nach B abstellen, dann ändert
sich der komplette Freiraum und müssen wir natürlich unsere
Berechnungen neu starten.
Es gibt aber hierzu approximative Methoden, mit denen man natürlich
diesen Freiraum einfacher, also auf eine effizientere Art und Weise
darstellen kann.
Ganz triviales Beispiel, damit ihr nur so einen Eindruck davon habt,
was es bedeutet, eigentlich den Freiraum oder auch Hindernisraum zu
berechnen.
Nehmen wir mal an, wir hätten einen Roboter mit zwei Gelenken, Theta 1
und Theta 2, und wir haben nur ein einfach geformtes Hindernis.
Ja, das ist dieses Objekt hier.
Und man sieht eigentlich hier, dass wir, wenn Theta 1 kleiner als 45
Grad hier, dass wir immer eine Kollision haben.
Also wenn Theta 1 kleiner als 45 Grad, egal was Theta 2, was dieses
Ellenbogengelenk macht, dann haben wir immer eine Kollision mit dem
Hindernis.
So, wenn Theta 1 größer als 45, also wir bewegen uns nach oben, dann
haben wir natürlich manchmal Situationen, wo wir natürlich durch Theta
2 kleiner als 90 Grad zu Kollisionen mit dem Objekt kommen, aber auch
andere, wo wir keine Kollision mit dem Objekt haben.
Wir können sicher, vielleicht ungefähr sicher, also approximativ
sagen, dass wir bei Theta 2 größer als 90 Grad und Theta 1 größer als
45 Grad, das ist Freiraum, aber Theta 1 größer als 45 und Theta 2
kleiner als 90, da wissen wir eigentlich nicht genau, was passiert,
weil das hängt ja von den Konfigurationen ab.
Wenn wir das ein bisschen näher betrachten und ein paar
Konfigurationen betrachten, also das heißt, diesen Bereich muss man
genauer nochmal angucken und schauen, wo habe ich eigentlich Freiraum
und wo habe ich einen Hindernisraum.
Wenn wir das genauer angucken, also sehen wir mal, das ist der Punkt
A, der Punkt A ist hier, das ist der Schnitt von diesen zwei Linien.
Das ist ein Punkt B, gegeben durch die Konfiguration 45 und 0, also
Theta 2 ist 0 und man sieht das ja gerade an der Grenze hier, also das
ist der Punkt B, das ist der Punkt C, das ist auch eine
kollisionsfreie Konfiguration, der Punkt C.
Und das ist der Punkt D mit diesen Gelenkwinkelkonfigurationen, wie
man sieht hier, Theta 1 ist größer als 45 und wenn Theta 2 70 ist,
dann hätte ich angefangen an meine Kollisionen, also Theta 2 kleiner
als 70, dann habe ich Kollisionen und das wäre der Punkt hier D.
Und auf diese Art und Weise sieht man, dass man diese Räume ja
rekursiv, iterativ mal in solchen Bereichen unterteilen kann, die
kollisionfrei sind, beziehungsweise wo ich nicht weiß, ob dort
Kollisionen vorhanden sind oder nicht.
Also zum Beispiel der hellblaue Bereich hier, das ist approximiert in
Kollision, beziehungsweise hier approximiert betrachtet ist es frei
hier, der dunkelgrüne Bereich.
Genau, wenn man das Ganze hier weiterführt, das war unser A hier und
dann sieht man hier, dass man noch eine feinere Unterteilung hier in
diesen Bereichen, in freien Bereichen beziehungsweise kollisionsfreien
oder gemischten Bereichen.
Das ist nur so ein triviales Beispiel mit zwei Gelenken und mit einem
sehr einfachen Hindernis, von einer einfachen Geometrie und
zweidimensional.
Und da merkt man, das ist ja nicht ohnehin.
Und jetzt stellt euch mal vor, Objekte komplexerer Geometrie,
Roboterarmee mit sieben, acht Freiheitsgraden, also mit einer großen
Anzahl von Freiheitsgraden, da sind diese Berechnungen natürlich nicht
so trivial.
Genau, das heißt, was ganz wichtig ist natürlich für die ganze
Berechnung von kollisionsfreien Bewegungen, ist, dass wir eigentlich
wissen, wie die Umgebung oder die Umwelt aussieht.
Ja, und wenn wir exakte Modelle von den Objekten, von der Umgebung
haben, dann ist die Sache natürlich relativ einfach.
Ja, schnelle Rechner und die können rechnen und Freiraum,
Kollisionsraum, Asternsuche, Rapidly Exploring Random Trees, wie wir
sehen werden und dann hat man eine Lösung.
Aber das ist nicht immer der Fall.
Also die Umweltmodellierung ist entscheidend, exakt.
Das heißt, ich habe eine sehr genaue Beschreibung von allen Objekten
in der Szene und von dem Roboter selber, zum Beispiel mit Constructed
Solid Geometry, also konstruktive Festkörper Geometrie, wo komplex
geformte Objekte aus Grundprimitiven, also wie Kugeln, Zylinder,
Pyramiden, Ringe und so weiter und so fort, als Kombination von
solchen Grundprimitiven dargestellt werden, mithilfe von logischen
Operatoren.
Und die andere Variante, ich habe ja eine Näherung eigentlich von der
Umgebung, beziehungsweise von der Umwelt, zum Beispiel ich
approximiere jetzt hier diesen Bereich hier in der Szene durch einen
Würfel und nicht die Details von diesem Overhead-Projektor.
Genau.
Weitere Grundlagen, die für uns interessant sind, sind einmal diese
Begrifflichkeiten, Pferdplanung, das heißt, ich habe ein starres
Objekt und wir betrachten tatsächlich nur starre Objekte hier und
starre oder nicht deformierbare Objekte.
Wir haben einen mobilen Roboter oder ein autonomes Fahrzeug für die
Pferdplanung.
Das ist ein 2D-Problem, das heißt XYZ- beziehungsweise 3D-Problem,
wenn wir die Orientierung auch berücksichtigen.
Und das ist das Piano-Movement-Problem.
Das heißt, wir müssen schauen, wie wir das Objekt hier durch Passagen
und in dem Freiraum in der Wohnung, also das Piano beziehungsweise ein
Möbelstück hier verschieben können.
Bewegungsplanung, also Pferdplanung für 2D-Probleme, beziehungsweise
3D, wenn wir die Orientierung berücksichtigen von dem Fahrzeug.
Und Bewegungsplanung bezieht sich auf Mehrkörpersysteme, also zum
Beispiel Roboterarmee, Systeme mit mehreren Robotern, also Zwei-Arm
-Systeme oder mehrere Roboter mit einzelnen oder mehreren Armen.
Und das sind hochdimensionale Problemstellungen, weil wenn wir jetzt
den Arme zum Beispiel 6 nehmen mit 8 Freiheitsgraden pro Arm, dann
haben wir insgesamt 16 für beide Arme.
Wir haben ein Teleskopgelenk, das heißt 17, und wir haben 3
Freiheitsgrade für die mobile Basis, also insgesamt 20.
Und dann müssen wir in diesem Raum planen für andere Roboter, zum
Beispiel der Arme 3 im Konfigurationsraum 43.
So, die Randbedienungen, auch Zwangsbedienungen genannt, da
unterscheidet man bei diesen Randbedienungen zwischen globalen und
lokalen Randbedienungen.
Und die globalen Randbedienungen limitieren den gültigen
Konfigurationsraum, zum Beispiel aufrechte Position vom Endeffektor,
zum Beispiel die minimalen Motorströme.
Und die lokalen Randbedienungen schränken die Übergänge zwischen
Konfigurationen, also zum Beispiel nichtholonome Fahrzeuge, die können
sich nicht zur Seite bewegen, sondern die müssen wie ein Auto
geradeaus und dann lenken, um an eine Zielposition und Orientierung
anzukommen.
Oder die können sich nicht auch auf der Stelle drehen.
Weitere lokale Randbedienungen sind zum Beispiel die maximalen
Geschwindigkeiten und Beschleunigungen, die eingehalten werden müssen.
Die Komplexität von dem Problem, von dem Bewegungsplanungsproblem, ist
ein P-Space Komplett oder ist P-Space vollständig.
Das heißt, diese Probleme können von deterministischen Turing
-Maschinen erst mit polynomialem Platzbedarf gelöst bzw.
entschieden werden.
Und damit man weiß, was das bedeutet, wir wissen vielleicht als
Informatiker, was das MPE-vollständige oder MPE-harte Probleme sind.
Und diese P-Space-harte Probleme, muss das Wort hier korrigiert
werden, P-Space-harte Probleme sind eigentlich, oder diese MPE
-vollständige Probleme sind nur eine Untermenge von P-Space-harten
Problemen.
So, weitere Begriffe, die wir auch das letzte Mal angeguckt haben.
Wir haben Unterschiede zwischen einem vollständigen Algorithmus und
zum Beispiel einem randomisierten Algorithmus.
Mit vollständigen Algorithmen verstehen wir oder unter vollständigen
Algorithmen verstehen wir Planungsprobleme oder Algorithmen, die
Planungsprobleme lösen und die zwar mindestens eine Lösung finden bzw.
in endlicher Zeit erkennen, dass es keine Lösung gibt.
Das ist natürlich sehr vorteilhaft, wenn ich jetzt eine Lösung suche
für ein bestimmtes Problem und ich habe irgendwelche Zeitvorgaben als
Randbedienungen, ich muss die Lösung innerhalb von ein paar
Millisekunden oder einer Sekunde finden, dann ist es wertvoll zu
wissen, ich werde eine Lösung finden oder innerhalb dieser Zeit kann
ich Aussagen darüber machen, dass keine Lösung hier existiert.
Randomisierte Algorithmen, die benutzen Zufallsgrößen und wir werden
einige von denen hier kennenlernen in der Vorlesung, zum Beispiel der
Rapidly Exploring Random Tree, randomisiert die Zufallsgrößen, um den
Ablauf bei der Bestimmung von einer kollisionsfreien Bahn zu
berechnen, ja, also benutzen Zufallsgrößen bei der Bestimmung von
einer kollisionsfreien Bahn und oft verwenden sie auch Heuristiken, um
die Suche nach dieser Bahn zu beschleunigen, also um die Berechnung
eigentlich, wenn es Suche ist, zu beschleunigen.
Dann gibt es sogenannte auflösungsvollständige Algorithmen und das
sind Algorithmen, bei denen man nicht von kontinuierlichen
Problemstellungen ausgeht, also dass man jetzt die komplette
Beschreibung der Umgebung kontinuierlich, sondern eine diskrete bzw.
quantisierte Darstellung der Umgebung und je nachdem, wie groß diese
Auflösung, mit der man das darstellt bzw.
wie groß die Auflösung, mit der man zwischen Konfigurationen
umschalten kann, hat man einen anderen approximativen Algorithmus,
also die sind jetzt nicht genau, sondern approximate Algorithmen und
die nennt man in dem Fall auflösungsvollständige Planungsalgorithmen.
Und die vierte Variante sind sogenannte probabilistisch vollständige
Algorithmen und solche Algorithmen finden mindestens eine Lösung,
falls sie existiert.
Das heißt, die Wahrscheinlichkeit, dass eine Lösung gefunden wird,
konvergiert mit der Zeit gegen eins.
Allerdings können wir keine Aussagen darüber treffen oder können diese
Algorithmen keine Aussagen darüber treffen, wenn es keine Lösung
existiert.
Also im Vergleich der vollständigen Algorithmen, die sowas machen
können.
Wenn man das Ganze hier zusammenfassen will, dann haben wir
unterschiedliche Schwierigkeitsgrade des Problems der
Bewegungsplanung, also des Auffindens einer kollisionsfreien Bahn von
einer Startkonfiguration zu einer Zielkonfiguration.
So haben wir das Problem definiert.
Und vielleicht der einfachste Fall ist, wenn wir ein vollständiges
Modell der Umgebung haben, das heißt mit vollständiger Spezifikation
von Nebenrand- und Zwangsbedienungen.
Und natürlich suchen wir eine kollisionsfreie Trajektorie und wir
werden hier Methoden kennenlernen in diesem Kapitel, wie wir das
bestimmen, wenn alles vorgegeben und vollständig bekannt ist.
Aber das muss nicht immer der Fall sein.
Also es kann sein, dass wir ein unvollständiges Umweltmodell haben.
Beispielsweise es kommen neue Objekte dazu auf den Tisch und der
Roboter soll trotzdem kollisionsfrei die Zielobjekte manipulieren und
diese neuen Objekte sind nicht modelliert und nicht Teil vom
Umweltmodell.
Wir haben auch kein komplettes Kenntnis über Neben- und Rand- und
Zwangsbedienungen.
Und natürlich das Problem, das man hier hat, dass man Kollisionen mit
unbekannten Objekten berücksichtigen muss, beim Lösen des Problems.
Also es ist nicht nur etwas Festes gegeben, eine Konfiguration und ich
habe meinen Freiraum, Kollisionsraum berechnet und ich suche in dem
Freiraum eine kollisionsfreie Trajektorie, sondern durch neue Objekte
oder durch unbekannte Teile vom Objektmodell kann es natürlich zu
Kollisionen kommen, wenn diese unbekannten Teile nicht berücksichtigt
werden.
Also ein bisschen schwieriger als die Klasse A.
Die Klasse C, wir haben zwar ein Umweltmodell, das kennen wir, aber
der verändert sich mit der Zeit.
Das heißt, unser Ziel ist immer eine kollisionsfreie Trajektorie vom
Start zum Ziel und hier haben wir also Hindernisse, die Varianten
sind, deren Zustand sich verändert in Ort und in Zeit.
Und man kann sich vorstellen, dass die Sache hier weitergeht, wenn wir
überhaupt kein Umweltmodell haben, dann müssen wir natürlich für die
Suche nach einer kollisionsfreien Bewegung zunächst mal so ein
Umweltmodell uns schaffen.
Das heißt, man muss die Umgebung kartografieren, also Rekonstruktionen
von allem, was man in der Szene sieht und dann natürlich in dieser
gewonnenen Rekonstruktion oder mithilfe von diesem gewonnenen Modell
die kollisionsfreie Trajektorie berechnen.
Und die Klasse E, vielleicht das Schwierigste, wir haben ein
zeitvariantes Umweltmodell und wir suchen eine Trajektorie zu einem
bewegten Objekt.
Das heißt, es ist zum Beispiel ein Roboterarm, wo der Roboter fährt
und Objekte auf einem Fließband, die sich auch bewegen, greifen
müssen.
Oder man kann sich vorstellen, eine Rakete, die vielleicht irgendwas
mal verfolgt, was auch fliegt.
Eine Drohne, die eine andere Drohne beispielsweise verfolgt.
Das heißt, Zielzustand, also Ziel, unser Kuhziel ist sowohl
veränderlich im Ort und in der Zeit.
So, das sind die unterschiedlichen Klassen von den Problemen und wir
werden uns natürlich nicht mit all diesen Klassen hier beschäftigen.
Wir werden davon ausgehen, dass wir ein Umweltmodell haben, das heißt,
das steht uns zur Verfügung.
In anderen Vorlesungen, zum Beispiel in Robotik 3, werden wir sehen,
wie wir solche Umweltmodelle aus Bilddaten oder Tiefenbilder oder
hauptsächlich aus Bilddaten erstellen können.
Also zum Beispiel mit Slam-Methoden und ähnliches, aber das soll jetzt
hier euch nicht beschäftigen, sondern wir haben ein Umweltmodell und
wir wollen jetzt in diesem Umweltmodell unsere kollisionsfreien Bahnen
planen.
Und als erstes, wie ich bereits erwähnt habe, wollen wir das für
mobile Roboter machen und wir wollen hier zwei Klassen von Methoden
kennenlernen.
Einmal grafenbasierte Methoden, das werden wir heute kennenlernen und
das nächste Mal machen wir weiter mit Potentialfeldmethoden und in den
nächsten Vorlesungen mit Bewegungsplanung für Mehrkörpersysteme, also
für Manipulatoren.
Wie ist das Problem definiert für die Fahrtplanung für einen mobilen
Roboter?
Wir haben ein 2D-Weltmodell, also es ist gegeben, zum Beispiel eine
Straßenkarte, auch von einem Auto, nicht unbedingt von einem Roboter,
Start - und Zielkonfiguration und wir suchen die günstigste Verbindung
vom Start zum Ziel, also zum Beispiel die kürzeste Verbindung bzw.
vielleicht die schnellste Verbindung, die nicht immer die kürzeste
ist, weil man irgendwelche Probleme unterwegs hat.
Und die zentrale Idee bei all diesen Algorithmen, die wir kennen, ist
zunächst mal ein Netz zu erstellen oder einen Graphen zu erstellen,
der für uns tatsächlich kollisionsfreie Punkte definiert, die wir
annehmen können oder die ein Roboter oder ein Auto annehmen kann, beim
Versuchen vom Start zum Ziel zu kommen.
Also zunächst mal, man konstruiert ein Netz von Wegen in Zephri.
Also was bedeutet das?
Es bedeutet eigentlich, ich mache mal ein 2D-Beispiel.
Nehmen wir mal an, wir haben unseren Konfigurationsraum hier und wir
haben hier ein paar Hindernisse, wie die Baustellen in Karlsruhe, die
man nicht durchfahren kann.
Und die Aufgabe besteht darum, dass wir zunächst mal irgendein Wegnetz
im freien Raum, also das ist unser Hindernisraum und weiß ist unser
Freiraum.
Und was hier auf der Folie steht, wir müssen so irgendeinen Graphen
bilden.
Wir müssen einen Graphen bilden und mithilfe von diesem Graphen
beliebige Planungsprobleme durchführen.
Also das heißt, im nächsten Schritt, wenn wir vom Q-Start nach Q-Ziel
gehen wollen, also nehmen wir mal an,
das ist unser Ziel und das ist hier unser Start.
Man bildet den Q-Start und den Q-Ziel auf den nächsten Knoten in
diesem Graphen ab.
Das heißt eigentlich, man sucht mit anderen Worten den nächsten
Nachbarn, also praktisch den nächsten Knoten in diesem Graphen, der am
nächsten zu diesen zwei Punkten ist.
Also das wäre zum Beispiel der hier, ja, Z-Strich und das wäre jetzt
hier S-Strich.
Und dann sucht man einen Pfad in diesem Graphen zwischen S-Strich und
C -Strich und nehmen wir mal an, das wäre jetzt hier der Weg, den wir
gefunden haben.
Und anschließend muss man natürlich einen Weg für diese kurzen
Strecken hier finden, also zwischen Z-Strich und Z-Strich und zwischen
S -Strich und S-Strich.
Weil natürlich diese Abbildung, die wird nicht immer so sein, dass man
direkt auf einen Punkt in diesem Wegenetz kommt, sondern man wird den
nächsten Nachbarn oder den nächsten Punkt auf dem Graphen nehmen und
das ist eigentlich die komplette, also das ist alles, was wir
verstehen müssen.
Das heißt, was sind die Probleme hier, die wir haben?
Also natürlich brauchen wir den Freiraum und den Hindernisraum, aber
das Hauptproblem, das wir hier haben, ist, dieses Netz zu erstellen,
also diesen Graphen zu erstellen und dann auf dem Graphen mit
bekannten Suchmethoden, also Wegsuchmethoden, eine Bahn oder eine
Verbindung vom Start zum Ziel finden.
So, und hier wollen wir eine ganze Menge von Methoden kennenlernen,
wie wir dieses Wegenetz W berechnen.
Und da gibt es hier eine ganze Menge von Methoden, zum Beispiel
Vorneudiagramme, Sichtgrafen bzw.
Zellenzerlegung.
Und für das zweite Hauptproblem, wenn wir diesen Graphen erstellt
haben, müssen wir natürlich in diesem Graphen jetzt einen Weg suchen,
zum Beispiel mit der Baumsuche oder mit dem beliebten und bekannten A
-Stern -Algorithmus.
Und wir fangen an mit Vorneudiagrammen.
Vorneudiagramme visualisieren die Zerlegung eines Raumes in Regionen,
basierend auf vorgegebenen Punkten.
Das heißt, wir haben hier ein paar vorgegebene Punkte.
Normalerweise sind diese Punkte die Hindernisse, stellen die
Hindernisse dar.
Also wir gehen von punktförmigen Hindernissen aus.
Natürlich, wenn die Hindernisse bestimmte Auslehnungen haben, dann
muss man das verallgemeinern oder entsprechend betrachten.
Und eine Region, also zum Beispiel diese Region hier von einem
Vorneudiagramm, ist definiert als die Menge aller Punkte hier, deren
Abstand zu diesem Hindernis geringer ist als zu allen benachbarten
Hindernissen.
Also der Abstand hier von diesen Punkten zu diesem Hindernis ist
geringer als zu dem oder geringer als zu dem und geringer als zu dem.
Was bedeutet eigentlich das?
Das bedeutet, dass alle Punkte, die auf der Grenze liegen, also auf
diesen grünen geraden Linien liegen, haben den gleichen Abstand zum
eigenen und zum benachbarten Hindernis.
Das heißt, die Punkte auf diesen Geraden hier haben den gleichen
Abstand zu diesem Punkt und zu diesem Punkt, die Punkte auf diesen
Geraden haben den gleichen Abstand zu diesem Punkt und zu diesem Punkt
und die Punkte auf diesen Geraden haben den gleichen Abstand zu diesem
Punkt und zu diesem Punkt und so weiter und so fort.
Und die Frage ist, wie baut man dieses Voronoi-Diagramm?
Nehmen wir an, man hat solche Punkte, P, also eine Menge von
Hindernissen gegeben hier.
Das sind fünf Punkte, wie man sieht, und die Punkte stellen
Hindernisse dar in diesem Kontext.
Und was man macht, man unterteilt diese Punkte zunächst mal in etwa
gleich große Teilmengen.
Also man sieht hier durch eine Linie, dann habe ich eine Teilmenge P1
und eine Teilmenge P2, also einmal mit drei und einmal mit zwei
Punkten.
Und das macht man rekursiv, bis man am Ende entweder zwei Punkte oder
drei Punkte hat.
Also natürlich durch sukzessive oder rekursive Unterteilung hier kommt
man bis zu diesem Punkt, also wenn ich jetzt mehr als fünf Punkte
habe.
Aber hier in dem Beispiel sehen wir, dass wir schon dort sind.
Wir haben einen Fall, wo wir zwei Punkte und einen Fall, wo wir drei
Punkte haben.
Wenn ich mehr Punkte habe, kann ich diese Unterteilung so
weitermachen, dass ich zu dieser Situation oder zu diesen
Konfigurationen lande.
Und also durch diese rekursive Unterteilung der Punktmengen kann das
Problem der Erstellung eines Voronoi-Programm auf zwei einfache Fälle
reduziert werden.
Fall 1, ich habe zwei Punkte und die Kante von einem Voronoi-Diagramm
hat den gleichen Abstand zu beiden Punkten, zu beiden Hindernissen.
Das ist also nichts anderes als die Mittelsenkrechte auf die
Verbindungslinie zwischen diesen zwei Punkten.
Also ich verbinde diese zwei Punkte und in der Mitte habe ich die
Senkrechte drauf und das ist ja eine Kante von meinem Voronoi
-Diagramm, was mir sagt, okay, alle Punkte auf dieser Linie haben den
gleichen Abstand zu beiden Hindernissen.
Das Gleiche natürlich bei einem Fall von drei Punkten.
Ich verbinde die Punkte miteinander, ich bilde die Mittelsenkrechten
und schneide sie ab.
Das heißt, sie gehen hier weiter und weiter und weiter.
Aber ich schneide sie an der Stelle hier und dann habe ich einen Teil
von meinem Voronoi-Diagramm und da sieht man hier, dass diese zwei
Punkte den gleichen Abstand zu dieser Linie haben, diese zwei Punkte
den gleichen Abstand und diese zwei Punkte den gleichen Abstand zu
dieser Linie.
Wenn wir das machen in unserem Beispiel, dann bekommen wir so etwas
hier.
Das sind die drei Punkte und das haben wir gemacht mit den
Mittelsenkrechten und dann abschneiden und hier Mittelsenkrechte auf
die Verbindungslinie für die Punkte in P2.
Aber wir haben noch kein komplettes zusammenhängendes Voronoi
-Diagramm.
Was man jetzt noch machen muss, man muss die Punkte am Rand, also
entlang der Trennebene oder der Trennlinien, wo wir getrennt haben,
verbindet man die Punkte miteinander.
Also wir haben hier getrennt, also das ist hier ein Nachbar von dem
und das ist ein Nachbar von dem und das ist hier ein Nachbar von dem
und wenn wir sie miteinander verbinden, dann haben wir auch diese
Linien, dann bilden wir nochmal die Mittelsenkrechten und schneiden
wir ab.
Also Mittelsenkrechte hier, die schneidet den Rest an der Stelle,
alles andere eliminieren wir.
Die Mittelsenkrechte hier schneidet die zwei hier und die
Mittelsenkrechte hier schneidet das hier und wenn wir alle diese
Linien wegtun, dann haben wir eigentlich unser Voronoi-Diagramm, das
wir gesucht haben.
So, was bedeutet das?
Das bedeutet eigentlich, ich weiß, ich habe sehr sichere Linien oder
Bahnen, entlang deren ich fahren kann.
Weil wenn ich jetzt hier beispielsweise von einem Punkt hier, also man
könnte jetzt hier das Problem nochmal veranschaulichen, das heißt,
wenn ich jetzt hier die Aufgabe hätte,
ich soll von Start hier zum Ziel hier kommen.
Ja, was bedeutet unser Problem?
Also das sind unsere Punkte, wir müssen diese Punkte auf irgendwelche
Punkte auf unserem Netz abbilden.
Also zum Beispiel hier, der nächste Punkt ist S-Strich, hier wäre das
Z -Strich und dann kann ich meine kollisionsfreie Trajektorie planen
von S-Strich zu Z-Strich und natürlich, wie man sieht hier, damit ist
die Sache nicht getan, sondern ich brauche so ein bisschen einen
lokalen Planer, der natürlich Z mit Z-Strich und S mit S-Strich
verbindet, damit ich wirklich vom Start zum Ziel komme.
Und wenn man das macht, dann hat man natürlich eine Garantie, dass man
immer mit dem maximalen Abstand zu den Hindernissen fährt.
Also das wäre natürlich die Bahn, die einzige Bahn, die uns vom Start
zum Ziel bringt und überall haben wir den maximalen Abstand zu
Hindernissen.
So, das ist noch ein weiteres Beispiel, also keine punktförmigen
Hindernisse, sondern Hindernisse mit einer bestimmten Ausdehnung, also
die schwarzen Bereiche sind hier die Hindernisse.
Und wenn wir praktisch hier diese Vorhinein-Diagramme bilden, dann
bekommen wir sowas.
Also man sieht hier, das sind ja keine geradlinigen Linien, weil da
müssen wir immer den Abstand, also dieser Punkt hier muss natürlich
den gleichen Abstand zu dem und zu dem haben, und deshalb ist es nicht
notwendigerweise eine Linie, sondern das können ja gekrümmte Kurven
sein.
Und für diesen Konfigurationsraum oder beziehungsweise in diesem
Freiraum, mit diesem Hindernisraum hier, bekommen wir diesen Vorhinein
-Diagramm.
Und wir wissen, wenn wir uns entlang dieser Linien bewegen, dann haben
wir immer den maximalen Abstand zu den Hindernissen.
Und da kommt jetzt hier, was wir gerade vorher mehrmals inzwischen
gesehen haben, das ist unser Ziel oder unser Startpunkt.
Deshalb bilden wir diesen Ziel und Startpunkt zu den nächsten Punkten
auf diesem Netz.
Und dann suchen wir auf diesem Netz ein Pferd von Start zum Ziel und
natürlich am Ende müssen wir hier dieses kleine Stück fahren, also
zwischen Q-Start und Q-Start-Strich, beziehungsweise Q-Ziel und Q-Ziel
-Strich.
Es gibt andere Verfahren.
Zu den Nachteilen, in der Regel ist der gefundene Weg nicht der
kürzeste Weg.
Warum eigentlich?
Warum ist der gefundene Weg nicht der kürzeste Weg?
Genau, eigentlich kann es einen viel kürzeren Weg hier finden, und
zwar so.
Also die Forderung, dass wir immer entlang der Linien fahren, wo wir
die maximale Distanz zu den Objekten garantieren, bedeutet nicht, dass
wir immer den kürzesten Weg kriegen.
Und ich glaube, die rote Linie ist viel kürzer als zum Beispiel jetzt
eine Linie entlang der Kanten des Voronoi-Diagramms.
Bei wenigen Hindernissen werden natürlich wenige Wege generiert.
Das sehen wir hier.
Wir haben zwei Hindernisse und da haben wir ganz wenige Möglichkeiten
eigentlich, wie wir von einem bestimmten Punkt zum anderen in diesem
Konfigurationsraum kommen können.
Es gibt andere Methoden, zum Beispiel Sichtgrafen.
Und bei Sichtgrafen, auch bei Sichtgrafen, geht davon aus, dass man
die Hindernisse kennt.
Also das ist Obstacle 1, Obstacle 2 und Obstacle 3, deshalb O,
Obstacle für Hindernisse.
Und was man macht hier, man verbindet jedes Paar von Eckpunkten von
den Hindernissen, also auf dem Rand von dem Freiraum, durch eine
Linie, wenn diese Linie oder dieses Liniensegment kein Hindernis
schneidet.
Also man nimmt hier diese Ecken und verbindet sie miteinander.
Das ist auch eine Ecke, verbindet sie.
Aber das hier mache ich natürlich nicht, weil das schneidet ja ein
Hindernis.
Also das geht weg.
Und wenn wir alles hier machen, dann bekommen wir so ein Netz und auf
diesem Netz können wir uns dann bewegen.
Und was ist das Problem?
Das Problem, wenn ich jetzt hier von Q-Start zu Q-Ziel kommen will,
dann bilde ich das vielleicht auf dem nächsten Punkt hier ab, also Q
-Ziel -Strich und dann hier Q-Start-Strich.
Ich suche einen Weg zwischen diesem Q-Strich und Q-Strich und dann
muss ich natürlich dafür sorgen, dass ich jetzt hier von Q zu Q-Start
und Q-Ziel zu Q-Ziel komme.
Also die gleiche Vorgehensweise.
Das ist hier ein weiteres Beispiel, also man sieht hier für die
Objekte kann ich dann natürlich nachher vielleicht den kürzesten Weg
suchen von Q-Start zum Q-Ziel.
Und was ist der Nachteil von dieser Methode hier?
Nein, wir haben bis jetzt überhaupt keine Aussagen darüber gemacht,
wie wir den kürzesten Weg berechnen oder nicht.
Also berechnen nicht unbedingt immer den kürzesten Weg, aber wir
können auch keine Kurven fahren, aber das ist alles vielleicht nicht
das Hauptproblem.
Genau, man fährt sehr nah an den Hindernissen vorbei, weil zum
Beispiel eine Kante von einem Hindernis, wie bei O3, kann tatsächlich
eine Kante von einem Graph sein.
Also das ist ja eine Kante, ich habe jetzt hier das verbunden, wenn
ich die zwei miteinander verbinde und ich suche vielleicht den
kürzesten Weg, dann ist der kürzeste Weg ein Weg, wo die Kante hier
entlang der Kante von einem Hindernis ist.
Das heißt, so wird es nicht funktionieren, weil jeder Roboter hat eine
gewisse physikalische Ausdehnung und ist nicht nur punktförmig.
Aber das Verfahren hier, also mit Sichtgrafen, kann man eigentlich
sagen, dass diese Wege, die man findet, optimal sind, zum Beispiel am
kürzesten bei 2D-Problemen und wenn der Roboter und Hindernisse durch
konvexe Polynome darstellbar sind.
Der Nachteil ist, die Wege sind nicht unbedingt kollisionsfrei, denn
Hindernisskanten können auch Wegsegmente sein und abhilfig schafft
hier die Erweiterung von Hindernissen.
Das heißt, man vergrößert die Hindernisse so, dass es nicht zu
Kollisionen kommt, wenn man entlang der Kante eines Hindernisses
fährt.
Und die Methode, die ist jetzt natürlich nur in 2D oder haben wir nur
in 2D kennengelernt, aber die ist auch in 3D anwendbar, aber die Wege,
man kann keine Garantien mehr geben, dass die Wege, die dort gefunden
werden, die kürzesten oder die optimalsten sind.
Und wie man diese Hindernisse erweitert, also damit wir sowas
vermeiden, dass wir entlang der Kante eines Hindernisses fahren,
könnte man sagen, naja, eigentlich ist es ja ganz einfach.
Wenn ich so einen Roboter habe, einen kreisförmigen Roboter, dann
vergrößere ich alle Hindernisse um den Radius von diesem Roboter.
Das heißt, O1 wird ein bisschen größer, und zwar an allen Stellen
genau so um R erweitert, wenn R der Radius vom Roboter ist.
Und wenn ich dann solche Wege finde, wo ich zum Beispiel an der Kante
von einem Hindernis fahre, also normalerweise würden wir hier an
diesem Punkt vorbeifahren und es würde natürlich eine Kollision mit
dem Hindernis kommen, aber dadurch, dass wir dieses Hindernis um R,
wobei R ist hier der Radius von dem Roboter, vergrößert haben, werden
wir natürlich im Abstand von R an dem Hindernis vorbeifahren und somit
diese Kollision vermeiden.
Natürlich ist das jetzt nicht allgemein, also das wäre jetzt für einen
kreisförmigen Roboter, das ist zum Beispiel ein rechteckiger Roboter
und der kann sich in xy-Richtung bewegen.
Und man sieht hier, dass man sich Gedanken darüber machen muss, wie
man diese Hindernisse vergrößern muss, um alle möglichen
Konfigurationen vom Roboter zu betrachten und Lösungen, bei denen man
entlang der Kante eines Hindernisses fahren muss, nicht zu einer
Kollision führen.
Gut, gibt es Fragen dazu?
Okay, das heißt, wir haben ein Voronoi-Diagramm und wir haben
Sichtgrafen kennengelernt.
Die dritte Möglichkeit sind sogenannte Zellenzerlegungen und wir gehen
immer davon aus, wir haben ein vollständiges Umweltmodell.
Das heißt, wir kennen den Konfigurationsraum, wir kennen den Freiraum
und wir kennen den Hindernisraum.
Bei Zellenzerlegung, also eigentlich muss man Tricks finden, wie man
in diesem Freiraum sich bewegen kann, um eine kollisionsfreie
Trajektorie zu finden.
Bei Zellenzerlegung sagt man, wir zerlegen diesen Freiraum in Zellen,
sodass ein Weg zwischen zwei Konfigurationen innerhalb einer Zelle
leicht zu finden ist.
Und man stellt dann die Nachbarschaften zwischen Zellen in einem
Grafen dar und sucht dann den optimalen Weg vom Start zum Ziel in
diesem Grafen.
Und für diese Zellenzerlegung gibt es zwei Arten, einmal eine exakte
Zellenzerlegung und einmal eine approximative Zellenzerlegung.
Und die exakte Zellenzerlegung bedeutet, dass der Freiraum C-free in
Zellen ZI zerlegt wird, sodass keine zwei Zellen sich überlappen.
Also der Durchschnitt von zwei Zellen ist die Leeremenge und die
Vereinigung von allen ZIs, also allen Zellen, in denen man den
Freiraum zerlegt hat, dem Freiraum ergeben.
Und wie macht man das?
Das ist zum Beispiel eine Methode, wie man diese exakte
Zellenzerlegung mit einem kleinen Sweep macht.
Und zwar, man hat hier einen Konfigurationsraum, Hindernisraum ist
schwarz und Freiraum ist weiß.
Und man geht hin und lässt eine Linie über diesen Konfigurationsraum
hinfegen.
Also eine Linie bewegt sich von links nach rechts, diese vertikale
Linie hier in diesem zweidimensionalen Beispiel.
Das ist zunächst mal diese Ecke hier, eine vertikale Linie runter und
dann weiß ich, ich habe hier eine Region 1, dann die nächste Ecke hier
von dem Hindernis.
Und dann, das heißt, diese Linie bewegt sich von links nach rechts und
immer, wenn sie sich auf ein Hindernis oder auf eine Ecke von einem
Hindernis stößt, habe ich eine neue Region.
Ja, also das ist die Region 2.
Dann gehen wir weiter, die Linie bewegt sich.
Dann habe ich hier die Ecke hier und ich gehe mal weiter, wie man
sieht hier, dann habe ich diesen Bereich hier und so weiter hier bei 4
und so weiter und so fort.
Und wenn ich das hier mache, über den gesamten Bereich, dann habe ich
eigentlich meinen Freiraum, also der weiße Bereich hier unterteilt in
mehreren Regionen mit den Nachbarschaften von diesen Regionen.
Und das kann ich jetzt auf einem Graphen abbilden, also 1 und 2 sind
miteinander verbunden.
Und wie man sieht hier, bei 2 habe ich eine Verzweigung zu Region 3
und Region 6 und von Region 3 auf 4 und von 4 auf 5.
Und man sieht hier, von 5 komme ich nie raus.
Das heißt, wenn ich irgendwo in 5 lande, dann ist es eine Sackgasse.
Von 4 komme ich aber weiter zu 7.
7 ist auch mit 6 verbunden, weil ich kann von 6 zu 7 kommen und von 7
zu 8 und von 8, wie man sieht, zu 9, zu 10.
Aber von 7 auch zu 16 und von 16 zu 17.
Und hier von 10 sieht man zu 13 oder zu 11.
Von 13 auch zu 14, wo ich auch hier nie wieder rauskommen würde.
Von 11 wieder zu 12.
Und von 12 zu 19 und von 19 zu 20.
Also das heißt, man hat so eine Zerlegung von dem Freiraum und anhand
von dieser Zerlegung kann man diesen Graphen hier auf eine leichte Art
und Weise erzeugen.
Und jetzt will man ein Planungsproblem führen.
Zum Beispiel sagt man, ich habe meine Startkonfiguration hier und
Zielkonfiguration hier.
Und was man machen muss, ist eigentlich festzustellen, in welcher
Region ist meine Startkonfiguration und meine Zielkonfiguration.
Das ist 3, also das heißt der Knoten 3 hier, mein Start und mein Ziel
ist in der Region 19.
Also eigentlich, ich muss nur in einem Graphen einen Weg zwischen dem
Knoten 3 und dem Knoten 19 suchen.
Und das wäre die Lösung für mein Planungsproblem.
Und man sieht hier, dass das über 4, 7, 8, 9, 10, 13, 15, 17, 18, 19
geht.
Das ist eine Lösung.
Und da wir jetzt hier überhaupt keine Aussagen über Kosten gemacht
haben, ist natürlich auch 3, 4, 7 oder 3, 4, 7, 16, 17, 18, 19 auch
eine Lösung.
Oder 3, 4, 7, 8, 9, 10, 11, 12, 19 auch eine Lösung.
Also eine sehr einfache Methode.
Man hat natürlich diesen Konfigurationsraum mit den Hindernissen, mit
dem Freiraum.
Man lässt eine Linie so über diesen Raum hinfegen und an allen Ecken,
wie man sieht hier, definiert man oder werden diese Regionen definiert
durch diese vertikalen Linien von den Ecken der Hindernissen und dann
im Graph und dann in der Graph-Suche.
Was bedeutet das?
Das heißt, eine einfache Möglichkeit, eigentlich solche Pferde- bzw.
kollisionsfreien Trajektorien zu finden.
Im zweidimensionalen Fall übrigens.
Die approximative Zellenzerlegung ist ein bisschen anders, also
approximativ nicht genau.
Also hier sind wir sehr genau, wie man gesehen hat in dem Beispiel.
Hier zerlegen wir den Freiraum in Zellen von einer vordefinierten
Form.
Also wir sagen zum Beispiel, unsere Zellen sind rechteckig und initial
hat eine Zelle zum Beispiel eine Kantenlänge von 4 cm.
Wenn eine Zelle nicht vollständig im Freiraum passt oder liegt, also
wenn ich jetzt durch diese Kacheln, ich fange an mal Kacheln in diesem
Raum zu legen und wenn eine Kachel zu Kollisionen mit einem Hindernis
kommt, also nicht mehr dort reinpasst, dann sage ich, okay, ich muss
kleinere Kacheln nehmen oder kleinere Zellen nehmen.
Also wenn eine Zelle nicht passt, dann verringern wir die Größe von
dieser Zelle und zerlegen wir weiter, zum Beispiel im Quadri und dann
wiederholen wir diesen Schritt bis zu einer minimalen Größe der Zelle,
weil wir sagen, okay, die kleinsten Zellen, die wir berücksichtigen,
die sollen 1 x 1 cm groß sein, also ausgehend von 4 x 4 cm die
Initialzellen, mit denen wir angefangen haben.
Vorteil, sehr einfache Zerlegung und dadurch natürlich sehr einfache
Wegsuche, weil eigentlich die Wegsuche ist nichts anderes als die
Suche von einer Sequenz von Kacheln oder Zellen, die ich gelegt habe,
von denen ich weiß, die sind frei.
Das heißt, ich habe schon die Informationen eigentlich bei dieser
Zerlegung mit und schleppe sie mit und kann sie nur nutzen, um eine
Kollisionfreie Bahn zu berechnen.
Der Nachteil, der Freiraum kann im Allgemeinen nur annähernd
beschrieben werden, es sei denn, die Hindernisse, die sind alle
quadratisch praktisch, wie die Zellen und deshalb der Name
approximative Zerlegung.
Hier sieht man ein Beispiel, das ist unser Konfigurationsraum mit
Freiraum und Hindernissen, Start- und Endkonfiguration und wir fangen
mit diesen Zellen an.
Wir fangen an, so Zellen mal hinzulegen in den Freiraum und irgendwann
mal versuchen wir mal hier eine Zelle zu legen und merken, das passt
nicht.
Deshalb nehmen wir eine kleinere Zelle, die passt, die passt, die
passt nicht, die passt ein bisschen und deshalb zerlegen wir weiter
und so weiter und so fort.
Und das wollen wir ein bisschen jetzt genauer kennenlernen und zwar,
wir haben jetzt verstanden, dass wir diesen Freiraum irgendwie
repräsentieren müssen als Voronoi-Diagramm, also Freiraum mit
Hindernissen -Voronoi-Diagramm als Graph mit zum Beispiel
Zellenzerlegung und jetzt der nächste Schritt ist eigentlich, den Weg
zu suchen innerhalb von diesen Graphen oder entlang dieser Zellen.
Man sieht hier in dem Beispiel, dass ich das eigentlich hier auf eine
sehr einfache Art und Weise jetzt meinen Weg planen kann von Q-Start
zum Q-Ziel.
Aber das wollen wir ein bisschen genauer angucken, weil wir sind
jetzt, wir haben ja den ersten Schritt erschlagen und wir wollen jetzt
sehen, wie wir tatsächlich in diesem Wegnetz einen Weg mithilfe von
Baumsuche finden können.
So, der Anwendungsfall mobile Roboter, also 2D-Arbeits- oder
Konfigurationsräume und im 2D unterscheidet man dann nicht so sehr
zwischen Arbeits- oder Konfigurationsraum.
Oft spricht man auch von Konfigurationsraum in diesen Fällen.
Wir stellen also jetzt diesen Konfigurationsraum als Quad-Tree.
Wir unterteilen den Konfigurationsraum rekursiv in Kacheln.
Die Kacheln sind dann entweder frei oder belegt, also oder kollidieren
mit einem Hindernis oder enthalten einen Teil von einem Hindernis.
Und die Fahrtplanung ist nichts anderes, als solche Kacheln zu finden,
in denen sich Start- und Zielkonfigurationen befinden und dann
benachbartfreie Kacheln im Baum vom Start zum Ziel miteinander
verbinden.
Und dann natürlich haben wir unsere Bahn.
So, wie sieht das Ganze aus?
Das heißt, nehmen wir mal an, wie stellt man diesen Konfigurationsraum
als Quad-Tree?
Wie ich bereits angedeutet habe, gehen wir von einer Initial-Große,
zum Beispiel von dieser Zelle, also sagen wir mal 4x4.
Schwarz sollen Hindernisregionen sein, weiß sollen freie Regionen oder
Freiraum sein.
Und wir wollen diese Bezeichnung hier verwenden.
Das heißt, alle Quadrate wollen wir also unten links mit 0, dann 1 und
dann 2 und dann 3 haben.
Schwarze Knoten sind Hindernisregionen, weiße Knoten sind Freiraum und
grüne Knoten sind gemischte Knoten.
Also, wo sowohl Freiraum als auch Hindernisraum dort vorhanden ist.
Und was macht man?
Also, wir haben zunächst mal den ganzen Konfigurationsraum, das ist
nur ein Knoten in diesem Baum.
Und zwar, das ist der Knoten hier.
Und diesen Knoten zerlegen wir zunächst mal in 4.
Und was bekommen wir hier?
Wir bekommen eigentlich 4 gemischte Regionen, weil wir haben überhaupt
keine neue Zelle, in der wir nur Hindernisse oder nur Freiraum haben.
Also in 0 haben wir Hindernisse und Freiraum, in 1 haben wir Freiraum
und Hindernisse, hier haben wir auch Freiraum und Hindernisse und hier
haben wir auch Freiraum und Hindernisse.
Deshalb bekommen wir 4 gemischte Knoten zunächst mal.
Dann nehmen wir diesen Knoten hier, Knoten 0, und wir zerlegen den
Knoten nochmal rekursiv in 4 und da bekommen wir für 0 einen weißen
Knoten, für 1 bekommen wir einen schwarzen, für 2 einen weißen und der
dritte hier, der dritte Teil ist natürlich gemischt, deshalb bekommen
wir einen Kreis, einen grünen Kreis.
Das heißt, den müssen wir wieder zerlegen in 4 Teilen.
Und wenn wir den in 4 Teilen zerlegen, dann bekommen wir frei
Hindernisse, also weiß, weiß, schwarz, schwarz.
Und wenn wir das alles hier machen, bis wir am Ende in diesem Baum
überhaupt keine Kreise haben, sondern nur schwarze oder weiße
Quadranten, dann sind wir fertig und das ist dann die Darstellung
eigentlich von dem freien bzw.
dem Hindernisraum und da kann man dann die Bestimmung von einer
kollisionsfreien Bahn als eine Suche in diesem Baum hier definieren.
So, Beispiel.
Und zwar, wir hätten hier einen Arbeitsraum mit diesen Hindernissen
und das ist unser Roboter.
Und wenn man jetzt solche Planungsprobleme in diesem Raum finden oder
lösen will, dann muss man natürlich auch die Ausdehnungen von dem
Roboter hier betrachten.
Was bedeutet das?
Wir müssen also das Problem im Konfigurationsraum betrachten, also
welche Konfiguration vom Roboter, Position, Orientierung vom Roboter
führen zu Kollisionen mit den Hindernissen.
Und wenn wir jetzt den Hindernisraum im Konfigurationsraum hier
bestimmen, dann kommen wir auf sowas aus.
Es fällt natürlich auf, oder manche Leute würden jetzt hier denken,
das ist nur eine Vergrößerung von den Hindernissen, aber das ist keine
reine Vergrößerung von den Hindernissen, sondern das ist ähnlich zu
dem Beispiel, was wir vorher gesehen haben, wo wir Freiraum und
Hindernisraum bestimmt haben, weil O1 im Konfigurationsraum nicht die
gleiche Form hat wie O1 im Arbeitsraum, beziehungsweise auch O2 und
O3.
Die Hindernisse sind ein bisschen ausgedehnt, um die Ausdehnungen oder
die Abmessungen von dem Roboter, aber nicht nur das, weil diese Ecke
hier von O1 ist ja im Arbeitsraum nicht vorhanden, aber wohl im
Konfigurationsraum.
Obwohl das jetzt nur ein 2D-Beispiel ist.
Und wenn wir jetzt hier diesen Freiraum zerlegen mit unserem Tree,
dann fangen wir an mit diesen Zellen.
Da sieht man hier, dass die Zellen kleiner und kleiner werden.
Und dann können wir jetzt, wenn wir eine kollisionsfreie Bahn zum
Beispiel zwischen einer Start- und einer Zielkonfiguration haben, dann
brauchen wir nur eine Folge von freien Zellen, beziehungsweise Kacheln
zu identifizieren, beziehungsweise zu finden, die das erreichen.
Also beispielsweise entlang dieser Linie hier vom Start zum Ziel.
Und mithilfe von dieser Methode kann man sogar reaktives Verhalten
realisieren.
Das heißt, man nehme an, unser Arbeitsraum oder Hindernisraum war so
und jetzt auf einmal kommen ein paar neue Hindernisse dazu.
Da kann man natürlich hier diese Hindernisse berücksichtigen und dann
lokale Ausweichmanöver hier planen.
Okay, das heißt, wir haben jetzt drei Methoden kennengelernt, um diese
Netze zu bauen.
Die geben natürlich ein Umweltmodell, das heißt unser Freiraum und
Hindernisraum und wir haben eine Methode kennengelernt, mit der wir
tatsächlich die Suche nach einem Pfad, also das Auffinden von einer
kollisionsfreien Bahn mithilfe von Baumsuche machen können.
Aber wenn wir jetzt solche Probleme haben oder solche Probleme auf die
Art und Weise lösen, dann haben wir bis jetzt überhaupt keine Aussagen
darüber gemacht, ob die Pfade, die wir bestimmt haben, vielleicht die
optimalsten sind, die kürzesten Pfade beispielsweise.
Oder ob es überhaupt unterschiedliche Möglichkeiten gibt, zwischen
denen man wählen kann und nicht nur irgendeine Lösung, sondern
vielleicht die beste Lösung im Sinne eines Optimalitätskriteriums
betrachten.
Und das wollen wir als nächstes hier angucken.
Aber ich sehe, es gibt eine Frage.
Die grüne Linie ist dadurch entstanden, dass ich eine Sequenz von
freien Zellen zwischen Start und Ziel bekomme.
Ja, das ist nur eine Variante, also nur eine Lösung, die hier
dargestellt ist.
Nein, nein, nein, nein.
Das, was ich gerade erzählt habe als letztes.
Gut, das heißt, wir wollen uns ein bisschen mal genauer damit
beschäftigen jetzt als nächstes, wie sieht es aus mit optimalen
Lösungen, zum Beispiel mit den kürzesten Wegen zwischen einer Start-
und einer Endkonfiguration.
Nehmen wir mal an, wir hätten hier den Arma 4 und der soll jetzt in
diesem Raum von Start zum Ziel kommen.
Start grün, Ziel rot.
Und alles, was grau ist, hier ist nicht befahrbar, um zum Beispiel
diese Müsli-Box hier zu holen.
Und es ist klar, dass wir eine ganze Menge von Möglichkeiten haben.
Also wenn wir zum Beispiel hier mit Zellenzerlegung arbeiten, dann
würde sowas passieren.
Ja, also da wissen wir nicht.
Das ist ja irgendeine Sequenz von freien Kacheln oder Zellen, die wir
nehmen wollen.
Aber was uns interessiert, ist tatsächlich den Weg zu finden und zwar
den kürzesten Weg zu finden vom Start zum Zielpunkt.
Und hierzu gibt es einen sehr bekannten Algorithmus in der Informatik.
Für die Informatiker ist es natürlich ein sehr bekannter Algorithmus,
denke ich mal, oder?
Der A-Stern-Algorithmus.
Wer kennt den A-Stern-Algorithmus?
Okay, wer will es uns erklären?
Nein?
Also, der A-Stern-Algorithmus ist ein sehr beliebter Algorithmus zur
Routenplanung und zwar Routenplanung in sogenannten gewichteten
Graphen.
Das heißt, damit wir wirklich den kürzesten Weg finden, müssen wir in
einem Graph, was wir zum Beispiel mit Linesweep oder Ähnliches, müssen
wir auch Gewichte an den Kanten mal hintun.
Und da sieht man hier ein Beispiel, das heißt, das ist so ein
gewichteter Graph mit den Knoten A, B, C und so weiter und so fort bis
I.
Und an den Kanten hier sind die Kosten bzw.
die Gewichte von einer Kante.
Also man sieht zum Beispiel, dass diese Kante zwischen B und G extrem
teuer oder stark gewichtet ist, weil es vielleicht so lange dauert,
von A nach G zu kommen, weil es dort so viele Baustellen gibt.
Während von B nach H nach E nach G komme ich ja viel schneller mit 8,
vielleicht 8 als Kostenfaktor oder ja im Vergleich hier zu einer
direkten Verbindung.
So, das heißt, wenn man das hier betrachtet, dann sieht man, ich suche
jetzt irgendeinen Weg oder den Weg mit den minimalsten Kosten zwischen
A und I, dann sieht man, dass man in diesem Graph mit Hilfe von dieser
Information hier, also mit Hilfe von den Gewichten, wobei die Gewichte
hier die Kosten darstellen, dass diese grüne Linie hier die
optimalste, die kostengünstigste Linie ist.
Das kann natürlich der Abstand sein, aber das können wirklich
irgendwelche anderen Kosten, zum Beispiel die Zeit, die man braucht,
entlang dieser unterschiedlichen Knoten im Graph zu fahren.
Und wie funktioniert dieser Algorithmus?
Ja?
Gibt es Fragen?
Skypest du mit jemandem oder mit wem redest du dann?
Okay.
Gibt es Fragen soweit?
Nein.
So, wie funktioniert das Ganze?
Also natürlich müssen wir das auf unsere Probleme lösen, anwenden.
Das heißt, wir haben hier einen Konfigurationsraum, das ist unser
Quadrat hier und wir haben ein Hindernis.
Und natürlich müssen wir irgendeine approximate Darstellung jetzt von
diesem Freiraum finden und zwar müssen wir ein Netz dort erzeugen, ein
Netz und auf diesem Netz natürlich unseren Weg suchen.
Und was man hier macht, natürlich Diskretisierung zunächst mal von
diesem Raum ist notwendig und dann, das ist unser Hindernis, das
heißt, diese Knoten eigentlich, also wir gehen von einer equidistanten
Diskretisierung von dem Raum hier, sehr vereinfacht dargestellt hier
das Beispiel und diese Punkte, die zur Kollision mit dem Hindernis
führen, die können wir überhaupt nicht benutzen bei unserer Suche.
Deshalb werden sie hier aus diesem Graph eliminiert und bekommen wir
diesen resultierenden Graph, der beschreibt für uns alle Positionen
bzw.
Stationen im Freiraum, die wir bei der Suche nach einem Pfad annehmen
können.
Und die Vorgehensweise ist immer gleich.
Also ich kriege irgendwo in meinem Raum hier einen Q-Start und ich
kriege irgendwo hier ein Q-Ziel und dann muss ich natürlich diese zwei
Punkte zu den nächsten Nachbarn auf diesem Netz abbilden und dann
zwischen diesen zwei Punkten auf dem Netz den kürzesten Pfad finden
und dann anschließend natürlich zwischen Q-S und Q-S, was ich hier
jetzt nicht nochmal schreiben werde, über eine lokale Planung auch
eine Verbindung.
So und dieser Algorithmus funktioniert wie folgt, man definiert eine
Kostenfunktion und diese Kostenfunktion f von x ist die Summe von zwei
Teilfunktionen, eine g und eine h-Funktion und g entspricht den Kosten
vom Startknoten zu einem Knoten x.
Also wenn wir zum Beispiel hier einen Knoten x haben, dann beschreibt
für uns die Funktion g die Kosten, zum Beispiel der Abstand vom Start
zu x und die Funktion h entspricht den geschätzten Kosten von diesem
Knoten x zum Zielknoten.
Das heißt einmal die Kosten vom Start zum Knoten und einmal eine
Schätzung der Kosten vom Knoten x zum Zielknoten.
Und der Algorithmus findet dann den optimalen Pfad vom Start zum Ziel,
also die Knoten bezeichnen wir jetzt mit V und V-Ziel im Gegensatz zu
Q und Q-Ziel, das sollte ja überhaupt kein Problem sein.
Und hier ist eine Visualisierung, wie dieser Algorithmus, bevor ich
den erkläre, funktioniert.
Das heißt, wir haben jetzt hier den roten Punkt, das ist unser
Startpunkt und den grünen Punkt, das ist unser Zielpunkt und das ist
unser Hindernis.
Und natürlich müssen wir, wie ich bereits erwähnt habe, das Ganze
diskretisieren.
Und da sieht man, dass der Algorithmus zunächst mal versuchen wird,
entlang einer Linie zum Ziel zu kommen.
Aber er wird ja natürlich an manchen Stellen feststellen, dass es zu
Kollisionen kommt mit dem Hindernis hier.
Und man sieht hier in dieser Darstellung, dass wir irgendwelche Punkte
haben, die sind hellblau markiert.
Und diese hellblau markierten Punkte, das sind Punkte, zu denen wir
überhaupt kommen vom Start, aber die sind noch nicht endgültig
untersucht, ob sie wirklich Teil einer Lösung sind oder nicht.
Die ausgefüllten Punkte, die sind endgültig untersucht und die haben
auch zusätzlich die Informationen bezüglich des Abstands zum Ziel.
Das heißt, je weiter sie vom Ziel sind, diese ausgefüllten Punkte,
desto roter die sind, also hier rot.
Und wenn wir abgeschlossen behandelte oder betrachtete Punkte, und ich
werde gleich erklären, was das bedeutet, wenn wir solche
abgeschlossenen Punkte haben, die näher zum Ziel sind, dann werden sie
grüner.
Also grün heißt abgeschlossen betrachtet, analysiert dieser Punkt, ob
das wirklich zu einer optimalen Lösung führt und rot, auch analysiert,
ob das zu einer optimalen Lösung, aber der Abstand zum Ziel ist noch
sehr weit.
Und man merkt hier, ganz interessant, ganz am Ende, obwohl der
Algorithmus jetzt zum Ziel gekommen ist, sucht er noch weiter nach
anderen Varianten oder nach anderen Knoten, die eventuell zu einer
besseren oder optimaleren Lösung führen.
Wie funktioniert das Ganze?
Das Ganze ist ein iterativer Ansatz und allgemein funktioniert der
Algorithmus so, dass man zwei Mengen oder Listen von Knoten definiert,
eine sogenannte Open List und eine Closed List oder Set,
Entschuldigung.
Das heißt, die Open Set enthält alle Knoten, die noch zu besuchen
sind, also zu untersuchen, zu besuchen und zu untersuchen sind.
Und in dieser Closed Set Menge C alle Knoten, die man bereits
untersucht hat.
Und das heißt, man weiß, von diesen Knoten, die führen zu einem Ziel
oder gar nicht, die werden nicht Teil einer Lösung.
Und dann macht man einen Update für jeden besuchten Knoten.
Also wenn wir einen Knoten, wie wir in der Animation vorher gesehen
haben, vn besuchen, machen wir einen Update.
Das heißt einmal, was war eigentlich der Vorgänger Knoten zu dem
aktuellen Knoten?
Was sind die akkumulierten Kosten, um diesen Knoten vn, den wir gerade
betrachten, zu erreichen?
Also die Funktion g von n, das sind die Kosten vom Start bis zu diesem
Knoten.
Also immer eigentlich vom Start bis zu diesem Knoten.
Und dann mithilfe von der gegebenen Heuristik des Algorithmus, welche
Kosten sind noch zu erwarten, um von diesem aktuellen Knoten vn zum
Ziel zu kommen.
Wie initialisiert man den Algorithmus?
Einmal die Open Set ist natürlich nur der Startknoten.
Die Closed Set ist zunächst einmal die leere Menge, weil wir haben
überhaupt keine Knoten besucht und untersucht.
Damit wir überhaupt die erste Lösung akzeptieren können, ja, und wir
akzeptieren nur solche Lösungen, die zu geringeren Kosten, die
geringere Kosten haben, initialisieren wir alle Kosten von allen
Knoten mit irgendwas ganz Großem, also im Idealfall unendlich.
Also großen Wert einsetzen für die initialen Kosten von allen Knoten,
die wir untersuchen sollen.
Und natürlich die Kosten, um den Startknoten hier zu erreichen, sind
null, weil ich bin ja im Startknoten.
So, und dann, solange also dieses Open Set nicht leer ist, bestimmen
wir immer den zu erweiterten Knoten.
Also man findet einen Knoten aus der offenen Menge mit einem minimalen
Kosten.
Das heißt, die Gesamtfunktion f für diesen Knoten vi ist gleich g von
vi plus h von i sind minimal.
Wenn natürlich dieses vi unser Ziel ist, dann haben wir eine Lösung
bereits gefunden.
Sonst müssen wir natürlich hier dieses vi nach jeder Untersuchung,
also wenn wir den besucht und analysiert haben, aus der Open Set
entfernen und dann natürlich zu der Closed Set hinzufügen.
Und dann müssen wir in jedem Schritt so ein Update machen, und zwar
für alle Nachfolger von diesem Knoten, was wir gerade betrachten, also
vi.
Und wenn zum Beispiel der Nachfolger von einem Knoten vi in der Closed
Set ist, dann natürlich überspringen wir das.
Das heißt, wir haben das schon mal besucht und deshalb brauchen wir
das nicht mehr zu betrachten.
Wir überspringen den.
Wenn der nicht in der Open Set ist, dann müssen wir natürlich das
hinzufügen, weil wir das noch nicht besucht haben.
Und dann betrachten wir diese Kosten.
Also eigentlich muss man sich vorstellen, ich bin jetzt hier im
Knoten.
Ich bin im Knoten vi und das ist jetzt mein vi.
Ja.
Und wenn jetzt die Kosten von vi, also natürlich starte ich hier
irgendwo an einem Startpunkt, hier vs.
So, wenn die Kosten von vi, also natürlich um dorthin zu kommen, habe
ich hier irgendwelche Kosten, und zwar das ist g von vi und um von vi
zu vj zu kommen, habe ich natürlich auch Kosten.
Und das sind Kosten vi, vj.
Wenn die Kosten von g von vi plus die Kosten um von vi zu vj kleiner
als die Kosten von vj, weil vj könnte natürlich man erreichen über
einen anderen Weg.
Und das wäre jetzt hier die Kosten vj.
Wenn also diese Summe der Kosten kleiner als alle anderen
Möglichkeiten, um an den Punkt oder an den Knoten vj zu kommen, dann
sage ich okay, die Kosten von vj sind die Kosten von vi plus die
Kosten von vi, vj.
Also ich akzeptiere eigentlich vj als der nächste Punkt bzw.
vi als der Vorgänger von vj.
Und ich muss natürlich diese Heuristik berechnen, das heißt, was sind
die geschätzten Kosten jetzt von vj zum Ziel, das ist irgendeine
Heuristikfunktion, die eingegeben ist natürlich durch den Algorithmus.
Und ich sage, dass der Vorgänger von vj ist vi.
Also für jeden Knoten muss ich mir das alles merken.
Einmal muss ich merken, sind die Kosten von dem Vorgänger plus die
Kosten von dem Vorgänger zu dem jetzigen Punkt, den ich analysiere,
kleiner als alle anderen Kosten?
Dann definiere ich diesen neuen Punkt als den Nachfolger bzw.
vi als den Vorgänger von vj.
Und ich muss mir diese ganze Information merken, damit ich natürlich
nachher rückwärts den Weg finde vom Ziel, wenn ich das Ziel erreiche,
bis zum Startpunkt.
Und das Ganze wollen wir anhand von einem Beispiel angucken.
Also das ist so ein Raum, den haben wir diskretisiert hier.
Wir haben Gitter mit 15 Knoten und wir sollen den optimalen Weg von V2
nach V13 finden.
Wir dürfen uns nur vertikal und horizontal bewegen.
Und wir haben folgende Kosten, wenn wir eine graue Zelle betreten,
dann haben wir eine Kosten von 1, wenn wir eine gelbe Zelle betreten,
z.B.
von V2 nach V5 oder V4 nach V5, dann haben wir Kosten von 4.
Und unsere Heuristik, die H-Funktion, ist nichts anderes als die
Heuristik, also die H-Funktion von irgendeiner Zelle, ist nichts
anderes als die euklidische Distanz zum Ziel, zum Ziel, zu V13.
Also z.B.
die Heuristik um H bei Knoten V11 ist nichts anderes als 1 plus 1 zum
Quadrat, also 2 zum Quadrat.
Die euklidische Distanz ist Wurzel 2.
Also das heißt, diese Heuristik muss natürlich immer definiert werden.
So, und dann die Kosten natürlich pro Schritt.
Und jetzt, wie gehen wir weiter?
Wir initialisieren das Ganze, das heißt, wir fangen bei V2, weil wir
wollen ja von V2 nach V13 kommen.
Das heißt, unsere Funktion, Kostenfunktion von V2 ist natürlich die G
-Kosten von V2, die sind 0.
Wir initialisieren ja die Kosten für den Start, Knoten sind 0, plus
die Heuristik von V2.
Das bedeutet, die euklidische Distanz von V2 zu V13, das ist 1, 2, 3,
4 zum Quadrat, plus 1 zum Quadrat, also Wurzel aus 17, also 4,12.
So, und die Closed Set ist natürlich noch leer.
Was machen wir?
Wir machen jetzt ein Update und zwar bei diesem Update expandieren wir
jetzt, gucken wir ja, welche Möglichkeiten haben wir jetzt von V2?
Wir können zu V1 gehen, zu V5 und zu V3.
Das heißt, unser Open Set ist jetzt V1, V3 und V5.
Alle benachbarten Knoten von unserem Startknoten.
Und was müssen wir machen?
Wir müssen natürlich die Kostenfunktionen von allen Knoten im Open Set
jetzt bestimmen.
Und diese Kostenfunktion f ergibt sich aus der Kostenfunktion g plus
die Heuristik h.
Also das heißt, wenn ich jetzt hier ein bisschen zurückgehe, das ist
eigentlich unsere Funktion g. Das ist Funktion g und das ist die
Funktion h.
So, das heißt, wenn ich hier zu V1 gehe, von V2, dann betrete ich eine
graue Zelle.
Deshalb sind die Kosten 1, um bei V1 zu landen, plus die Heuristik, um
von V1 zu V13 zu kommen.
Das sind nur 4 Blöcke, wie man sieht.
Also Wurzel aus 4 Quadrat ist 4.
Also 1 plus 4 ist 5.
Von V3, ich betrete auch eine graue Zelle.
Deshalb sind die Kosten 1 plus die Heuristik von V3 zu V13.
Das ist 1, 2, 3, 4 zum Quadrat plus 2 zum Quadrat.
Also 20 zum Quadrat ist 1 plus, also Wurzel von dem ist gleich 5, das
hier.
Und bei 5 sind die Kosten, ich betrete eine gelbe Zelle, deshalb ist g
von 5 4 plus die Heuristik, die Kosten, also die Heuristik von V5 nach
V13.
Das ist 1, 2, 3 zum Quadrat plus 1 zum Quadrat, also 10 zum Quadrat,
10 und Wurzel daraus.
Also insgesamt habe ich die Kosten 7,16.
Was bedeutet das?
Was haben wir jetzt gemacht?
Das heißt, wir haben jetzt den Punkt V2 abgeschlossen.
Was machen wir als nächstes?
Was ist der nächste Schritt jetzt in dem Algorithmus?
Ja, das ist ja unser Ziel.
Unser Ziel ist herauszufinden, welcher Weg der beste ist.
Aber was genau muss ich jetzt machen als nächster Schritt?
Genau, wir müssen eigentlich alle Knoten in diesem Open Set mal auf
die gleiche Art und Weise analysieren.
Das heißt, wir haben den Zustand, das ist unser Open Set.
Das sind die Kosten von den Knoten in diesem Open Set und das ist
unser Closed Set.
Jetzt müssen wir ein Update machen.
Wir können sagen, okay, wir expandieren V1 und man sieht hier von V1,
wenn ich V1 expandiere, dann kommt natürlich V4 hier zum Open Set.
Und V4, die Kosten sind, um von V2 nach V4 zu kommen, muss ich eine
graue Zelle und nochmal eine graue Zelle betreten.
Also deshalb die Kosten 2 plus die Heuristik von V4 zu V13.
1, 2, 3.
Wurzel aus 3 zum Quadrat ist 3, also insgesamt 5.
Und somit habe ich hier V1 abgeschlossen.
Natürlich von V1 kann man zu V2 gehen, aber V2 ist ja in der Closed
Loop, deshalb überspringe ich den Schritt hier und brauche ich hier
diese Analyse nicht mehr zu machen.
Genau, das Beispiel werden wir in der Übung dann zu Ende führen.
Ich werde natürlich nicht das ganze Beispiel jetzt hier zu Ende
führen, damit wir den richtigen bzw.
den optimalen, kostengünstigeren Weg von V2 nach V13 machen.
Und ich will nur kurz mit ein paar Eigenschaften, obwohl die Zeit ist
aus, deshalb machen wir am Donnerstag weiter mit ein paar
Schlussbetrachtungen hier zum Algorithmus und dann weiter natürlich
mit der Vorlesung, mit der Bewegungsplanung für Manipulatoren.
Für heute bedanke ich mich sehr für die Aufmerksamkeit und wünsche
euch noch einen schönen Abend.