WEBVTT 00:06.520 --> 00:10.280 Ja, dann eigentlich zur Übung, aber erst noch einen Einschub. 00:12.420 --> 00:16.240 Ihr wisst, die Klausur steht bis in einem Monat ungefähr. 00:17.840 --> 00:19.640 Viele von euch haben sich auch schon angemeldet. 00:20.360 --> 00:22.880 Das Interessante ist, hier sitzen vielleicht, ich weiß nicht, nicht 00:22.880 --> 00:25.760 mal 100 Leute, es haben sich schon ungefähr 300 Leute für die Klausur 00:25.760 --> 00:26.240 angemeldet. 00:26.580 --> 00:30.500 Wir erwarten so ungefähr 500 oder so in der Größenordnung. 00:31.160 --> 00:33.940 Das wäre eine normale Zahl an Klausurteilnehmern. 00:35.080 --> 00:38.100 Die ist am Montag, 11.03., 14 bis 15 Uhr. 00:38.380 --> 00:41.480 Die Hörsäle können wir erst kurz vorher bekannt geben. 00:41.860 --> 00:46.040 Ihr dürft euch ja bis eine Woche vorher anmelden, bis zum 04.03. 00:46.380 --> 00:49.240 Und erst dann können wir planen, welche Leute wir in welche Hörsäle 00:49.240 --> 00:52.520 packen, weil wir euch natürlich nicht hier zum Beispiel in der HASA 00:52.520 --> 00:56.700 prüfen können, sondern das werden dann fünf bis zehn Hörsäle sein, je 00:56.700 --> 00:59.560 nachdem wie viele sich anmelden und wie groß die Hörsäle sind, die wir 00:59.560 --> 00:59.840 haben. 01:01.140 --> 01:03.060 Das wird dann alles im IDIAS bekannt gegeben. 01:03.940 --> 01:06.820 Für die Klausur wichtig, es wird natürlich auch nochmal 01:06.820 --> 01:11.560 rumgeschrieben, im IDIAS bekannt gegeben, aber trotzdem bekommen wir 01:11.560 --> 01:12.940 immer 20, 30 E-Mails. 01:13.160 --> 01:16.280 Es sind keine Hilfsmittel zugelassen, also keine Taschenrechner. 01:16.360 --> 01:19.460 Ihr dürft auch euer Smartphone nicht benutzen oder so, also keine 01:19.460 --> 01:19.940 Hilfsmittel. 01:20.700 --> 01:25.180 Schreibmaterial ist natürlich okay, also Geodreieck, Stift braucht ihr 01:25.180 --> 01:26.120 natürlich zum Schreiben. 01:26.960 --> 01:31.140 Ihr solltet nichts mit Bleistift machen, also auch keine Zeichnungen. 01:32.400 --> 01:35.940 Egal was ihr mit Bleistift draufschreibt, wird als nicht existent 01:35.940 --> 01:38.380 bewertet, weil ihr könntet das in der Klausureinsicht ändern. 01:39.020 --> 01:42.080 Also Kugelschreiber, Füller, alles okay, aber bitte nichts mit 01:42.080 --> 01:44.160 Bleistift machen, weil dann müssen wir da einfach null Punkte 01:44.160 --> 01:46.860 hinschreiben, auch wenn das vielleicht richtig ist, was ihr gemacht 01:46.860 --> 01:47.140 habt. 01:48.740 --> 01:50.700 Genau, die Hörsaalverteilung wird bekannt gegeben. 01:50.980 --> 01:54.040 Auch wichtig, bitte bringt sowohl euren Studentenausweis als auch 01:54.040 --> 01:55.920 irgendeine andere Form von Ausweis mit. 01:55.920 --> 01:59.900 Und ne, irgendwie eine Penny-Mitgliedskarte ist kein Ausweis, also 01:59.900 --> 02:02.360 irgendein amtliches Ausweisdokument. 02:04.000 --> 02:07.820 Das geht natürlich dann trotzdem, das ist für uns dann aber und für 02:07.820 --> 02:08.860 euch auch sehr viel Aufwand. 02:08.940 --> 02:11.680 Dann müsst ihr so ein Dokument unter Vorbehalt unterschreiben und dann 02:11.680 --> 02:15.260 damit zu unserem Sekretariat nachher gehen und wir müssten das extra 02:15.260 --> 02:15.700 behandeln. 02:16.160 --> 02:18.220 Also irgendeinen Führerschein, Personalausweis, 02:18.400 --> 02:21.220 Aufenthaltsgenehmigung, was auch immer, irgendwas Amtliches, mit dem 02:21.220 --> 02:23.060 ihr euch ausweisen könnt, mitbringen. 02:23.840 --> 02:26.540 Genau, und das hier sind die Nummern, die ich von unserem Sekretariat 02:26.540 --> 02:27.620 bekommen habe zum Anmelden. 02:28.040 --> 02:30.640 Wenn ihr euch da nicht anmelden könnt, ich hatte ja auch schon einige 02:30.640 --> 02:34.040 hier vorne, ich kann euch da nicht helfen, ich bin nur der hier 02:34.040 --> 02:39.020 Teildozent, genauso wie Tamim, müsst ihr euch an unser Sekretariat 02:39.020 --> 02:39.340 wenden. 02:39.480 --> 02:42.240 Die können sich dann darum kümmern, also ob ihr Scheine braucht oder 02:42.240 --> 02:43.700 ob irgendwas im System kaputt ist. 02:43.760 --> 02:47.420 Das können die machen, also bei Problemen an unser Sekretariat wenden. 02:49.240 --> 02:52.080 Genau, und am besten meldet ihr euch auch jetzt schon an. 02:52.080 --> 02:54.800 Wir haben immer Leute, die kommen dann am 5.3. 02:54.940 --> 02:57.080 und sagen, ich habe total verplant, mich anzumelden. 02:58.040 --> 03:01.920 Aber weil die Klausur so groß ist, also wie gesagt, wir nehmen an, 03:02.020 --> 03:05.120 ungefähr 500 Teilnehmer werden kommen, vielleicht mehr, müssen wir 03:05.120 --> 03:06.240 schon am 4.3. 03:06.460 --> 03:08.100 dann anfangen mit der Vorbereitung. 03:08.320 --> 03:12.040 Also wir fangen dann schon an, die Hörsäle zu machen, die Klausuren in 03:12.040 --> 03:13.500 Druck zu geben, wie viele das sind. 03:14.120 --> 03:16.920 Und da können wir dann nicht 50 Leute, die dann nachträglich noch 03:16.920 --> 03:17.900 kommen, irgendwo unterbringen. 03:18.140 --> 03:20.520 Da ist dann einfach kein Platz für, weil wir auch nicht wissen, wer 03:20.520 --> 03:21.120 sich wann meldet. 03:21.120 --> 03:23.720 Also wie gesagt, ihr könnt euch jetzt schon anmelden, ihr könnt euch 03:23.720 --> 03:26.820 auch bis eine Minute vor der Klausur abmelden. 03:27.320 --> 03:31.780 Also online geht es, glaube ich, nur bis Mitternacht, aber ihr könnt 03:31.780 --> 03:33.240 auch vor Ort kommen und euch abmelden. 03:33.360 --> 03:36.400 Also abmelden geht immer, aber wenn ihr teilnehmen wollt, dann meldet 03:36.400 --> 03:39.220 euch am besten jetzt schon an, dann kommt ihr nicht in dieses Problem, 03:39.340 --> 03:42.540 dass ihr vergessen habt, euch anzumelden und wir euch dann nicht mehr 03:42.540 --> 03:44.380 helfen können, weil alles schon verplant ist. 03:45.620 --> 03:46.140 Genau. 03:48.080 --> 03:50.260 Das nur als Erinnerung. 03:50.520 --> 03:53.080 Ich meine, ich gehe davon aus, dass die 100 Leute, die hier sind, dann 03:53.080 --> 03:55.680 auch nicht das Problem sind, aber naja. 03:56.620 --> 03:57.140 Genau. 03:59.140 --> 04:01.220 Gut, dann kommen wir zur eigentlichen Übung. 04:03.440 --> 04:07.660 Und zwar der erste Teil der Übung ist einfach nur ein bisschen nochmal 04:07.660 --> 04:11.340 die symbolische Planung, die wir mit Strips kennengelernt haben. 04:12.240 --> 04:17.300 An einem Beispiel mal durchzugehen und dann machen wir einmal eine 04:17.300 --> 04:20.420 Implementierung mit Simox. 04:20.500 --> 04:28.120 Also Simox ist unser Robotik-Framework in C++ und implementieren 04:28.120 --> 04:33.320 einmal Astern und ERT, damit ihr mal gesehen habt, wie wir die meisten 04:33.320 --> 04:35.060 Sachen in C++ implementieren. 04:35.940 --> 04:42.880 Ja, also die erste Aufgabe war symbolische Planung, in dem ein 04:42.880 --> 04:44.700 Initialzustand gegeben war. 04:44.760 --> 04:48.660 Das haben wir kennengelernt, das ist diese Prädikatenlogik, in dieser 04:48.660 --> 04:49.980 Prädikatenlogik definiert. 04:51.780 --> 04:57.280 Ein Zustand beschreibt ja immer nur die positiven Prädikate und 04:57.280 --> 05:02.680 aufgrund der Closed-World-Assumption oder der Annahme für die 05:02.680 --> 05:03.440 geschlossene Welt 05:07.360 --> 05:10.100 wissen wir ja, dass alles andere falsch ist. 05:10.420 --> 05:12.960 Also deshalb müssen wir hier nicht hinschreiben, was alles falsch ist. 05:21.280 --> 05:27.340 Genau, also wir haben hier bestimmte Objekte, Tisch, Ofen, die sind 05:27.340 --> 05:30.000 Orte, dann haben wir einen Gripper, wir haben einen Roboter, wir haben 05:30.000 --> 05:34.240 eine Pfanne und die Pfanne ist auf dem Tisch und so weiter, ist hier 05:34.240 --> 05:34.620 beschrieben. 05:35.060 --> 05:38.980 Und die Pfanne soll nachher auf dem Ofen sein, im Stove, deshalb S. 05:38.980 --> 05:44.060 Und wenn wir den Zielzustand beschreiben, oder die Zielzustandsmenge 05:44.060 --> 05:48.240 eher gesagt, dann geben wir immer nur ja den Teil an, der wahr sein 05:48.240 --> 05:48.520 muss. 05:49.020 --> 05:56.260 Und im Ziel ist uns bis auf den Teil, den wir definieren, ist uns 05:56.260 --> 05:57.140 alles andere egal. 05:57.580 --> 06:00.520 Also das kann wahr oder falsch sein, ist nicht wichtig. 06:01.800 --> 06:02.280 Genau. 06:05.460 --> 06:08.760 Und das ist unser Initialzustand und Zielzustand. 06:09.300 --> 06:12.680 Jetzt gibt es ein paar Aktionen, die der Roboter durchführen kann. 06:13.120 --> 06:16.760 Die erste Aktion ist eine Pickup-Aktion, also der Agent A nimmt das 06:16.760 --> 06:19.280 Objekt O mit der Hand H von Ort L. 06:21.000 --> 06:24.640 Da gibt es gewisse Vorbedingungen, die dafür gelten müssen, damit man 06:24.640 --> 06:26.140 das Objekt davon nehmen kann. 06:26.300 --> 06:29.260 Also es muss sich da befinden und der Agent muss sich auch dort 06:29.260 --> 06:29.700 befinden. 06:31.220 --> 06:35.080 Das sind hier diese Preconditions. 06:35.940 --> 06:41.720 Und die anderen Preconditions, also diese hier zum Beispiel, die 06:41.720 --> 06:50.480 Location und die Hand und der Agent, das ist eher sowas wie eine 06:53.000 --> 06:53.300 Typprüfung. 06:55.800 --> 06:59.380 Also es gibt ja in der Strips-Logik keine Typen, das ist alles nicht 06:59.380 --> 06:59.880 typisiert. 06:59.880 --> 07:03.960 Aber indem man eben solche Prädikate einführt wie A ist ein Agent oder 07:03.960 --> 07:08.160 H ist eine Hand, kann man eine gewisse Typisierung einbringen hier. 07:08.580 --> 07:11.420 Und das stellt eben, die ersten Prädikate stellen sicher, dass das, 07:11.480 --> 07:14.440 was man da reingibt, auch vom richtigen Typ ist, wenn man so will. 07:15.180 --> 07:15.660 Genau. 07:16.360 --> 07:20.280 Die Effekte sind hier einmal ein bisschen anders hingestellt. 07:20.380 --> 07:23.940 Wir haben das in der Vorlesung dann ein bisschen formeller gemacht. 07:23.940 --> 07:29.580 Und die negativen Prädikate, also die Effekte, die Prädikate, die 07:29.580 --> 07:34.580 gelöscht werden, die haben wir in so eine Delete-List geschrieben. 07:35.480 --> 07:39.160 Und die Prädikate, die hinzukommen, haben wir in so eine Add-List 07:39.160 --> 07:39.620 geschrieben. 07:40.880 --> 07:44.320 Das ist dann schon sehr nah an der Implementierung. 07:44.920 --> 07:48.060 Oft findet man aber auch so eine Schreibweise, also in der eben die 07:48.060 --> 07:50.820 negativen Prädikate und die positiven einfach aufgelistet werden. 07:51.880 --> 07:52.320 Genau. 07:54.600 --> 07:55.040 Ja. 07:56.360 --> 07:59.120 Dann kann der Agent als zweite Aktion noch ein Objekt abstellen. 07:59.480 --> 08:01.500 Also er kann eins aufheben und eins abstellen. 08:01.680 --> 08:04.220 Agent A platziert Objekt O mit Hand H auf Ort L. 08:06.540 --> 08:07.420 Ähnliche Bedingungen. 08:08.320 --> 08:09.700 Und der Roboter kann sich auch bewegen. 08:11.600 --> 08:13.960 Agent A bewegt sich von Ort L zu Ort M. 08:15.060 --> 08:23.760 Und das hat eben den Effekt, dass sich der Agent von dem Ort L zu dem 08:23.760 --> 08:24.720 Ort M bewegt. 08:26.320 --> 08:27.180 Genau. 08:28.660 --> 08:35.800 Die Definition so hat aber noch ein Problem, zumindest ein technisches 08:35.800 --> 08:39.400 Problem, das sich logisch widerspricht. 08:39.400 --> 08:46.460 Wenn ich jetzt zum Beispiel den Befehl bewege, meinen Roboter vom 08:46.460 --> 08:52.180 Tisch zum Tisch ausführe, der Effekt von dieser Aktion wäre ja, dass 08:52.180 --> 08:58.200 sich der Roboter nicht mehr am Tisch befindet und dass sich der 08:58.200 --> 09:01.200 Roboter danach am Tisch befindet. 09:01.920 --> 09:06.060 Das ist natürlich logisch, kann das nicht existieren, das ist ein 09:06.060 --> 09:06.620 Widerspruch. 09:12.420 --> 09:17.980 Das heißt, wir können es eigentlich nicht zulassen, dass Startort und 09:17.980 --> 09:19.100 Zielort identisch sind. 09:20.280 --> 09:24.100 Das ist allerdings in der Prädikatenlogik gar nicht so einfach zu 09:24.100 --> 09:24.660 definieren. 09:24.980 --> 09:27.300 Es ist einfach zu definieren, aber aufwendig. 09:29.040 --> 09:32.100 Aber um das einfach zu halten, nehmen wir einfach eine vereinfachte 09:32.100 --> 09:38.280 Annahme an, dass bei diesem Befehl L und M unterschiedlich sind, um 09:38.280 --> 09:41.120 uns dann ein bisschen Definitionen zu sparen. 09:42.380 --> 09:42.700 Genau. 09:43.140 --> 09:43.340 Gut. 09:44.380 --> 09:47.540 Also das ist unsere Planungsdomäne, in der wir agieren. 09:48.160 --> 09:52.500 Und wir sollen jetzt die kürzeste Aktionssequenz angeben, um vom 09:52.500 --> 09:54.640 initialen Weltzustand in den Zielzustand zu kommen. 09:56.020 --> 10:04.860 Und in der Vorlesung selbst haben wir dazu die Breitensuche einmal 10:04.860 --> 10:05.520 kennengelernt. 10:05.520 --> 10:07.780 Das ist aber relativ aufwendig. 10:08.620 --> 10:11.580 Das haben vielleicht einige von euch dann mal ausprobiert für diesen 10:11.580 --> 10:16.480 Fall, da man bis Ebene 4 dann nachher runter muss. 10:17.160 --> 10:21.160 Und wir machen das jetzt eher so ein bisschen einfach freihand. 10:21.260 --> 10:24.220 Die Aufgabe ist so einfach gestellt, dass im Grunde jede Aktion, die 10:24.220 --> 10:28.160 man ausführen muss, führt einen näher zum Ziel und dann ist man bald 10:28.160 --> 10:28.440 da. 10:31.020 --> 10:36.540 Wie das Problem hier aussieht, ist im Grunde, man hat diesen Ofen hier 10:36.540 --> 10:45.020 und dann hat man seinen Roboter. 10:46.600 --> 10:50.900 Der Roboter ist gerade am Ofen, das ist ja diese Bedingung, und man 10:50.900 --> 10:52.340 hat irgendwo anders einen Tisch stehen. 10:57.970 --> 10:59.190 Und auf dem Tisch ist die Pfanne. 10:59.730 --> 11:02.630 Und was der Roboter eben jetzt machen muss, um sein Ziel zu erreichen, 11:03.270 --> 11:05.250 ist super einfach. 11:05.250 --> 11:09.970 Der Roboter muss einmal rüberlaufen, die Pfanne nehmen und dann mit 11:09.970 --> 11:14.490 der Pfanne zurücklaufen und die Pfanne wieder abstellen, also 4 11:14.490 --> 11:15.430 Aktionen durchführen. 11:15.910 --> 11:18.550 Das ist also kein aufwendiges Planungsproblem. 11:19.970 --> 11:24.710 Und die 4 Aktionen rüberfahren, aufnehmen, zurückfahren und abstellen, 11:25.270 --> 11:30.210 wenden wir jetzt auf den Initialzustand an und schauen dann, dass wir 11:30.210 --> 11:31.970 am Ende wirklich im Zielzustand ankommen. 11:34.030 --> 11:34.470 Genau. 11:35.430 --> 11:39.410 Also das Erste, was wir machen wollen, ist, dass sich der Roboter vom 11:39.410 --> 11:40.710 Ofen zum Tisch bewegt. 11:42.750 --> 11:48.070 Und wenn wir eine Aktion anwenden wollen auf einen Zustand, dann 11:48.070 --> 11:50.190 müssen wir erst schauen, dürfen wir das überhaupt? 11:50.410 --> 11:53.510 Also die Vorbedingungen prüfen, das ist immer der erste Schritt. 11:56.390 --> 12:00.970 Und hier gibt es, wie gesagt, so zwei Arten von Prädikaten, das liegt 12:00.970 --> 12:02.210 einfach an der Planungsdomäne. 12:03.810 --> 12:07.830 Ich muss erstmal diese Typprüfung machen, also ist er überhaupt ein 12:07.830 --> 12:10.350 Agent, sind S und T Orte? 12:11.690 --> 12:14.830 Das sind so Prädikate, die sich auch nie ändern. 12:14.830 --> 12:19.930 Und dann muss ich natürlich prüfen, ob sich mein Roboter auch an dem 12:19.930 --> 12:21.750 Ort befindet, an meinem Startort. 12:22.070 --> 12:24.570 Sonst kann ich den Move Befehl nicht anwenden, die Move Aktion. 12:26.330 --> 12:26.850 Genau. 12:28.410 --> 12:34.210 Und ich schaue also in meinem Zustand, finde ich die Vorbedingungen 12:34.210 --> 12:36.470 und ja, alle Vorbedingungen sind hier erfüllt. 12:37.870 --> 12:40.750 Wenn alle Vorbedingungen erfüllt sind, kann ich dann die Aktion 12:40.750 --> 12:42.190 ausführen und die Effekte anwenden. 12:43.990 --> 12:51.570 Und da gibt es eben diese zwei Kategorien, einmal das Delete, wenn ich 12:51.570 --> 12:55.190 hier ein negatives Prädikat habe, also not at RS. 12:55.690 --> 12:59.770 Das heißt, ich lösche diese Eigenschaft, dieses Prädikat aus meinem 12:59.770 --> 13:06.610 Zustandsbeschreibung und ich habe Prädikate, die hinzugefügt werden in 13:06.610 --> 13:07.490 meinen Weltzustand. 13:08.490 --> 13:08.890 Genau. 13:09.270 --> 13:11.910 Und damit habe ich einen neuen Zustand, mit dem ich dann 13:11.910 --> 13:12.870 weiterarbeiten kann. 13:15.230 --> 13:15.630 Genau. 13:16.550 --> 13:23.950 Ich bin also jetzt zu dem Ofen hingegangen, zum Tisch hingegangen, um 13:23.950 --> 13:26.170 jetzt vom Tisch die Pfanne zu nehmen. 13:27.170 --> 13:31.290 Und hier ist es jetzt auch wieder so, nur diesmal ignorieren wir mal 13:31.290 --> 13:33.830 diese, die sind jetzt hier grau hinterlegt, diese statischen 13:33.830 --> 13:39.130 Typprüfungen, die sind bei uns immer erfüllt und schauen uns die 13:39.130 --> 13:39.610 anderen an. 13:39.930 --> 13:43.570 Also ich kann nur was hochnehmen, wenn mein Gripper leer ist und sich 13:43.570 --> 13:46.470 das Objekt an dem Ort befindet, an dem ich auch gerade stehe. 13:47.370 --> 13:54.510 Das ist jetzt hier erfüllt, in der hier farblich hervorgeheben, wo man 13:54.510 --> 13:56.610 sieht, dass die Vorbedingungen für die Aktion erfüllt sind. 13:58.010 --> 14:01.910 Und dann müssen wir wieder schauen, okay, es gibt wieder zwei 14:01.910 --> 14:08.510 Prädikate, die gelöscht werden und ein Prädikat, das hinzugefügt wird. 14:12.910 --> 14:13.350 Genau. 14:13.350 --> 14:16.530 Dann habe ich jetzt meine Pfanne in der Hand und muss jetzt 14:16.530 --> 14:18.350 zurückfahren vom Tisch zum Ofen. 14:19.390 --> 14:22.430 Das ist jetzt wieder nichts Besonderes, das haben wir schon mal 14:22.430 --> 14:22.650 gemacht. 14:22.650 --> 14:26.030 Wir müssen wieder schauen, okay, sind die Vorbedingungen erfüllt? 14:26.330 --> 14:28.450 Ich bin am Tisch, also kann ich zum Ofen fahren. 14:29.650 --> 14:30.230 Was passiert? 14:30.770 --> 14:33.710 Okay, ich befinde mich nicht mehr am Tisch, sondern jetzt am Ofen. 14:34.670 --> 14:35.150 Okay. 14:36.310 --> 14:40.570 Und als letzte Aktion muss ich dann die Pfanne nur noch abstellen. 14:41.990 --> 14:43.430 Wieder dasselbe Vorgehen. 14:44.350 --> 14:47.310 Erst alle Vorbedingungen prüfen, sind sie in meinem aktuellen Zustand 14:47.310 --> 14:47.710 erfüllt? 14:47.710 --> 14:48.930 Das sind sie. 14:49.710 --> 14:59.350 Dann kann ich meine Effekte anwenden und dann prüfe ich, was sie 14:59.350 --> 15:03.250 natürlich eigentlich in jedem Schritt machen, ist meine Zielbedingung 15:03.250 --> 15:03.690 erfüllt? 15:04.810 --> 15:09.350 Wir sehen hier, die Zielbedingung ist erfüllt und alle anderen 15:09.350 --> 15:10.870 Prädikate sind uns ja egal. 15:10.870 --> 15:14.550 Es geht ja nur darum, dass die Submenge an Prädikaten, die unsere 15:14.550 --> 15:17.070 Zielzustandsmenge beschreiben, erfüllt sind. 15:17.370 --> 15:18.250 Dann sind wir fertig. 15:19.630 --> 15:19.990 Genau. 15:20.410 --> 15:22.870 Und dann haben wir hier eine Aktionssequenz von vier Aktionen. 15:24.890 --> 15:30.470 Jetzt kann man natürlich berechtigterweise die Frage stellen, ist das 15:30.470 --> 15:30.930 minimal? 15:31.070 --> 15:33.250 Also nichts von dem, was wir jetzt gemacht haben, um diese 15:33.250 --> 15:37.530 Aktionssequenz herzuleiten, beweist, dass diese Aktionssequenz minimal 15:37.530 --> 15:37.810 ist. 15:38.930 --> 15:42.210 Was man dafür eigentlich dann machen würde, ist das, was wir in der 15:42.210 --> 15:43.290 Vorlesung gemacht haben. 15:45.690 --> 15:46.690 Eine Breitensuche. 15:46.810 --> 15:49.850 Eine Breitensuche geht ja jede Ebene durch. 15:50.190 --> 15:52.790 Und in der ersten Ebene, in der wir eine Lösung finden, wissen wir 15:52.790 --> 15:58.130 dann, dass das die kürzeste Aktionssequenz ist, weil wir sonst auf 15:58.130 --> 16:00.830 einer höheren Ebene schon den Zielzustand erreicht hätten müssen. 16:01.530 --> 16:02.050 Genau. 16:08.760 --> 16:11.820 Und wie gesagt, das könnt ihr euch ja vielleicht anschauen, wenn ihr 16:11.820 --> 16:15.760 die Aufgabe mal in der Breitensuche macht und dann den Graph aufbaut, 16:15.820 --> 16:20.180 wie würde der dann hier aussehen und wann findet man dann die Lösung. 16:21.280 --> 16:21.800 Genau. 16:24.380 --> 16:30.280 Dann haben wir noch ein paar mehr so Handhabungsaufgaben. 16:30.280 --> 16:32.960 Also die kommen manchmal vor, habt ihr vielleicht schon in der 16:32.960 --> 16:36.220 Klausurvorbereitung gesehen, dass man manchmal eigene 16:36.220 --> 16:40.080 Planungsoperatoren erstellen soll, auf Basis von bestehenden 16:40.080 --> 16:40.380 Operationen. 16:41.340 --> 16:42.400 Das ist hier Aufgabe 2. 16:43.100 --> 16:46.540 Man soll im Grunde Move und Pickup kombinieren, also sich irgendwo 16:46.540 --> 16:48.500 hinbewegen und dann ein Objekt dort hochnehmen. 16:51.800 --> 16:56.260 Und dafür eben die Vorbedingungen und Effekte definieren, um dann eben 16:56.260 --> 16:59.640 zu zeigen, dass man weiß, wie so die Stripsnotation funktioniert. 17:00.420 --> 17:01.900 Im Grunde eine kleine Aufgabe. 17:03.340 --> 17:03.860 Genau. 17:07.080 --> 17:10.320 Und man hat in der Klausur natürlich dann gegeben die Move und Pickup 17:10.320 --> 17:13.000 -Aktionen und muss dann die eben zusammen kombinieren. 17:17.000 --> 17:17.480 Genau. 17:17.480 --> 17:20.040 Und wenn wir jetzt zum Beispiel die Vorbedingungen für die Move und 17:20.040 --> 17:23.080 Pickup -Aktionen hinschreiben wollen, dann müssen wir erstmal alle 17:23.080 --> 17:26.220 diese Typisierungsprüfungen machen. 17:27.000 --> 17:28.880 Also zum Beispiel A ist ein Agent, 17:32.260 --> 17:33.200 A ist eine Hand, 17:37.740 --> 17:39.940 L ist ein Ort und M ist ein Ort. 17:42.900 --> 17:43.420 Genau. 17:44.800 --> 17:49.520 Und jetzt müssen wir natürlich gucken, was muss alles erfüllt sein, 17:49.640 --> 17:53.760 also von den veränderbaren Prädikaten, damit ich diese Aktion 17:53.760 --> 17:54.500 ausführen kann. 17:55.240 --> 18:04.770 Und damit ich mich von L nach M bewegen kann, muss ich am Anfang ja an 18:04.770 --> 18:05.710 dem Ort L stehen. 18:07.130 --> 18:11.710 Und damit ich dann, wenn ich am Ort M bin, auch das Objekt greifen 18:11.710 --> 18:14.050 kann, muss meine Hand leer sein 18:18.110 --> 18:24.630 und das Objekt muss sich auch an dem Ort M befinden, sonst kann ich es 18:24.630 --> 18:25.330 nicht hochnehmen. 18:27.990 --> 18:28.570 Genau. 18:30.670 --> 18:34.070 Hoffen wir, dass das die Vorbedingungen sind. 18:34.830 --> 18:35.370 Genau. 18:35.790 --> 18:39.730 Also wie gesagt, natürlich hat diese Aktion wieder das Problem, dass 18:39.730 --> 18:43.970 wenn L und M gleich sind, dass es dann nicht funktioniert. 18:44.250 --> 18:49.470 Aber wie gesagt, das brauchen wir nicht explizit beachten. 18:49.770 --> 18:50.790 Das ist so ein Sonderfall. 18:52.590 --> 18:53.130 Genau. 18:54.050 --> 18:54.230 Gut. 18:54.530 --> 18:55.950 Was hat diese Aktion für Effekte? 18:58.370 --> 18:58.850 Gut. 18:59.150 --> 19:02.630 Ich habe mich von A nach B bewegt, oder von L nach M eher gesagt. 19:04.210 --> 19:10.430 Das heißt, mein Roboter ist nicht mehr am Ort L, sondern stattdessen 19:10.430 --> 19:12.130 hat er sich nach M hin bewegt. 19:13.430 --> 19:20.790 Und gleichzeitig ist meine Hand auch nicht mehr leer. 19:20.790 --> 19:22.990 Ich habe ja jetzt das Objekt in der Hand. 19:25.190 --> 19:34.580 Das Objekt befindet sich nicht mehr auf dem Ort M, sondern, wie 19:34.580 --> 19:39.180 gesagt, stattdessen in der Hand des Roboters. 19:41.700 --> 19:42.180 Genau. 19:42.740 --> 19:47.280 Und was hier natürlich so eine kleine Sache ist, die man beachten 19:47.280 --> 19:51.120 muss, also man bekommt, wie gesagt, die Move- und Pickup-Aktion kennen 19:51.120 --> 19:52.840 wir ja schon aus dem ersten Aufgabenteil. 19:52.840 --> 19:57.080 Was natürlich nicht funktioniert, ist einfach die Vorbedingungen von 19:57.080 --> 20:01.040 Move und Pickup zusammen zu kopieren und die Effekte von Move und 20:01.040 --> 20:06.400 Pickup zusammen zu kopieren, weil ja gewisse Vorbedingungen von der 20:06.400 --> 20:09.620 zweiten Aktion können ja schon teilweise erfüllt werden durch die 20:09.620 --> 20:10.200 erste Aktion. 20:10.920 --> 20:14.620 Also zum Beispiel Pickup hat ja die Vorbedingung, dass sich der 20:14.620 --> 20:19.040 Roboter an dem Ort M befindet, sonst kann er das Objekt nicht 20:19.040 --> 20:19.520 hochheben. 20:19.520 --> 20:23.640 Aber diese Vorbedingung wird ja automatisch erfüllt durch das 20:23.640 --> 20:24.200 Hinbewegen. 20:24.800 --> 20:26.400 Das heißt, das muss man hier beachten. 20:27.700 --> 20:31.260 Das ist nicht einfach nur Copy-Paste von Vorbedingungen und Effekten, 20:31.660 --> 20:34.020 sondern ist eine Verkettung der Aktion. 20:35.700 --> 20:40.980 Und dann haben wir nochmal so, auch wieder sind alles so 20:40.980 --> 20:46.780 Übungsaufgaben, um sich mit diesem Strips-Konzept auseinanderzusetzen 20:46.780 --> 20:48.080 und der symbolischen Planung. 20:48.080 --> 20:53.020 Jetzt soll man mit dem gebauten Operator, den soll man mal ausführen 20:53.020 --> 20:56.100 und danach den Weltzustand angeben. 20:56.760 --> 21:00.800 Also wir befinden uns in diesem Zustand, dann machen wir Move und 21:00.800 --> 21:09.480 Pickup und dann haben wir irgendeinen neuen Weltzustand. 21:14.800 --> 21:17.620 Und wir sollen jetzt sagen, wie sieht der aus? 21:21.460 --> 21:23.540 Und das ist jetzt eigentlich nur eingepackt. 21:23.620 --> 21:26.280 Im Grunde ist es das, was wir schon im ersten Aufgabenteil die ganze 21:26.280 --> 21:27.180 Zeit gemacht haben. 21:27.680 --> 21:30.380 Wir müssen erstmal gucken, ist das eine Fangfrage? 21:30.620 --> 21:33.120 Also kann ich die Aktion überhaupt ausführen? 21:33.240 --> 21:35.440 Wenn ich sie nicht ausführen kann, macht die Frage keinen Sinn. 21:35.740 --> 21:37.040 Was ist der Weltzustand danach? 21:39.260 --> 21:42.660 Das ist hier in diesem Fall erfüllt, also die Vorbedingungen gelten. 21:42.920 --> 21:44.160 Ich darf die Aktion ausführen. 21:45.520 --> 21:50.560 Dann muss ich wie gesagt wieder die negativen Prädikate löschen und 21:50.560 --> 21:52.480 die positiven Prädikate hinzufügen. 21:54.580 --> 21:56.660 Und dann bin ich eigentlich schon fertig. 21:58.000 --> 22:02.420 Was hier aber wichtig ist, wenn man die Frage stellt, was ist der 22:02.420 --> 22:08.080 Weltzustand nach der Aktion, dann reicht es nicht, hinzuschreiben, zum 22:08.080 --> 22:12.980 Beispiel nur hier so ein Delta vom Weltzustand. 22:16.220 --> 22:18.700 Sondern die Frage war ja, was ist der gesamte Weltzustand? 22:18.720 --> 22:22.400 Und der gesamte Weltzustand enthält natürlich alle diese Eigenschaften 22:22.400 --> 22:24.940 noch, die vorher wahr waren und die nachher auch wahr waren. 22:25.060 --> 22:26.400 Also die sich gar nicht verändert haben. 22:28.060 --> 22:31.500 Wenn man sie nicht angeben würde, dann wäre ja aufgrund der Closed 22:31.500 --> 22:33.320 World Assumption, wären die ja alle falsch. 22:34.240 --> 22:37.120 Und das macht ja keinen Sinn, also der Tisch kann ja nicht aufhören, 22:37.220 --> 22:37.860 ein Tisch zu sein. 22:38.160 --> 22:42.520 Also wenn man ihn schreddert vielleicht, aber das ist ja hier nicht in 22:42.520 --> 22:45.320 unserer Planungsdomäne ist sowas nicht vorgesehen, dass Objekte 22:45.320 --> 22:46.440 vernichtet werden oder so. 22:47.480 --> 22:51.200 Genau, deshalb muss man da immer, wenn nach dem Weltzustand gefragt 22:51.200 --> 22:53.480 ist, alle Prädikate angeben, die wahr sind. 22:53.580 --> 22:56.000 Auch die, die sich nicht verändert haben durch eine Aktion. 22:57.920 --> 22:58.520 Genau. 23:02.140 --> 23:07.700 Ja, also das ist eigentlich so der Strips-Teil hier, der nur nochmal 23:07.700 --> 23:13.260 so ein bisschen das Thema im Detail vorstellen sollte. 23:18.030 --> 23:18.630 Genau. 23:22.370 --> 23:30.170 Und dann haben wir jetzt den tatsächlichen Programmierteil, war ja die 23:30.170 --> 23:35.730 Vorlesung zum Programmieren, allerdings auf einer höheren Ebene. 23:36.710 --> 23:40.270 Wir machen jetzt quasi die Details, was muss ich jetzt machen, damit 23:40.270 --> 23:44.050 ich wirklich mal zum Beispiel einen Bewegungsplanungsalgorithmus für 23:44.050 --> 23:47.690 einen mobilen Roboter schreiben, testen und ausführen kann. 23:49.810 --> 23:52.870 Da gehen wir jetzt so vor, das machen wir natürlich nicht, das habe 23:52.870 --> 23:56.370 ich hier jetzt schon auf dem Windows 7 PC gemacht, aber wir haben hier 23:56.370 --> 23:59.470 natürlich noch die Anleitung. 24:00.890 --> 24:05.150 Das CMOGS Framework ist so ein Robotik-Toolkit, mit dem man 24:05.150 --> 24:08.110 Bewegungsplanung greifen, Robotermodellierung machen kann. 24:09.530 --> 24:12.470 Also wir setzen das immer nur unter Ubuntu ein, deshalb funktioniert 24:12.470 --> 24:13.210 es da am besten. 24:14.330 --> 24:17.430 Alles andere kriegt man wahrscheinlich auch irgendwie zum Laufen. 24:18.890 --> 24:21.710 Allerdings kann man das Ubuntu sicher auch unter Windows 10 24:21.710 --> 24:23.930 installieren und so machen wir das jetzt auch hier in der Übung. 24:24.550 --> 24:27.110 Also wenn ihr daran Interesse habt, dann könnt ihr es auch unter 24:27.110 --> 24:31.570 Windows benutzen und kann man so ein Subsystem für Linux aktivieren in 24:31.570 --> 24:32.190 Windows 10. 24:33.650 --> 24:36.170 Sich dann einfach im Store Ubuntu runterladen. 24:36.470 --> 24:39.070 Ich finde es lustig, dass sie auch hinschreiben, es ist freigegeben ab 24:39.070 --> 24:39.550 null Jahren. 24:39.970 --> 24:42.290 Also ich wüsste nicht, was ein dreijähriges Kind damit anfangen soll, 24:42.410 --> 24:43.530 aber gut. 24:45.150 --> 24:46.330 Ist deren Storedesign. 24:47.450 --> 24:50.910 Dann braucht man noch so einen X-Server, also den braucht man nicht, 24:50.990 --> 24:54.850 aber wenn man das installiert, hat man nur die Kommandozeile von 24:54.850 --> 24:55.330 Ubuntu. 24:55.570 --> 24:59.770 Und hiermit kann man dann auch GUI-Programme starten mit grafischen 24:59.770 --> 25:00.330 Oberflächen. 25:02.970 --> 25:04.770 Genau, man muss noch einen Nutzer anlegen. 25:05.510 --> 25:08.170 Dann sollte man das System natürlich aktualisieren und diesen X-Server 25:08.170 --> 25:08.370 konfigurieren. 25:10.950 --> 25:14.190 Da kann man Xemox installieren, da gibt es eine Installationsanleitung 25:14.190 --> 25:16.150 zu, das ist hier aber nochmal gecopy-pasted. 25:16.390 --> 25:19.030 Das sind im Grunde zwei Pakete, muss man selber bauen. 25:19.630 --> 25:22.650 Bullet, das ist die Physik-Simulation und Xemox. 25:26.290 --> 25:30.290 Und dann kann man eben diesen X-Server starten und Beispiele aus Xemox 25:30.290 --> 25:30.790 ausführen. 25:31.510 --> 25:33.650 Das zeige ich dann gleich mal hier auf dem... 25:35.010 --> 25:37.190 Da kann man sich auch ein paar Beispiele anschauen, wenn man mal 25:37.190 --> 25:39.710 wissen will, wie so andere Dinge funktionieren, die wir in der 25:39.710 --> 25:40.690 Vorlesung gemacht haben. 25:40.790 --> 25:42.730 Da gibt es auch Dinge zum Greifen und so weiter. 25:43.650 --> 25:45.030 Wir machen ja hier nur Bewegungsplanung. 25:47.230 --> 25:52.390 Genau, also wenn wir dann das System aufgesetzt haben, dann können wir 25:52.390 --> 25:54.150 eben diese Skeleton-Datei runterladen. 25:54.250 --> 25:57.770 Das ist hier so gedacht, dass man nur den Teil programmiert, der für 25:57.770 --> 25:59.710 Astern notwendig ist und für ERT. 25:59.890 --> 26:01.430 Deshalb ist alles drumherum schon gegeben. 26:02.470 --> 26:04.790 Das sind so ähnliche Aufgaben, die wir zum Beispiel in unseren 26:04.790 --> 26:05.610 Praktika machen. 26:07.130 --> 26:09.590 Und man kann sich natürlich auch anschauen, wie das gesamte Projekt 26:09.590 --> 26:11.430 aufgebaut ist, wenn einen das interessiert. 26:12.350 --> 26:12.810 Genau. 26:14.990 --> 26:18.230 Und in der Projektstruktur gibt es eben eine Datei, das ist die Datei, 26:18.270 --> 26:19.150 in der wir jetzt arbeiten. 26:19.710 --> 26:22.970 Das sind natürlich andere Dateien, die dann die Fenster aufbauen und 26:22.970 --> 26:24.730 die Sachen rendern und so weiter. 26:25.350 --> 26:27.630 Und dann gibt es eine ausführbare Datei, mit der wir das Programm 26:27.630 --> 26:28.250 starten können. 26:28.610 --> 26:30.250 Also relativ einfach gehalten. 26:31.910 --> 26:36.090 Und ja, das machen wir dann einfach mal für die Asternaufgabe. 26:38.830 --> 26:44.090 Aber vielleicht schauen wir uns erstmal in dem Simox-Programm... 26:45.310 --> 26:46.490 Was gibt es dort? 26:48.090 --> 26:52.770 Da gibt es zum Beispiel so eine Grasp-ERT-Demo, also die greifen- und 26:52.770 --> 26:55.150 ERT -Bewegungsplanung kombiniert. 26:58.250 --> 27:01.990 Die Auflösung hier ist so ein bisschen gruselig niedrig, aber das 27:01.990 --> 27:04.290 liegt an diesem X-Server unter Windows. 27:06.250 --> 27:10.590 Genau, also wir haben hier Arma 3 in Simulation. 27:12.570 --> 27:14.050 Er hat hier zwei Objekte vor sich. 27:14.490 --> 27:15.910 Ich glaube, er soll die Dose greifen. 27:17.190 --> 27:22.590 Und was der Code hier macht, ist erstmal einen Griff hierfür, für 27:22.590 --> 27:23.330 dieses Objekt auszuwählen. 27:24.330 --> 27:27.430 Und dann ein ERT dahin zu planen. 27:27.650 --> 27:28.570 Oh, der war jetzt recht kurz. 27:29.850 --> 27:32.350 Hier sieht man jetzt, kann man jetzt die Trajektorie abfahren. 27:33.730 --> 27:36.450 Man sieht so ein bisschen die ERT-Struktur, dass er nicht direkt 27:36.450 --> 27:36.950 hinfährt. 27:37.530 --> 27:42.090 Dafür gibt es dann zum Beispiel so Nachbearbeitungs-Algorithmen, Post 27:42.090 --> 27:42.650 -Processing. 27:43.490 --> 27:49.610 Wo er dann eben schaut, ob er die durch die ERT zufällig, ist ja ein 27:49.610 --> 27:53.150 randomisierter Algorithmus, probabilistischer Algorithmus, ein 27:53.150 --> 27:54.630 bisschen optimieren kann, glätten kann. 27:56.150 --> 27:58.330 Wenn ich das mal nochmal ausführe. 27:58.850 --> 28:01.950 Manchmal dreht der ERT nämlich komplett durch, das ist immer ganz 28:01.950 --> 28:02.790 witzig anzuschauen. 28:03.190 --> 28:10.070 Hier kann man jetzt zum Beispiel sehen, wo der ERT eine ganz kuriose 28:10.070 --> 28:11.150 Lösung gefunden hat. 28:11.390 --> 28:14.770 Ist natürlich gültig, aber ich glaube, man will nicht sehen, was mit 28:14.770 --> 28:17.330 dem Roboter passiert, wenn er versucht, das wirklich auszuführen. 28:19.030 --> 28:20.590 Genau, schauen wir mal. 28:21.010 --> 28:27.270 Und die Post-Process-Lösung findet natürlich dann trotzdem über eine 28:27.270 --> 28:31.490 Shortcut -Analyse dann einen Weg, der sinnvoll auszuführen ist. 28:33.030 --> 28:33.710 Genau. 28:35.530 --> 28:38.430 Ja, und da gibt es in dem Simox ein paar Beispiele. 28:38.830 --> 28:41.570 Man kann auch relativ schnell dann die quasi kopieren und für sich 28:41.570 --> 28:43.750 anpassen, wenn man damit mal was machen möchte. 28:45.470 --> 28:50.750 Genau, aber zurück zu unserer Übung. 28:52.290 --> 28:52.850 Genau, 28:56.170 --> 28:58.750 ich habe hier eigentlich alles schon hingepackt. 28:59.750 --> 29:03.050 Das hier ist diese A-Starplanner-CPP, in der wir arbeiten werden. 29:03.390 --> 29:04.630 Ich öffne die mal schon mal. 29:05.150 --> 29:06.950 Sehr großer Code. 29:10.230 --> 29:12.690 Und dann muss ich das noch finden. 29:18.160 --> 29:25.740 Tatsächlich ist dieses Ubuntu unter Windows ziemlich nett, sonst 29:25.740 --> 29:28.580 müsste ich jetzt irgendwie neu booten oder einen anderen PC nehmen. 29:33.010 --> 29:35.230 Ist aber natürlich ein bisschen eingeschränkt, 29:38.400 --> 29:40.280 was man damit machen kann. 29:42.560 --> 29:43.040 Genau. 29:43.040 --> 29:46.420 Ich glaube, ich habe das Ganze hier schon mal gebaut, damit wir jetzt 29:46.420 --> 29:47.260 nicht warten müssen. 29:48.860 --> 29:52.300 Also das ist dieses Beispielprogramm. 29:52.600 --> 29:57.120 Die Idee ist, dass hier Arma von hier nach hier hin laufen soll und 29:57.120 --> 29:58.700 natürlich nicht gegen die Hindernisse kommt. 30:00.000 --> 30:02.540 Wir haben hier verschiedene Hindernisse, die man aufbauen kann. 30:02.780 --> 30:03.500 Was heißt verschiedene? 30:03.660 --> 30:04.040 Zwei Stück. 30:04.740 --> 30:07.140 Man kann hier so eine Falle aufbauen. 30:07.140 --> 30:09.580 Also hier passt er nicht durch und hier passt er nicht durch, wenn 30:09.580 --> 30:12.000 dann der Planungsalgorithmus erst mal versucht, hier hin zu kommen. 30:12.600 --> 30:14.000 Man muss dann lernen, außen rum zu gehen. 30:15.200 --> 30:18.820 Man kann auch ein leeres machen, um nur den Algorithmus mal zu sehen. 30:19.300 --> 30:19.660 Genau. 30:20.040 --> 30:23.920 Also das ist so diese Testumgebung, in der wir dann Bewegungsplanung 30:23.920 --> 30:25.540 für die mobile Plattform machen wollen. 30:32.220 --> 30:32.580 Gut. 30:34.220 --> 30:35.500 Ja, also das ist der Code. 30:35.500 --> 30:39.980 Natürlich muss man sich, bevor man jetzt irgendwie anfängt, müsste man 30:39.980 --> 30:42.240 sich zumindest so ein bisschen schlau machen, was passiert hier 30:42.240 --> 30:42.720 drumherum. 30:43.260 --> 30:46.440 Also hier ist so ein Teil markiert, in dem soll man jetzt Asteren 30:46.440 --> 30:46.940 programmieren. 30:47.320 --> 30:49.720 Aber wenn man nicht weiß, was drumherum ist, kann man natürlich auch 30:49.720 --> 30:50.540 nicht viel anfangen. 30:52.260 --> 30:55.140 Aber man sieht hier, das ist im Grunde die Hauptplanungsroutine. 30:55.860 --> 30:58.840 Die macht erst mal irgendwelche Gültigkeitsprüfungen, um zu schauen, 30:59.040 --> 31:01.060 ob ich überhaupt einen Roboter habe und so weiter. 31:03.860 --> 31:08.020 Dann holt sie sich das Kollisionsmodell, erstellt ein Grid und auf 31:08.020 --> 31:09.400 diesem Grid machen wir dann Asteren. 31:11.840 --> 31:15.820 Und wir sollen planen von einem Startpunkt zum Zielpunkt. 31:17.540 --> 31:20.840 Und Asteren kann ja nicht von beliebigen Positionen planen. 31:20.940 --> 31:25.820 Das heißt, es wird erst mal der nächste Knoten in dem Grid gefunden. 31:25.820 --> 31:31.100 Und dann haben wir hier unser Open Set, unser Closed Set. 31:32.640 --> 31:37.220 Wir haben hier so eine Map, im Grunde ein assoziativer Speicher dann 31:37.220 --> 31:44.400 für die akkumulierten Kosten g und für die dann zusammengerechten 31:44.400 --> 31:45.340 heuristischen Kosten. 31:47.740 --> 31:48.260 Genau. 31:49.540 --> 31:53.420 Und dann fangen wir erst mal so an, indem wir uns erinnern, wie denn 31:53.420 --> 31:56.080 nochmal Asteren funktioniert hat. 31:57.580 --> 32:00.940 Ist ja nicht der schwierigste Algorithmus, aber wir können es ja erst 32:00.940 --> 32:02.640 mal einfach als Kommentare hinschreiben. 32:03.160 --> 32:05.640 Erst mal müssen wir natürlich das Ganze initialisieren. 32:06.520 --> 32:11.140 Asteren fängt an, indem wir zuerst unseren Startknoten in das Open Set 32:11.140 --> 32:11.500 packen. 32:13.080 --> 32:16.260 Wir haben ein Closed Set, unser Closed Set ist zuerst leer. 32:19.760 --> 32:28.420 Dann setzen wir die akkumulierten Kosten von allen Knoten auf 32:28.420 --> 32:30.120 unendlich. 32:32.580 --> 32:38.140 Also für alle i von 1 bis k. 32:43.600 --> 32:48.480 Und dann setzen wir von unserem Startknoten, gibt es ja noch keine 32:48.480 --> 32:50.620 akkumulierten Kosten, die setzen wir alle auf 0. 32:53.280 --> 32:53.900 Genau. 32:54.960 --> 32:56.420 Dann haben wir eine Schleife. 32:58.220 --> 33:03.700 Solange unser Open Set nicht leer ist, also irgendwas da drin ist, 33:04.460 --> 33:05.160 machen wir was. 33:12.290 --> 33:13.290 Genau. 33:14.090 --> 33:17.530 Und das sind jetzt die Iterationsschritte von Asteren. 33:18.230 --> 33:26.330 Die laufen so ab, dass wir erst mal einen Knoten vi finden, den wir 33:26.330 --> 33:27.270 expandieren wollen. 33:30.830 --> 33:35.190 Und zwar so, dass 33:39.630 --> 33:44.350 vi kommt natürlich aus dem Open Set. 33:44.350 --> 33:53.530 Und was wir minimieren wollen, sind eben die Kosten f von vi. 33:53.710 --> 33:57.530 Die bestehen eben aus den akkumulierten Kosten und unserer Heuristik. 33:58.710 --> 34:02.550 Die Heuristik bestimmt ja, schätzt die Kosten, noch verbleibenden 34:02.550 --> 34:03.570 Kosten zum Ziel. 34:04.730 --> 34:05.530 Genau. 34:06.370 --> 34:10.210 Dann haben wir einen Knoten, den wir expandieren wollen. 34:12.710 --> 34:16.610 Jetzt müssen wir noch schauen, wenn dieser Knoten schon unser Ziel 34:16.610 --> 34:20.590 ist, dann sind wir im Prinzip fertig. 34:24.670 --> 34:26.890 Sobald wir unser Ziel expandieren, sind wir fertig. 34:27.850 --> 34:28.450 Genau. 34:29.430 --> 34:38.210 Wenn wir aber noch nicht fertig sind, dann entfernen 34:44.280 --> 34:47.860 wir unseren Knoten aus dem Open Set. 34:48.000 --> 34:49.820 Das ist ja der Knoten, den wir jetzt expandieren. 34:54.620 --> 34:59.680 Und wir fügen ihn zum Closed Set hinzu, damit wir fertig sind. 35:01.080 --> 35:01.800 Genau. 35:06.110 --> 35:12.650 Dann müssen wir noch die Nachbarn updaten, die Nachfolger. 35:18.410 --> 35:23.290 Weil es ja gegebenenfalls kürzere Wege geben könnte hierdurch, dass 35:23.290 --> 35:27.610 wir jetzt diesen Knoten expandiert haben. 35:33.260 --> 35:37.460 Und dann müssen wir wieder schauen, dieser Nachbarknoten, wenn wir den 35:37.460 --> 35:44.600 schon einmal bearbeitet haben, also der im Closed Set ist, dann ist 35:44.600 --> 35:45.220 der uns egal. 35:46.000 --> 35:47.400 Dann überspringen wir den einfach. 35:49.760 --> 35:50.360 Genau. 35:50.840 --> 35:55.860 Wenn er nicht im Closed Set ist, dann fügen wir den zum Open Set 35:55.860 --> 35:57.040 hinzu. 35:59.160 --> 36:03.500 Das heißt, das ist einer der Knoten, die wir möglicherweise als 36:03.500 --> 36:04.540 nächstes betrachten können. 36:06.980 --> 36:12.260 Und dann müssen wir schauen, finden wir einen kürzeren Weg, das ist ja 36:12.260 --> 36:16.120 die Idee hinter Astern, zu diesem Knoten vj. 36:20.060 --> 36:29.000 Und zwar bezüglich den akkumulierten Kosten zu vi plus den Kosten von 36:29.000 --> 36:31.360 vi zu vj. 36:35.880 --> 36:39.060 Das ist im Grunde die Frage, haben wir eine Abkürzung gefunden? 36:39.900 --> 36:41.500 Über den Knoten vi. 36:42.580 --> 36:48.100 Wenn wir diese Abkürzung gefunden haben, dann müssen wir eben den 36:48.100 --> 36:49.480 Aktualisierungsschritt hier machen. 36:54.300 --> 36:56.920 Das heißt, die Kostenfunktionen aktualisieren. 37:02.580 --> 37:06.040 Das heißt, wir haben jetzt hier die Abkürzung über vi gefunden. 37:06.040 --> 37:14.880 Das heißt, unsere neuen Kosten sind die Kosten bis vi plus die Kosten 37:14.880 --> 37:16.180 von vi nach vj. 37:18.240 --> 37:23.180 Und dann können wir auch unsere Heuristik berechnen. 37:29.120 --> 37:31.240 Von vi zum Ziel. 37:34.480 --> 37:37.740 Und am Ende müssen wir noch, weil wir jetzt eine Abkürzung gefunden 37:37.740 --> 37:41.040 haben, den Pfad aktualisieren, den wir bisher gefunden haben. 37:41.260 --> 37:43.100 Und den Pfad speichern wir in den Vorgängern. 37:44.640 --> 37:47.200 Also der neue Vorgänger von vj ist jetzt vi. 37:51.200 --> 37:52.360 Genau. 37:53.320 --> 38:01.120 Und das ist im Grunde der gesamte A-Stern-Algorithmus in jetzt so 38:01.120 --> 38:03.620 halbem Pseudocode hingeschrieben. 38:04.780 --> 38:10.980 Jetzt wollen wir das Ganze natürlich hier jetzt in C++ implementieren. 38:13.220 --> 38:13.740 Genau. 38:17.020 --> 38:22.760 Einige Dinge werden im Grunde ein entsprechendes Äquivalent haben. 38:23.000 --> 38:26.560 Also ich kann zum Beispiel in das OpenSet einfach meinen Start-Knoten 38:26.560 --> 38:27.060 einfügen. 38:30.420 --> 38:31.380 Dann ist er drin. 38:31.860 --> 38:34.720 Unser Close-Set ist sowieso schon leer initialisiert, da müssen wir 38:34.720 --> 38:35.380 jetzt nichts machen. 38:37.260 --> 38:42.820 Und auch diese Schritte hier, diesen Schritt hier sparen wir uns, 38:43.840 --> 38:48.000 indem wir einfach alle Einträge leerlassen in diesem assoziativen 38:48.000 --> 38:48.440 Speicher. 38:48.560 --> 38:51.500 Das heißt, wir tragen nicht für jeden Knoten da schon Infinity ein, 38:52.200 --> 38:53.840 sondern wir machen das dann On-Demand. 38:54.460 --> 38:55.520 Das sehen wir dann später. 38:57.220 --> 38:58.180 Genau. 38:58.660 --> 39:03.140 Wir können aber in den Speicher natürlich erstmal reinschreiben, dass 39:03.140 --> 39:08.760 aktuell die akkumulierten Kosten von vStart null sind. 39:11.120 --> 39:17.720 Und gleichzeitig bemerken wir uns auch die Heuristik, 39:21.120 --> 39:22.760 damit wir die nicht immer wieder berechnen. 39:28.890 --> 39:33.190 Die Heuristik müssen wir sagen, schätze die Kosten von diesem Knoten 39:33.190 --> 39:36.150 zu diesem Knoten, geben wir also Start und Ziel an. 39:38.090 --> 39:38.350 Genau. 39:40.030 --> 39:43.610 Dann die Schleife, die ist auch wieder Äquivalent, also solange unser 39:43.610 --> 39:52.010 OpenSet nicht leer ist, iterieren wir hier durch. 39:54.910 --> 39:57.930 Gut, dann sollen wir jetzt hier, das ist ja in dem Pseudocode jetzt 39:57.930 --> 40:01.390 ein bisschen höherlevelig beschrieben, wir sollen den Knoten vi 40:01.390 --> 40:05.170 finden, den wir expandieren wollen. 40:05.490 --> 40:09.670 Dafür müssen wir herausfinden, wer hat das minimale f unter den vi 40:09.670 --> 40:10.110 Knoten. 40:10.110 --> 40:14.190 Und da wir jetzt hier keine intelligente Struktur haben, wie zum 40:14.190 --> 40:19.210 Beispiel ein Heap oder was ähnliches, was man in einer performanten 40:19.210 --> 40:22.650 Sternenimplementierung verwenden würde, müssen wir jetzt einfach über 40:22.650 --> 40:23.710 alle Knoten iterieren. 40:24.770 --> 40:25.410 Genau. 40:25.410 --> 40:30.150 Das heißt, wir haben jetzt hier einfach eine Schleife, die versucht, 40:30.970 --> 40:36.590 das Minimum zu finden, oder nicht versucht, sondern das Minimum 40:36.590 --> 40:41.570 findet, hoffentlich, sofern ich keine... 40:41.570 --> 40:47.090 Genau, das heißt, wir gehen alle Knoten im OpenSet durch und schauen, 40:47.350 --> 40:49.710 okay, was ist der Funktionswert f. 40:49.710 --> 40:56.950 Dafür müssen wir g von v plus h von v addieren, also die akkumulierten 40:56.950 --> 40:58.050 Kosten und die Heuristik. 41:00.250 --> 41:04.810 Und dann schauen, okay, ist dieses f kleiner als mein bisheriges f. 41:07.750 --> 41:11.230 Bisheriges minimales f, das habe ich initialisiert mit dem Maximalwert 41:11.230 --> 41:12.710 für Float-Werte. 41:13.370 --> 41:15.270 Das heißt, das wird hoffentlich passen. 41:17.110 --> 41:21.230 Genau, und wenn es natürlich minimal ist, dann muss ich meine Werte 41:21.230 --> 41:22.070 aktualisieren. 41:22.410 --> 41:26.170 Dann habe ich ein neues Minimum, bisheriges Minimum gefunden. 41:27.650 --> 41:27.910 Genau. 41:28.550 --> 41:34.550 Also diese Schleife ist im Grunde nur finde das Akmin von dem f. 41:36.150 --> 41:36.750 Genau. 41:39.600 --> 41:40.200 Gut. 41:40.640 --> 41:43.160 Wir haben also unseren Knoten gefunden, den wir expandieren wollen. 41:44.860 --> 41:46.900 Dann haben wir jetzt hier noch den kurzen Check. 41:47.040 --> 41:48.300 Okay, sind wir vielleicht schon fertig? 41:51.080 --> 41:56.160 Wenn wir fertig sind, dann brechen wir unsere Schleife einfach ab. 42:02.570 --> 42:02.830 Genau. 42:05.490 --> 42:14.090 Und dann, wenn wir unser Ziel nicht erreicht haben, müssen wir vi aus 42:14.090 --> 42:15.530 dem OpenSet entfernen. 42:21.660 --> 42:23.800 Und zum CloseSet hinzufügen. 42:29.580 --> 42:30.160 Genau. 42:31.560 --> 42:31.940 Gut. 42:33.740 --> 42:36.700 Jetzt steht hier wieder so Update all Successors. 42:37.340 --> 42:40.960 Zum Glück sind die Datenstrukturen jetzt in diesem Fall uns etwas 42:40.960 --> 42:41.980 freundlicher gesinnt. 42:42.080 --> 42:44.700 Das heißt, wir müssen nicht irgendwo drüber iterieren, sondern wir 42:44.700 --> 42:50.960 können einfach sagen, Okay, eine VE-Schleife über alle VJ, also die 42:50.960 --> 42:51.740 Nachbarknoten. 42:52.460 --> 42:55.740 Nicht die Nachbarknoten, sondern die Folgeknoten von VI. 42:56.540 --> 43:01.860 Und da haben wir die Successors in VI direkt drin stehen, über die wir 43:01.860 --> 43:02.540 iterieren können. 43:04.700 --> 43:05.420 Genau. 43:08.000 --> 43:11.860 Dann haben wir hier wieder so einen kleinen Check, wenn der 43:11.860 --> 43:15.180 Nachfolgeknoten schon abgedeckt wurde. 43:17.620 --> 43:19.520 Das können wir über Count machen. 43:19.700 --> 43:22.300 Also Count zählt, wie viele Einträge es in diesem assoziativen 43:22.300 --> 43:22.900 Speicher gibt. 43:23.380 --> 43:27.220 Wenn es also einen gibt, dann skippen wir diesen Eintrag. 43:29.140 --> 43:30.600 Machen wir also einfach Continue. 43:30.600 --> 43:35.740 Continue heißt, wir gehen zum nächsten Successor, ohne den Code danach 43:35.740 --> 43:36.300 auszuführen. 43:38.040 --> 43:42.960 Und dann können wir das Ganze in unserem OpenSet einfügen. 43:45.200 --> 43:46.040 Okay. 43:47.460 --> 43:47.920 Gut. 43:48.420 --> 43:54.980 Jetzt müssen wir nur noch den Kernteil von Asterion implementieren. 43:55.620 --> 43:57.400 Haben wir einen kürzeren Pfad gefunden. 43:57.880 --> 44:04.200 Um das herauszufinden, müssen wir die neuen Kosten mit den alten 44:04.200 --> 44:05.580 Kosten vergleichen. 44:05.840 --> 44:08.440 Wir können das natürlich auch alles direkt hinschreiben, aber wir 44:08.440 --> 44:09.400 machen mal hier ein paar. 44:10.180 --> 44:12.280 Erstmal die neuen Kosten und dann die alten Kosten. 44:12.280 --> 44:22.520 Die neuen Kosten sind die Kosten von V i plus die Heuristik von V i, 44:29.180 --> 44:32.780 V j und die... 44:32.780 --> 44:33.440 Ah ja, genau. 44:34.040 --> 44:38.760 Wir benutzen hier diese Heuristik-Funktion auch als Kosten-Funktion. 44:39.460 --> 44:42.880 Also wenn ich hier V Goal hinschreibe, dann ist es meine Heuristik 44:42.880 --> 44:43.320 -Funktion. 44:43.320 --> 44:45.620 Und hier missbrauche ich die quasi. 44:45.860 --> 44:51.400 Also die berechnet die kathesische Distanz zwischen den beiden Knoten. 44:52.180 --> 44:54.540 Und die benutze ich hier als Kosten-Funktion. 44:55.100 --> 44:57.780 Missbrauche ich quasi. 44:58.400 --> 44:59.160 Genau. 45:00.580 --> 45:02.100 Und die alten Kosten. 45:02.760 --> 45:04.420 Jetzt müssen wir hier aufpassen. 45:04.980 --> 45:08.120 Wir haben ja diesen assoziativen Speichern nicht initial überall mit 45:08.120 --> 45:10.020 Infinity gefüllt oder mit Floatmax. 45:11.580 --> 45:14.100 Also kann uns das an dieser Stelle passieren, dass wir gar keinen 45:14.100 --> 45:16.280 Eintrag haben zu V j. 45:16.880 --> 45:20.780 Und wenn wir keinen Eintrag haben, dann können wir den auch nicht 45:20.780 --> 45:21.400 auslesen. 45:22.420 --> 45:24.400 Oder es macht keinen Sinn, den auszulesen. 45:25.800 --> 45:28.920 Und das ist jetzt hier der Teil, der prüft. 45:29.280 --> 45:31.520 Okay, haben wir einen Eintrag, dann können wir ihn auslesen. 45:32.000 --> 45:34.940 Wenn wir keinen Eintrag nehmen, dann nehmen wir halt Floatmax oder 45:34.940 --> 45:35.400 Infinity. 45:35.400 --> 45:37.080 Einen großen Wert. 45:38.900 --> 45:39.260 Genau. 45:40.880 --> 45:41.400 Gut. 45:41.740 --> 45:45.620 Und dann können wir eben gucken, sind die neuen Kosten kleiner als die 45:45.620 --> 45:46.260 alten Kosten? 45:47.800 --> 45:55.400 Und wenn das der Fall ist, dann können wir unsere Kosten-Funktionen 45:55.400 --> 45:55.840 updaten. 45:56.760 --> 45:58.100 Das ist erstmal das G. 46:00.000 --> 46:02.180 Das entspricht jetzt den neuen Kosten. 46:04.060 --> 46:05.140 Und das H. 46:12.440 --> 46:15.240 Dort speichern wir uns die Heuristik ab, wie gesagt. 46:15.620 --> 46:18.220 Einfach nur aus dem Grund, dass wir die nicht immer wieder neu 46:18.220 --> 46:18.960 berechnen wollen. 46:19.460 --> 46:21.480 Man könnte sie auch immer on the fly berechnen. 46:22.920 --> 46:24.020 Das macht keinen Unterschied. 46:26.380 --> 46:26.820 Genau. 46:26.940 --> 46:29.120 Und dann müssen wir noch unseren Vorgänger eintragen. 46:29.120 --> 46:32.080 Also Vj. 46:34.840 --> 46:35.540 Okay. 46:38.940 --> 46:40.780 Der Vorgänger ist jetzt Vi. 46:43.650 --> 46:44.350 Genau. 46:45.550 --> 46:51.710 Und das ist eigentlich dann die simpelste Variante von Astern, die man 46:51.710 --> 46:52.550 implementieren kann. 46:53.270 --> 46:56.810 Schauen wir mal, wie viel ich falsch gemacht habe. 46:57.930 --> 47:00.790 Ich glaube, ich habe es noch nie hingekriegt, dass irgendetwas beim 47:00.790 --> 47:03.130 ersten Mal funktioniert hat. 47:03.410 --> 47:10.010 Aber schauen wir mal, wo überall Semikolons fehlen und wo Zeichner 47:10.010 --> 47:10.810 vertauscht sind. 47:11.570 --> 47:13.090 Leider ist das so ein bisschen langsam. 47:13.290 --> 47:16.890 Ich glaube, das liegt daran, weil das Dateisystem nicht so schön ist. 47:16.950 --> 47:17.790 Oh, es hat funktioniert. 47:18.390 --> 47:20.470 Aber dann ist es bestimmt falsch implementiert. 47:25.060 --> 47:25.840 Gut, genau. 47:25.940 --> 47:28.160 Also was sieht man, wenn man das jetzt geschafft hat zu 47:28.160 --> 47:28.800 implementieren? 47:29.680 --> 47:33.060 Hoffen wir, dass wir etwas sehen. 47:33.820 --> 47:34.620 Okay, genau. 47:34.940 --> 47:38.840 Dann sehen wir jetzt hier einen Pfad, den der Roboter abfährt, der 47:38.840 --> 47:40.180 kollisionsfrei ist. 47:42.180 --> 47:43.540 Und ihn zum Ziel führt. 47:45.420 --> 47:48.400 Und wir können das Ganze auch in einer anderen Umgebung machen. 47:48.400 --> 47:51.020 Und schauen, ob das hier funktioniert. 47:53.720 --> 47:55.560 Und genau. 47:56.380 --> 48:02.320 Wenn wir dann natürlich die super simple Umgebung nehmen, dann fährt 48:02.320 --> 48:04.460 er natürlich einfach geradeaus zum Ziel. 48:12.310 --> 48:12.770 Gut. 48:22.680 --> 48:26.740 Dann müssen wir hier einmal zurückgehen. 48:29.750 --> 48:33.110 Genau, also das ist im Grunde einmal so eine Implementierung in 48:33.110 --> 48:33.470 Simbox. 48:33.570 --> 48:35.570 Ihr könnt euch auch mal versuchen, andere zu implementieren. 48:36.650 --> 48:40.890 Das ist so eine Aufgabe, ein Teil der Aufgabe, die wir zum Beispiel in 48:40.890 --> 48:42.270 einem Praktikum von uns machen. 48:42.970 --> 48:44.430 Da muss man nur noch ein bisschen mehr machen. 48:45.610 --> 48:47.490 Genau, auf dem Folien ist nochmal ein Stern drauf. 48:48.070 --> 48:49.210 Da sind wir durchgegangen. 48:51.570 --> 48:51.970 Genau. 48:52.970 --> 49:01.630 Dann gibt es noch den RRT-Teil, der so ein bisschen interessanter ist 49:01.630 --> 49:02.810 vielleicht, weil da fehlt mehr. 49:05.450 --> 49:07.950 Den können wir uns auch mal anschauen, was man da machen muss. 49:09.370 --> 49:12.770 Aber da müssen wir nicht so intensiv drauf eingehen. 49:14.810 --> 49:16.430 Ah, habe ich tatsächlich noch hier. 49:18.430 --> 49:18.770 Genau. 49:20.750 --> 49:23.610 Wir hatten ja RRT in der Vorlesung kennengelernt. 49:24.230 --> 49:30.950 Probabilistischer Algorithmus, der eben keine Garantie hat, dass man 49:30.950 --> 49:32.690 innerhalb eines Zeitlimits etwas findet. 49:33.130 --> 49:36.690 Aber wenn eine Lösung existiert und man unendlich lange sampelt, dann 49:36.690 --> 49:37.370 funktioniert das. 49:39.150 --> 49:42.630 Ist eben effizient in hochdimensionalen Problemstellungen. 49:42.730 --> 49:47.350 Genau da, wo eben die Robotik ist mit achtdimensionalen 49:47.350 --> 49:50.350 Konfigurationsräumen von Roboterarmen zum Beispiel. 49:51.290 --> 49:52.030 Genau. 49:52.750 --> 49:55.650 Und wie funktioniert RRT nochmal im Schnelldurchlauf? 49:56.650 --> 50:00.730 Wir wissen ja nicht, wie das Hindernis im Konfigurationsraum aussieht. 50:00.730 --> 50:04.950 Das heißt, wir initialisieren erstmal irgendwo einen Startpunkt. 50:06.050 --> 50:07.850 Fügen den in unseren Baum ein. 50:08.730 --> 50:13.030 Und dann iterieren wir, indem wir immer zufällige Punkte erzeugen. 50:14.190 --> 50:17.010 Und dann, hier ist dieser zufällige Punkt. 50:17.450 --> 50:20.670 Dann versuchen wir, die nächsten Nachbarn im Netz mit diesem 50:20.670 --> 50:22.130 zufälligen Punkt zu verbinden. 50:22.830 --> 50:25.510 Allerdings nur bis zu einer maximalen Schrittweite d. 50:27.450 --> 50:30.030 Und machen das dann, bis wir an dem Punkt sind. 50:30.190 --> 50:32.090 Wenn das kollisionsfrei geht, ist das alles okay. 50:35.530 --> 50:35.930 Genau. 50:36.070 --> 50:39.610 Wenn wir aber zum Beispiel hier sampeln, dann ist hier unser nächster 50:39.610 --> 50:40.070 Nachbar. 50:40.750 --> 50:43.390 Und dann stellen wir fest, dass wir einen weiterkommen, aber dann hier 50:43.390 --> 50:44.270 in Kollision gehen. 50:45.190 --> 50:49.230 Das heißt, hier hört dann die Expansion schon auf, an dieser Stelle. 50:52.650 --> 50:56.470 Und es gibt auch Verfahren, die ab und an mal dann versuchen, den Baum 50:56.470 --> 50:58.010 direkt mit dem Ziel zu verbinden. 50:58.970 --> 51:01.290 Also ERT hat sehr, sehr viele unterschiedliche Varianten. 51:01.950 --> 51:04.330 Aber von der Idee her ist ja alles sehr ähnlich. 51:04.750 --> 51:08.190 Und am Ende, wenn man dann sein Ziel erreicht hat, kann man eben den 51:08.190 --> 51:09.290 Baum rückwärts ablaufen. 51:09.870 --> 51:10.450 Oder vorwärts. 51:10.730 --> 51:11.830 Und kommt dann an sein Ziel. 51:14.050 --> 51:14.330 Genau. 51:18.030 --> 51:19.730 Was haben wir dazu? 51:24.980 --> 51:27.480 Dazu haben wir hier den ERT-Planer. 51:36.470 --> 51:36.550 Okay. 51:38.930 --> 51:39.490 Genau. 51:39.750 --> 51:42.590 Also hier ist auch wieder alles im Prinzip vorgegeben. 51:43.450 --> 51:45.210 Das heißt, wir haben gar nicht viel zu tun. 51:47.030 --> 51:50.310 Sondern nur den Teil, der hier fehlt. 51:51.050 --> 51:56.850 Was wir als erstes machen sollen, ist den nächsten Vertex zu finden, 51:56.930 --> 51:57.690 den nächsten Nachbarn. 51:58.310 --> 52:00.130 Das ist ja Teil des ERT. 52:01.090 --> 52:03.970 Und weil man ja versucht, mit dem nächsten Nachbarn was zu verbinden. 52:04.670 --> 52:08.290 Und den nächsten Nachbarn ist wieder so ein einfacher Min-Algorithmus. 52:08.450 --> 52:13.650 Das heißt, wir gehen einfach durch alle unsere Knoten. 52:14.630 --> 52:17.590 Das ist jetzt wieder hier dieselbe Datenstruktur, die wir auch schon 52:17.590 --> 52:19.410 aus dem Astern kennen. 52:20.090 --> 52:21.470 Alle Knoten durch. 52:21.990 --> 52:25.250 Schauen uns an, okay, was ist denn der Abstand? 52:25.330 --> 52:28.070 Das ist natürlich hier ein zweidimensionales Problem. 52:31.780 --> 52:37.120 Und dort müssen wir den Abstand von unserem zufälligen Vektor und 52:37.120 --> 52:40.560 unserem aktuell betrachteten Vektor nehmen. 52:43.000 --> 52:43.640 Genau. 52:44.640 --> 52:48.260 Und dann können wir daraus uns den Abstand holen. 52:49.100 --> 52:51.520 Also das ist hier aus der Eigenbibliothek. 52:51.620 --> 52:54.560 Das ist auch was, was wir standardmäßig bei uns benutzen. 52:54.700 --> 52:59.920 Das ist eine Mathebibliothek, die in C++ sehr beliebt ist, würde ich 52:59.920 --> 53:00.240 sagen. 53:03.800 --> 53:07.020 Die ist natürlich hier für dieses kleine Programm ein bisschen 53:07.020 --> 53:10.380 overkill, um die Größe eines Vektors zu berechnen. 53:10.580 --> 53:12.120 Aber warum nicht? 53:14.160 --> 53:14.760 Genau. 53:15.120 --> 53:18.040 Also hier eine einfache Schleife, die das Minimum der Distanz 53:18.040 --> 53:20.320 berechnet und dann am Ende zurückgibt. 53:21.360 --> 53:25.180 Nichts Besonderes, aber ordnet sich eben als nearest neighbor search 53:25.180 --> 53:26.840 in den ERT ein. 53:27.400 --> 53:30.400 Natürlich machen richtige ERT-Implementierungen, machen nearest 53:30.400 --> 53:32.360 neighbor -Suche natürlich intelligenter. 53:32.760 --> 53:36.140 Aber für so eine einfache Implementierung, um das Problem mal zu 53:36.140 --> 53:36.840 verstehen, nicht schlecht. 53:37.860 --> 53:39.220 Dann gibt es den Extend-Schritt. 53:39.220 --> 53:44.220 Das ist der Schritt, wo wir versuchen, vom nächsten Nachbarn in 53:44.220 --> 53:46.080 Richtung des zufälligen Knoten zu erweitern. 53:49.040 --> 53:53.080 Dafür holen wir uns wieder so einen zweidimensionalen Vektor vom 53:53.080 --> 53:57.060 nächsten Nachbarn zu dem random Knoten, um erstmal die Richtung zu 53:57.060 --> 53:57.480 bestimmen. 54:07.720 --> 54:08.380 Genau. 54:12.320 --> 54:14.200 Das ist die tatsächliche Distanz. 54:19.800 --> 54:24.780 Allerdings müssen wir diese tatsächliche Distanz ja beschränken. 54:34.460 --> 54:40.060 Das heißt, wir wollen ja vom nächsten zum random Sample hingehen. 54:40.840 --> 54:43.860 Dafür können wir den Vektor normalisieren, also einen Einheitsvektor 54:43.860 --> 54:56.530 daraus machen und dann multiplizieren mit dem Minimum aus der 54:56.530 --> 55:04.090 tatsächlichen Distanz und der vorgegebenen Incremental Distance. 55:04.470 --> 55:07.370 Die Incremental Distance ist hier dieses d, die Schrittweite. 55:08.750 --> 55:11.490 Wenn ich das Minimum davon nehme, dann überschreite ich diese 55:11.490 --> 55:13.750 Schrittweite nie, die d dahinter. 55:15.950 --> 55:16.890 Genau. 55:19.330 --> 55:24.130 Und dann kann ich die neue Position setzen. 55:24.750 --> 55:30.490 Neue Position ist die nächste Nachbarposition plus eben dieses 55:30.490 --> 55:32.410 Inkrement, was ich berechnet habe. 55:33.170 --> 55:39.250 Und dieses Inkrement ist eben maximal die Schrittlänge lang und geht 55:39.250 --> 55:44.130 in die Richtung vom nächsten Nachbarn zum random Sample. 55:45.270 --> 55:48.890 Das ist nur ein bisschen Geometrie, sag ich mal, lineare Algebra. 55:49.450 --> 55:51.370 Na, nicht mal das, Geometrie. 55:53.510 --> 55:54.030 Genau. 55:54.990 --> 55:59.190 Das ist also der Extentschritt in diese Richtung, so und so weit. 56:01.870 --> 56:05.410 Damit das Ganze, warum man ERT benutzt, ist eben, weil man sehr schön 56:05.410 --> 56:09.290 integrieren kann, zum Beispiel Kollisionsprüfungen für jede 56:09.290 --> 56:10.050 Konfiguration. 56:10.050 --> 56:13.510 Das ist das, was wir hier machen, also Einschränkungen überprüfen, 56:13.610 --> 56:14.170 Constraints. 56:14.850 --> 56:18.770 Constraints können natürlich viele Formen annehmen. 56:18.930 --> 56:24.890 Zum Beispiel ist diese Position stabil oder ist sie weit genug von 56:24.890 --> 56:25.650 Gefahren weg. 56:26.770 --> 56:29.130 Aber in unserem Fall ist es einfach nur eine Kollisionsprüfung. 56:29.690 --> 56:32.570 Und das haben wir hier mal aufgenommen, damit man auch mal sieht, wie 56:32.570 --> 56:36.550 Kollisionsprüfung in Simox funktioniert. 56:36.550 --> 56:43.510 Das ist ein bisschen umständlich, aber wir zeigen das mal. 56:45.010 --> 56:47.430 Genau, also man macht so einen Collision-Checker-Objekt, 56:52.740 --> 56:58.660 der dafür zuständig ist, Kollisionen zu prüfen. 57:01.120 --> 57:04.720 Und für Convenience-Zwecke gibt es davon einen globalen. 57:04.720 --> 57:06.720 Den kann man natürlich nicht benutzen, wenn man irgendwie 57:06.720 --> 57:10.380 Multithreading macht oder so, aber für unsere Zwecke ist man 57:10.380 --> 57:11.020 ausreichend. 57:12.860 --> 57:19.240 Und dann gehen wir über alle Kollisionsmodelle. 57:20.680 --> 57:23.480 Also Simox hat so das Konzept von einem Kollisionsmodell. 57:23.720 --> 57:24.640 Das sind unsere Hindernisse. 57:26.520 --> 57:32.820 Und unsere Hindernisse sind in so einem Obstacles-Array drin, von dem 57:32.820 --> 57:37.700 wir uns alle Kollisionsmodelle geben lassen können. 57:48.680 --> 57:52.680 Ach ja, der Code wird natürlich immer schön lang. 57:53.360 --> 57:56.460 Genau, also wir iterieren über alle Kollisionsmodelle in den 57:56.460 --> 57:56.960 Hindernissen. 57:58.240 --> 58:00.940 Ein Hindernis kann natürlich aus mehreren Kollisionsmodellen bestehen 58:00.940 --> 58:01.420 und so weiter. 58:02.900 --> 58:12.480 Aber wir prüfen jetzt, ob eine Kollision mit diesem speziellen 58:12.480 --> 58:14.120 Kollisionsmodell steht. 58:14.700 --> 58:19.660 Da wird intern so ein PQP-Kollisionscheck gemacht, der auf dem 58:19.660 --> 58:21.560 Dreiecksmesh arbeitet. 58:22.640 --> 58:25.680 Aber ist für uns auf High-Level-Ebene nicht so wichtig. 58:28.960 --> 58:31.160 Genau, ich nehme das Roboter-Kollision-Model. 58:31.360 --> 58:34.240 Das ist ein spezielles Modell vom Roboter, weil natürlich die 58:34.240 --> 58:42.680 Visualisierung oft komplexer ist als das Kollisionsmodell, das man 58:42.680 --> 58:43.660 tatsächlich benötigt. 58:44.660 --> 58:47.560 Da hat man meist ein vereinfachtes Kollisionsmodell vom Roboter. 58:48.560 --> 58:54.100 Und wenn wir jetzt hier so eine Kollision gehabt haben, dann sagen 58:54.100 --> 58:56.320 wir, unsere Constraints sind nicht erfüllt. 58:57.440 --> 59:00.500 Also diese Methode ist hier so aufgebaut, dass sie einen Boolean 59:00.500 --> 59:03.960 zurückgibt, wenn die Einschränkungen erfüllt sind. 59:04.320 --> 59:06.900 Wenn wir also kollisionsfrei sind, gibt sie True zurück. 59:07.340 --> 59:09.980 Und wenn wir eine Kollision haben, gibt sie False zurück. 59:11.660 --> 59:17.600 Genau, hier eine Schleife über die Hindernisse. 59:21.560 --> 59:26.760 Und dann haben wir hier die Plan-Funktion. 59:26.760 --> 59:29.960 Das ist im Grunde das Kernstück, wo der ERT eigentlich durchgeführt 59:29.960 --> 59:30.220 wird. 59:31.860 --> 59:35.040 Und das meiste vom Boilerplate-Code ist für uns schon gemacht. 59:35.360 --> 59:37.880 Also wir haben hier oben so ein bisschen Initialisierung und Prüfung 59:37.880 --> 59:39.140 von Anfangsbedingungen. 59:40.240 --> 59:41.980 Hier werden die Kollisionsmodelle geholt. 59:43.440 --> 59:44.880 Und hier ist die eigentliche Schleife. 59:47.200 --> 59:48.460 Und hier fehlt jetzt alles. 59:49.260 --> 59:53.740 Und jetzt könnte man denken, oh mein Gott, muss ich jetzt nochmal ERT 59:53.740 --> 59:54.940 jetzt hier komplett implementieren. 59:54.940 --> 59:58.200 Aber die Idee war, dass die Methoden, die wir jetzt vorher 59:58.200 --> 01:00:01.320 implementiert haben, dass wir die jetzt hier einfach benutzen können. 01:00:03.540 --> 01:00:04.180 Genau. 01:00:04.180 --> 01:00:08.940 Also das erste, was ERT am Anfang macht, ist ein zufälliger 01:00:08.940 --> 01:00:09.800 Knotensample. 01:00:17.570 --> 01:00:18.210 Genau. 01:00:19.090 --> 01:00:26.610 Und wir geben hier den Zielknoten mit rein, weil das jetzt hier eine 01:00:26.610 --> 01:00:30.110 Variante ist, bei dem nicht immer willkürliche zufällige Knoten 01:00:30.110 --> 01:00:32.930 generiert werden, sondern mit einer gewissen Wahrscheinlichkeit wird 01:00:32.930 --> 01:00:36.770 auch der Zielknoten als zufälliger Knoten wiedergegeben, damit der 01:00:36.770 --> 01:00:40.890 Raum eben in Richtung des Ziels eher wächst und nicht einfach nur in 01:00:40.890 --> 01:00:41.650 den Raum hinaus. 01:00:42.270 --> 01:00:45.330 Eine typische Variante von ERT. 01:00:48.330 --> 01:00:48.930 Genau. 01:00:49.330 --> 01:00:53.670 Die nearest vertex Methode haben wir ja selber implementiert. 01:00:54.810 --> 01:01:02.300 Die findet den nächsten Nachbarn zu dem zufälligen Sampleknoten, den 01:01:02.300 --> 01:01:03.160 wir übergeben müssen. 01:01:05.480 --> 01:01:09.840 Und dann müssen wir ja schauen, dass unser Knoten nicht die 01:01:09.840 --> 01:01:10.760 Schrittweite einhält. 01:01:11.040 --> 01:01:13.620 Das ist die extent Funktion, die wir auch implementiert haben. 01:01:15.860 --> 01:01:20.340 Da sollen wir vom nächsten Nachbarn zum Zielknoten hin, aber dabei die 01:01:20.340 --> 01:01:21.940 incremental distance einhalten. 01:01:24.660 --> 01:01:25.220 Genau. 01:01:26.140 --> 01:01:29.580 Also das hier sind die beiden Funktionen, die wir eben implementiert 01:01:29.580 --> 01:01:31.320 haben, nearest vertex und extent. 01:01:33.760 --> 01:01:39.980 Dann müssen wir schauen, okay, dieser neue Knoten, ist der in 01:01:39.980 --> 01:01:40.740 Kollision vielleicht? 01:01:40.740 --> 01:01:43.180 Oder ist der okay? 01:01:43.300 --> 01:01:44.240 Darf ich den benutzen? 01:01:44.800 --> 01:01:46.970 Dafür prüfen wir die Constraints, die Einschränkungen. 01:01:47.900 --> 01:01:51.040 Das ist die Methode, die wir auch eben implementiert haben. 01:01:53.260 --> 01:01:53.840 Genau. 01:01:54.900 --> 01:01:57.580 Und wenn wir alle Einschränkungen erfüllen, dann können wir eben den 01:01:57.580 --> 01:02:00.500 Knoten hinzufügen zu unserem Baum. 01:02:02.580 --> 01:02:05.400 Wir fügen also den Knoten und die Kante hinzu. 01:02:06.440 --> 01:02:08.980 Vom nächsten Nachbarn zum neuen Knoten. 01:02:17.610 --> 01:02:22.790 Dann schauen wir, okay, wie weit sind wir von unserem Ziel entfernt? 01:02:24.290 --> 01:02:30.030 Der neue Knoten ist zum Ziel, davon die Länge. 01:02:31.830 --> 01:02:33.810 Und wenn wir nah genug am Ziel sind, 01:02:38.480 --> 01:02:43.500 dann haben wir so einen Y-Wert, den wir dafür benutzen. 01:02:43.500 --> 01:02:46.460 Der oben drüber definiert ist. 01:02:48.140 --> 01:02:53.160 Dann sind wir fertig und sagen dann eben, okay, die äußere Schleife 01:02:53.160 --> 01:02:55.500 möchte wissen, dass wir dann eine Lösung gefunden haben. 01:02:56.900 --> 01:03:01.560 Und unser Zielknoten ist dann unser neuer Knoten. 01:03:02.360 --> 01:03:06.140 Damit wir nachher den Baum rückwärts ablaufen können. 01:03:08.860 --> 01:03:09.340 Genau. 01:03:12.160 --> 01:03:15.240 Natürlich war das jetzt ein bisschen schneller. 01:03:15.360 --> 01:03:17.540 Wenn ihr das macht, müsst ihr euch natürlich erstmal umschauen, was 01:03:17.540 --> 01:03:21.060 gibt es hier für Variablen, wie funktionieren die Schleifen und so 01:03:21.060 --> 01:03:21.280 weiter. 01:03:21.920 --> 01:03:23.560 Ist natürlich nicht alles euer Code. 01:03:23.980 --> 01:03:27.520 Aber ich denke, der Code selbst ist so einfach gehalten, dass man, 01:03:28.900 --> 01:03:31.700 wenn jemand das interessiert, wie das wirklich implementiert wird, 01:03:31.980 --> 01:03:33.860 dass man sich da durcharbeiten kann. 01:03:33.860 --> 01:03:39.680 Aber schauen wir erstmal, wie viel ich dabei jetzt kaputt gemacht 01:03:39.680 --> 01:03:40.000 habe. 01:03:54.710 --> 01:03:58.490 Okay, diesmal wird es wahrscheinlich irgendwas erwischt haben. 01:04:03.210 --> 01:04:05.450 Okay, naja, zumindest die Syntax passt. 01:04:08.570 --> 01:04:10.750 Gut, wir hatten ja Astern gesehen. 01:04:11.230 --> 01:04:15.190 Astern findet ja immer den kürzesten Weg. 01:04:15.410 --> 01:04:18.170 Und da wir hier so einen Grid durchlegen, sieht der Fahrt sehr 01:04:18.170 --> 01:04:19.010 regelmäßig aus. 01:04:19.010 --> 01:04:27.230 Wenn wir uns jetzt Astern anschauen, dann sieht man hier, dass der 01:04:27.230 --> 01:04:33.170 Fahrt eben sehr, hier sieht man die zufälligen Aspekte in dem Fahrt 01:04:33.170 --> 01:04:34.250 sehr deutlich. 01:04:37.050 --> 01:04:41.830 Besonders deutlich sieht man es natürlich, wenn man den leeren Pfad 01:04:41.830 --> 01:04:42.450 hier betrachtet. 01:04:43.290 --> 01:04:46.610 Hier wäre natürlich die gerade Linie der kürzeste Weg, aber man sieht 01:04:46.610 --> 01:04:51.550 hier, dass der Roboter natürlich trotzdem hier die zufälligen Elemente 01:04:51.550 --> 01:04:51.910 drin hat. 01:04:52.990 --> 01:05:01.090 Und in dem Trap-Beispiel geht Astern natürlich mal rechts rum und mal 01:05:01.090 --> 01:05:06.430 links rum, je nachdem, wie sich der Baum gerade entwickelt hat. 01:05:08.690 --> 01:05:12.090 Astern müsste eigentlich deterministisch sein. 01:05:13.050 --> 01:05:16.170 Also immer den einen Weg gehen. 01:05:18.530 --> 01:05:24.610 Während T durch den zufälligen Aspekt mal links und mal rechts rum 01:05:24.610 --> 01:05:27.370 geht und auch mal ein bisschen anders aussieht. 01:05:30.750 --> 01:05:33.150 Man sieht hier, dass es sich näher dahin bewegt. 01:05:35.890 --> 01:05:36.370 Okay. 01:05:37.950 --> 01:05:44.530 Ja, also das war nur, damit ihr mal so ein bisschen was seht, wie wir 01:05:44.530 --> 01:05:46.330 normalerweise programmieren, also unsere Frameworks. 01:05:47.910 --> 01:05:50.250 Ich denke, es wird sehr ähnlich auch in den anderen Frameworks sein. 01:05:51.270 --> 01:05:57.390 Genau, ja, und das ist eigentlich auch schon alles für dieses 01:05:57.390 --> 01:05:57.970 Semester. 01:05:59.230 --> 01:06:02.970 Ich hoffe, ihr hattet Spaß, konntet ein paar Dinge lernen. 01:06:03.530 --> 01:06:07.170 Wir sind natürlich immer offen auch für Vorschläge, das besser zu 01:06:07.170 --> 01:06:10.470 machen, wenn ihr euch direkt an uns wenden wollt, per E-Mail oder 01:06:10.470 --> 01:06:11.070 vorbeikommen. 01:06:11.670 --> 01:06:14.230 Ist natürlich ein bisschen einfacher, als wenn ein paar Punkte in 01:06:14.230 --> 01:06:16.150 diesen Evaluationsbögen ausgefüllt werden. 01:06:16.550 --> 01:06:18.550 Also, wenn ihr mal gerne interessiert. 01:06:19.130 --> 01:06:21.550 Und wie ihr wisst, haben wir auch die Ausschreibungen für Hiwis und 01:06:21.550 --> 01:06:22.190 Abschlussarbeiten. 01:06:22.650 --> 01:06:24.130 Also, seid ihr natürlich gerne gesehen. 01:06:24.130 --> 01:06:28.210 Ansonsten, danke für eure Aufmerksamkeit.