So, dann begrüße ich Sie recht herzlich zur heutigen Übung in Robotik
I.
Fangen wir gleich an.
Es geht heute um das fünfte Übungsblatt.
Das Übungsblatt haben Sie sich ja vermutlich schon angeschaut.
Auf diesem fünften Übungsblatt gab es fünf Aufgaben zu bearbeiten.
Die erste Aufgabe zu Voronoi-Diagrammen.
Die zweite Aufgabe zu dem Line-Sweep-Verfahren.
Die dritte Aufgabe zu RRT.
Dann A-Stern und Potenzialfelder.
Was haben diese Aufgaben gemeinsam?
Es sind alles unterschiedliche Verfahren zur Bewegungsplanung.
Das heißt, wenn Sie einen Roboter haben, unter Umständen auch in einem
hochdimensionalen Raum, also Sie haben zum Beispiel einen sieben- oder
achtdimensionalen Gelenkwinkelraum, und Sie haben eine
Startkonfiguration für den Roboter gegeben und eine Zielkonfiguration,
dann stellt sich die Frage, wie finden Sie in diesem hochdimensionalen
Raum eine Trajektorie, um von Ihrem Startpunkt zum Zielpunkt zu
kommen.
Und das ist kein leichtes Problem, das können Sie sich vermutlich
vorstellen.
Deswegen haben sich hier unterschiedliche Verfahren etabliert.
Fangen wir zunächst mal mit den Voronoi-Diagrammen an.
Voronoi-Diagramme an sich sind jetzt keine Technik zur
Bewegungsplanung, aber sie liefern eine wichtige Grundlage, mit denen
Sie dann eine Bewegungsplanung durchführen können, nämlich eine
Repräsentation Ihrer Umwelt oder Ihrer Umgebung als Graph.
Das werden wir gleich noch sehen.
Das wurde aber auch, glaube ich, in der Vorlesung gezeigt.
Fangen wir zunächst mal mit ein paar Begriffsdefinitionen an.
Aufgabenstellung auf dem Übungsblatt war ja, erklären Sie die Begriffe
Voronoi -Region, Voronoi-Kante und Voronoi-Knoten.
Und dann fangen wir einfach mal an.
Hier sehen Sie schon ein Voronoi-Diagramm.
Und was ist eine Voronoi-Region?
Nun, die Voronoi-Region ist definiert als die Menge aller Punkte des
euclidischen Raums, die näher am Zentrum der Region liegen als an
allen anderen Zentren, die eben zur Auswahl stehen.
Das heißt, wenn wir das mal betrachten, vielleicht nehme ich hier am
besten den Presenter, wenn wir jetzt mal den grünen Punkt betrachten,
der grüne Punkt wäre jetzt in dem Fall das Zentrum der Region und alle
Punkte, die in dieser Region liegen, die hier eben durch diese blauen
Kanten begrenzt wird, gehören zur Voronoi-Region dieses Punktes.
Das heißt, die liegen näher an diesem Zentrum als an allen anderen
möglichen Zentren, die jetzt hier rot dargestellt sind.
Das mag trivial erscheinen, aber wir müssen diese Begrifflichkeiten
klären, natürlich auch hinsichtlich auf Übungsaufgaben oder auf
Klausuraufgaben, damit es hier nicht zu irgendwelchen
Missverständnissen kommt.
Das ist jetzt mein erster Versuch hier mit diesem Convertible.
Ich habe das vorhin extra ein bisschen geprobt, aber bitte verzeihen
Sie mir das trotzdem, wenn es jetzt nicht alles so auf Anhieb perfekt
funktioniert.
Das heißt, die Region, die ist definiert als die Menge aller Punkte,
deren Abstand zum Zentrum, aus irgendeinem Grund macht er jetzt hier
oben, geringer ist als zu allen
anderen Zentren.
Okay,
Sie haben es natürlich hier auch nochmal mit dem Text auf den Folien,
falls Sie jetzt meine Schrift hinterher nicht so gut lesen können.
Dann der nächste Begriff, die Voronoi-Kante, die hatte ich ja gerade
schon erwähnt.
Die Voronoi-Kante ist genau der Punkt, wo Sie Punkte des euclidischen
Raums haben, die equidistant zwischen zwei oder mehr Zentren liegen.
Das heißt, es ist die Kante zwischen zwei Voronoi-Regionen, die sind
hier jetzt blau dargestellt.
Das heißt, die Kante
ist die Menge der Punkte auf der Grenze
zwischen zwei Voronoi-Regionen.
Und das ist dann gleicher Abstand zum eigenen und benachbarten
Zentrum.
Okay, dann die letzte Definition.
Hier geht es um den Voronoi-Knoten.
Am Begriff des Knotens können Sie schon sehen, was ich erwähnt habe
mit dem Graphen.
Das Voronoi-Diagramm ist natürlich eine Sache, die nicht aus der
Robotik kommt.
Aber diese Terminologie mit dem Knoten, die deutet schon darauf hin,
wie wir das dann im Kontext der Robotik anwenden werden.
Der Voronoi-Knoten ist nämlich die Ecken der Polygone bzw.
Voronoi-Regionen.
Und jetzt kommen wir zur zweiten Teilaufgabe.
Und das ist die Konstruktion eines Voronoi-Diagramms.
Also die Aufgabe lautet, bestimmen Sie das Voronoi-Diagramm für p,
wobei p eben diese Punktmenge hier ist.
Jetzt gibt es ein grafisches Konstruktionsverfahren, wie wir dieses
Voronoi -Diagramm bestimmen können.
Bevor ich jetzt anfange, haben Sie sich das angeschaut?
Wissen Sie, wie das geht?
Wer weiß, wie man diese Aufgabe löst?
Okay, es meldet sich niemand.
Eine Person, okay.
Dann zeige ich es Ihnen.
Das Ganze ist ein rekursives Verfahren.
Sie können also nicht, wenn Sie jetzt zehn oder sechs Punkte gegeben
haben, jetzt einfach zack sagen, Sie legen jetzt irgendwie ein Lineal
rein und zeichnen da das Voronoi-Diagramm ein.
Sondern was Sie machen, ist, dass Sie erst einmal die Menge Ihrer
Punkte separieren.
Das heißt, Sie müssen diese Punkte irgendwie in irgendeiner Weise in
zwei gleich große Teilmengen unterteilen, wobei eine der Teilmengen
natürlich einen Punkt mehr beinhalten darf, wenn Sie eine ungerade
Anzahl an Punkten haben.
Und das machen wir jetzt mal.
Am besten nehme ich hierzu eine andere Farbe.
Vielleicht grau gibt es nicht, vielleicht grün.
Unterteilen wir es mal ganz naiv, unterteilen wir es mal so.
Falls es etwas krakelig wird, wie gesagt, Sie finden auch da noch mal
eine sauber gezeichnete Version in den Folien hinterher.
Und jetzt haben wir in jeder dieser Teilmengen nur noch drei Punkte.
Und für diese drei Punkte können wir das Ganze lösen.
Das ist der sogenannte Basisfall.
Und in diesem Basisfall, dieser Basisfall funktioniert so, dass wir
jetzt erst einmal die Punkte verbinden.
Das hat aber mit dem Voronoi-Diagramm noch nichts zu tun.
Das heißt, wir haben jetzt hier zwei Dreiecke.
Sie sehen schon, dass das etwas hakelig wird.
Und die Idee ist jetzt, dass wir auf diesen Verbindungslinien, in der
Mitte dieser Verbindungslinien, orthogonal dazu Linien einzeichnen.
Das sind dann auch schon Voronoi-Kanten.
Die sind allerdings in ihrer Länge noch nicht endgültig.
Das werden wir gleich noch sehen.
Das sind also die sogenannten Mittelsenkrechten, die wir jetzt
einzeichnen.
Und um diese Mittelsenkrechten einzuzeichnen, brauchen Sie nur ein
Geodreieck.
Sie können ja mit dem Geodreieck messen, wo ist die Mitte.
Sie können den rechten Winkel abmessen und dann die Mittelsenkrechte
einzeichnen.
Das machen wir vielleicht blau.
Dann haben wir also hier eine Mittelsenkrechte.
Wie gesagt, die Länge dieser Mittelsenkrechten ist noch nicht
endgültig.
Aber Sie sehen, dass es schon in die Richtung eines Voronoi-Diagramms
geht.
Und das Gleiche machen wir jetzt hier unten.
Da haben Sie den Spezialfall, dass die Mittelsenkrechte der dritten
Kante, die würde hinter der Trennlinie liegen, deswegen muss ich die
jetzt hier nicht einzeichnen, dann haben Sie hier das jeweils lokale
Voronoi -Diagramm bestimmt.
Und jetzt kommt der nächste Schritt.
Diesen Schritt des Unterteilens würden Sie natürlich rekursiv
durchführen, wenn Sie mehr als sechs Punkte haben.
Wenn Sie sechs Punkte haben, passt das.
Wenn Sie zum Beispiel zehn Punkte hätten, dann müssten Sie eben diesen
Unterteilungsschritt zweimal durchführen und lösen das Voronoi-Problem
auf der untersten Ebene, wo Sie nur drei Knoten haben oder drei
Zentren.
Und jetzt müssen Sie das wieder merchen, wieder von bottom up merchen.
Und für diesen Schritt gehen Sie jetzt von der untersten Ebene des
Baumes hin und verbinden die Nachbarn aus dem letzten Split, den Sie
quasi gemacht haben.
Hier gab es jetzt nur einen Split.
Die verbinden Sie.
Das mache ich jetzt mal gelb.
Das heißt, die Nachbarn, die eben am nächsten zur Kante liegen, also
den hier, den hier und den auch und den.
Mit dem Punkt da oben müssen Sie nichts verbinden, weil der ja in
einer Voronoi-Region liegt, also in dieser Region hier oben, die gar
nicht angrenzt an die Trennebene, die Sie jetzt hier haben.
So, und jetzt machen Sie das gleiche Spielchen wieder.
Jetzt zeichnen Sie hier wieder die Mittelsenkrechten ein.
Machen wir das zum Beispiel jetzt mal hellblau.
Dann haben wir hier die Mittelsenkrechten.
So.
Und so.
Und die Mittelsenkrechte hier, die fängt quasi erst hier an.
Das heißt, hier haben Sie auch den Fall, dass das quasi außerhalb des
Bereichs liegt.
Und jetzt sind Sie im Prinzip schon fertig.
Jetzt müssen nur noch die Linien entsprechend gekürzt bzw.
verlängert werden.
Das heißt, überall, also ein Beispiel zum Beispiel hier, überall, wo
Sie jetzt eine Linie haben, die nach diesem Merge-Schritt, nach diesem
Korrekturschritt quasi außerhalb der entsprechenden Voroneuregion
liegt, müssen Sie die jetzt abschneiden.
Jetzt habe ich natürlich ein bisschen das Problem, dass es mir hier
sehr schwer fällt, das abzuschneiden.
Ich werde es jetzt einfach rot durchstreichen.
Ich meine, das können Sie sich dann entsprechend vorstellen.
Das würde man jetzt eben hier wegschneiden.
Und diese Linie hier, die würde man verlängern nach da oben.
Und das ist die Vorgehensweise.
Gibt es dazu Fragen?
Okay, das ist nicht der Fall.
Wie gesagt, Sie können es hier nochmal, wir können es uns nochmal
zusammen ordentlich anschauen.
Also, Sie separieren das Ganze, lösen den Basisfall jeweils, zeichnen
die Mittelsenkrechten ein.
Verbinden die Nachbarn.
Und zeichnen dann wieder die Mittelsenkrechten ein.
Das sind jetzt hier die hellblauen Linien der
Nachbarverbindungslinien.
Und dann führen Sie diesen Korrekturschritt aus.
Und jetzt sind wir fertig in dem Fall, weil wir nur einmal gesplittet
haben.
Wenn wir jetzt zum Beispiel zwölf Punkte gehabt hätten, dann hätten
wir einmal und dann noch zweimal gesplittet.
Dann würden Sie das jetzt zum Beispiel hier nebendran in Ihrer anderen
Region parallel nochmal machen und dann das Ganze nochmal merchen.
Aber die Vorgehensweise ist genau die gleiche.
Sie können sich aber natürlich vorstellen, dass wenn so eine Aufgabe
mal irgendwo drankommt, die in ihrer Komplexität natürlich jetzt nicht
so sein wird, dass Sie dann da am Ende mit 15 Punkten rumjonglieren
müssen.
Wichtig ist hier noch, eine Sache war ja hier nicht vorgegeben, die
war willkürlich.
Nämlich, was passiert, wenn wir das Ganze hier anders aufteilen.
Ich sehe jetzt gerade, das ist eine Bonusaufgabe, das haben wir also
nicht auf dem Übungsblatt.
Aber das können Sie sich ja mal überlegen.
Dadurch, dass das Vor- und Neudiagramm eindeutig definiert ist, ist
die Antwort natürlich, dass am Ende das gleiche Vor- und Neudiagramm
hier entstehen muss.
Es kann nicht sein, dass plötzlich ein anderes Vor- und Neudiagramm
entsteht.
Das ist aber relativ beeindruckend, warum das jetzt genauso ist.
Mathematisch beweisen kann ich es Ihnen jetzt nicht.
Ich vermute, dass der Beweis möglich ist, aber das habe ich mir jetzt
nicht angeschaut.
Sie können es einfach mal ausprobieren.
Vielleicht als Übung führen Sie das mal mit einem anderen Split.
Sie können auch hier so den Split durchführen oder Sie können die
Punktmenge beliebig anders splitten, wenn Sie hier zum Beispiel so die
Kante dadurch ziehen.
Und führen Sie das dann mal aus.
So, jetzt aber nochmal ganz kurz zurück zur Robotik.
Wie würde man jetzt so ein Vor- und Neudiagramm anwenden in der
Robotik, wenn wir jetzt dieses Vor- und Neudiagramm haben?
Wie funktioniert es für die Bewegungsplanung?
Stellen Sie sich mal vor, die Punkte, die wir hier haben, sind
Hindernisse.
Und Ihr Ziel ist es, möglichst robust von einem Start zu einem
Zielpunkt zu kommen und dabei den Hindernissen nicht zu nahe zu
kommen.
Das heißt, Ihr Ziel ist letztendlich, dass Sie immer einen maximalen
Abstand zum nächsten Hindernis einhalten.
Und diesen maximalen Abstand zum nächsten Hindernis erhalten Sie
genau, wenn Sie sich nur auf den Vor- und Neukanten bewegen.
Das heißt, Sie definieren sich hier einen Graphen, der besteht aus den
Vor - und Neukanten zwischen den Vor- und Neuknoten.
Also die Vor- und Neuknoten sind die Knoten dieses Graphs und die
Kanten sind eben die Kanten zwischen die Verbindungen.
Und wenn Sie jetzt irgendwo einen Startpunkt haben, dann müssen Sie
nur schauen, dass Sie eben zu dem nächstgelegenen Vor- und Neuknoten
kommen.
Zum Beispiel mit einer direkten Verbindung, weil dieser Weg, der wird
in der Regel nicht sehr lang sein.
Sie können das dann auch mit einem anderen Verfahren, mit RRT noch
planen zum Beispiel.
Und Sie müssen schauen, was ist der Vor- und Neuknoten, der Ihrem Ziel
am nächsten ist.
Und wenn Sie das haben, dann müssen Sie nur auf diesem Graph eine
Verbindung von dem Vor- und Neuknoten des Starts zum Vor- und
Neuknoten des Ziels finden.
Das können Sie dann zum Beispiel mit Astern lösen oder mit dem
Dijkstra -Algorithmus oder mit einem anderen Suchverfahren.
Den Astern-Algorithmus, den werden wir ja auch gleich noch hier sehen.
Der wurde ja auch in der Vorlesung behandelt.
Okay, wenn es keine Fragen gibt, dann würde ich jetzt zur zweiten
Aufgabe kommen, nämlich zum Line-Sweep-Verfahren.
Das Line-Sweep-Verfahren ist, also hier gehen wir jetzt nicht mehr von
punktförmigen Hindernissen aus, wie bei Vor- und Neudiagrammen,
sondern hier haben Sie jetzt einen Hindernisraum, der sieht zum
Beispiel so aus, wie der jetzt hier in der Aufgabe gegeben ist.
Und wir möchten auch wieder eine Graph-Repräsentation dieses Raums
gewinnen, um dann im Anschluss zum Beispiel mit Astern Wege in diesen
Graphen zu planen.
Okay, laut Aufgabenstellung ist das der Grundriss einer Wohnung.
Ein bisschen seltsame Wohnung, aber ist ja okay.
Bestimmen Sie die Zellzerlegung des gegebenen Grundrisses mittels des
Line -Sweep-Verfahrens und nummerieren Sie die Zellen.
Dann, Sie sehen, hier ist eine Animation drin.
Einzeichnen muss ich die Linie noch von selbst.
Für das Line-Sweep-Verfahren müssen Sie natürlich immer definieren,
wie Ihre Linie über das Bild drüberwischt.
Wir machen das jetzt hier in der Aufgabe von links nach rechts und
nummerieren die Zellen eben von links nach rechts und bei gleicher X
-Koordinate von oben nach unten.
Falls so eine Aufgabe mal in einer Klausur zum Beispiel drankommt,
wird das natürlich auch dann entsprechend nochmal in der
Aufgabenstellung gegeben sein.
Oder es ist natürlich alles richtig, was Sie dann letztendlich da
annehmen.
Okay.
Machen wir wieder blau.
Und jetzt, das Line-Sweep-Verfahren funktioniert so, dass unsere
Linie, die eben hier durch den Grundriss überfährt, immer dann eine
Trennlinie oder eine Kante setzt, wenn sich unsere Hindernisgeometrie
entsprechend ändert.
Das heißt, unsere erste Linie, die brauchen wir hier an dieser Ecke.
Dann brauchen wir die zweite Linie, also wir gehen hier weiter, dann
hier an dieser Stelle.
Wichtig ist jetzt hier, diese Trennlinie, Sie haben jetzt hier ein
Hindernis, aber hier haben Sie ja das Hindernis im Weg.
Das heißt, diese Linie beim Line-Sweep-Verfahren, die wird nur hier
oben gesetzt.
Also hier oben, diesen Freiraum hier, den unterteilen Sie in zwei
Zellen, also links und rechts.
Während Sie hier unten nichts unterteilen müssen.
Genau.
Dann, das nächste ist hier.
Also wir können es auch...
Ist die jetzt gerade wieder verschwunden?
Wir können es auch gerne gleich nummerieren.
Nummerieren wir mal.
Hier haben wir die 1, hier haben wir die 2.
Ich habe ja gesagt, bei gleicher X-Koordinate quasi von oben nach
unten.
Das heißt, hier unten steht dann die 3.
Dann haben wir hier die 4.
Und hier unterteilen wir natürlich auch.
Das heißt, hier ist die 4, hier ist die 5.
Und hier müssen wir unterteilen und hier auch.
Das ist die 6.
Hier ist ein Hindernis.
Das ist die 7.
Dann haben wir das hier.
Dadurch ergibt sich hier unten die 8.
Das hier oben, das ist die 9.
Also Sie gehen einfach von links nach rechts.
Das kann ein bisschen verwirrend sein.
Deswegen sollten Sie das vielleicht ein, zwei Mal üben, dass Sie eben
auch keine Ecke vergessen.
Weil in dem Moment, wo Sie eine Ecke vergessen, wird natürlich Ihre
Nummerierung komplett falsch.
Heißt jetzt nicht, dass es in der Klausur dann da plötzlich 0 Punkte
gibt.
Das wird schon entsprechend gewertet dann als Folgefehler auch und so
weiter und so fort.
Aber es ist natürlich trotzdem immer ärgerlich.
Genau, die Linie, die muss natürlich auch hier durchgehen.
Dann haben wir also hier.
Hier oben ist ja die 9.
Das heißt, hier unten ist dann die 10.
Und hier ist die nächste Ecke.
Dann ergibt sich hier die 11.
Und hier oben ist die 12.
Hier haben wir wieder...
Hier haben wir wieder eine Ecke.
Hier ist hier die 13, die 14.
Das ist trivial hier der Fall.
Dann ist hier die 15.
16.
Und hier ist 17.
18.
19.
20.
21.
Und wichtig, nicht das letzte hier vergessen, 22.
Ich glaube, das war sogar eine Aufgabe in der letzten Klausur.
Ich bin ja eigentlich nicht für die Klausur zuständig, aber ich habe
mit korrigiert.
Ich habe die Aufgabe korrigiert.
Okay.
Dann hätten wir diese Aufgabenstellung gelöst.
Nächste Aufgabenstellung.
Ermitteln Sie den Adjacenzgraf?
Ah, es ist sogar als Animation vorhanden.
Okay, gut.
Da hat sich jemand viel Mühe gemacht.
So, der Adjacenzgraf.
Das ist jetzt natürlich ein bisschen blöd, weil Sie jetzt die Lösung
aus dem vorherigen Teil nicht mehr sehen können.
Ich zeichne den jetzt trotzdem einfach mal hin.
Ja, ich zeichne ihn kurz.
Nur, dass Sie sehen, wie dieser Adjacenzgraf aussehen sollte.
Dann haben wir hier die 8.
Das heißt, im Adjacenzgraf besteht eine Verbindung zwischen zwei
Knoten, wobei die Knoten eben entsprechend den nummerierten Bereichen
ihres Freiraums entsprechen, besteht genau dann, wenn diese beiden
Bereiche des Freiraums durch eine Kante verbunden sind.
Machen wir mal hier Punkt, Punkt, Punkt.
Ich glaube, das reicht.
So sieht er aus, der Adjacenzgraf.
Und hier haben wir die Aufgabenstellung gegeben, im dritten
Aufgabenteil jetzt ein Pfad von Q-Start zu Q-Ziel zu finden.
Und Q-Start und Q-Ziel, müssen wir vielleicht nochmal zurück, dass wir
das sehen können.
Q-Start und Q-Ziel befinden sich in Bereichen des Freiraums.
Jetzt wissen wir, das war die 22.
Und das hier war die 6.
Das müssen Sie sich jetzt kurz merken.
Das heißt, wir wollen von Knoten Nummer 6 zu Knoten Nummer 22.
Und ich denke, es ist hier relativ offensichtlich, welchen Weg Sie
gehen würden.
Sie gehen also, ich meine, Sie können hier runter und dann hier rüber,
hier hoch und hier rüber.
Als Algorithmus könnten Sie jetzt hier beispielsweise den A-Stern
-Algorithmus einsetzen.
Und da ist natürlich noch die wesentliche Frage jetzt, wenn Sie jetzt
so einen Pfad planen, woher wissen Sie denn, zum Beispiel hier, ob Sie
hier unten rumlaufen über den Knoten 15 oder über den Knoten 16.
Und das ist die sogenannten Kantenkosten eben für den A-Stern
-Algorithmus, wenn Sie den anwenden möchten.
Da können Sie unterschiedliche Theoristiken verwenden in der Praxis.
Wenn es Ihnen einfach nur darum geht, irgendwie zum Ziel zu kommen,
spielt das natürlich keine Rolle.
Wenn Sie effizient zum Ziel kommen würden, könnten Sie beispielsweise
die Größe der gemeinsamen Kante betrachten.
Denn wenn die gemeinsame Kante sehr schmal ist, dann bedeutet das ja,
dass Sie eben nah an einem Hindernis vorbei müssten.
Das ist also unter Umständen gefährlich.
Oder Sie könnten den Abstand der Zentren der beiden Freiraumregionen
betrachten.
Da können Sie also verschiedene Metriken einsetzen.
Das wird aber jetzt hier in dieser Aufgabe nicht weiter vertieft.
Und dementsprechend können Sie hier diesen Pfad planen.
Wie gesagt, mit dem Knoten 16 statt 15 wäre es natürlich auch eine
korrekte Lösung.
Oder gleich, wenn Sie hier eben, na gut, wenn Sie hier oben rumlaufen,
dann haben Sie einen Knoten mehr.
Aber auch das kann ja unter Umständen sogar besser sein, wenn es eben
kleine Regionen sind, wo Sie schneller durch können.
Gut.
Dann die dritte Aufgabe.
Da geht es um RRT, also Rapidly Exploring Random Trees.
Und im Speziellen geht es hier um den RRT-Sternalgorithmus.
Der RRT-Sternalgorithmus, der ist noch ein bisschen ausgefuchster.
Da haben Sie noch den Rewire-Schritt, das werden wir gleich sehen.
Das wurde ja auch in der Vorlesung gezeigt.
Und hier haben wir jetzt den Graphen schon gegeben.
Also der RRT-Algorithmus, der lief hier schon eine Weile.
Er hat irgendwo angefangen, hier bei Q1.
Und hat hier schon einen Baum gebaut, der schon zehn oder neun Knoten
umfasst.
Und es ist jetzt noch ein Knoten dazugekommen.
Das heißt, wir haben also die Knoten hier Q1 bis Q9, wobei eben Q1
unser Startpunkt ist.
Und die Wegkosten für jede Kante, die sind hier an den Kanten
angegeben.
Das heißt, um von Q1 nach Q3 zu kommen, haben Sie Kosten von 1 plus 2,
das heißt Gesamtkosten von 3.
Das werden wir gleich noch betrachten.
Und jetzt haben wir in dem aktuellen Iterationsschritt, den wir gerade
durchführen, hier den Knoten Qnew hinzugefügt.
Basierend auf QS, das werden wir jetzt als erstes betrachten.
Denn die erste Frage ist, wie wurde der Knoten Qnew überhaupt
ermittelt?
Und da kommt die sogenannte Steer-Funktion ins Spiel.
Das ist also genau unser RRT-Stern.
Wenn Sie also den normalen RRT-Algorithmus haben, dann sampeln Sie
irgendeinen Punkt und setzen da einen Knoten hin.
Ich glaube, es ist sowieso noch auf blau eingestellt.
Dann haben wir also hier QS.
Das ist das aktuelle Sample.
Also es ist ja ein randomisierter Algorithmus, das heißt in jedem
Schritt, wenn Sie Ihren RRT wachsen lassen wollen, sampeln Sie
irgendeinen Punkt.
Also Sie wählen einfach einen zufälligen Punkt des Raums aus.
Das ist Ihr QS.
Und dann haben Sie die Schrittweite D, die ist gegeben.
Die Schrittweite ist einfach ein Parameter, den legen Sie fest vorher.
Und je nachdem, ob Sie den gut oder schlecht festlegen, wird Ihr RRT
-Algorithmus auch effizienter oder weniger effizient Lösungen finden.
Und dann haben Sie QNN und QNN ist das, was Sie bestimmt haben, das
ist der nächste Nachbar.
Und dieses QNN ergibt sich aus der Steer-Funktion.
Wir haben also hier...
Nein, Quatsch.
QNN, der nächste Nachbar, ist der Punkt, der am nächsten an QS dran
liegt.
Und das ist der Punkt, von dem aus Ihre Steer-Funktion jetzt den neuen
Punkt erzeugt.
Dann jetzt haben wir hier QNU.
Und QNU ergibt sich aus der Steer-Funktion von QNN, QS und D.
Das heißt,
wir haben hier...
Aber ich glaube, das ist jetzt auf den Folien besser zu sehen.
Wir haben hier den gesamtelten Punkt, suchen uns den nächsten Nachbar
raus.
Eben hier Q7, der Punkt, der am nächsten dran ist.
Und gehen jetzt ausgehend von Q7 die Schrittweite D auf dieser
Verbindung in Richtung von QS.
In dem Fall ist jetzt D gleich 1 und dort setzen Sie Ihren neuen
Punkt.
Wozu brauchen wir diese Schrittweite?
Die brauchen wir einfach deswegen, weil wir wollen nicht, dass unser
Baum beim Wachsen riesige Sprünge macht und extrem lange Kanten
ergänzt, sondern wir wollen eigentlich, dass der etwas zielgerichteter
wächst.
Das heißt, wenn wir einen Punkt sammeln, der sehr weit weg ist, machen
wir damit einen Schritt, der eben dem vorgegebenen Wachstum unseres
Grafen entspricht oder des Baums.
Das heißt, diese Schrittweite legt quasi fest, wie schnell unser Baum
wächst.
Wenn Sie also die Schrittweite zu groß wählen, dann haben Sie einen
sehr groben RRT, der unter Umständen Probleme hat, an engen Stellen
noch eine Lösung zu finden.
Wenn Sie den zu klein wählen, dann dauert es einfach länger, bis Sie
eben Ihren gewünschten Zielpunkt erreichen, weil Sie viel öfter
sammeln müssen.
So, die nächste Aufgabe.
Bestimmen Sie die Pfadkosten für die Knoten Q1 bis Q9 und Qnew.
Und das ist einfach die kumulierte Funktion dieser Kosten an den
Kanten.
Das heißt, hier haben wir 0.
Für Q2, da haben wir 1.
Wir müssen also hier nur eine Kante entlang laufen.
Nach Q3 haben wir 1 plus 2 ist gleich 3.
Für Q4 haben wir 1 plus 2 plus 1 ist gleich 4.
Und so weiter.
Und dann ergibt sich hier diese Pfadkosten.
Nächste Teilaufgabe.
Beschreiben Sie die RT-Sternfunktion NIR TQNUR.
Und diese NIR-Funktion, die...
Ich glaube, das muss ich jetzt nicht einzeichnen.
Oder vielleicht doch.
Vielleicht zeichne ich das kurz ein.
Diese NIR-Funktion ermittelt alle Knoten, die in diesem Radius R um
eingegebenen Knoten liegen.
Also T ist einfach Ihr Baum.
Und jetzt haben wir hier den Radius R um unseren Knoten QNU.
Und haben dann hier in dem Fall eben...
QNIR ist dann Q5,
Q7, Q8.
Genau.
Hier sehen Sie jetzt nochmal diese Knoten, die eben in der Menge von
QNIR drin sind, grün markiert.
Und die vierte Aufgabe, die wird hier gar nicht explizit beantwortet.
Oder habe ich die übersprungen?
Ja genau, weil das ist genau unser QNIR.
Wir haben jetzt noch im RT-Sternalgorithmus diesen REWIRE-Schritt.
Und der REWIRE-Schritt, der ist sehr wichtig, weil der REWIRE-Schritt
führt dazu, dass wenn Sie jetzt einen neuen Knoten in Ihrem Baum
ergänzt haben, Sie unter Umständen, wenn Sie den einfach nur mit dem
nächsten Nachbar verbinden, Kanten erhalten, also so wie Sie das im
RRT -Algorithmus machen, Kanten erhalten, die, wenn Sie später dann
Ihren Kraftzug-Algorithmus darauf anwenden, total unnötige Umwege in
Ihrem Freiraum machen.
Also es führt nicht dazu, dass Sie irgendwie Ziele erreichen können,
die Sie sonst nicht erreichen können, aber dieser REWIRE-Schritt
verhindert, dass Sie wenig intelligente Umwege machen müssen.
Und relevant für diesen REWIRE-Schritt sind eben alle Knoten, wenn Sie
jetzt einen Knoten eingefügt haben, alle Knoten, die in einer gewissen
Entfernung R zu diesem Knoten stehen, also die Bestandteil von der
Kunierfunktion sind, die wir ja gerade definiert haben.
Und wie funktioniert der REWIRE-Schritt?
Sie prüfen...
Okay, das kann ich jetzt nicht auf die Folie schreiben.
Sie prüfen für jeden Knoten, den Sie hier haben in Kunier, ob Sie
diesen Knoten statt mit seinem momentanen Vorgängerknoten mit Qnew
verbinden müssen.
Machen wir mal ein Beispiel, wenn wir das jetzt für Q9 prüfen würden.
Sie sehen, von Q5 nach Q9 haben Sie Kosten von 4.
Wenn Sie jetzt von Qnew zu Q9 mit Kosten 1 kommen würden, dann wäre es
natürlich besser, Sie laufen von Q5 nach Q7, nach Qnew und dann zu Q9,
statt diese Kante zu nehmen.
Das setzt natürlich voraus, dass Sie Ihre Kosten kennen.
Die sind jetzt in der Aufgabenstellung gegeben, diese Kosten für die
Verbindung von Qnew zu diesem grünen Knoten.
In dem Fall, diese Kante hat tatsächlich die Kosten 1.
Und prüfen wir es zunächst für Q5.
Bei Q5 müssen wir kein Rewiring durchführen.
Bei Q8 haben wir hier eine Kante von 3, während von Qnew zu Q8 die
Kante hat nur Kosten von 1.
Das heißt, es ist auf jeden Fall besser, wir laufen stattdessen hier
rum und jetzt führen wir hier dieses Rewiring durch.
Bei Q9 genau das gleiche, das hatte ich ja gerade schon gesagt.
Und jetzt sind Sie fertig mit dem Rewire-Schritt.
Und haben den entsprechend aktualisierten Baum.
Das war vielleicht jetzt etwas wenig anschaulich, weil Sie diese
Kosten für die Kanten aus der Aufgabenstellung hier nicht auf den
Folien gesehen haben.
Aber Sie können sich das ja nochmal in Ruhe anschauen.
Und die andere Frage ist natürlich, woher diese Kosten kommen.
Das habe ich Ihnen jetzt nicht erklärt.
Wenn Sie das Ganze jetzt in der Praxis ausführen, dann haben Sie
natürlich immer noch irgendeine Metrik dabei, die für diesen Raum,
also es kann auch zum Beispiel ein hochdimensionaler
Konfigurationsraum sein.
Das ist natürlich in der Praxis kein zweidimensionaler Raum.
Ich hoffe, dass Sie sich das irgendwie vorstellen können.
Im zweidimensionalen Fall sehen diese Probleme immer sehr trivial aus.
Da fragt man sich, warum braucht man da überhaupt den Graphen.
Aber wenn Sie das in einem achtdimensionalen Raum machen, dann ist es
eben nicht mehr so anschaulich und so trivial, sondern dann können Sie
ohne so eine systematische Vorgehensweise gar keinen Weg finden.
Okay, dann kommen wir zur vierten Aufgabe.
Das ist ein ganz bekanntes Graphs-Hochverfahren, nämlich der A-Stern
-Algorithmus.
Und die Aufgabe lautet, in dem abgebildeten Gitter soll der kürzeste
Pfad zwischen V2, also V2 hier oben, und V13 ermittelt werden.
Dazu gelten folgende Rahmenbedingungen.
Es sind nur horizontale und vertikale Bewegungen zu benachbarten
Knoten erlaubt.
Wir können also nicht diagonal laufen.
Die Bewegungskosten sind abhängig von der Farbe der Zell.
Das Betreten einer grauen Zelle kostet eins und das Betreten einer
gelben Zelle kostet vier.
Also Sie sehen schon, worauf es hinausläuft.
Die Lösung ist natürlich, dass wir hier außen rumlaufen und nicht hier
über den gelben Bereich drüber.
Und als Heuristik H wird die euclidische Distanz zum Zielknoten
verwendet.
Das bedeutet, wenn wir beispielsweise hier mal von V11 ausgehen, das
Beispiel ist ja auch hier auf der Folie, von V11 zu V13, euclidische
Distanz wäre eben hier Wurzel 2, also 1² plus 1² und daraus die
Wurzel.
Und das ist Ihre Metrik oder die Heuristik.
Und für diese Heuristik beim A-Stern-Algorithmus muss eine spezielle
Eigenschaft gelten, damit Sie das überhaupt als Heuristik verwenden
dürfen.
Das darf ich Ihnen aber glaube ich gerade nicht sagen, weil das noch
als Aufgabenstellung gleich kommt.
Genau, das ist nämlich der Aufgabenteil 2.
Okay, und jetzt schauen wir uns den A-Stern-Algorithmus nochmal kurz
an.
Ich weiß nicht, ob Sie den gerade so präsent haben.
Das ist also ein iterativer Algorithmus und im Prinzip ist es eine
modifizierte Breitensuche.
Und zwar ist es eine Breitensuche oder eine heuristische Breitensuche,
bei der Sie immer den Knoten expandieren.
Das heißt, von einem Knoten aus mögliche Nachfolgeknoten betrachten,
der gerade am vielversprechendsten erscheint.
Und zwar expandieren Sie immer den Knoten, für den, den Sie noch nicht
expandiert haben, der also Bestandteil in diesem Open Set ist und für
den gilt, dass die Summe aus den Kosten, die Sie brauchen, um zu
diesem Knoten hinzukommen, plus der Wert Ihrer Heuristik, was Sie also
schätzen, wie weit Sie noch mit diesem Knoten vom Zielknoten entfernt
sind, minimal wird.
Und für jeden Knoten, den Sie besuchen, speichern Sie den
Vorgängerknoten.
Also Sie müssen sich immer merken, für alles, was Sie besucht haben,
was in diesem Closed Set ist, wie sind Sie da hingekommen?
Also wie ist der optimale Weg, um zu diesem Knoten im Closed Set
hinzukommen?
Was sind die akkumulierten Kosten, wenn Sie eben über diesen
Vorgängerknoten dahin gehen?
Das sind also Informationen, das haben Sie während der Ausführung des
Verfahrens, das können Sie einfach speichern.
Und wie viele Kosten schätzen Sie gemäß Ihrer Heuristik, dass Sie noch
brauchen, um von diesem Knoten zum Ziel zu kommen?
Und die Initialisierung dieses iterativen Ansatzes, also wir sehen das
Verfahren auch gleich nochmal auf der Folie, die sieht so aus, dass
Sie zunächst mal in Ihrem Open Set nur den Startknoten haben.
Das heißt, der erste Knoten, den Sie in Ihrer ersten Iteration
expandieren, das ist immer Ihr vorgegebener Startknoten.
Und klar, Sie haben noch keinen Knoten besucht, also c ist die leere
Menge.
Und die akkumulierten Kosten, um das Ziel zu erreichen, die sind für
jeden Knoten, außer für Ihren Startknoten unendlich, weil Sie ja noch
keinen anderen Knoten erreicht haben.
Und für den Startknoten sind Sie null, denn da starten Sie ja.
Und das Verfahren läuft jetzt so, solange Sie also hier noch einen
Knoten in Ihrem Open Set drin haben, läuft das Verfahren.
Wenn Ihr Open Set leer ist und Sie haben Ihren Zielknoten nicht
erreicht, dann ist irgendwas schief gelaufen.
Das bedeutet dann, dass Ihr Zielknoten gar nicht erreichbar ist.
Der Fall tritt aber, wenn Sie einen zusammenhängenden Graphen haben,
wo Sie überall endliche Kosten haben, kann der Fall natürlich nicht
auftreten, weil Sie irgendwann Ihren Zielknoten erreichen werden.
Und in jeder Iteration bestimmen Sie, wie gesagt, zunächst den Knoten,
aus dem die Summe der Kosten plus dem Wert der Heuristik minimal ist.
Also dieses G sind die Kosten, die Sie brauchen, um vom Start zu
diesem Knoten VI zu kommen.
Und H ist eine Schätzung, wie viel Sie noch brauchen, um vom VI zum
Zielknoten zu kommen.
Und die Summe daraus ist demnach eine Abschätzung der Gesamtkosten vom
Start zum Ziel, wenn Sie eben über VI gehen.
Und Sie suchen sich den Knoten aus Ihrem Open Set, der dieses
Funktional minimiert und prüfen jetzt zunächst mal, haben Sie Ihr Ziel
erreicht?
Also ist der Knoten, den Sie gerade expandieren, Ihr Zielknoten?
Wenn das der Fall ist, sind Sie fertig, denn Sie expandieren ja die
Knoten in steigender Reihenfolge Ihrer Kosten.
Das heißt, wenn Sie in diesem Fall eintreten, dann wissen Sie, Sie
sind am Ziel und Sie wissen aber auch gleichzeitig, dass Sie einen
Knoten finden, der niedrigere Kosten hat.
Denn wenn Sie schon im Ziel sind, hat die Heuristik ja den Wert 0.
Das heißt, Ihre Kosten bestehen nur noch aus diesen Kosten.
Und diese Funktion, das ist keine Heuristik, sondern das sind 100%ig
sichere, bekannte Kosten.
Das heißt, Sie haben den Knoten rausgesucht mit dieser minimalen
Funktion.
Heuristik ist 0.
Das heißt, Sie können gar keinen anderen Knoten mehr finden, der noch
einen besseren Weg
hat als den momentan expandierten Knoten aus Ihrem OpenSet, fügen den
in die Menge der schon besuchten Knoten hinzu und Sie führen diesen
eigentlichen Update-Schritt durch.
Und der Update-Schritt, der betrachtet jetzt alle Nachfolgerknoten von
dem Knoten, den Sie gerade expandieren.
Das ist also der Expansionsschritt.
Und wenn Sie den Nachfolgerknoten schon besucht haben, wenn Sie da
schon mal waren, dann können Sie den überspringen.
Denn dann haben Sie den schon
expandiert.
Und wenn Sie jetzt hier monoton steigend sind durch dieses
Minimalitätskriterium bei der Auswahl, können Sie keine bessere
Verbindung finden zu dem Knoten, den Sie schon expandiert haben.
Wenn der Knoten, der Nachfolgerknoten, noch nicht im OpenSet drin ist
und Sie den auch nicht besucht haben vorher, dann ist es ein Knoten,
den Sie noch gar nicht gesehen haben.
Das ist also irgendein neuer Knoten.
Dann fügen Sie den im OpenSet hinzu.
Das heißt, Sie sagen, Sie wollen den auch später irgendwann mal noch
expandieren.
Sie wissen ja jetzt, wie Sie dahin kommen.
Und dann wollen Sie irgendwann später noch schauen, wie kommen Sie von
dort aus weiter.
Und dann prüfen Sie hier, das ist eigentlich der entscheidende Teil,
Sie prüfen, haben Sie zu diesem Nachfolgerknoten eine bessere
Verbindung gefunden, einen besseren Weg als den, den Sie bisher schon
kennen.
Also diese beiden Bedingungen, die bedeuten ja,
Sie kennen schon einen Weg zu diesem Knoten, da ist er schon im
OpenSet drin.
Und jetzt prüfen Sie, haben Sie jetzt über den Knoten, den Sie
momentan expandieren, also VI, einen besseren, einen kürzeren Weg zu
diesem Knoten gefunden.
Falls das der Fall ist, müssen Sie das natürlich entsprechend
vermerken.
Das heißt, Sie vermerken hier den entsprechenden Vorgängerknoten.
Dieser Fall, der tritt natürlich auch dann ein, wenn Sie den Knoten
gerade erst zum OpenSet hinzugefügt haben, kann der Initial mit
unendlich initialisiert werden.
Das heißt, auch wenn Sie den Knoten zum ersten Mal überhaupt sehen,
dann würden Sie quasi hier diesen Teil ausführen.
So, jetzt schauen wir uns das Ganze im Beispiel an.
Das Beispiel habe ich Ihnen ja schon gezeigt.
Ich weiß nicht, ob ich das jetzt alles schreiben soll.
Ich glaube, ich gehe das jetzt hier einfach anhand der Folien durch.
Also die Initialisierung zunächst.
Unser OpenSet wird initialisiert mit V2.
Das ist hier V2.
Und die Kosten, um zu V2 zu kommen, die sind natürlich null.
Und unsere Heuristik entspricht ja dem euglidischen Abstand.
Das heißt, der euglidische Abstand zu unserem Ziel von V2 zu V13, der
entspricht ja der Wurzel aus, hier sind es 4 und hier ist es 1, also 4
Quadrat plus 1 Quadrat und daraus die Wurzel.
Das ist also die Wurzel aus 17.
Das ist ungefähr 4,12.
Wir rechnen also jetzt hier mit leicht ausreichenden Daten.
Es geht ja jetzt hier um die Funktionsweise des Algorithmus und nicht
darum, jetzt hier möglichst genau irgendwelche Kosten zu bestimmen.
Und unser ClosedSet initialisieren wir mit der leeren Menge.
Jetzt sind wir im ersten Schritt und expandieren jetzt V2 und
betrachten alle möglichen Nachfolgeknoten von V2.
Wir hatten ja gesagt, dass wir immer nur horizontal und vertikal uns
bewegen dürfen.
Das heißt, es geht um die Nachfolgeknoten und für alle drei mögliche
Nachfolgeknoten, das hier muss eine 4 sein, da ist ein...
Mich gerade gewundert, denn ihre Kosten hängen ja von der Farbe ihrer
neu betretenen Zelle ab.
Das heißt, wenn Sie nach V1 gehen, dann haben Sie Kosten von 1, weil
das eine graue Zelle ist, plus den Wert der Heuristik von 1 zu V13 und
das ist in dem Fall hier die Wurzel aus 0 Quadrat plus 4 Quadrat, also
genau 4 von hier nach hier.
So, wenn Sie nach V3 gehen, dann haben Sie auch Kosten von 1 und Ihre
Heuristik 4 Quadrat plus 2 Quadrat und daraus die Wurzel.
Dann haben Sie also hier 5,47 und wenn Sie in den gelben Bereich
reingehen, dann haben Sie die Kosten von 4, weil es ja eine neue Zelle
betreten und haben
hier die Heuristik hat den Wert 3 Quadrat plus 1 Quadrat, daraus die
Wurzel.
Dann haben Sie hier 7,16.
Also Sie sehen schon, der Algorithmus zeigt jetzt hier schon, dass es
wahrscheinlich nicht so schlau ist, hier in diesen gelben Bereich
reinzugehen überhaupt.
Und V2 haben Sie expandiert, das heißt V2 ist jetzt im Closed Set, das
wird in der Zukunft nicht mehr betrachtet.
Sie können, auch wenn Sie expandieren, nicht mehr einen besseren Weg
finden nach V2.
An der Stelle ist es sowieso klar, weil es ja Ihr Startknoten ist.
Es macht keinen Sinn, irgendwo hinzugehen und dann wieder zu Ihrem
Startknoten zurück, weil dann können Sie sich diesen Umweg auch direkt
sparen.
So.
Zweiter Schritt.
Jetzt expandieren Sie den Knoten V1, weil V1 hat Ihre niedrigsten
Kosten.
Die haben Sie nur den 1 plus, die Heuristik hat 4, also 5.
Und expandieren den.
Diese Verbindung zurück brauchen Sie nicht zu betrachten, weil V2 ja
schon im Closed Set ist.
Das heißt, es geht nur nach V4.
Da haben Sie Kosten von 2, genau.
1 plus 1.
Und die Heuristik hat den Wert von, Wurzel von 3 Quadrat, also 3.
Also haben Sie auch den Wert 5.
Das heißt, jetzt haben Sie hier V4 als Knoten mit dem minimalen Wert
in Ihrem Open Set, würden jetzt dann V4 expandieren.
Und Sie sehen schon, worauf das hinausläuft.
Sie können jetzt natürlich nach V5, aber V5, wenn Sie jetzt hier nach
V5 gehen, haben Sie höhere Kosten, als wenn Sie direkt nach V5
gegangen wären.
Das heißt, da müssen Sie in Ihrer Datenstruktur nichts verändern.
Und Sie können nach V7.
Das hat allerdings dann Kosten von 1 plus 1 plus 4, also 6, plus den
Wert der Heuristik, plus 2.
Und dann haben Sie hier V4 auch expandiert.
Und jetzt würden Sie als nächstes V3 expandieren.
Aber ich glaube, wir müssen in der Aufgabenstellung nur drei Schritte
durchführen.
Genau.
Aber Sie können sich vorstellen, wie das weitergeht.
Das heißt, am Ende haben Sie dann hier den Pfad, der eben hier so
außen rum führt.
Und jetzt müssen wir noch eine Sache diskutieren.
Warum ist die euclidische Distanz überhaupt eine geeignete Heuristik?
Denn der R-Stern-Algorithmus, der garantiert Ihnen was.
Der garantiert Ihnen, dass Sie immer den optimalen Weg zu Ihrem Ziel
finden.
Entsprechend zum Beispiel dem Dijkstra-Algorithmus, der Ihnen das auch
garantiert.
Aber der R-Stern-Algorithmus ist natürlich wesentlich effizienter.
Und damit er Ihnen das garantieren kann, damit Sie aufweisen können,
dass Sie immer den optimalen Weg finden, müssen Sie... also da stehen
noch ein paar Annahmen dahinter.
Das können Sie sich gerne in der Literatur anschauen mit keinen
negativen Kosten und solche Sachen.
Aber damit es funktioniert, muss Ihre Heuristik eine Eigenschaft
aufweisen.
Welche Eigenschaft muss Ihre Heuristik aufweisen, damit sie für die
Verwendung im R-Stern-Algorithmus zulässig ist?
Sie können sich ruhig melden, wenn Sie es wissen.
Ja?
Genau.
Ich wiederhole es vielleicht noch mal kurz.
Also Ihr Kommiliton hat gesagt, der Wert der Heuristik muss kleiner
oder gleich den tatsächlichen Kosten sein.
Das stimmt.
Ihre Heuristik darf also die tatsächlichen Kosten zum Ziel niemals
überschätzen.
Denn wenn Sie die Kosten zum Ziel überschätzen würden, dann würde das
ja bedeuten, dass Sie einen Knoten haben, der vielleicht eigentlich
ganz gut ist, der schon eine kurze Verbindung zum Ziel hat.
Aber Ihre Heuristik sagt, er ist total weit noch vom Ziel entfernt.
Und dann würden Sie den nicht expandieren.
Dann würden Sie also unter Umständen einen Knoten, der gut ist, nicht
rechtzeitig expandieren und würden terminieren, bevor Sie diesen
Knoten expandiert haben.
Und jetzt können wir uns natürlich noch kurz überlegen, gilt das für
die Euclidische Heuristik.
Wir haben also hier für eine Bewegung, also für eine Kante immer
mindestens Kosten von 1.
Wenn wir in ein gelbes Feld laufen, sogar Kosten von 4.
Aber wir können das nach unten abschätzen mit Kosten von 1.
Das heißt, was wir im Wesentlichen als Distanz haben, ist die
Manhattan -Distanz.
Also wenn wir von hier zum Beispiel nach hier laufen, dann hätten wir
mindestens Kosten von 3.
Wie gesagt, eventuell mehr, wenn da gelbe Felder im Spiel sind.
Und die Heuristik der Euclidischen Distanz, die ist natürlich immer
kleiner als die Manhattan-Distanz.
In Numerik haben Sie ja wahrscheinlich gehört, da gibt es dann ja auch
die Mahalanobis-Distanz, glaube ich, falls es behandelt wird.
Spielt eigentlich keine Rolle.
Und das ist der Fall.
Wichtig ist eben hier, es darf keinen Knoten mit negativen Kosten
geben.
Wenn Sie das hätten, oder wenn Sie zum Beispiel Kosten hätten, wenn
Sie Kosten hätten, die kleiner sind als 1.
Wenn Sie zum Beispiel sagen, eine horizontale Bewegung hat aber nur
Kosten von 0,1, dann ist der Weg von hier nach hier, der hat dann ja
nur Kosten von 1,2, aber Ihre Euclidische Distanz wäre größer, dann
würde die Heuristik nicht funktionieren.
Aber für die gegebenen Kosten von 1 und 4 funktioniert das.
Und jetzt, das haben wir eigentlich schon geklärt, also das war schon
im Algorithmus dargestellt, aber wir können es noch mal kurz
diskutieren.
Wann findet der Asternalgorithmus eine Lösung?
A, wenn der Zielknoten expandiert wird, oder B, wenn der Zielknoten
zum Open Set hinzugefügt wird.
Genau.
Machen wir es vielleicht interaktiv, eine kleine Abstimmung.
Wer von Ihnen ist für
Option A?
Okay, wenige melden sich.
Wer von Ihnen ist für Option B?
Okay, auch wenige melden sich.
Das ist nicht ganz eindeutig jetzt.
Schauen wir uns das mal im Algorithmus an.
Das ist der gleiche Algorithmus, der war ja vorhin schon auf der
Folie.
Wir haben also, achso, hier steht es jetzt schon, wann er terminiert.
Okay, aber wir können uns vielleicht noch kurz überlegen, also er
terminiert bei A, also er terminiert dann, wenn der Zielknoten zum
Open Set hinzugefügt wird.
Und er terminiert nicht schon dann, wenn wir hier den Zielknoten zum
Open Set hinzufügen.
Das wäre also Option B.
Option B liegt zeitlich vor Option A.
Also bevor Sie hier oben an diese Stelle kommen können, müssen Sie
irgendwann davor den Knoten zum Open Set hinzugefügt haben, weil Sie
ja immer hier Knoten aus dem Open Set ziehen.
Und die Frage ist jetzt natürlich, warum genügt es nicht, wenn wir den
Knoten zum Open Set hinzufügen?
Warum dürfen wir erst dann aufhören, wenn wir den Knoten auch wirklich
expandieren?
Und die Antwort ist, wir expandieren die Knoten ja in monoton
steigender Kostenfolge.
Das heißt, jeder Knoten, den wir expandieren, hat gemäß diesem G plus
H höhere Kosten als alle Knoten davor.
Wenn wir jetzt den Zielknoten betrachten, dann hat die Heuristik aber
den Wert Null, weil wir ja schon am Ziel sind.
Die Heuristik darf ja die Kosten zum Ziel nicht überschätzen.
Die tatsächlichen Kosten zum Ziel sind aber nicht.
Eine akzeptable Heuristik muss auch den Wert Null haben.
Und das bedeutet konkret, wenn wir hier davon ausgehen, dass wir den
Zielknoten haben und wir sind hier an der Stelle, dann haben wir alle
anderen Knoten, die niedrigere Kosten haben als der Zielknoten, schon
expandiert.
Das heißt, alle Kosten, die danach kommen, haben höhere Kosten.
Und wenn wir davon ausgehen, dass es keine Kanten gibt mit negativen
Kosten, das ist eine Annahme vom Astern-Algorithmus, dann können wir
mit niedrigeren Kosten als von dem momentanen Knoten zum Ziel kommen.
Wenn wir hier unten schon aufhören würden, dann könnte das aber noch
passieren.
Dann könnte es durchaus sein, dass wir jetzt momentan den... also wir
haben schon einen Vorgängerknoten vom Zielknoten gefunden.
Wir haben schon einen Knoten gefunden, von dem aus wir sagen, ein
Nachfolgerknoten von dem momentanen Knoten ist unser Zielknoten.
Aber es könnte ja trotzdem noch sein, dass wir über einen anderen
Knoten noch besser zum Zielknoten kommen können als über den
momentanen Knoten.
Deswegen dürfen Sie im Fall B noch nicht aufhören, sondern erst, wenn
Sie hier oben an der Stelle A sind.
Okay, jetzt haben wir noch eine halbe Stunde.
Ah, okay, die Begründung ist auch auf der Folie, das ist natürlich
super.
Das können Sie sich dann noch mal anschauen.
Ah, es gibt auch noch Bonusfragen.
Okay, für die habe ich jetzt keine Musterlösung.
Müssen wir uns das auch mal anschauen.
Können wir aber kurz diskutieren.
Ist die euclidische Distanz eine zulässige Heuristik, wenn diagonale
Bewegungen mit gleichen Kosten erlaubt sind?
Mit gleichen Kosten bedeutet wahrscheinlich, wenn wir von hier nach
hier gehen, das beantwortet schon fast die Frage, dann hätten wir auch
nur Kosten von 1.
Und dann sehen Sie, dann kann die euclidische Distanz keine gültige
Heuristik mehr sein, denn die euclidische Distanz von V2 nach V6 ist
ja Wurzel aus 2, also 1,4.
Wenn aber diagonale Bewegungen mit den gleichen Kosten erlaubt sind,
hätten wir hier die realen Kosten nur in Höhe von 1.
Das bedeutet, die euclidische Distanz würde die realen Kosten
überschätzen und ist damit keine gültige, keine gültige Heuristik
mehr.
Nächste Frage, ist die Manhattan-Distanz eine zulässige Heuristik?
Die Manhattan-Distanz kennen Sie vielleicht, muss ich kurz hier
hinschreiben.
Also die euclidische Distanz, ich verstehe das nicht, warum sind wir
hier oben?
Die euclidische Distanz haben Sie
x, also die Wurzel aus x² plus y² und die Manhattan-Distanz, das ist
einfach x plus y.
Das heißt, Sie schauen einfach, wie viel müssen Sie sich... benannt
ist das tatsächlich nach dem Stadtteil Manhattan in New York, denn
dort haben Sie also Häuserblocks und wenn Sie in so einem Häuserblock
von Manhattan, wie in jeder Stadt, von einem Punkt zum anderen kommen
wollen, dann können Sie eben entsprechend den Horizontalen, also den
Querstraßen folgen oder den Straßen, die orthogonal dazu sind.
Sie können aber nicht einfach diagonal durch ein Häuserblock durch.
Das heißt, deswegen nennt man das Manhattan-Distanz, weil Sie eben
immer nur entlang der Straßen von diesen Häuserblocks sich bewegen
können.
Und wäre das zulässig?
In dem Fall ja, wäre es, weil wir haben ja Kosten von 1 bzw.
von 4.
Die Manhattan-Distanz sieht aber für jede Bewegung, die wir hier
machen, können immer Kosten von 1 vor, egal ob wir in ein graues Feld
oder in ein gelbes Feld gehen.
Das heißt, die Manhattan-Distanz unterschätzt oder ist immer kleiner
gleich den realen Kosten und damit ist es eine zulässige Heuristik.
Und die letzte Frage, ist die Manhattan-Distanz dann eine bessere oder
eine schlechtere Heuristik als die Euclidische Distanz?
Vielleicht in Anbetracht der Zeit, mal überlegen, ist sie besser,
müsste besser sein, ja, weil die Manhattan-Distanz die realen Kosten
besser einschätzt.
Also eine Heuristik ist dann, die Heuristik darf ja ihre Kosten nie
überschätzen, aber sie darf die Kosten unterschätzen.
Und wenn Ihre Heuristik die Kosten unterschätzt, macht das natürlich
im Algorithmus weniger effizient, weil Sie dann unter Umständen Knoten
expandieren, die vielleicht gar nicht so gut sind, wie Sie denken.
Wenn Sie also die Heuristik im Extremfall haben, Sie die Heuristik
Null, Sie sagen immer, Ihre Heuristik ist immer Null, das heißt jeder
Knoten ist gemäß Ihrer Heuristik Null vom Ziel entfernt.
Und was erhalten Sie dann, wenn Sie das machen?
Das müssten Sie aus GBI oder Info 1, wie das heißt, inzwischen kennen.
Was ist das dann mit Heuristik Null?
Das ist dann der Algorithmus von Dijkstra.
Also dann haben Sie keine Heuristik, sondern Sie expandieren den
Knoten, der die geringsten Kosten ausgehend vom Staat hat.
Dieses H von V fällt dann einfach weg.
Das heißt, eine Heuristik darf zwar die Kosten nie überschätzen, aber
sie ist besser, wenn sie die Kosten möglichst wenig unterschätzt und
das tut die Manhattan-Distanz.
Die Manhattan-Distanz ist ja größer als die Euclidische Distanz, also
zum Beispiel hier, die Euclidische Distanz wäre 1,41, die Manhattan
-Distanz ist 2, das heißt, die Manhattan-Distanz hat weniger die
Tendenz dazu, die Kosten zum Ziel zu unterschätzen.
So, dann kommen wir zur letzten Aufgabe, da muss man relativ viel
rechnen.
Keine Sorge, ich werde jetzt nicht die ganzen Formeln hier
anschreiben.
Jetzt geht es hier um Potenzialfelder, das ist also ein physikalisch
inspirierter Ansatz der Bewegungsplanung.
Sie haben nach wie vor das Ziel, Sie wollen, hier ist ein Beispiel
schon gegeben, Sie wollen von einem Startpunkt, das ist hier QR, oder
ein momentaner Punkt, das ist Ihr momentaner Punkt, das ist ein
punktförmiger Roboter, zu einem Zielpunkt und Sie haben drei
abstoßende Potenziale gegeben.
Das sind hier die roten Punkte, das sind also punktförmige
Hindernisse.
Anschaulich, wenn Sie sich das mal überlegen, Sie würden
wahrscheinlich irgendwie so hier oben rumlaufen.
Also Sie würden erst mal gucken, dass Sie hier von diesen Hindernissen
wegkommen, denn die sind ja abstoßend, Sie wollen das Risiko einer
Kollision mit denen möglichst klein halten und Sie müssen natürlich
gucken, dass Sie zu diesem anziehenden Potenzial, zu dem Ziel
hinkommen.
Das heißt, Sie laufen irgendwie hier so einen Bogen.
Okay, Aufgabe 1, also ich lese jetzt nicht alle Koordinaten vor, die
stehen ja hier auf der Folie.
Welche der abstoßenden Potenziale UAB1, UAB2 und UAB3 wirken auf den
Roboter, wenn man einen Wirkungsradius von Rho 0 ist gleich 5 zugrunde
legt.
Und jetzt müssen wir letztendlich nur schauen, welche dieser
Hindernisse sind gemäß der euclidischen Distanz näher als 5 an ihrem
punktförmigen Roboter.
Man kann es natürlich auch ausrechnen.
Also ist das überhaupt auf den Folien?
Ja, es ist auf den Folien, aber wir können schon mal an der Stelle
schon mal festhalten, natürlich sind die alle näher als 5 an dem
Roboter.
Das heißt, die Roboter, die sich beeinflussen an der Position, wo der
Roboter momentan ist, beeinflussen die alle den Roboter.
Warum haben sie überhaupt diesen Cut-Off?
Also warum sagen sie, sie wollen den Roboter nicht mehr beeinflussen,
wenn sie ein gewisses Stück weg sind?
Der Hintergrund ist einfach, anders als bei einem Ziel, wo sie sagen,
der Roboter muss da hin, spielt ein Hindernis, was weit von dem
Roboter weg ist, keine Rolle mehr.
Also wenn das Hindernis drei Meter von dem Roboter entfernt ist, dann
ist es nicht so, dass sie da noch eine geringe Abstoßung haben wollen,
sondern sie wollen das aus ihren Berechnungen komplett rauswerfen.
Zum einen aus Effizienzgründen und zum anderen, weil ihr Ziel ist,
nicht mit dem Hindernis zu kollidieren.
Wenn sie aber schon sehr weit entfernt sind, dann besteht ja überhaupt
keine Kollisionsgefahr mehr.
Das ist jetzt nochmal erst eine Wiederholung aus der Vorlesung.
Diese Folie müssten Sie aus der Vorlesung schon kennen.
Wie ist das Potenzial definiert?
Man kann natürlich so ein Potenzial auf unterschiedliche Weisen
definieren, zum Beispiel linear oder quadratisch.
Und in dem Fall machen wir das jetzt hier.
Oder das ist ein Beispiel, wie Sie das Ganze quadratisch definieren
können.
Wir gehen jetzt aber hier von einem linearen Fall aus.
Also ignorieren wir die beiden Folien vielleicht mal und schauen uns
jetzt erst mal das hier an.
Das hatte ich ja gerade schon gesagt.
Also alle Ihre Hindernisse, Sie berechnen jetzt den Abstand Ihres
Roboters von den Fällen, die kleiner als 5 sind.
Das heißt, die sind alle relevant für die folgenden Berechnungen.
Nächste Frage.
Bestimmen Sie, jetzt kommt nämlich das lineare Potenzial, bestimmen
Sie UQR als die Summe der wirkenden Potenzialfelder zunächst
unabhängig vom konkreten Wert von QR.
Also wir sollen jetzt analytisch den Wert der wirkenden
Potenzialfelder bestimmen, analytisch, ohne jetzt eine konkrete
Roboterposition.
Nehmen Sie für das Zielpotenzial einen linearen Verlauf an.
Nehmen Sie weiterhin für die Skalierung der Potenziale Faktoren von K
gleich 1 und V gleich 1 an.
Das sehen Sie gleich noch in den Gleichungen.
Das ist überall der Faktor 1.
Das fällt dann einfach raus.
In der Praxis können Sie das eben noch skalieren.
Das heißt, wenn Sie ein Hindernis haben, was unter Umständen selbst
mit einer Unsicherheit behaftet ist, dann müssen Sie das größer
skalieren.
Denn Sie wissen ja der Roboter hat ja kein absolutes Wissen über die
Umwelt.
Der Roboter hat selber eine Sensorik, mit der sich ein Umgebungsmodell
irgendwie extrahiert.
Und da haben Sie zum Beispiel einen Laserscanner, den Sie irgendwo
angebracht haben.
Und dann haben Sie auch wieder eine Unsicherheit.
Und wenn die Unsicherheit größer ist, dann wollen Sie unter Umständen
das entsprechende Potenzial auch stärker skalieren, weil Sie einfach
sagen, da müssen wir noch mehr Abstand halten.
Okay, das lineare Modell ist natürlich das Einfachste.
Also hier haben wir den Wert des Potenzials.
Das ist der Abstand von dem Potenzial zu unserem Ziel.
Und das Ganze skaliert mit K.
K ist wie gesagt eins.
Und dann haben Sie hier noch die Kraft.
Und die Kraft betrachtet Ihren Gradient.
Also das Potenzial, hier müssen Sie unterscheiden, das Potenzial ist
ein Skalarerwert.
Das ist sowas wie in der Physik die potenzielle Energie, wenn Sie zum
Beispiel in einem Schwerkraftfeld sind.
Die Kraft ist das, was aus dem Potenzial entsteht.
Und die Kraft ist ein Vektor.
Und dieser Vektor, der zeigt immer in Richtung Ihres Zielpotenzials.
Also das ist ja jetzt hier ein anziehendes Potenzial.
Das heißt, dieser Gradient zeigt immer in Richtung Ihres Ziels.
Und wird skaliert mit dem Abstand von dem Ziel.
Und wird eben linear skaliert.
Und das führt natürlich dazu, für kleine Distanzen, wenn Sie nah am
Ziel sind, wird die Kraft groß.
Und wenn Sie weiter weg sind, wird sie klein.
Das ist auch anschaulich, wenn Sie eben noch weiter weg sind von Ihrem
Ziel und Sie haben irgendwelche Hindernisse im Weg, dann laufen Sie
dann Umweg.
Wenn Sie weiter weg sind und dann lassen Sie sich nicht mehr so leicht
von dem Hindernis ablenken.
Okay.
Und jetzt berechnen wir das Potenzial.
Und da haben wir zum einen das anziehende Potenzial, also AN ist
anziehend, von Ihrer aktuellen Position, QR ist Ihre Roboterposition.
Und wir addieren darauf die Summe der Potenziale von den abstoßenden
Potenzialfeldern.
Und das Tolle an der Potenzialfeldmethode ist eben genau das, dass Sie
es einfach aufaddieren können.
Also Ihre Potenziale, Ihre Potenzialfelder, die überlagern sich und
Sie müssen das einfach nur aufaddieren.
Und dementsprechend müssen Sie auch einfach nur die Gradienten, die
Kräfte, die Sie erhalten, einfach aufaddieren.
Sie können für jedes Potenzialfeld separat berechnen, was bedeutet das
für den Roboter, welche Kraft entsteht daraus.
Das dann aufaddieren, die Vektoren aufaddieren und dann erhalten Sie
die Kraft, die eben Ihnen sagt, wie sollte sich Ihr Roboter jetzt
gemäß dieser Potenzialfeldmethode bewegen.
Und das setzen wir jetzt hier ein, also das anziehende Potenzial, das
hatten wir auf der Folie davor.
Das abstoßende Potenzial sieht so aus.
Das hatten wir, das ist das quadratische Potenzial, das hatten wir auf
den Vorlesungsfolien, die ich davor hatte.
Das ist Ihr abstoßendes Potenzial und das setzen Sie hier ein.
Also das ist hier vorne, das ist der erste Teil und hier ist dann die
Summe.
Und falls Sie sich jetzt fragen, warum steht hier ein Halb?
Das werden wir gleich sehen.
Wenn wir das Ganze nämlich ableiten, dann hebt sich die 2 hier, die
bei der Kettenregel entsteht, genau weg mit dem Halb.
Und das ist jetzt die dritte Frage.
Also das ist die analytische Lösung Ihres Potenzials.
Wie gesagt, beachten Sie, das ist ein skalarer Wert.
Wir berechnen jetzt hier die Stärke des Potenzialfelds und in der
nächsten Teilaufgabe ist gefragt, bestimmen Sie die Richtung, in die
sich der Roboter durch die wirkenden Potenziale bewegen würde.
Das heißt, jetzt wollen wir die Kraft bestimmen, die sich aus den
Potenzialen ergibt und da brauchen wir jetzt den Gradienten.
Wir haben also hier eingesetzt, das ist das, was Sie schon kennen, das
ist Ihr Potenzialfeld und wir wollen jetzt den Gradienten bestimmen.
Und das Minus dementsprechend, weil wir ja zu einem niedrigen
Potenzial hinwollen.
Also wir wollen zum Ziel kommen.
Gut, jetzt erstmal das Minus hier reingezogen und jetzt das Ganze
abgeleitet.
Wir haben also hier vorne diese lineare Potenzialfunktion, das hatte
ich ja auf der Folie vorhin schon, das ist die Kraft, die daraus
resultiert und hier hinten müssen Sie das jetzt auch ableiten.
Sie müssen also aus dem Potenzialfeld den Gradienten bestimmen und
wenn Sie das hier ableiten, dann haben Sie, das ist ein Halbfeld weg,
das ist also die innere Ableitung.
Das da ist ja dieser Ausdruck hier, wenn Sie sich den mal merken, also
1 durch diese Norm minus 1 durch Rho.
Das ist genau das, was Sie hier haben, das ist die innere Ableitung
und dann haben Sie hier die äußere Ableitung.
Also Sie haben ja hier, das was hier unten steht, diese Norm, das ist
ja quasi, wenn die oben steht, eine Wurzel, also hoch ein Halb und
wenn Sie das ableiten, dann ist es hoch minus ein Halb.
Dann haben Sie hier also quasi die Norm unten im Nenner stehen und das
hier hinten ist genau das gleiche wie vorne.
Das ist also hier dieser Ausdruck hier, wenn Sie den ableiten, dann
erhalten Sie als Gradient das hier.
Das ist wieder der aus dem linearen Potenzialfeld.
Okay, das ist die analytische Lösung.
Ah genau, aber gefragt ist natürlich, wir hatten ja in der
Aufgabenstellung auch konkrete Zahlenwerte gegeben.
Bestimmen Sie die Richtung, jetzt sollen wir konkret noch die Richtung
bestimmen.
Das machen wir jetzt mal noch.
Wir setzen also jetzt die Werte ein.
QR ist die Position unseres Roboters.
Das sind die Abstoßen, ich weiß nicht, warum die jetzt ABS heißen
plötzlich, gerade eben war es noch AB.
Das sind die abstoßenden Potenziale, die auf den Roboter wirken und
ihre Zielpotenzial und diesen Faktor und also das ist hier der
Schwellwert, ab dem die Potenziale wirken.
Die wirken gerade hier jetzt alle und jetzt setzen wir ein.
Wir setzen also, ich weiß nicht, ob ich das jetzt alles vorlesen muss,
wir setzen eigentlich nur noch in diese Formel ein gerade jetzt.
Wir berechnen also jetzt für uns hier den Wert dieses Ausdrucks,
gerade noch symbolisch, aber gleich haben wir die numerische Lösung.
Das heißt, das ist unsere Kraft und um aus dieser Kraft eine Richtung
zu bestimmen, müssen wir die noch normieren.
Das heißt, wir teilen nochmal hier durch 0,224 und das ist genau das,
was wir uns vorhin anschaulich schon überlegt haben.
Sie gehen also hier so leicht eine Kurve nach oben und der Witz ist
eben, bei der Ausführung dieser Potenzialfeldmethode führen Sie diese
Berechnung ständig durch.
Also, Sie gehen jetzt nicht hier hin zu diesem Zielpunkt.
Diese Kraft gibt Ihnen nur die Richtung vor, also wie schnell sollten
Sie dahin, also wie viel Gas geben Sie quasi, aber dann theoretisch
nach einem unendlich kleinen Zeitschritt führen Sie diese Berechnung
wieder durch und berechnen eine neue Kraft und Ihre Richtung ändert
sich dadurch natürlich graduell.
Das heißt, Sie fahren so eine Art Kurve dann am Ende.
Genau, damit bin ich eigentlich durch.
Hier gibt es auch keine Bonusfragen mehr bei dieser fünften Aufgabe.
Es war jetzt vielleicht ein bisschen schnell, aber andererseits, wenn
ich das jetzt alles angeschrieben hätte, dann glaube ich, hätte das
Ihnen auch nicht sehr viel gebracht.
Dann würden Sie nur hier rumsitzen und warten.
Haben Sie noch irgendwelche Fragen?
Keine Fragen?
Dann vielen Dank für Ihre Aufmerksamkeit und wünsche ich Ihnen noch
einen schönen Abend.
Tschüss.