Ja, hallo, guten Abend.
Wie ihr wisst, ist das heute die letzte Vorlesung in Robotik 1, die
wir haben.
Wir machen heute noch eine kleine Übung zu Programmieren.
Eigentlich nur einen Teil der Klausur relevant, ist danach noch so ein
kleiner Einblick in Programmieren mit CMOGS.
Wir machen heute symbolische Planung mit Strips.
Das haben wir euch in irgendeiner Vorlesung noch vorgestellt.
Das ist auch eine Aufgabe, die öfter mal in der Klausur drin vorkommt.
Habt ihr bestimmt schon gesehen in den Altklausuren.
Und wir machen jetzt eine...
Ich glaube, das ist aus der letzten Klausur oder vorletzten Klausur.
Rechnen wir einmal durch.
Und dann haben wir ein bisschen was implementieren mit CMOGS Astern.
Und je nachdem, wie viel Zeit wir haben, machen wir das noch für ERT.
Das ist eine Aufgabe aus unserem Praktikum tatsächlich.
Ich weiß nicht genau, aus welchen.
Könnte Roboter oder humanide Roboter sein.
Aber da machen wir dann einen kleinen Teil raus.
Genau.
Die symbolische Planung, die Aufgabe, die hier gestellt war.
Wir haben einen Ausgangszustand, der aus mehreren Prädikaten besteht.
Wir haben einen Tisch, ein Table, Stove.
Table und Stove sind beides Locations.
Das wird durch die zusätzlichen Prädikate hier beschrieben.
Wir haben einen Gripper, der auch eine Hand ist.
Einen Robot, der auch ein Agent ist.
Und dann haben wir ein Objekt, das PNP.
Initial ist die Hand leer, soll sie leer sein.
Und der Pen befindet sich auf dem Tisch.
Und der Robot, der Roboter ist an dem Stove gerade.
Und wir wollen das Ziel erreichen, dass sich der Roboter nachher, dass
sich die Pen nachher auf dem Stove befindet.
Ist ja momentan auf dem Tisch.
Und die Aufgabe wird dann sein, eine Aktionssequenz zu finden, die
eben diesen initialen Weltzustand transformiert, in einen Weltzustand,
der unser Ziel enthält.
In dieser Aufgabe sind drei Aktionen möglich.
Mehr gibt es nicht, um den Weltzustand zu ändern.
Der erste ist so eine Pickup-Aktion.
Also der Agent A nimmt ein Objekt O mit der Hand H von Ort L.
Und diese umgangssprachliche Beschreibung ist eigentlich ziemlich
wertlos.
Die packen wir nur immer dazu, damit man sich darunter was vorstellen
kann.
Was wirklich wichtig ist, sind immer die Vorbedingungen und die
Effekte.
Wie die Aktion heißt oder wie man sie beschreibt, ist unwichtig.
Und wir haben also Vorbedingungen.
Die Vorbedingungen müssen erfüllt sein, sonst kann man die Aktion
nicht ausführen.
Da sind ein paar Bedingungen dabei, die irgendwie trivial sind.
Also bei A muss es sich um Agenten handeln, bei H um eine Hand, bei L
um eine Location.
Und da sind ein paar Bedingungen dabei, die hängen vom dynamischen
Weltzustand ab.
Also ist die Hand gerade leer?
Wo befindet sich das Objekt?
Wo befindet sich der Agent?
Genau.
Und wenn diese Vorbedingungen erfüllt sind, dann können wir diese
Aktion ausführen.
Und dann hat sie Effekte auf die Umwelt, auf den Weltzustand.
Und diese Effekte beschreiben wir auch eben in dieser Prädikatslogik.
Wir benutzen hier dieses Ausrufezeichen als Negation.
Wird manchmal auch so geschrieben, in der bootschel-Logik.
Aber naja, wir benutzen das Ausrufezeichen.
Und was jetzt hier der Effekt von so einem Pickup ist, okay, das
Objekt befindet sich jetzt nicht mehr auf diesem Ort, wo es vorher
war.
Die Hand ist nicht mehr leer, weil sich das Objekt hier drin befindet.
Und dann haben wir hier ein neues Prädikat, das Objekt befindet sich
jetzt in dieser Hand.
Genau.
Man muss sich da so ein bisschen von dem intuitiven Verständnis lösen,
weil was am Ende zählt, sind einfach nur diese logischen Prädikate.
Die Aktion könnte auch vollkommen anders heißen.
Und in hand könnte auch irgendwie XYZ heißen.
Es geht nur darum, dass man die logischen Prädikate beschreibt, als
Vorbedingungen und als Effekte.
Genau.
Dann im gleichen Maß haben wir eine Aktion, wo der Roboter ein Objekt
absetzt.
Da haben wir dann umgekehrte Vorbedingungen.
Also das Objekt muss sich in der Hand befinden, wenn ich diese Aktion
ausführen will.
Der Roboter muss sich auch an dem Ort befinden.
Und dann passiert eben, dass sich danach das Objekt auf diesem Ort
befindet, dass danach die Hand wieder leer ist und wir das Objekt
nicht mehr in der Hand haben.
Genau.
Also das sind diese beiden Pickup und Putdown.
Und dann haben wir noch eine ganz triviale Aktion, das Bewegen.
Also Agent A bewegt sich von Ort L zu Ort M.
Da haben wir jetzt wieder, okay, wir brauchen einen Agenten und zwei
Orte.
Und der Agent muss sich an dem Ort befinden.
Der Effekt ist dann, okay, jetzt befindet er sich nicht mehr an dem
Ort, sondern an dem Ort.
Und das ist tatsächlich, diese Aufgabe haben wir ja in der Klausur
gestellt und einer hat tatsächlich gemerkt, dass die so definierte
Aktion unvollständig ist.
Man kann sich das zum Beispiel vorstellen, man würde die Aktion
ausführen, ich habe einen Roboter, der soll sich vom Stove zum Stove
bewegen.
Und dann wäre ja der Effekt davon, dass sich der Roboter nicht mehr am
Stove befindet und dass sich der Roboter am Stove befindet.
Also das ist ein Widerspruch, ja, also dass es beides wahr sein kann,
kann nicht sein.
Deshalb, wenn man diese Aktion wirklich definieren will für Bewegungen
von einem Ort zum gleichen Ort, dann müsste man das entweder
komplizierter machen oder wir sagen, das ist nur erlaubt, wenn die
beiden Orte unterschiedlich sind.
Hatte tatsächlich einer bemerkt bei der letzten Klausur.
Genau.
Ist für die nachfolgende Aufgabe aber relativ unwichtig.
War auch nicht erwartet, dass irgendjemand das erkennt in der Klausur.
Genau.
So, also das sind der Weltzustand und die Aktionen, die uns zur
Verfügung stehen und wir sollen jetzt die kürzeste Aktionssequenz
angeben.
Da komme ich nachher noch dazu, also es geht jetzt nicht darum,
irgendeinen intelligenten Planungsalgorithmus, der wirklich die
kürzeste Aktionssequenz findet, einzusetzen.
Das ist einfach nur dafür da, dass da irgendwie ein vorhersagbares
Ergebnis rauskommt, weil man den Roboter ja beliebig oft hin und her
fahren lassen könnte.
Genau.
Und dann machen wir noch einen Planungsoperator, also wo wir selber
Vorbedingungen und Effekte definieren und wir bestimmen den
Weltzustand, nachdem wir eine Aktion ausgeführt haben.
Das müssen wir eh schon vorher machen, aber nochmal explizit.
Genau.
Und wir haben jetzt hier mal zusammengefasst wieder unseren initialen
Zustand, unseren Zielzustand und wir wollen jetzt eine Aktionssequenz
finden, um das auszuführen.
Und diese Aufgabe ist absichtlich relativ einfach gestellt worden.
Der Robot, die Pen soll sich ja nachher auf dem Stove befinden.
Momentan ist sie aber auf dem Tisch.
Und der Roboter ist am Stove.
Also wir haben im Grunde so eine Situation.
Hier ist der Stove, da steht der Roboter.
Wir haben irgendwo ein Table.
Auf dem Table ist die Pen.
Und was wir erreichen wollen, ist, dass nachher auf dem Stove die Pen
steht.
Und die Aufgabe ist extra so gestellt, dass man sie auch mit Logik
lösen kann.
Der Roboter soll sich erst rüber bewegen, dann nimmt er die Pen auf,
dann muss er sich wieder zurück bewegen und dann kann er die Pen
absetzen.
Also im Grunde, das ist die Lösung der Aufgabe.
Das funktioniert aber, wie ich gesagt habe, eigentlich auf der High
-Level -Ebene nicht, sondern wir müssen uns immer anschauen, sind auch
wirklich die Vorbedingungen der Aktionen erfüllt, die wir ausführen
wollen.
Also fangen wir an.
Der Roboter soll sich erst mal zum Tisch bewegen, um nachher die Pen
aufheben zu können.
Das heißt, wir setzen die konkreten Werte in den Move-Befehl ein.
Der hatte ja vorher nur abstrakte Werte wie Agent L, Location L und
Location M.
Und wir setzen also jetzt hier die konkreten Variablen ein, die wir
hier oben definiert haben.
Dementsprechend ändern sich dann auch die Effekte und in die
Vorbedingungen werden dann auch die konkreten Variablen eingesetzt.
Und was wir jetzt machen müssen, ist eben da mal gucken, sind jetzt im
Initialzustand überhaupt die Vorbedingungen erfüllt, um uns bewegen zu
können.
Und dann sehen wir, okay, wir haben so ein paar Bedingungen, die immer
erfüllt sein werden.
Also R ist immer ein Agent.
Location S und T, das sind immer Locations.
Aber wo sich der Roboter befindet, das wird sich ändern im Laufe der
Ausführung.
Aber hier sind jetzt alle Bedingungen erfüllt und wir können diese
Aktion ausführen.
Das heißt, als nächstes müssen wir die Effekte der Aktion auf den
initialen Zustand anwenden.
Das heißt, wir haben hier eine Negation, das heißt der Roboter
befindet sich danach nicht mehr am Ort S.
Das ist hier, deshalb streichen wir es hier durch.
Stattdessen befindet er sich am Table.
Also das ist die einfache Move-Befehl.
Und wenn wir die Effekte anwenden, dann haben wir eben einen neuen
Weltzustand, mit dem wir dann weiterarbeiten können.
Also unser Roboter ist jetzt am Ort T.
Und die Pan ist auch am Ort T.
Und wenn diese beiden Bedingungen erfüllt sind, dann können wir ein
Objekt aufheben.
Wir müssen natürlich auch trotzdem die anderen Bedingungen noch
prüfen.
Ich habe jetzt mal hier diese Standardbedingungen, die immer erfüllt
sind, weil sie sich nie ändern.
Für unseren Fall sind die statisch.
Es gibt keine Aktionen, die diese ändern könnten.
Aber die anderen müssen wir prüfen.
Also ist die Hand leer?
Befindet sich das Objekt dort?
Ist der Roboter am Ort?
Ist natürlich alles erfüllt.
Dann wenden wir die Effekte an.
Das heißt, hier befindet sich das Objekt jetzt nicht mehr auf dem
Tisch.
Unsere Hand ist nicht mehr leer und wir bekommen ein neues Prädikat.
Jetzt befindet sich die Pan im Gripper.
Genau.
Dann hat unser Roboter die Pan in der Hand.
Jetzt müssen wir nur noch zurückfahren.
Das ist jetzt wieder vollkommen identisch wie beim letzten Mal.
Das heißt, was wir prüfen müssen ist, wo befindet sich der Roboter am
richtigen Ort?
Ja, befindet er sich am Tisch und wir wollen zurück zum Stove.
Das machen wir dann.
Der Effekt tritt wieder ein.
Okay, wir sind jetzt am Stove.
Und kommt die letzte Aktion, das Putdown, die jetzt hier wieder ihre
Vorbedingungen hat.
Die Pan befindet sich im Gripper.
Der Roboter befindet sich am Stove.
Wenn das erfüllt ist, dann können wir die Pan am Stove absetzen.
Das heißt, wir haben jetzt wieder die Vorbedingungen, können wir
prüfen.
Die Effekte treten wieder ein.
Und dann haben wir einen neuen Weltzustand, der unseren Zielzustand
jetzt enthält.
So sind wir im Grunde fertig.
Der aktuelle Zustand enthält den Weltzustand.
Und damit haben wir eine Aktionssequenz, die die Aufgabe erfüllt.
Wichtig ist, und ich glaube es steht auch immer in den Aufgaben drin,
dass man eben auf die konkreten Variablen achtet.
Also das R und P und so weiter.
Wenn die Aktionen quasi beschrieben werden, dann sind sie immer in
diesem allgemeinen Umfeld beschrieben.
Also Putdown wird beschrieben als ein Agent A, ein Objekt O, eine Hand
H und ein Ort L.
Und wichtig, wenn ihr diese Aktionssequenzen aufschreiben müsst, ist,
dass man dann wirklich die konkreten Variablen, die im Weltzustand
gegeben sind, einsetzt.
Typischer Fehler, genau.
Und wie gesagt, um diese kürzeste Sequenz muss man sich nicht so arg
kümmern.
Es geht nur darum, dass man jetzt nicht irgendwie...
Also man könnte ja hier zum Beispiel beliebig oft sich vom Table zum
Stove bewegen, die Aktionssequenz so lang machen wie möglich.
Es geht einfach nur darum, dass man versucht, die möglichst kurze
Sequenz zu finden.
Nicht die beweisbar kürzeste Sequenz, um das Ziel zu erreichen.
Genau.
Dann gab es im zweiten Aufgabenteil, ging es darum, einen eigenen
Planungsoperator zu definieren.
Also sinnvolle Vorbedingungen und Effekte für eine Aktion zu
definieren, die ein bisschen komplexer ist.
Der Agent soll sich von Ort L zu Ort M bewegen und dort das Objekt O
mit der Hand H aufnehmen.
Es geht so ein bisschen darum, dass die Aktionen, die man vorher
kennengelernt hat in der ersten Aufgabe, ja Vorbedingungen haben.
Und wenn man jetzt diese Aktionen quasi implementieren wollte, dann
muss man natürlich die da schon vorhandenen Vorbedingungen auch
beachten.
Genau.
Also wir haben jetzt hier Move and Pick Up und was wir natürlich
brauchen, sind immer diese Standard-Vorbedingungen.
Also bei A muss es sich um einen Agenten handeln, damit wir das
ausführen können.
Bei H muss es sich um eine Hand handeln.
Und L und M sind eben Locations, also Orte.
Und wahrscheinlich wollen wir auch, dass L ungleich M ist, das haben
wir schon gelernt, sonst passiert wieder dieser kuriose Fall, dieser
Widerspruchsfall.
Das sind so diese statischen Bedingungen, die erfüllt sein müssen.
Und dann soll sich initial der Agent am Ort L befinden, um sich
nachher zum Ort M zu bewegen.
Das Objekt soll sich an Ort M befinden und damit wir das Objekt auch
aufnehmen können, muss unsere Hand leer sein.
Ich hoffe, das war jetzt alles.
Schauen wir mal nach.
Also die sind ja auch schon so ein bisschen getrennt, das ist so der
Formalismus, den man machen muss.
Und das sind der konkrete veränderbare Weltzustand, der erfüllt sein
sollte.
Was hat diese Aktion für Effekte?
Okay, der Agent befindet sich nicht mehr am Ort L, sondern
stattdessen, nachdem er die Aktion ausgeführt hat, dann steht er eben
an dem anderen Ort, zu dem er hingefahren ist.
Das Objekt befindet sich auch nicht mehr am Ort M, sondern ist
stattdessen in der Hand.
Und deshalb ist die Hand auch nicht mehr leer.
Das sind die Effekte.
Was nicht funktioniert ist, also man kann sich ja vorstellen, wenn man
diese Aktion implementieren wollte, dann könnte man das tun als, okay,
ich bewege meinen Agenten von L zu M und dann mache ich ein Pickup mit
meinem Agenten vom Objekt O mit der Hand H am Ort M.
Und wenn man jetzt einfach die Vorbedingungen von den beiden hier
nimmt und hier hinschreibt, dann funktioniert das nicht.
Es liegt daran, dass der Move hat ja zum Beispiel die Vorbedingung,
dass sich der Roboter an dem Ort L befindet.
Und das Pickup hat die Vorbedingung, dass sich der Roboter an Ort M
befindet.
Und diese Vorbedingung vom Pickup wird eben erfüllt durch die Aktion
vom Move.
Also einfach nur die Vorbedingung von beiden zu kopieren, funktioniert
nicht, weil es immer diese...
Es gibt einige Vorbedingungen, die von Aktionen in der Sequenz erfüllt
werden, direkt.
Genau.
Also das ist in dieser Aufgabe gefordert, einfach nur mal
Vorbedingungen und Effekte von einer kombinierten Aktion
hinzuschreiben.
Genau.
Wenn wir diese Vorbedingungen und Effekte kennen, dann können wir sie
auch anwenden.
Das haben wir ja eben schon bei der Aktion-Sequenz gemacht.
Das heißt, wir haben in dieser Aufgabe explizit gesagt, wir gehen
wieder zurück in den initialen Weltzustand und wollen die Aktion
anwenden.
Was müssen wir hier jetzt wieder machen?
Okay, wir müssen die Vorbedingungen prüfen.
Wir haben wieder den Hauptteil an Vorbedingungen, die eh statisch
sind, die immer erfüllt sind.
Und den Rest können wir überprüfen.
Also wir haben, der Roboter befindet sich an dem Ort.
Unser Gripper ist empty.
Und die Pan befindet sich auf dem Tisch.
Genau.
Das ist also erfüllt.
Damit können wir dann die Effekte anwenden.
Das heißt, einige von den Eigenschaften, die wir hatten, im
Weltzustand, fallen weg.
Und andere kommen hinzu.
Und damit haben wir auch im Grunde schon die Aufgabe erfüllt.
Was wichtig ist, was auch oft vergessen wird, die Antwort ist nicht
dieses Delta.
Das ist ja im Grunde das Delta vom Weltzustand.
Sondern die Aufgabe fragt explizit nach dem gesamten Weltzustand.
Und dazu gehören eben all diese langweiligen Eigenschaften, wie dass
der Roboter ein Agent ist und so weiter, gehören alle dazu.
Also wenn gefragt ist, geben sie den gesamten Weltzustand an.
Dann muss man eben alles nochmal hinschreiben, was in der Aufgabe
gegeben ist.
Plus eben die Änderungen, die sich ergeben haben.
Genau.
Also das ist eine von diesen Strips-Aufgaben, die wie gesagt in der
einen oder anderen Ausführung öfter in den Klausuren vorkommt.
Und die von euch, die sich mal die Klausuren angesehen haben, wissen,
dass auch mehrere schon in den Altklausuren drin waren.
In unterschiedlicher Art und Weise.
Ja.
Ah.
Nicht wirklich.
Das ist mehr hier so als Spielbeispiel drin.
Aber die Planungsoperatoren machen schon Sinn und wir nutzen sie sogar
tatsächlich.
Also die Eigenschaft Agent, die verliert ihr nie.
Das ist keine dynamische Eigenschaft.
Aber wir benutzen das tatsächlich und was wir jetzt hier so gesehen
haben, also die Kombination von zum Beispiel Move und Pickup zu einem
neuen Planungsoperator, da haben wir auch tatsächlich Forschung zu
gemacht, in dem der Roboter quasi nicht...
Also hier machen wir es ja so, wir geben diese Operatoren vor und dann
wird darauf geplant.
Unser Roboter kann tatsächlich aus diesen Basis-Operationen komplexere
Planungsoperatoren kombinieren, die Vorbedingungen selber aus den
Basis -Operationen ableiten, die sowieso erfüllten auch dann quasi
rauswerfen und kann dann quasi eine High-Level-Aktion daraus ableiten.
Das hat Mirko Wächter von uns gemacht, unter anderem in seiner
Dissertation.
Also es findet tatsächlich Anwendung, aber natürlich nicht in diesem
trivialen Fall, dass jetzt der Roboter ein Agent ist oder so.
Das ist mehr so, um die Übung zu machen, aber es ist nicht irgendwie
nur Theorie.
Es findet tatsächlich Anwendung, die Strips und meistens komplexere
Planungsframeworks, aber die meisten basieren eben auf diesen Strips
-Operationen.
Dann haben wir eine kleine Einheit dazu, so ein bisschen tatsächlich
zu programmieren.
Wir haben jetzt hier nur eine ganz einfache Aufgabe, wo wir im Grunde
so einen Skelett-Code, der in Simox geschrieben wurde.
Simox ist unser kleines Framework für Roboter-Programmierung.
Wo wir das erweitern und den entsprechenden Code für Astern mal
implementieren und anschauen, was daraus kommt.
Simox ist ein bisschen komplex zu installieren.
Wir haben jetzt hier ein paar Anleitungen dafür drin, aber schauen wir
mal.
Wir schreiben dann erstmal eine Lösung im Pseudocode und dann in C++,
um das irgendwie einmal durchzukauen.
Also wie gesagt, Simox kann man sich installieren.
Problem ist, es geht zwar alles unter Windows und theoretisch unter
Mac, aber das wird überwiegend unter Ubuntu eingesetzt.
Also man kann zum Beispiel sich eine VM machen, das da installieren.
Neuerdings gibt es auch unter Windows 10 dieses Ubuntu-Subsystem,
damit werde ich das gleich machen.
Also man kann einfach sich eine Ubuntu-Distribution unter Windows
installieren und kann dann Linux-Programme laufen lassen.
Da hat ein Kollege von mir eine kurze Anleitung gemacht, wie man das
hinbekommen könnte.
Also hier ist die Anleitung dazu, wenn man das unter Windows 10 mal
machen will.
Man kann im Grunde unter den Einstellungen so ein Subsystem für Linux
aktivieren.
Wenn man das macht, dann kann man im Store Ubuntu installieren.
Und dann braucht man im Grunde nur noch so einen X-Server.
Der X-Server ist dafür da, dass man nachher auch GUIs anzeigen kann.
Und dann hat man unter Windows auch die ganz normale Linux-Bash, die
man kennt.
Kann mit Upget Updates installieren, Programme installieren und genau.
Dann kann man nämlich auch dieser Anleitung unter Xemux für Ubuntu
folgen.
Also ich habe Xemux auch mal unter Windows installiert, also Basis mit
Visual Studio kompilieren und so.
Aber das ist irgendwie aufwendiger als tatsächlich dieser Prozess,
weil es nicht so oft getestet wird.
Und das sind dann die ganz normalen Befehle, um eben die Sachen
auszuchecken und Xemux zu bauen.
Und wenn man das dann alles gemacht hat, dann kann man auch kurz
testen, ob die Xemux-Programme laufen unter Windows.
Aber wie gesagt, wir machen das auch hier einmal vor.
Also was im Iliad ist, habe ich hochgeladen.
Ich habe einmal so Projektdateien, wo Codeschnipsel halt fehlen, die
wir jetzt programmieren wollen.
Und auch eben die Musterlösung hochgeladen.
Wir werden jetzt gleich eben das Zip entpacken und dann mal schauen,
ob das baut und ausführen.
Und im ersten Schritt machen wir halt die Astern-Implementierung, das
ist in dieser Datei hier, die wir dann öffnen.
Und wir bekommen dann eine ausführbare Datei, um eben diesen
Algorithmus auszuführen.
Das heißt, ich habe jetzt hier nochmal kurze Wiederholungen vom Astern
-Algorithmus in die Folien gebracht.
Ist eben ein iterativer Ansatz, der mit einem OpenSet und einem
ClosedSet arbeitet.
OpenSet enthält die noch zu besuchenden Knoten und das ClosedSet die
bereits besuchten Knoten.
Und der Algorithmus hat einen Initialisierungsschritt, wo wir unseren
Startknoten in das OpenSet packen.
Das ClosedSet ist initial leer und wir haben sogenannte akkumulierte
Kosten, die wir bisher gebraucht haben, um den Knoten vn zu erreichen.
Die setzen wir für alle erstmal auf unendlich, außer für den
Startknoten auf 0.
Und dann können wir zum eigentlichen Algorithmus kommen.
Solange das OpenSet eben leer ist, holen wir uns den zu erweiterten
Knoten.
Das ist der, der die minimalen erwarteten Kosten noch hat.
Wenn das der Zielknoten ist, dann sind wir fertig.
Ansonsten nehmen wir den Knoten raus aus dem OpenSet, fügen ihn ein
ins ClosedSet.
Und dann müssen wir noch alle Nachfolgerknoten von diesem expandierten
Knoten bearbeiten.
Das heißt, wenn er sich schon im ClosedSet befindet, dann haben wir
ihn schon bearbeitet, sind wir fertig.
Wir müssen ihn zum OpenSet hinzufügen.
Das ist ein bisschen redundant, weil O ja eigentlich eine Menge ist.
Und wenn wir eine Abkürzung gefunden haben, also die Kosten über den
jetzt erweiterten Knoten günstiger sind als die bisherigen Kosten,
dann aktualisieren wir die Kosten, die Heuristik und setzen den
Vorgänger.
Also das ist der Algorithmus, den wir implementieren wollen.
Dann schauen wir mal, ob das funktioniert.
Ich habe irgendwo auch eine Bash-Shortcut hingelegt.
Genau.
Also wenn man diese Bash installiert hat, dann kann man unter in
dieser Windows-Bash einfach Bash eingeben.
Und dann ist man unter Linux, wie man es erwarten würde.
Jetzt muss ich nur eben dahin navigieren.
Robotic 1.
Genau.
Und da gehen wir quasi in das
Bildverzeichnis.
Und diese Simox-Projekte sind immer CMake-Projekte.
Das heißt, wir führen erstmal CMake zum Konfigurieren aus.
Steht auch so auf den Folien.
Und dann können wir das Projekt einmal bauen und schauen, ob es
ausgeführt werden kann.
Genau.
Machen wir es erstmal so.
Und in der Zwischenzeit, in diesem Code-Ordner stand ja, dass in
diesem Astern-Planner-CPP befindet sich die Datei, in der wir gleich
arbeiten werden.
Das müssen wir jetzt noch bauen.
Genau.
Genau,
das ist diese Astern-Planner-CPP-Datei.
Und die hat schon einiges an Code drin.
Also die erstellt schon einen Grid und Knoten und so weiter.
Und wir sollen im Grunde diesen Teil hier implementieren.
Nachher.
Genau, ja.
Ja, ich war auch erstaunt, ich habe es erst in diesem Semester
gelernt, dass man auch Ubuntu unter Windows installieren kann.
Ist manchmal tatsächlich nützlich.
So.
Genau, und in diesem Ordner haben wir jetzt eine Path-Planning
ausführbarer Datei.
Wenn ich die jetzt einfach so starte, dann ist es mit einer grafischen
Anwendung, dann bekomme ich hier canal-connect-to-x-server.
Also x-server ist eine der GUI-Komponenten.
Wenn ihr der Anleitung folgt, dann habt ihr einen x-server, den ihr
starten könnt.
Und dann müsst ihr auch die Anwendung starten.
Genau, ich glaube, sie startet immer so im Hintergrund.
Genau, also das ist hier die Anwendung.
Das ist der Arma 3 als Modell.
Und der soll jetzt von dieser Startposition an die Zielposition
laufen.
Ich glaube, die Schrift ist super klein, aber hier kann man den
Planner starten.
Sieht ein bisschen aus wie Windows 98, aber es liegt daran, dass es
dieses Linux unter Windows ist.
Unter normalem Ubuntu sieht es ein bisschen schöner aus.
Wenn ich das jetzt klicke, passiert nichts, weil wir ja noch nichts
implementiert haben.
Genau.
Also das ist im Grunde der Test, ob man jetzt die Projektdateien, die
man entpackt hat, ausführen kann.
Sieht gut aus.
Und dann fangen wir mal an.
Die erste Aufgabe war irgendwie so Pseudocode-mäßig das zu
implementieren.
Und wie wir das jetzt machen, ist einfach mal als Kommentare
reinschreiben und dann nachher fügen wir den wirklichen Code ein.
Zum Kontext, was wir hier haben.
Also wir haben schon Variablen, die unser OpenSet darstellen, unser
ClosedSet.
Wir haben Datenstrukturen, um die akkommodierten Kosten und die
Heuristik abzuspeichern.
Und wenn man sich in der Datei umsieht, dann gibt es schon einige
Funktionen, sind eben schon fertig, wie zum Beispiel die Heuristik
berechnen.
Ist schon von gemacht worden.
Genau.
Also zuerst mal müssen wir den Initialisierungsschritt noch
implementieren.
Das heißt, wir wollen in unser OpenSet den Startknoten reinschreiben.
Unser ClosedSet soll initial leer sein.
Die Kosten für alle Knoten wollen wir auf unendlich setzen, für alle
unsere Is.
Und initial sind die akkommodierten Kosten für den Startknoten auf 0
gesetzt.
Das ist der Initialisierungsschritt von Astern.
Dann kommt der eigentliche Algorithmus.
Wir wollen, also solange unser OpenSet nicht leer ist,
wollen wir was machen.
Oh, das ist ja interessant.
Und zwar die einzelnen Schritte.
Als erstes müssen wir den Knoten finden, den wir expandieren wollen.
Und das ist ja der Knoten, der die minimalen Kosten hat.
Also wir suchen den Knoten, für den die gesamten akkommodierten
Kosten, die erwarteten Kosten, f.
f ist ja die Summe aus g und h, für den die minimal sind.
Und jetzt kommt die Zielabfrage.
Wenn der Knoten, den wir expandieren wollen, jetzt schon das Ziel ist,
dann sind wir eben fertig.
Dann sind wir done.
Dann kommt das kurze Update für das OpenSet und das ClosedSet.
Nachdem wir den Knoten rausgenommen haben, entfernen wir den aus dem
OpenSet und wir fügen ihn zum ClosedSet hinzu.
Und dann müssen wir noch alle Nachfolger von diesem Knoten
aktualisieren.
Wenn der Nachfolger schon im ClosedSet drin ist, dann ist der uns
egal, dann haben wir den ja schon bearbeitet.
Wollen den also nicht nochmal bearbeiten.
Und wir wollen den Knoten, den Nachbarn, zum OpenSet hinzufügen, also
sofern er nicht im ClosedSet war.
Und jetzt geht es eben darum, ob wir Abkürzungen gefunden haben zu
diesem Knoten.
Das können wir überprüfen, indem wir schauen, wir nehmen die
akkumulierten Kosten zu dem Knoten, den wir gerade expandiert haben.
Wir addieren die Kosten vom expandierten Knoten zu seinem Nachbarn
dazu.
Wenn die kleiner sind als die bisherig eingetragenen Kosten für den
Nachbarknoten, dann haben wir eine Abkürzung gefunden.
Und was müssen wir machen, wenn wir eine Abkürzung gefunden haben?
Wir müssen die Kostfunktionen updaten und wir müssen die Vorgänger
updaten.
Kostfunktionen, also wir haben jetzt unsere G-Funktion, also die
akkumulierten Kosten.
Die entsprechen jetzt den neuen Kosten, den kürzeren Kosten, die wir
gefunden haben.
Und wir speichern uns auch die Heuristik schon mal ab.
Die könnte man auch immer neu berechnen, aber für den Ansatz, den wir
jetzt gewählt haben, speichern wir uns die Heuristik immer mit ab.
Und wir wollen natürlich den Vorgänger von unserem Knoten jetzt neu
setzen, weil wir haben ja den kürzeren Pfad gefunden und der soll
nachher auch entdeckt werden.
Genau, und das ist im Grunde der Sternalgorithmus jetzt hier in den
Kommentaren hingeschrieben.
Wie gesagt, wenn wir das jetzt hier in dem C++ Snippet implementieren
wollen, dann müssen wir uns immer so ein bisschen umschauen, was gibt
es denn hier schon?
Es gibt schon OpenSet, CloseSet, wie gesagt, diese Funktionen g und h,
approximiert als Map, als Abbildung von einem Knoten auf einen
Floatwert.
Und dann können wir also hier unser OpenSet, in dem wir initial
unseren Startknoten reinschreiben wollen, können wir ihn einfügen.
Fürs CloseSet müssen wir gar nichts machen, das ist hier leer
initialisiert worden.
Und wir machen auch für diesen Schritt, also wir könnten hier jetzt
alles auf Infinity setzen oder so.
Wir werden das später so machen, dass wir einfach nachschauen, ob ein
Wert schon hier drin steht und wenn er nicht drin steht, dann nehmen
wir eben einen Infinity oder einen großen Wert an.
Also den Teil hier machen wir auch nur implizit.
Aber den Teil hier, die akkumulierten Kosten zum Startknoten, setzen
wir initial mal auf den Wert 0.
Also hier sind das jetzt eckige Klammern, das liegt daran, dass wir
diese Map benutzen aus C++.
Selbst sind es hier keine runden Klammern.
Im Prinzip ist es das gleiche.
Genau.
Das sind die Initialisierungsschritte.
Und dann der eigentliche Algorithmus.
Also wir wollen, solange das OpenSet nicht leer ist, und die Set
-Methoden unter C++ haben eben eine Empty-Methode, wenn wir das
abfragen können.
Dann, das hier dauert ein bisschen länger, wir könnten dafür eine
Standardfunktion nehmen, wir implementieren das aber mal von Hand.
Wir wollen den Knoten vi finden, der die minimalen erwarteten Kosten
hat.
Das heißt, wir legen uns erstmal einen Knoten an und sagen, okay, wir
wollen den mit minimalen Kosten finden.
Und ich setze das mal hier auf float max, das ist ein großer Wert, das
heißt die anderen Werte werden definitiv kleiner sein, die wir finden.
Und dann gehen wir einfach über alle Knoten in der Map im OpenSet
und schauen, was sind die gesamten Kosten für den Knoten.
Die setzen sich zusammen aus den akkumulierten Kosten und der
Heuristik für den Knoten.
Und wenn diese erwarteten Kosten f, wenn die kleiner sind als die
bisherigen, dann aktualisieren wir unseren Knoten.
Das heißt, wir haben einen Knoten mit niedrigeren Kosten gefunden im
OpenSet.
Also das Ganze könnte man auch, gibt's schon Standardfunktionen zu in
C++, aber hier jetzt mal eine ganz triviale Schleife, die nur das
minimale Element, den Knoten mit den minimalen Kosten raussucht.
Das steht dann nachher in vi drin.
Dann können wir schauen, ob wir am Ziel sind.
Und in diesem Fall wollen wir dann aus dieser Schleife rausgehen.
Wir wollen nicht aus der Funktion raus, weil die Funktion noch den
Pfad berechnet und so weiter.
Also beenden wir hier nur die Schleife, wenn wir fertig sind.
Genau, also das ist der erste Teil vom Astern-Algorithmus.
Minimalen Knoten finden, expandieren, prüfen, ob wir das Ziel erreicht
haben.
Dann diesen Knoten, den wir gefunden haben wollen, wir zum OpenSet
hinzufügen und, ah, entfernen.
Das wäre interessant geworden.
In C++ die Methode dafür erase und das CloseSet, da wollen wir den
Knoten einfügen, weil wir ihn expandiert haben.
Genau, um alle Nachfolger abzudaten, haben wir hier den Vorteil, dass
diese Knoten enthalten schon alle Nachfolger als Array, sag ich mal.
Das heißt, wir können einfach in vi nachschauen, was sind deine
Nachfolger.
Können über die iterieren.
Wie gesagt, wir müssen jetzt noch gucken, ob dieser Nachfolger
vielleicht schon behandelt wurde.
Das ist so ein bisschen awkward mit diesen Standard-Sets, aber man
kann zum Beispiel nachfragen, wie viele von denen sind denn bei dir
drin.
Ein Set kann eigentlich nur einen enthalten, aber wenn wir mehr als
einen enthalten, dann findet sich das Element im Set.
Das ist diese Count-Methode.
Dann wollen wir skippen, also nur dieses Element skippen, aber mit der
Schleife weitermachen, also machen wir continue.
Wenn es nicht geskippt wurde, dann wollen wir es ins OpenSet einfügen.
Dann wollen wir herausfinden, ob wir einen kürzeren Pfad gefunden
haben.
Dafür müssen wir uns mal anschauen, was sind die neuen akkumulierten
Kosten.
Das ist vi plus die Kosten von vi nach vj.
Eigentlich, in dieser Aufgabe gibt es keine explizite Kostenfunktion.
Das heißt, wir benutzen jetzt hier, weil wir faul sind, auch die
Heuristik -Funktion, um die tatsächlichen Kosten zu bestimmen.
Die funktioniert auch in diesem Fall, weil hier sind es einfach nur
der kathesische Abstand, die Kosten.
Und die alten Kosten, die waren ja in vj drin.
Und das ist die Stelle, wo wir jetzt aufpassen müssen, weil wir haben
jetzt ja nicht überall infinity reingeschrieben, sondern wir haben
unser g leer gelassen für die Elemente, die wir noch nicht behandelt
haben.
Das heißt, wir müssen hier eigentlich schauen, gibt es überhaupt ein
vj hier drin.
Wenn es das gibt, dann können wir das abfragen.
Wenn es das nicht gibt, dann geben wir einfach einen besonders großen
Wert zurück.
Also das ist jetzt der Schritt, den wir machen mussten, weil wir am
Anfang zu faul waren, alle Werte auf float max oder infinity zu
initialisieren.
Und dann müssen wir gucken, wenn die neuen Kosten kleiner sind als die
alten Kosten, dann müssen wir die Kostenfunktion aktualisieren.
Das heißt, vj wird jetzt auf die neuen Kosten gesetzt.
Die neuen Kosten haben wir ja schon einmal berechnet, also können wir
es auch hier so hinschreiben.
Und in diesem Fall haben wir die Heuristik auch immer gecached, das
heißt, wir speichern die uns ab.
Wir könnten sie, wie gesagt, auch immer neu berechnen.
Das ist auch kein Problem.
Und abschließend müssen wir noch die Vorgänger aktualisieren.
Das ist hier auch wieder relativ einfach gemacht.
Dieses vj hat einfach eine predecessor-Eigenschaft, die wir
umschreiben können.
Und damit müssten wir fertig sein.
Ich habe bestimmt irgendwas falsch getippt, aber wir schauen uns das
einfach mal an,
was da jetzt rauskommt.
Ah, ein Semikolon vergessen.
Vor der while-Schleife.
Ah,
und cj anstatt vj geschrieben.
Ja, ich hätte gerne einen Qt-Creator oder eine andere
Entwicklungsumgebung gezeigt, aber der Qt-Creator ist ein bisschen
langsam in dieser emulierten Linux-Umgebung.
Deshalb müssen wir jetzt damit zurechtkommen, dass ich einige
Tippfehler gemacht habe.
Okay, aber es hat gebaut.
Hoffen wir, es macht auch das Richtige.
Okay, wir sind wieder hier.
Wir haben unsere Umgebung.
Der Roboter.
Wir haben A-Start-Planner ausgewählt.
Mein Gott, ist die Schrift klein.
Und können Run-Planner klicken.
Oh, und es hat sogar funktioniert.
Man sieht hier die einzelnen Knoten und die verbundenen Pfade.
Also die Knoten wurden hier einfach an einem Grid erstellt.
Und wir können jetzt den Roboter hier mit seiner Plattform durch die
Hindernisse bewegen.
Der Sinn dieser Aufgabe.
Genau.
Also das war so ein bisschen gedacht, dass ihr einmal mit CMOS
rumspielen könnt, euch ein bisschen das anschauen könnt.
Die nächste Aufgabe geht um den ERT-Planner in dieser Aufgabe, in
diesem Code-Paket.
Dafür habe ich aber, glaube ich, nochmal ein paar Folien eingefügt.
Genau.
Also wir haben den ERT-Planner, der ist jetzt hier in einer anderen
Datei.
Und ich habe nochmal die Folien reingefügt, die im 8.
Kapitel war es, dass, glaube ich, dran kam, um die einzelnen Schritte
beim ERT zu erklären.
Und dann implementieren wir, ich glaube, die meisten davon, außer
vielleicht das Sampling.
Vielleicht auch ein bisschen als Wiederholung, wie ERT funktioniert.
Gar nicht so schlecht.
Genau.
Also bei ERT haben wir einen Startknoten.
Von dem Startknoten aus bauen wir langsam einen Baum auf.
Bis wir irgendwann beim Zielknoten angekommen sind.
Und wie funktioniert der Algorithmus?
Also angenommen, ich habe meinen Baum.
Dann wird immer ein zufälliger Punkt gesampelt.
Von diesem zufälligen Punkt wird der nächste Nachbar bestimmt.
Der nächste Nachbar.
Und dann wird zwischen dem nächsten Nachbar und dem gesampelten Punkt
ein sogenannter Extentschritt ausgeführt.
Den wir dann auch gleich implementieren werden.
Also ich glaube, wir machen nächster Nachbar und den Extentschritt und
vielleicht irgendwie Constraints prüfen.
Und was dabei passiert ist, dass wir uns in Richtung vom gesampelten
Knoten bewegen.
Aber nicht voll hin, sondern in einem gewissen Abstand d immer.
So einen inkrementellen Abstand.
Und das machen wir so lange, bis wir da sind.
Und wir prüfen immer jeweils die Teilfade auf Kollision.
Das heißt, hier und hier prüfen wir, ob die in Kollision sind.
Das implementieren wir auch, ist aber auch nicht so relevant, wie das
im Detail gemacht wird.
Wichtig ist, dass der Schritt hier erfolgt.
Das heißt, hier in diesem Fall hätten wir zwei Expansionsschritte,
weil keine Kollision passiert.
Landen wir dort.
Wenn wir stattdessen ein Sample hier unten haben.
Und unseren nächsten Nachbar da oben.
Dann passiert eben bei dem Extentschritt, dass es erstmal gut geht.
Und dann eben fehlschlägt.
Das heißt hier, das hier ist okay.
Und das hier schlägt fehl, weil wir uns da in Kollision befinden.
Das heißt, unser Graph wird bei diesem gesampelten Punkt nur in einen
Schritt erweitert.
Genau, also das sind die Schritte.
Man sampelt den Punkt, man bestimmt den nächsten Nachbarn und man
erweitert ihn in die Richtung.
Und prüft dabei mal Kollisionen mit der Umgebung.
Und das wollen wir dann auch einmal im Code machen.
Also das ist hier die ERT Planner CPP Datei, die gegeben war.
Ein bisschen Code drumherum.
Der Code, um einen zufälligen Knoten zu erzeugen, ist schon gegeben.
Das heißt, den müssen wir nicht mehr implementieren.
Aber den nächsten Nachbarn finden, ist ja eine Aufgabe.
Nächsten Nachbarn finden ist wieder...
Wir haben es eben ja schon, den Knoten mit minimalen Kosten bestimmt.
Hier ist es jetzt wieder sehr, sehr ähnlich.
Das heißt, wir merken uns einfach die bisher minimale Distanz.
Schreiben da einen großen Wert rein.
Und gehen über alle Knoten.
Und wir haben hier die Knoten hier gegeben.
Als Vertices.
Und dann müssen wir jetzt hier die Distanz bestimmen.
Und diese Knoten haben immer eine 2D-Position drin.
Wir benutzen jetzt hier Eigen als Mathe-Bibliothek.
Zumindest für die meisten Dinge.
Das heißt, hier sind auch überladene Operatoren drin.
Das heißt, ich kann einfach die Position vom random Knoten nehmen.
Und von dem die Position vom nächsten Knoten nehmen.
Das heißt, das hier ist ein Vektor, der zeigt vom nächsten Knoten zum
random Knoten hin.
In 2D.
Und von dem kann ich mir dann auch die Länge geben lassen.
In Eigen gibt es dann die Methode Norm dafür.
Heißt halt nicht Längs, aber Norm.
Damit bekommt man die Distanz.
Und wenn diese Distanz kleiner ist als die bisherige minimale Distanz,
dann können wir eben aktualisieren.
Und wir schreiben unser Ergebnis hier in die Variable nearest rein,
die hier gegeben ist.
Das heißt, wie eben eine ganz normale Schleife über alle Knoten gehen,
die mit der minimalen Distanz bestimmen, ausgehen.
Genau.
Dann der Extentschritt, der ist sicherlich interessanter, weil der RT
-spezifisch ist.
Gegeben haben wir jetzt hier den nächsten Knoten und den zufälligen
Knoten.
Und wir haben hier so eine Incremental Distance gegeben.
Also diese Incremental Distance ist das D, was wir im Algorithmus
kennengelernt haben.
Also die Schrittweite, die wir gehen wollen.
Also was müssen wir machen?
Wir bestimmen erstmal einen Vektor, der vom nächsten Knoten zum random
Knoten zeigt.
Gut, der ist natürlich immer noch von einer beliebigen Länge.
Das heißt, wir müssen ihn jetzt kürzen, dass er nur noch die Länge D
hat.
Das kann man auf beliebig viele Art und Weisen machen.
Ich glaube, hier haben wir es so gemacht, dass wir uns erstmal die
Länge von ihm genommen haben.
Also wie lang ist er aktuell?
Und dann haben wir das tatsächliche Inkrement bestimmt, indem wir den
Vektor normalisiert haben.
Also es gibt eine Methode normalize, die macht den Vektor zu einem
Einheitsvektor.
Das heißt, wir haben hier den Einheitsvektor, der von Near nach Random
zeigt.
Und dann wollen wir ihn begrenzen, dass er maximal die Distanz
Incremental Distance annimmt.
Und das ist so ein bisschen... sieht paradox aus, aber wenn man einen
Wert aufs Maximale begrenzen will, dann nimmt man das Minimum von
seiner aktuellen Länge und dem Maximum.
Also wenn jetzt hier Incremental Distance, unser D, größer ist als die
tatsächliche Abstand, dann nehmen wir den tatsächlichen Abstand, weil
er kleiner ist.
Wenn der tatsächliche Abstand größer ist als unser D, dann kriegen wir
den minimalen Wert, das ist das D, dann raus.
Das heißt, dieser Extent-Schritt begrenzt hier die Länge des Vektors
auf D.
Kann man auch auf beliebige andere Art und Weise berechnen.
Genau.
Und in dieser Funktion sollen wir unsere Lösung in die New Post
reinschreiben, die wir zurückgegeben.
Das heißt, wir starten beim Nearest-Knoten und wir addieren das
Increment dazu.
Damit haben wir einen neuen 2D-Vektor, der dann zurückgegeben wird.
Genau, also der wichtige Schritt zur Begrenzung ist im Grunde hier der
Teil.
Und die Richtung bestimmen wir, indem wir den Random-Knoten und den
Nächsten -Knoten betrachten.
Genau, damit können wir den Extent-Schritt machen.
Jetzt ist hier noch ein Schritt drin, der prüfen soll, ob die
Constraints erfüllt sind.
Das ist eigentlich relativ unwichtig, weil das ist nur spezifischer
Code zu CMOGS, aber nur damit ihr es mal gesehen habt.
Wie prüft man denn Kollisionen in unserem Framework?
Da gibt es einen Collision-Checker-Komponente, von der wir uns ein
Instanzieren oder
uns die globale Instanz einfach holen.
Und mit diesem können wir dann überall unsere Hindernisse iterieren.
Also es gibt so eine Obstacles-Collection hier, von der wir uns alle
Kollisionsmodelle holen können.
Und dann können wir diesen Collision-Checker einfach fragen,
ob sich zwei Objekte in Kollision befinden.
Und wir haben jetzt hier das Robot-Collision-Model, also den Roboter,
gegeben.
Wir haben unser Obstacle gegeben, wir können ihn fragen, ist das
Obstacle mit dem Roboter in Kollision?
Wenn das so ist,
dann erfüllen wir die Vorbedingungen nicht.
Aber wie gesagt, das ist relativ unwichtig jetzt für den Inhalt von
Robotik 1, aber kommt eben in dieser Praktikumsaufgabe auch vor.
Also so könnte man Kollisionen zwischen dem Roboter und der Umgebung
prüfen.
Genau.
So.
Und das sind tatsächlich alle Einzelschritte.
Also wie gesagt, das Erzeugen von zufälligen Knoten war ja schon
gegeben.
Wir haben den nearest neighbor implementiert, wir haben den extend
-Schritt implementiert und wir haben auch eine Methode geschrieben, um
Constraints zu prüfen.
Das heißt, wir können jetzt einfach den ERT-Algorithmus mit den
bestehenden Methoden hinschreiben.
Wir sehen, wir sind hier schon in einer Schleife drin.
Der ERT arbeitet ja iterativ, das heißt, wir müssen nur einen
Schleifenschritt jetzt implementieren.
Also der Algorithmus geht ja so vor, dass er zuerst einen zufälligen
Knoten erzeugt.
Was wir hier jetzt zusätzlich noch haben...
Für einen zufälligen Knoten bräuchte der eigentlich gar keine
Parameter, aber diese Funktion wählt mit einer gewissen
Wahrscheinlichkeit den Zielknoten aus, als gesampelten Knoten.
Also zum Beispiel könnte node.random gleich 0,5 sein und dann wird mit
50 % Wahrscheinlichkeit der Zielknoten als zufälliger Knoten gewählt
von dieser Funktion.
Damit bringt man den Baum so in die Richtung, dass er tendiert zum
Ziel zu expandieren und nicht einfach nur in die Breite.
So eine typische Variation vom ERT.
Genau, dann müssen wir den nächsten Nachbarn bestimmen.
Die Methode haben wir ja eben implementiert.
nearestVertex und wir wollen den nächsten Knoten, der am nächsten an
node.random dran ist, rausholen.
Genau.
Und jetzt wollen wir natürlich die Expansion des Baums beschränken.
Also er soll nicht direkt zum random gehen, sondern nur um die
inkrementelle Distanz voranschreiten.
Das heißt, wir extenden.
Das ist auch wieder die Methode, die wir eben implementiert haben.
Wir extenden vom nächsten Nachbarn in Richtung des zufälligen Knoten.
Und diese Klasse hat jetzt schon ein Member für die inkrementelle
Distanz.
Da müssen Sie uns hier nicht einen Wert ausdenken.
Genau, also als wir den Algorithmus eben, wie wir den in der Vorlesung
vorgestellt haben, wird dieses Extend in der Schleife durchgeführt,
bis man wirklich an den Sample-Knoten rankommt oder in Kollision
steht.
Eine Variante vom ERT, die wir jetzt hier implementieren, macht nur
einen Extend-Schritt, also keine Schleife hier drumherum.
Also der ERT hat sehr, sehr viele unterschiedliche Varianten.
Das ist eine der Stellen, wo man variieren kann.
Aber was wir noch gucken müssen, ist, ob der neue Knoten jetzt
kollisionsfrei verbunden werden kann.
Das heißt, wir prüfen die Constraints für den neuen Knoten.
Das ist die Methode, die wir jetzt eben über die Collision-Checker
implementiert haben.
Ist auch nur eine Näherung, weil wir prüfen nur, ob der Roboter in der
Konfiguration nicht in Kollision steht.
Eigentlich müssten wir den ganzen Pfad prüfen, aber wir machen ein
paar Vereinfachungen hier.
Also angenommen, das ist kollisionsfrei, dann können wir den neuen
Knoten hinzufügen.
Und eine Kante hinzufügen.
Vom nächsten Knoten zum neuen Knoten.
Und jetzt gibt es hier noch eine Überprüfung, ob wir das Ziel erreicht
haben.
Das ist jetzt auch etwas vereinfacht dargestellt.
Also wir schauen einfach, ob der neue Knoten nah genug am Ziel ist.
Also wir warten nicht, bis der Zielknoten wirklich verbunden wurde.
Das kann für manche Aufgaben ausreichend sein.
Also wenn dieser Abstand zum Ziel kleiner als ein Epsilon ist.
Epsilon ist auch schon in der Klasse vorgegeben.
Dann sagen wir, okay, wir haben eine Lösung gefunden.
Und jetzt kommt noch der kleine Trick.
Wir tun jetzt so, als wäre der Zielknoten der Knoten, den wir gerade
expandiert haben.
Das ist nur dafür da, damit nachher auch der Pfad richtig bestimmt
werden kann.
Weil der Pfad bestimmt wird, indem wir rückwärts vom Ziel laufen.
Und da wir hier jetzt diese Vereinfachung gemacht haben, dass wir
aufhören, wenn wir nah genug dran sind.
Ist es nicht unbedingt wirklich der Zielknoten.
Ist nur eine Vereinfachung.
Genau.
Das sieht man dann hier außerhalb, dass der Zielknoten dann benutzt
wird, um die Vorgänger abzulaufen.
Genau.
So, ich wette, ich habe jetzt wieder einiges unsinnigen Zeug
geschrieben, aber schauen wir mal.
Okay, not near was not declared.
Ah, ja, das heißt hier ja auch nearest.
Natürlich.
Auch distance to goal ist auch noch falsch.
So.
Hoffen wir, dass das die Anzahl an Tippfehler waren, die ich so...
Ah, okay, gut.
Jetzt hilft uns das natürlich immer noch nicht.
Vielleicht habe ich auch vollkommen Unsinn programmiert.
Wenn mal nicht.
Oh.
Vielleicht doch.
Hat jemand Unsinn mitbekommen, den ich eingetippt habe?
Sonst kann ich natürlich auch schauen, was anders ist.
Hm.
Gott sei Dank habe ich ja...
habe ich die Lösung mitgebracht, aber...
ich hoffe mal nicht...
dass die auch falsch ist.
Erstmal schauen, ob...
Okay, ich habe anscheinend etwas Dummes getan.
Na ja, bevor ich jetzt Zeit verschwende, den zu suchen.
Die Lösung habt ihr ja, und vielleicht kann mir dann einer auch
schreiben, was ich falsch getippt habe.
Oder ich schaue es selber nach.
Genau, und man sieht im Vergleich zum A-Stern...
ist der halt zufälliger.
Man sieht es hier, es ist natürlich ziemlich klein, aber...
der Pfad ist nicht so regelmäßig.
Wenn wir nochmal unseren A-Stern ausführen...
Ah, lustigerweise startet der dann da.
Okay, das war mir nicht bewusst.
Genau, der A-Stern sieht halt wesentlich gerader aus...
als der ERT.
Da sieht man die zufälligen Elemente drin.
Genau.
Wir haben noch...
einen kurzen Moment Zeit für...
einen kleinen Teil, den wir in der...
Vorlesung nicht behandelt haben.
Aber Tamin wollte, dass ich es euch kurz noch zeige.
Also was gibt es überhaupt alles an Software...
in dem Bereich.
Ich habe euch die ganzen Folien hochgeladen, aber...
es ist im Grunde nur so eine Übersicht, wie so diese ganzen...
Software -Frameworks aussehen.
Wir haben jetzt Simox gesehen.
Simox ist so im Bereich der allgemeinen Software.
Also es ist kein gesamtes Framework.
Das bekannteste Roboter-Framework...
oder auch sogar Operating-System genannt...
ist ROS, sicherlich.
Vor allem als Middleware eingesetzt.
Also es ist nicht wirklich ein Betriebssystem oder so.
Es ist die aktiveste Community...
in dem Robotik-Bereich.
Also wenn ihr irgendwas in Robotik macht, dann kommt ihr eigentlich
nicht um ROS herum.
Und durch die vielen Entwickler gibt es auch sehr, sehr viele...
Programme und Features.
Vom Konzept her ist es so, dass man...
einen ROS-Master hat und man schreibt einzelne...
ROS -Notes.
Das sind im Grunde...
kleine Programme, die Funktionalität anbieten.
Und die können untereinander mit Nachrichten kommunizieren.
Also viele dieser Robotik-Frameworks sind im Grunde...
Middleware für verteilte Systeme.
Und wir können hier über TCP kommunizieren.
Wir haben Nachrichten, also Topics, Publish, Subscribe.
Wir können auch RPCs basierend auf diesen Topics...
basierend auf den Messages implementieren.
Genau.
Aber was ROS so beliebt macht, oder inzwischen...
wo man nicht mehr drüber rumkommt, ist eben die ganze Software, die
schon dafür existiert.
Also es gibt zum Beispiel Avis, eine sehr bekannte Visualisierung.
Gazebo als Simulator.
Es gibt was für Koordinatentransformationen...
und URDF.
Das haben wir, glaube ich, nicht behandelt.
Aber es ist so dieses universelle Roboterformat, in dem...
man die Kinematik von Robotern beschreiben kann.
Um sie dann zum Beispiel...
in der Programmierung zu benutzen, für Simulationen...
und so weiter.
Es gibt schon Dinge für Navigation im 2D-Raum.
Es gibt Movit, was hier nicht draufsteht.
Es gibt auch Graspit.
Ich glaube, das kam in der Greif-Vorlesung schon mal vor.
Es gibt im Grunde schon für Bewegungsplanung, Greifplanung...
und so gibt es schon fertige Lösungen in ROS drin.
Also wenn es euch interessiert, ist es sicherlich eine interessante
Sache, sich anzuschauen.
Was wir gemacht haben damals...
als ROS noch nicht so groß ist, haben wir an unserem Lehrstuhl...
ein eigenes Framework gemacht.
Kann man so oder so sehen.
Basiert aber auf denselben Prinzipien.
Es ist einfach Middleware für verteilte Systeme.
Abstrahiert den Hardware-Zugriff.
Und erlaubt eben High-Level mit State-Charts...
die Roboter zu programmieren.
Das haben wir jetzt in dieser Vorlesung nicht gesehen.
Und man weiß immer, in welchem Zustand...
sich der Roboter befindet, weil wir eben diese High-Level State-Charts
benutzen.
Genau, da gibt es auch eine Webseite zu.
Möchte ich auch gar nicht ins Detail eingehen, aber so von der
Architektur...
Wir haben oben die Anwendungen, die man selber programmiert.
Dann gibt es ganz viele Sachen in dem Roboter-Framework...
in dem eben Komponenten bereitgestellt werden, die es schon gibt.
Wir haben eine Middleware und unten gibt es den, also das ist ICE in
unserem Fall...
also nicht einfaches TCP, sondern es ist noch eine Schicht höher.
Und unten haben wir eine Abstraktionsschicht...
wo zum Beispiel man entweder einen Roboter anschließen kann...
mit Realtime-Control...
oder man schießt einen Simulator an.
Und das, was wir tatsächlich geschafft haben, ist, dass man eben seine
High -Level-Software schreiben kann...
für den Simulator und den Wechsel auf den Roboter...
ist dann relativ einfach zu machen.
Hier ist es nochmal dargestellt.
Also High-Level machen wir das mit State-Charts.
Dann haben wir eben Komponenten, die so die Fähigkeiten des Roboters
abbilden.
Und unten gibt es dann die Verbindung zur wirklichen Hardware...
also die Treiber und die Kontrolleinheiten und so weiter.
Genau, MemoryX ist nicht so wichtig.
Genau, hier sieht man das dann einmal im Einsatz.
Also man denkt es nicht, aber heutzutage bestehen eben...
Roboter-Control-Frameworks wirklich aus 30 bis 40 Anwendungen...
die parallel laufen und alle miteinander kommunizieren.
Also man hat ein tatsächlich verteiltes System...
nicht nur eine monolithische Anwendung.
Genau, AmaX hat ein paar Tools, aber das skippen wir mal...
angesichts der Zeit.
Anderes Roboter-Framework ist auch relativ bekannt...
ist Yet Another Robot-Plattform.
Ja, überwiegend beim IIT-Einsatz für den iCub.
Den habt ihr bestimmt auch schon mal gesehen.
Das ist dieser Roboter, der so groß ist wie ein Kleinkind.
Der kann sogar seine Augen auf und zu machen.
Genau, wird überwiegend eben für den eingesetzt.
Hat aber auch Einzug in ein paar andere Roboter gefunden.
Ist auch sehr ähnlich zu...
ROS, ein bisschen lowleveliger als AmaX.
Genau, also...
YARP ist tatsächlich relativ lightweight.
Also man hat im Grunde nur die Möglichkeit...
Interfaces zwischen seinen Komponenten zu bestimmen...
und dann eben Nachrichten auszutauschen.
Aber die wirkliche Implementierung von Robot Control...
die muss man dann selber machen.
Und YARP hat tatsächlich ähnliche GUIs, die man auch in AmaX findet.
Also das hier ist im Grunde das Äquivalent zu unserem Szenario
Manager.
Also hier sieht man die Anwendungen, die alle gestartet sind und wie
sie verbunden sind.
Hier sieht man, glaube ich, ein Kontrollfenster.
Genau.
Und wir hatten halt ein paar Sachen kennengelernt, auch in der
Vorlesung.
Also es gibt so ein paar, ich sag mal, highleveligere Dinge.
Also wenn man in ROS, AmaX oder YARP was implementiert...
dann muss man halt wirklich die Dinge...
von Grund auf programmieren.
Aber es gibt, wie gesagt, MATLAB Robotics Toolbox...
auch so highlevel Dinge, die man dann in Simulation macht.
Aber ich habe auch oft schon Leute gesehen, die dann im Grunde ihren
MATLAB -Code nehmen...
und dann nach C übersetzen und damit dann Control machen.
Also das gibt es tatsächlich, ist aber dann ein bisschen aufwendiger.
Genau.
Simulink haben wir auch kurz kennengelernt...
und wird natürlich auch gerne dann für die Simulation...
und die Entwicklung von Regelkreisläufen und so weiter verwendet.
Ja, das letzte wirkliche...
Roboter-Framework ist Oracles, ist so ein bisschen älter...
und hat sehr starken Fokus auf Echtzeitregelung.
Also es kommt noch so aus der Zeit, als Fokus in Robotik nur Regelung
war.
Ist natürlich heute immer noch wichtig.
Aber heute sind auch andere Dinge wichtig.
Genau, also ist eins eher von den Älteren...
und ist heute nicht mehr so stark im Einsatz.
Genau.
Also hat hier sehr ähnlich, JAB macht das auch so.
Zwischen den einzelnen Komponenten definiert man Ports...
und über die Ports kann man dann Nachrichten austauschen...
zwischen den einzelnen Komponenten.
Genau, die beiden sind relativ unwichtig.
Und damit nur nochmal als Überblick, das stelle ich jetzt nicht mehr
vor.
Wir haben auch einiges davon schon behandelt.
Es gibt noch Software, die so in Robotik immer im Einsatz ist...
aber nicht wirklich in diese Roboter-Frameworks passt.
OpenCV haben wir kennengelernt in der Bildverarbeitung.
PCL ist für Pumpwolken.
Ist heutzutage ja auch wichtig wegen den 3D-Kameras.
Simox haben wir heute ein bisschen von gesehen.
MMM ist von uns, um Bewegungen von Menschen...
auf den Roboter übertragen zu können.
Graspit zum Greifen.
Und dann gibt es einige Simulatoren, die im Einsatz sind...
um eben dynamische Simulationen mit Roboter-Modellen machen zu können.
Damit würde ich das jetzt auch beenden.
Das war nur so kurz der Überblick.