WEBVTT 00:05.140 --> 00:10.020 Wir haben eine Startkonfiguration in diesem Konfigurationsraum und 00:10.020 --> 00:12.440 eine Zielkonfiguration, die wir erreichen wollen. 00:13.140 --> 00:19.780 Und wir suchen eine Trajektorie, zum Beispiel Tau, mit den 00:19.780 --> 00:25.520 Bedienungen, dass Tau natürlich zum Zeitpunkt 0, dass der Roboter an 00:25.520 --> 00:34.340 der Startkonfiguration Q-Start ist und am Ende Tau bei T gleich 1 am 00:34.340 --> 00:34.940 Ziel ist. 00:35.120 --> 00:39.300 Und natürlich müssen wir dabei eine ganze Menge von Bedienungen 00:39.300 --> 00:40.040 berücksichtigen. 00:40.500 --> 00:43.800 Wir müssen zum Beispiel Zwangsbedienungen, die durch den Roboter 00:43.800 --> 00:45.820 selbst vorgegeben sind, berücksichtigen. 00:46.340 --> 00:50.180 Das ist notwendig, wie wir wissen, Gelenkwinkel grenzen. 00:50.660 --> 00:53.760 Bestimmte Lösungen der Inversion Kinematik sind nicht gültig, weil sie 00:53.760 --> 00:57.620 sind außerhalb der Bahnsteuerungsvorlesung. 01:00.240 --> 01:04.920 ...freie Bewegung, das ist natürlich die Hauptbedienung, die wir 01:04.920 --> 01:06.300 berücksichtigen müssen. 01:06.540 --> 01:08.920 Aber zusätzlich das, was hier nochmal steht. 01:10.220 --> 01:14.060 Wir suchen nicht unbedingt irgendwelche Trajektorien, sondern 01:14.060 --> 01:17.400 vielleicht eine Trajektorie, die gute Kriterien oder 01:17.400 --> 01:19.160 Optimalitätskriterien erfüllt. 01:19.160 --> 01:24.300 Zum Beispiel die Trajektorie mit der kürzesten Dauer oder die 01:24.300 --> 01:28.200 Trajektorie, die mit dem geringsten Energieverbrauch verbunden ist 01:28.200 --> 01:32.820 oder die Trajektorie, die den großen Abstand zu Hindernissen hat. 01:35.880 --> 01:40.060 Und dann natürlich andere Neben- und Randbedienungen müssen 01:40.060 --> 01:43.780 berücksichtigt werden, dass wir entlang der Trajektorie zum Beispiel 01:43.780 --> 01:48.580 eine Tasse in der Hand in der aufrechten Position halten müssen, damit 01:48.580 --> 01:52.480 wir zum Beispiel die Flüssigkeit nicht schütten. 01:53.260 --> 01:55.240 Wie man sieht, ist es gar keine einfache Sache. 01:55.500 --> 01:57.380 Also natürlich Kollisionen vermeiden. 01:57.640 --> 02:02.180 Aber wie wir sehen werden in dieser Vorlesung, wir werden auch einige 02:02.180 --> 02:06.600 Methoden kennenlernen, die mit solchen Bedienungen, mit diesen 02:06.600 --> 02:11.340 Nebenzwangsbedienungen beziehungsweise auch guten Kriterien umgehen 02:11.340 --> 02:11.620 können. 02:12.420 --> 02:17.340 Und ganz vereinfacht unseren einfachen Roboterarm mit drei Gelenken 02:17.340 --> 02:20.780 hier, dargestellt im Arbeitsraum, das ist zum Beispiel der 02:20.780 --> 02:22.860 karthesische Raum R6. 02:23.700 --> 02:28.140 Und wir wissen, dass der Endeffektor wird immer mit TCP, also Tool 02:28.140 --> 02:29.720 Center Point hier bezeichnet. 02:30.140 --> 02:33.820 Und wenn wir jetzt eine Trajektorie von dieser Startposition zu dieser 02:33.820 --> 02:38.240 Endposition berechnen, kann man auch Konfiguration dazu sagen, aber 02:38.240 --> 02:40.880 das wäre jetzt eine Konfiguration im Arbeitsraum. 02:40.880 --> 02:46.540 Also gegeben durch die 6D-Pose zum Beispiel von dem Tool Center Point, 02:46.940 --> 02:50.380 dann wäre das eine gültige kollisionsfreie Trajektorie. 02:51.420 --> 02:56.320 Diese Trajektorie sieht natürlich im Konfigurationsraum anders aus, 02:56.500 --> 03:00.560 weil in dem Konfigurationsraum müssen wir zunächst mal dieses 03:00.560 --> 03:05.620 Hindernis hier, dieses quadratisch praktische Hindernis hier abbilden 03:05.620 --> 03:07.080 in dem Konfigurationsraum. 03:07.080 --> 03:11.800 Und der Konfigurationsraum wird aufgespannt von den drei Gelenken. 03:11.920 --> 03:12.540 Uppsala. 03:13.800 --> 03:16.220 Muss man hier kollisionsfrei laufen können. 03:16.960 --> 03:21.020 Von den drei Gelenken Theta 0, Theta 1 und Theta 2. 03:21.360 --> 03:26.520 Also die sind nicht alle 0 hier, die sollen 1 und 2 und 3 sein. 03:28.960 --> 03:34.100 Und wie man sieht, das ist die Abbildung von diesem Hindernis, was wir 03:34.100 --> 03:38.200 vorher gesehen haben im Konfigurationsraum, im Arbeitsraum, in den 03:38.200 --> 03:39.360 Konfigurationsraum. 03:39.880 --> 03:44.320 Und unsere Trajektorie, die blaue Trajektorie hier im Arbeitsraum, 03:46.140 --> 03:50.020 beziehungsweise ist diese gelbe Trajektorie im Konfigurationsraum. 03:50.760 --> 03:54.060 Das heißt, wir haben ein N-Dimensional im Konfigurationsraum. 03:54.300 --> 03:58.260 Man nennt das auch im Englischen C-Space, also Configuration Space. 03:58.260 --> 04:00.500 Wir haben den Freiraum. 04:00.680 --> 04:04.260 Und zwar, das sind alle kollisionsfreien Konfigurationen. 04:05.360 --> 04:08.480 Also alles, was weiß ist hier in diesem dreidimensionalen Raum, 04:09.960 --> 04:11.000 dreidimensionalen Konfigurationsraum. 04:11.500 --> 04:13.480 Und wir haben den Hindernisraum. 04:14.000 --> 04:16.640 Und der Hindernisraum, das sind alle roten Teile. 04:16.960 --> 04:21.200 Das heißt, alle Konfigurationen, die zu einer Kollision führen. 04:21.400 --> 04:25.220 Und wie man sieht, natürlich der komplette Konfigurationsraum, also 04:25.220 --> 04:29.580 alle möglichen Kombinationen von Täter 0, Täter 1, Täter 2, ist nichts 04:29.580 --> 04:34.200 anderes als die Vereinigung vom Freiraum und vom Hindernisraum. 04:35.600 --> 04:38.980 Und wie man sich vielleicht vorstellen kann, ist die Berechnung von 04:38.980 --> 04:41.820 diesem Hindernisraum alles andere als trivial. 04:42.160 --> 04:44.660 Da werden wir gleich hier ein Beispiel dazu sehen. 04:45.420 --> 04:48.500 Aber die Beziehungen hier zwischen Konfigurations- und Arbeitsraum 04:48.500 --> 04:52.060 kann man am besten anhand von diesem Beispiel hier sehen. 04:52.060 --> 04:54.860 Also nehmen wir mal an, wir wollen hier dieses grüne Objekt 04:54.860 --> 04:55.640 manipulieren. 04:56.360 --> 05:00.000 Und da sieht man eigentlich, dass man mit keiner Konfiguration von 05:00.000 --> 05:05.160 diesem dreiachsigen Roboter hier bis zum grünen Objekt kommt oder 05:05.160 --> 05:08.680 kommen kann, ohne dass es zu Kollisionen kommt. 05:09.900 --> 05:12.380 Der Konfigurationsraum momentan sieht so aus. 05:12.620 --> 05:18.540 Also das ist die Abbildung von all diesen Hindernissen in den Raum, 05:18.760 --> 05:24.340 der von den Gelenken Täter 1, Täter 2 und Täter 3 aufgespannt wird. 05:24.520 --> 05:29.640 Also das sind ja die Gelenke hier von diesem Roboterarm. 05:30.140 --> 05:33.340 Der hat auch ein drittes Gelenk, wie man sieht hier am Handgelenk. 05:34.300 --> 05:36.360 Und das letzte Mal... Ups, Entschuldigung. 05:37.260 --> 05:38.000 Das war zu schnell. 05:38.500 --> 05:42.560 Und das nächste Mal haben wir gesehen, wie sich das alles verändert. 05:44.440 --> 05:46.180 Das schalten wir mal aus. 05:47.180 --> 05:50.860 Das heißt, wenn wir jetzt hier dieses grüne Objekt manipulieren 05:50.860 --> 05:53.120 wollen, dann müssen wir natürlich den Weg frei machen. 05:54.380 --> 05:56.780 Das ist sehr naheliegend natürlich im Arbeitsraum. 05:57.040 --> 06:01.960 Jeder von euch kann sich vorstellen, was man machen muss, also welche 06:01.960 --> 06:05.700 Sequenz von Aktionen notwendig ist, um den Weg frei zu machen zum 06:05.700 --> 06:06.420 Zielobjekt. 06:07.980 --> 06:11.700 Aber im Konfigurationsraum sieht die Sache natürlich ein bisschen 06:11.700 --> 06:16.960 komplizierter aus, weil in dieser anfänglichen Situation hier, wenn 06:16.960 --> 06:22.580 das grüne Objekt komplett blockiert ist, befindet sich dieses Ziel, 06:22.780 --> 06:25.660 also das grüne Objekt, im Hindernisraum. 06:26.240 --> 06:30.180 Das heißt, da gibt es keine Chance, dass man dort rankommt ohne 06:30.180 --> 06:32.220 Kollisionen mit anderen Objekten. 06:33.140 --> 06:38.280 Während wenn wir diese Sequenz von Aktionen ausgeführt haben, z.B. 06:39.020 --> 06:43.000 das rote Objekt und das blaue Objekt zur Seite geschoben haben, dann 06:43.000 --> 06:47.820 sieht man hier, dass wir eine kleine Passage geschafft haben vom 06:47.820 --> 06:53.000 Start, also Start ist dieser grüne Punkt hier, zum Ziel, um 06:53.000 --> 06:54.700 kollisionsfrei dorthin zu kommen. 06:54.820 --> 06:58.740 Das heißt, wir haben jetzt ein paar Konfigurationen vom Roboterarm 06:58.740 --> 07:03.780 gefunden, mit denen wir das Zielobjekt greifen können, ohne dass wir 07:03.780 --> 07:05.580 mit anderen Objekten hier kollidieren. 07:06.260 --> 07:12.120 Und natürlich, jede Änderung im Arbeitsraum hat auch oder ändert den 07:12.120 --> 07:12.580 Konfigurationsraum. 07:13.340 --> 07:16.420 Also man sieht hier die Situation, der Konfigurationsraum hier in 07:16.420 --> 07:19.500 dieser Situation sieht wie folgt aus. 07:19.700 --> 07:23.000 Das sind nur Täter 1 und Täter 2, jetzt nur ein Ausschnitt von dem 07:23.000 --> 07:23.580 Konfigurationsraum. 07:24.560 --> 07:29.500 Und wenn wir hier das rote Objekt verschoben haben und das blaue auch 07:29.500 --> 07:34.120 ein bisschen mehr nach hinten verschoben, dann sieht man, dass sogar 07:34.120 --> 07:38.120 diese Passage ein bisschen breiter ist, um vielleicht nicht nur 07:38.120 --> 07:41.780 irgendeine Trajektorie, sondern eine Trajektorie, die im Sinne von 07:41.780 --> 07:46.580 irgendeinem Optimalitätskriterium günstiger ist, berechnen können. 07:47.560 --> 07:49.000 So, einige Definitionen. 07:49.060 --> 07:54.260 Also mit Konfiguration Q wollen wir den Zustand eines Roboters und 07:54.260 --> 07:58.160 zwar als Gelenkwinkelvektor im Gelenkwinkelraum bezeichnen. 07:58.300 --> 08:02.920 Also wenn wir von Konfiguration reden, dann werden wir immer im 08:02.920 --> 08:04.960 Konfigurationsraum sein. 08:05.240 --> 08:09.080 Also nicht im Arbeitsraum, sondern im Gelenkwinkelraum des Roboters. 08:11.340 --> 08:14.840 Also im Gegensatz zu dem, was auf der Folie stand bei der letzten 08:14.840 --> 08:15.800 Vorlesung übrigens. 08:17.220 --> 08:20.320 Konfigurationsraum C eines Roboters ist der Raum aller möglichen 08:20.320 --> 08:21.980 Konfigurationen der Gelenkwinkel. 08:22.880 --> 08:27.540 Und manchmal, nicht oft eigentlich, es soll hier manchmal heißen, 08:27.540 --> 08:31.320 werden Bewegungen auch im Arbeitsraum geplant. 08:31.620 --> 08:35.860 Dann spricht man in dem Fall auch vom Konfigurationsraum, weil für 08:35.860 --> 08:40.820 einen mobilen Roboter plant man natürlich in XY und Alpha die 08:40.820 --> 08:45.860 Orientierung und nicht vielleicht in dem Raum der Umdrehungen der 08:45.860 --> 08:46.680 einzelnen Räder. 08:46.920 --> 08:47.840 Könnte man das machen? 08:48.260 --> 08:54.280 Beziehungsweise bei einer Drohne plant man natürlich auch in XYZ und 08:54.280 --> 08:57.580 nicht in den Umdrehungen der einzelnen Rotoren von der Drohne. 08:58.220 --> 09:02.300 Aber in dem Fall spricht man tatsächlich in der Literatur manchmal von 09:02.300 --> 09:07.280 Konfiguration und diese Konfiguration wäre in dem Fall Position und 09:07.280 --> 09:09.020 Orientierung vom Roboter. 09:09.200 --> 09:13.460 Im zweidimensionalen bei einem mobilen Roboter oder im 09:13.460 --> 09:17.360 dreidimensionalen oder sechsdimensionalen Raum, zum Beispiel bei einer 09:17.360 --> 09:17.720 Drohne. 09:18.680 --> 09:26.300 Der Arbeitsraumhindernis ist das eigentlich, ist dieser Block, dieser 09:26.300 --> 09:27.200 rote Block hier. 09:27.900 --> 09:31.480 Das heißt, es ist der Raum, welcher von einem Objekt im Arbeitsraum 09:31.480 --> 09:32.380 angenommen wird. 09:32.700 --> 09:36.660 Also zum Beispiel diese Schachtel hier könnte ein Hindernis hier 09:36.660 --> 09:39.980 darstellen und dann habe ich ein Hindernis im Arbeitsraum. 09:40.740 --> 09:45.980 Der Konfigurationsraumhindernis, das Konfigurationsraumhindernis sieht 09:45.980 --> 09:50.160 anders aus und zwar die Abbildung von diesem Arbeitsraumhindernis in 09:50.160 --> 09:51.300 den Konfigurationsraum. 09:51.880 --> 09:55.920 Also es sind alle Konfigurationen des Armes, die zu einer Kollision 09:55.920 --> 09:57.680 mit dem Objekt führen. 09:59.140 --> 10:05.340 Der Hindernisraum, beziehungsweise Obstakelraum, deshalb C OBS, ist 10:05.340 --> 10:09.620 die Menge aller Konfigurationsraumhindernisse, also die Vereinigung 10:09.620 --> 10:13.900 aller Konfigurationsraumhindernisse ergibt dann den Hindernisraum. 10:14.720 --> 10:17.420 Weitere Definitionen der Freiraum ist klar. 10:17.540 --> 10:20.860 Der Freiraum ist der gesamte Konfigurationsraum abgezogen 10:20.860 --> 10:25.860 Hindernisraum, beziehungsweise alle Konfigurationen, die zu keiner 10:25.860 --> 10:26.840 Kollision führen. 10:27.740 --> 10:31.880 Und der Aufwand für diese Berechnung von dem Freiraum ist ziemlich 10:31.880 --> 10:32.320 hoch. 10:32.580 --> 10:37.440 Also die ist exponentiell in der Anzahl von den Freiheitsgraden des 10:37.440 --> 10:37.920 Roboters. 10:37.920 --> 10:42.540 Also wenn N Anzahl der Freiheitsgrade des Roboters, zum Beispiel 8 und 10:42.540 --> 10:49.480 M Anzahl der Hindernisse, dann haben wir M hoch 8 als Komplexität für 10:49.480 --> 10:52.420 die Berechnung vom Freiraum. 10:54.380 --> 10:58.860 Und bei komplexeren Kinematiken, also wenn wir eine große Anzahl von 10:58.860 --> 11:03.240 Freiheitsgraden bei dem Roboter oder Freiheitsgrade, die sehr komplex 11:03.240 --> 11:07.640 zueinander angeordnet sind, dann kann man diesen Freiraum nicht so 11:07.640 --> 11:08.700 effizient berechnen. 11:09.260 --> 11:13.960 Aber man muss natürlich beachten, dass dieser Freiraum der Grundlage 11:13.960 --> 11:16.960 für die Berechnung aller kollisionsfreien Trajektorien ist, weil wir 11:16.960 --> 11:21.060 Sequenzen von Konfigurationen in diesem Raum suchen. 11:22.060 --> 11:26.580 Das heißt, für jede Aufgabe müssen wir diesen Freiraum berechnen. 11:27.160 --> 11:30.920 Und dieser Freiraum ändert sich, wie die Objekte in der Szene sind. 11:30.920 --> 11:33.860 Das heißt, wenn wir ein Objekt von A nach B abstellen, dann ändert 11:33.860 --> 11:37.080 sich der komplette Freiraum und müssen wir natürlich unsere 11:37.080 --> 11:40.220 Berechnungen neu starten. 11:40.920 --> 11:45.860 Es gibt aber hierzu approximative Methoden, mit denen man natürlich 11:45.860 --> 11:50.880 diesen Freiraum einfacher, also auf eine effizientere Art und Weise 11:50.880 --> 11:51.860 darstellen kann. 11:52.640 --> 11:58.040 Ganz triviales Beispiel, damit ihr nur so einen Eindruck davon habt, 11:58.040 --> 12:02.020 was es bedeutet, eigentlich den Freiraum oder auch Hindernisraum zu 12:02.020 --> 12:02.400 berechnen. 12:03.060 --> 12:06.200 Nehmen wir mal an, wir hätten einen Roboter mit zwei Gelenken, Theta 1 12:06.200 --> 12:12.860 und Theta 2, und wir haben nur ein einfach geformtes Hindernis. 12:13.400 --> 12:15.000 Ja, das ist dieses Objekt hier. 12:15.800 --> 12:21.580 Und man sieht eigentlich hier, dass wir, wenn Theta 1 kleiner als 45 12:21.580 --> 12:24.480 Grad hier, dass wir immer eine Kollision haben. 12:24.480 --> 12:29.740 Also wenn Theta 1 kleiner als 45 Grad, egal was Theta 2, was dieses 12:29.740 --> 12:32.940 Ellenbogengelenk macht, dann haben wir immer eine Kollision mit dem 12:32.940 --> 12:33.440 Hindernis. 12:34.260 --> 12:42.280 So, wenn Theta 1 größer als 45, also wir bewegen uns nach oben, dann 12:42.280 --> 12:46.920 haben wir natürlich manchmal Situationen, wo wir natürlich durch Theta 12:46.920 --> 12:51.020 2 kleiner als 90 Grad zu Kollisionen mit dem Objekt kommen, aber auch 12:51.020 --> 12:53.720 andere, wo wir keine Kollision mit dem Objekt haben. 12:53.720 --> 12:57.420 Wir können sicher, vielleicht ungefähr sicher, also approximativ 12:57.420 --> 13:04.080 sagen, dass wir bei Theta 2 größer als 90 Grad und Theta 1 größer als 13:04.080 --> 13:10.180 45 Grad, das ist Freiraum, aber Theta 1 größer als 45 und Theta 2 13:10.180 --> 13:15.180 kleiner als 90, da wissen wir eigentlich nicht genau, was passiert, 13:15.300 --> 13:18.720 weil das hängt ja von den Konfigurationen ab. 13:19.300 --> 13:22.080 Wenn wir das ein bisschen näher betrachten und ein paar 13:22.080 --> 13:24.900 Konfigurationen betrachten, also das heißt, diesen Bereich muss man 13:24.900 --> 13:28.460 genauer nochmal angucken und schauen, wo habe ich eigentlich Freiraum 13:28.460 --> 13:31.760 und wo habe ich einen Hindernisraum. 13:32.640 --> 13:35.940 Wenn wir das genauer angucken, also sehen wir mal, das ist der Punkt 13:35.940 --> 13:42.020 A, der Punkt A ist hier, das ist der Schnitt von diesen zwei Linien. 13:42.740 --> 13:47.180 Das ist ein Punkt B, gegeben durch die Konfiguration 45 und 0, also 13:47.180 --> 13:51.200 Theta 2 ist 0 und man sieht das ja gerade an der Grenze hier, also das 13:51.200 --> 13:55.960 ist der Punkt B, das ist der Punkt C, das ist auch eine 13:55.960 --> 14:00.040 kollisionsfreie Konfiguration, der Punkt C. 14:00.400 --> 14:03.880 Und das ist der Punkt D mit diesen Gelenkwinkelkonfigurationen, wie 14:03.880 --> 14:08.820 man sieht hier, Theta 1 ist größer als 45 und wenn Theta 2 70 ist, 14:09.020 --> 14:13.480 dann hätte ich angefangen an meine Kollisionen, also Theta 2 kleiner 14:13.480 --> 14:17.200 als 70, dann habe ich Kollisionen und das wäre der Punkt hier D. 14:17.200 --> 14:21.900 Und auf diese Art und Weise sieht man, dass man diese Räume ja 14:21.900 --> 14:26.480 rekursiv, iterativ mal in solchen Bereichen unterteilen kann, die 14:26.480 --> 14:31.740 kollisionfrei sind, beziehungsweise wo ich nicht weiß, ob dort 14:31.740 --> 14:34.060 Kollisionen vorhanden sind oder nicht. 14:34.180 --> 14:41.840 Also zum Beispiel der hellblaue Bereich hier, das ist approximiert in 14:41.840 --> 14:46.500 Kollision, beziehungsweise hier approximiert betrachtet ist es frei 14:46.500 --> 14:49.120 hier, der dunkelgrüne Bereich. 14:50.360 --> 14:56.440 Genau, wenn man das Ganze hier weiterführt, das war unser A hier und 14:56.440 --> 14:59.560 dann sieht man hier, dass man noch eine feinere Unterteilung hier in 14:59.560 --> 15:02.980 diesen Bereichen, in freien Bereichen beziehungsweise kollisionsfreien 15:02.980 --> 15:03.980 oder gemischten Bereichen. 15:04.580 --> 15:10.240 Das ist nur so ein triviales Beispiel mit zwei Gelenken und mit einem 15:10.240 --> 15:14.460 sehr einfachen Hindernis, von einer einfachen Geometrie und 15:14.460 --> 15:15.200 zweidimensional. 15:15.520 --> 15:17.580 Und da merkt man, das ist ja nicht ohnehin. 15:18.840 --> 15:22.100 Und jetzt stellt euch mal vor, Objekte komplexerer Geometrie, 15:22.260 --> 15:26.040 Roboterarmee mit sieben, acht Freiheitsgraden, also mit einer großen 15:26.040 --> 15:29.520 Anzahl von Freiheitsgraden, da sind diese Berechnungen natürlich nicht 15:29.520 --> 15:30.620 so trivial. 15:32.440 --> 15:35.480 Genau, das heißt, was ganz wichtig ist natürlich für die ganze 15:35.480 --> 15:41.340 Berechnung von kollisionsfreien Bewegungen, ist, dass wir eigentlich 15:41.340 --> 15:44.020 wissen, wie die Umgebung oder die Umwelt aussieht. 15:44.940 --> 15:49.120 Ja, und wenn wir exakte Modelle von den Objekten, von der Umgebung 15:49.120 --> 15:52.620 haben, dann ist die Sache natürlich relativ einfach. 15:52.980 --> 15:57.080 Ja, schnelle Rechner und die können rechnen und Freiraum, 15:57.520 --> 16:04.380 Kollisionsraum, Asternsuche, Rapidly Exploring Random Trees, wie wir 16:04.380 --> 16:06.360 sehen werden und dann hat man eine Lösung. 16:06.360 --> 16:07.660 Aber das ist nicht immer der Fall. 16:08.100 --> 16:11.480 Also die Umweltmodellierung ist entscheidend, exakt. 16:11.680 --> 16:15.640 Das heißt, ich habe eine sehr genaue Beschreibung von allen Objekten 16:15.640 --> 16:20.600 in der Szene und von dem Roboter selber, zum Beispiel mit Constructed 16:20.600 --> 16:26.500 Solid Geometry, also konstruktive Festkörper Geometrie, wo komplex 16:26.500 --> 16:31.540 geformte Objekte aus Grundprimitiven, also wie Kugeln, Zylinder, 16:31.840 --> 16:37.060 Pyramiden, Ringe und so weiter und so fort, als Kombination von 16:37.060 --> 16:40.620 solchen Grundprimitiven dargestellt werden, mithilfe von logischen 16:40.620 --> 16:41.580 Operatoren. 16:42.240 --> 16:46.600 Und die andere Variante, ich habe ja eine Näherung eigentlich von der 16:46.600 --> 16:49.840 Umgebung, beziehungsweise von der Umwelt, zum Beispiel ich 16:49.840 --> 16:55.320 approximiere jetzt hier diesen Bereich hier in der Szene durch einen 16:55.320 --> 16:59.580 Würfel und nicht die Details von diesem Overhead-Projektor. 17:00.460 --> 17:01.220 Genau. 17:02.540 --> 17:07.700 Weitere Grundlagen, die für uns interessant sind, sind einmal diese 17:07.700 --> 17:11.140 Begrifflichkeiten, Pferdplanung, das heißt, ich habe ein starres 17:11.140 --> 17:14.940 Objekt und wir betrachten tatsächlich nur starre Objekte hier und 17:14.940 --> 17:18.920 starre oder nicht deformierbare Objekte. 17:19.680 --> 17:23.620 Wir haben einen mobilen Roboter oder ein autonomes Fahrzeug für die 17:23.620 --> 17:24.740 Pferdplanung. 17:25.100 --> 17:29.480 Das ist ein 2D-Problem, das heißt XYZ- beziehungsweise 3D-Problem, 17:29.580 --> 17:31.880 wenn wir die Orientierung auch berücksichtigen. 17:32.520 --> 17:35.500 Und das ist das Piano-Movement-Problem. 17:35.820 --> 17:40.600 Das heißt, wir müssen schauen, wie wir das Objekt hier durch Passagen 17:40.600 --> 17:45.960 und in dem Freiraum in der Wohnung, also das Piano beziehungsweise ein 17:45.960 --> 17:48.160 Möbelstück hier verschieben können. 17:49.560 --> 17:53.560 Bewegungsplanung, also Pferdplanung für 2D-Probleme, beziehungsweise 17:53.560 --> 17:56.640 3D, wenn wir die Orientierung berücksichtigen von dem Fahrzeug. 17:57.760 --> 18:01.500 Und Bewegungsplanung bezieht sich auf Mehrkörpersysteme, also zum 18:01.500 --> 18:06.360 Beispiel Roboterarmee, Systeme mit mehreren Robotern, also Zwei-Arm 18:06.360 --> 18:10.800 -Systeme oder mehrere Roboter mit einzelnen oder mehreren Armen. 18:11.540 --> 18:15.750 Und das sind hochdimensionale Problemstellungen, weil wenn wir jetzt 18:15.750 --> 18:21.330 den Arme zum Beispiel 6 nehmen mit 8 Freiheitsgraden pro Arm, dann 18:21.330 --> 18:23.590 haben wir insgesamt 16 für beide Arme. 18:24.110 --> 18:27.550 Wir haben ein Teleskopgelenk, das heißt 17, und wir haben 3 18:27.550 --> 18:31.330 Freiheitsgrade für die mobile Basis, also insgesamt 20. 18:31.550 --> 18:34.210 Und dann müssen wir in diesem Raum planen für andere Roboter, zum 18:34.210 --> 18:37.950 Beispiel der Arme 3 im Konfigurationsraum 43. 18:38.950 --> 18:43.430 So, die Randbedienungen, auch Zwangsbedienungen genannt, da 18:43.430 --> 18:47.170 unterscheidet man bei diesen Randbedienungen zwischen globalen und 18:47.170 --> 18:48.550 lokalen Randbedienungen. 18:48.690 --> 18:55.250 Und die globalen Randbedienungen limitieren den gültigen 18:55.250 --> 19:00.870 Konfigurationsraum, zum Beispiel aufrechte Position vom Endeffektor, 19:00.870 --> 19:03.870 zum Beispiel die minimalen Motorströme. 19:04.470 --> 19:09.490 Und die lokalen Randbedienungen schränken die Übergänge zwischen 19:09.490 --> 19:13.990 Konfigurationen, also zum Beispiel nichtholonome Fahrzeuge, die können 19:13.990 --> 19:18.270 sich nicht zur Seite bewegen, sondern die müssen wie ein Auto 19:18.270 --> 19:22.670 geradeaus und dann lenken, um an eine Zielposition und Orientierung 19:22.670 --> 19:23.290 anzukommen. 19:24.250 --> 19:27.030 Oder die können sich nicht auch auf der Stelle drehen. 19:28.710 --> 19:31.850 Weitere lokale Randbedienungen sind zum Beispiel die maximalen 19:31.850 --> 19:36.070 Geschwindigkeiten und Beschleunigungen, die eingehalten werden müssen. 19:37.010 --> 19:41.610 Die Komplexität von dem Problem, von dem Bewegungsplanungsproblem, ist 19:41.610 --> 19:49.070 ein P-Space Komplett oder ist P-Space vollständig. 19:49.410 --> 19:55.170 Das heißt, diese Probleme können von deterministischen Turing 19:55.170 --> 20:02.090 -Maschinen erst mit polynomialem Platzbedarf gelöst bzw. 20:02.310 --> 20:03.030 entschieden werden. 20:03.230 --> 20:06.150 Und damit man weiß, was das bedeutet, wir wissen vielleicht als 20:06.150 --> 20:11.630 Informatiker, was das MPE-vollständige oder MPE-harte Probleme sind. 20:12.210 --> 20:20.070 Und diese P-Space-harte Probleme, muss das Wort hier korrigiert 20:20.070 --> 20:24.990 werden, P-Space-harte Probleme sind eigentlich, oder diese MPE 20:24.990 --> 20:28.870 -vollständige Probleme sind nur eine Untermenge von P-Space-harten 20:28.870 --> 20:29.410 Problemen. 20:30.070 --> 20:34.850 So, weitere Begriffe, die wir auch das letzte Mal angeguckt haben. 20:35.030 --> 20:38.530 Wir haben Unterschiede zwischen einem vollständigen Algorithmus und 20:38.530 --> 20:40.730 zum Beispiel einem randomisierten Algorithmus. 20:40.910 --> 20:44.850 Mit vollständigen Algorithmen verstehen wir oder unter vollständigen 20:44.850 --> 20:50.010 Algorithmen verstehen wir Planungsprobleme oder Algorithmen, die 20:50.010 --> 20:55.430 Planungsprobleme lösen und die zwar mindestens eine Lösung finden bzw. 20:55.850 --> 20:58.710 in endlicher Zeit erkennen, dass es keine Lösung gibt. 20:59.170 --> 21:04.010 Das ist natürlich sehr vorteilhaft, wenn ich jetzt eine Lösung suche 21:04.010 --> 21:07.690 für ein bestimmtes Problem und ich habe irgendwelche Zeitvorgaben als 21:07.690 --> 21:10.930 Randbedienungen, ich muss die Lösung innerhalb von ein paar 21:10.930 --> 21:15.370 Millisekunden oder einer Sekunde finden, dann ist es wertvoll zu 21:15.370 --> 21:21.090 wissen, ich werde eine Lösung finden oder innerhalb dieser Zeit kann 21:21.090 --> 21:25.790 ich Aussagen darüber machen, dass keine Lösung hier existiert. 21:26.770 --> 21:31.430 Randomisierte Algorithmen, die benutzen Zufallsgrößen und wir werden 21:31.430 --> 21:34.810 einige von denen hier kennenlernen in der Vorlesung, zum Beispiel der 21:34.810 --> 21:39.650 Rapidly Exploring Random Tree, randomisiert die Zufallsgrößen, um den 21:39.650 --> 21:47.690 Ablauf bei der Bestimmung von einer kollisionsfreien Bahn zu 21:47.690 --> 21:53.210 berechnen, ja, also benutzen Zufallsgrößen bei der Bestimmung von 21:53.210 --> 21:57.310 einer kollisionsfreien Bahn und oft verwenden sie auch Heuristiken, um 21:57.310 --> 22:02.510 die Suche nach dieser Bahn zu beschleunigen, also um die Berechnung 22:02.510 --> 22:04.990 eigentlich, wenn es Suche ist, zu beschleunigen. 22:04.990 --> 22:09.390 Dann gibt es sogenannte auflösungsvollständige Algorithmen und das 22:09.390 --> 22:12.610 sind Algorithmen, bei denen man nicht von kontinuierlichen 22:12.610 --> 22:15.450 Problemstellungen ausgeht, also dass man jetzt die komplette 22:15.450 --> 22:20.290 Beschreibung der Umgebung kontinuierlich, sondern eine diskrete bzw. 22:21.250 --> 22:26.050 quantisierte Darstellung der Umgebung und je nachdem, wie groß diese 22:26.050 --> 22:28.550 Auflösung, mit der man das darstellt bzw. 22:28.830 --> 22:31.670 wie groß die Auflösung, mit der man zwischen Konfigurationen 22:31.670 --> 22:36.950 umschalten kann, hat man einen anderen approximativen Algorithmus, 22:37.150 --> 22:40.930 also die sind jetzt nicht genau, sondern approximate Algorithmen und 22:40.930 --> 22:46.010 die nennt man in dem Fall auflösungsvollständige Planungsalgorithmen. 22:46.830 --> 22:51.570 Und die vierte Variante sind sogenannte probabilistisch vollständige 22:51.570 --> 22:56.790 Algorithmen und solche Algorithmen finden mindestens eine Lösung, 22:56.970 --> 22:57.970 falls sie existiert. 22:57.970 --> 23:03.630 Das heißt, die Wahrscheinlichkeit, dass eine Lösung gefunden wird, 23:03.750 --> 23:07.110 konvergiert mit der Zeit gegen eins. 23:07.490 --> 23:12.510 Allerdings können wir keine Aussagen darüber treffen oder können diese 23:12.510 --> 23:15.350 Algorithmen keine Aussagen darüber treffen, wenn es keine Lösung 23:15.350 --> 23:16.030 existiert. 23:16.130 --> 23:21.450 Also im Vergleich der vollständigen Algorithmen, die sowas machen 23:21.450 --> 23:21.730 können. 23:23.230 --> 23:26.290 Wenn man das Ganze hier zusammenfassen will, dann haben wir 23:26.290 --> 23:30.930 unterschiedliche Schwierigkeitsgrade des Problems der 23:30.930 --> 23:35.890 Bewegungsplanung, also des Auffindens einer kollisionsfreien Bahn von 23:35.890 --> 23:38.590 einer Startkonfiguration zu einer Zielkonfiguration. 23:38.750 --> 23:40.310 So haben wir das Problem definiert. 23:42.910 --> 23:46.430 Und vielleicht der einfachste Fall ist, wenn wir ein vollständiges 23:46.430 --> 23:51.050 Modell der Umgebung haben, das heißt mit vollständiger Spezifikation 23:51.050 --> 23:53.150 von Nebenrand- und Zwangsbedienungen. 23:53.590 --> 23:56.410 Und natürlich suchen wir eine kollisionsfreie Trajektorie und wir 23:56.410 --> 24:00.370 werden hier Methoden kennenlernen in diesem Kapitel, wie wir das 24:00.370 --> 24:03.350 bestimmen, wenn alles vorgegeben und vollständig bekannt ist. 24:03.770 --> 24:05.550 Aber das muss nicht immer der Fall sein. 24:05.810 --> 24:08.710 Also es kann sein, dass wir ein unvollständiges Umweltmodell haben. 24:09.550 --> 24:12.630 Beispielsweise es kommen neue Objekte dazu auf den Tisch und der 24:12.630 --> 24:16.270 Roboter soll trotzdem kollisionsfrei die Zielobjekte manipulieren und 24:16.270 --> 24:19.710 diese neuen Objekte sind nicht modelliert und nicht Teil vom 24:19.710 --> 24:20.610 Umweltmodell. 24:21.150 --> 24:27.410 Wir haben auch kein komplettes Kenntnis über Neben- und Rand- und 24:27.410 --> 24:28.410 Zwangsbedienungen. 24:29.410 --> 24:34.330 Und natürlich das Problem, das man hier hat, dass man Kollisionen mit 24:34.330 --> 24:39.210 unbekannten Objekten berücksichtigen muss, beim Lösen des Problems. 24:39.330 --> 24:44.570 Also es ist nicht nur etwas Festes gegeben, eine Konfiguration und ich 24:44.570 --> 24:49.010 habe meinen Freiraum, Kollisionsraum berechnet und ich suche in dem 24:49.010 --> 24:53.790 Freiraum eine kollisionsfreie Trajektorie, sondern durch neue Objekte 24:53.790 --> 24:59.570 oder durch unbekannte Teile vom Objektmodell kann es natürlich zu 24:59.570 --> 25:06.690 Kollisionen kommen, wenn diese unbekannten Teile nicht berücksichtigt 25:06.690 --> 25:06.970 werden. 25:07.910 --> 25:10.210 Also ein bisschen schwieriger als die Klasse A. 25:10.350 --> 25:16.330 Die Klasse C, wir haben zwar ein Umweltmodell, das kennen wir, aber 25:16.330 --> 25:17.950 der verändert sich mit der Zeit. 25:19.170 --> 25:23.030 Das heißt, unser Ziel ist immer eine kollisionsfreie Trajektorie vom 25:23.030 --> 25:28.570 Start zum Ziel und hier haben wir also Hindernisse, die Varianten 25:28.570 --> 25:34.290 sind, deren Zustand sich verändert in Ort und in Zeit. 25:35.150 --> 25:38.910 Und man kann sich vorstellen, dass die Sache hier weitergeht, wenn wir 25:38.910 --> 25:42.210 überhaupt kein Umweltmodell haben, dann müssen wir natürlich für die 25:42.210 --> 25:45.270 Suche nach einer kollisionsfreien Bewegung zunächst mal so ein 25:45.270 --> 25:48.410 Umweltmodell uns schaffen. 25:48.990 --> 25:57.110 Das heißt, man muss die Umgebung kartografieren, also Rekonstruktionen 25:57.110 --> 26:00.230 von allem, was man in der Szene sieht und dann natürlich in dieser 26:00.230 --> 26:04.470 gewonnenen Rekonstruktion oder mithilfe von diesem gewonnenen Modell 26:04.470 --> 26:08.010 die kollisionsfreie Trajektorie berechnen. 26:08.830 --> 26:12.610 Und die Klasse E, vielleicht das Schwierigste, wir haben ein 26:12.610 --> 26:19.990 zeitvariantes Umweltmodell und wir suchen eine Trajektorie zu einem 26:19.990 --> 26:21.290 bewegten Objekt. 26:21.290 --> 26:30.690 Das heißt, es ist zum Beispiel ein Roboterarm, wo der Roboter fährt 26:30.690 --> 26:34.790 und Objekte auf einem Fließband, die sich auch bewegen, greifen 26:34.790 --> 26:35.150 müssen. 26:35.650 --> 26:38.730 Oder man kann sich vorstellen, eine Rakete, die vielleicht irgendwas 26:38.730 --> 26:41.330 mal verfolgt, was auch fliegt. 26:41.450 --> 26:44.470 Eine Drohne, die eine andere Drohne beispielsweise verfolgt. 26:44.470 --> 26:51.970 Das heißt, Zielzustand, also Ziel, unser Kuhziel ist sowohl 26:51.970 --> 26:55.990 veränderlich im Ort und in der Zeit. 26:56.770 --> 27:00.690 So, das sind die unterschiedlichen Klassen von den Problemen und wir 27:00.690 --> 27:04.770 werden uns natürlich nicht mit all diesen Klassen hier beschäftigen. 27:05.030 --> 27:09.370 Wir werden davon ausgehen, dass wir ein Umweltmodell haben, das heißt, 27:09.530 --> 27:11.090 das steht uns zur Verfügung. 27:11.770 --> 27:15.490 In anderen Vorlesungen, zum Beispiel in Robotik 3, werden wir sehen, 27:15.570 --> 27:20.850 wie wir solche Umweltmodelle aus Bilddaten oder Tiefenbilder oder 27:20.850 --> 27:25.590 hauptsächlich aus Bilddaten erstellen können. 27:25.850 --> 27:29.750 Also zum Beispiel mit Slam-Methoden und ähnliches, aber das soll jetzt 27:29.750 --> 27:33.550 hier euch nicht beschäftigen, sondern wir haben ein Umweltmodell und 27:33.550 --> 27:38.630 wir wollen jetzt in diesem Umweltmodell unsere kollisionsfreien Bahnen 27:38.630 --> 27:39.230 planen. 27:39.230 --> 27:42.990 Und als erstes, wie ich bereits erwähnt habe, wollen wir das für 27:42.990 --> 27:49.070 mobile Roboter machen und wir wollen hier zwei Klassen von Methoden 27:49.070 --> 27:49.750 kennenlernen. 27:49.970 --> 27:55.090 Einmal grafenbasierte Methoden, das werden wir heute kennenlernen und 27:55.090 --> 28:00.290 das nächste Mal machen wir weiter mit Potentialfeldmethoden und in den 28:00.290 --> 28:04.990 nächsten Vorlesungen mit Bewegungsplanung für Mehrkörpersysteme, also 28:04.990 --> 28:06.370 für Manipulatoren. 28:07.830 --> 28:13.330 Wie ist das Problem definiert für die Fahrtplanung für einen mobilen 28:13.330 --> 28:13.710 Roboter? 28:13.910 --> 28:17.570 Wir haben ein 2D-Weltmodell, also es ist gegeben, zum Beispiel eine 28:17.570 --> 28:20.930 Straßenkarte, auch von einem Auto, nicht unbedingt von einem Roboter, 28:21.850 --> 28:25.590 Start - und Zielkonfiguration und wir suchen die günstigste Verbindung 28:25.590 --> 28:30.470 vom Start zum Ziel, also zum Beispiel die kürzeste Verbindung bzw. 28:31.090 --> 28:33.870 vielleicht die schnellste Verbindung, die nicht immer die kürzeste 28:33.870 --> 28:36.390 ist, weil man irgendwelche Probleme unterwegs hat. 28:37.230 --> 28:42.230 Und die zentrale Idee bei all diesen Algorithmen, die wir kennen, ist 28:42.230 --> 28:48.350 zunächst mal ein Netz zu erstellen oder einen Graphen zu erstellen, 28:48.350 --> 28:55.970 der für uns tatsächlich kollisionsfreie Punkte definiert, die wir 28:55.970 --> 29:00.830 annehmen können oder die ein Roboter oder ein Auto annehmen kann, beim 29:00.830 --> 29:04.290 Versuchen vom Start zum Ziel zu kommen. 29:04.290 --> 29:11.010 Also zunächst mal, man konstruiert ein Netz von Wegen in Zephri. 29:11.370 --> 29:12.810 Also was bedeutet das? 29:12.890 --> 29:19.350 Es bedeutet eigentlich, ich mache mal ein 2D-Beispiel. 29:21.690 --> 29:27.270 Nehmen wir mal an, wir haben unseren Konfigurationsraum hier und wir 29:27.270 --> 29:30.890 haben hier ein paar Hindernisse, wie die Baustellen in Karlsruhe, die 29:30.890 --> 29:33.830 man nicht durchfahren kann. 29:34.910 --> 29:39.530 Und die Aufgabe besteht darum, dass wir zunächst mal irgendein Wegnetz 29:39.530 --> 29:43.730 im freien Raum, also das ist unser Hindernisraum und weiß ist unser 29:43.730 --> 29:44.410 Freiraum. 29:44.410 --> 29:50.010 Und was hier auf der Folie steht, wir müssen so irgendeinen Graphen 29:50.010 --> 29:50.510 bilden. 30:04.280 --> 30:09.260 Wir müssen einen Graphen bilden und mithilfe von diesem Graphen 30:09.260 --> 30:12.960 beliebige Planungsprobleme durchführen. 30:12.960 --> 30:17.580 Also das heißt, im nächsten Schritt, wenn wir vom Q-Start nach Q-Ziel 30:17.580 --> 30:19.920 gehen wollen, also nehmen wir mal an, 30:24.080 --> 30:31.540 das ist unser Ziel und das ist hier unser Start. 30:34.970 --> 30:40.570 Man bildet den Q-Start und den Q-Ziel auf den nächsten Knoten in 30:40.570 --> 30:42.290 diesem Graphen ab. 30:42.530 --> 30:47.590 Das heißt eigentlich, man sucht mit anderen Worten den nächsten 30:47.590 --> 30:52.590 Nachbarn, also praktisch den nächsten Knoten in diesem Graphen, der am 30:52.590 --> 30:55.410 nächsten zu diesen zwei Punkten ist. 30:55.410 --> 31:01.050 Also das wäre zum Beispiel der hier, ja, Z-Strich und das wäre jetzt 31:01.050 --> 31:02.070 hier S-Strich. 31:03.550 --> 31:08.370 Und dann sucht man einen Pfad in diesem Graphen zwischen S-Strich und 31:08.370 --> 31:14.190 C -Strich und nehmen wir mal an, das wäre jetzt hier der Weg, den wir 31:14.190 --> 31:15.010 gefunden haben. 31:15.010 --> 31:19.590 Und anschließend muss man natürlich einen Weg für diese kurzen 31:19.590 --> 31:24.730 Strecken hier finden, also zwischen Z-Strich und Z-Strich und zwischen 31:24.730 --> 31:26.990 S -Strich und S-Strich. 31:27.810 --> 31:31.670 Weil natürlich diese Abbildung, die wird nicht immer so sein, dass man 31:31.670 --> 31:36.090 direkt auf einen Punkt in diesem Wegenetz kommt, sondern man wird den 31:36.090 --> 31:41.230 nächsten Nachbarn oder den nächsten Punkt auf dem Graphen nehmen und 31:41.230 --> 31:44.630 das ist eigentlich die komplette, also das ist alles, was wir 31:44.630 --> 31:45.370 verstehen müssen. 31:45.370 --> 31:48.830 Das heißt, was sind die Probleme hier, die wir haben? 31:49.170 --> 31:53.770 Also natürlich brauchen wir den Freiraum und den Hindernisraum, aber 31:53.770 --> 31:58.830 das Hauptproblem, das wir hier haben, ist, dieses Netz zu erstellen, 31:59.490 --> 32:03.310 also diesen Graphen zu erstellen und dann auf dem Graphen mit 32:03.310 --> 32:09.370 bekannten Suchmethoden, also Wegsuchmethoden, eine Bahn oder eine 32:09.370 --> 32:12.010 Verbindung vom Start zum Ziel finden. 32:12.830 --> 32:16.330 So, und hier wollen wir eine ganze Menge von Methoden kennenlernen, 32:16.510 --> 32:20.330 wie wir dieses Wegenetz W berechnen. 32:20.490 --> 32:23.690 Und da gibt es hier eine ganze Menge von Methoden, zum Beispiel 32:23.690 --> 32:26.990 Vorneudiagramme, Sichtgrafen bzw. 32:28.470 --> 32:29.030 Zellenzerlegung. 32:29.030 --> 32:33.590 Und für das zweite Hauptproblem, wenn wir diesen Graphen erstellt 32:33.590 --> 32:36.910 haben, müssen wir natürlich in diesem Graphen jetzt einen Weg suchen, 32:37.070 --> 32:42.210 zum Beispiel mit der Baumsuche oder mit dem beliebten und bekannten A 32:42.210 --> 32:43.130 -Stern -Algorithmus. 32:44.090 --> 32:46.670 Und wir fangen an mit Vorneudiagrammen. 32:48.270 --> 32:53.670 Vorneudiagramme visualisieren die Zerlegung eines Raumes in Regionen, 32:54.030 --> 32:56.070 basierend auf vorgegebenen Punkten. 32:56.210 --> 32:59.170 Das heißt, wir haben hier ein paar vorgegebene Punkte. 32:59.170 --> 33:02.010 Normalerweise sind diese Punkte die Hindernisse, stellen die 33:02.010 --> 33:02.950 Hindernisse dar. 33:03.770 --> 33:06.830 Also wir gehen von punktförmigen Hindernissen aus. 33:06.970 --> 33:09.550 Natürlich, wenn die Hindernisse bestimmte Auslehnungen haben, dann 33:09.550 --> 33:13.390 muss man das verallgemeinern oder entsprechend betrachten. 33:13.390 --> 33:18.150 Und eine Region, also zum Beispiel diese Region hier von einem 33:18.150 --> 33:23.870 Vorneudiagramm, ist definiert als die Menge aller Punkte hier, deren 33:23.870 --> 33:34.370 Abstand zu diesem Hindernis geringer ist als zu allen benachbarten 33:34.370 --> 33:34.760 Hindernissen. 33:34.760 --> 33:38.280 Also der Abstand hier von diesen Punkten zu diesem Hindernis ist 33:38.280 --> 33:41.920 geringer als zu dem oder geringer als zu dem und geringer als zu dem. 33:42.520 --> 33:44.120 Was bedeutet eigentlich das? 33:44.280 --> 33:48.120 Das bedeutet, dass alle Punkte, die auf der Grenze liegen, also auf 33:48.120 --> 33:52.800 diesen grünen geraden Linien liegen, haben den gleichen Abstand zum 33:52.800 --> 33:55.040 eigenen und zum benachbarten Hindernis. 33:55.040 --> 33:59.880 Das heißt, die Punkte auf diesen Geraden hier haben den gleichen 33:59.880 --> 34:04.020 Abstand zu diesem Punkt und zu diesem Punkt, die Punkte auf diesen 34:04.020 --> 34:07.220 Geraden haben den gleichen Abstand zu diesem Punkt und zu diesem Punkt 34:07.220 --> 34:09.960 und die Punkte auf diesen Geraden haben den gleichen Abstand zu diesem 34:09.960 --> 34:11.940 Punkt und zu diesem Punkt und so weiter und so fort. 34:11.940 --> 34:15.740 Und die Frage ist, wie baut man dieses Voronoi-Diagramm? 34:16.600 --> 34:22.240 Nehmen wir an, man hat solche Punkte, P, also eine Menge von 34:22.240 --> 34:25.160 Hindernissen gegeben hier. 34:25.300 --> 34:28.520 Das sind fünf Punkte, wie man sieht, und die Punkte stellen 34:28.520 --> 34:31.180 Hindernisse dar in diesem Kontext. 34:31.940 --> 34:35.500 Und was man macht, man unterteilt diese Punkte zunächst mal in etwa 34:35.500 --> 34:37.020 gleich große Teilmengen. 34:37.780 --> 34:41.680 Also man sieht hier durch eine Linie, dann habe ich eine Teilmenge P1 34:41.680 --> 34:45.480 und eine Teilmenge P2, also einmal mit drei und einmal mit zwei 34:45.480 --> 34:45.860 Punkten. 34:47.040 --> 34:55.600 Und das macht man rekursiv, bis man am Ende entweder zwei Punkte oder 34:55.600 --> 34:56.600 drei Punkte hat. 34:57.220 --> 35:02.320 Also natürlich durch sukzessive oder rekursive Unterteilung hier kommt 35:02.320 --> 35:05.220 man bis zu diesem Punkt, also wenn ich jetzt mehr als fünf Punkte 35:05.220 --> 35:05.520 habe. 35:06.300 --> 35:09.320 Aber hier in dem Beispiel sehen wir, dass wir schon dort sind. 35:09.520 --> 35:12.940 Wir haben einen Fall, wo wir zwei Punkte und einen Fall, wo wir drei 35:12.940 --> 35:13.340 Punkte haben. 35:13.380 --> 35:16.160 Wenn ich mehr Punkte habe, kann ich diese Unterteilung so 35:16.160 --> 35:20.260 weitermachen, dass ich zu dieser Situation oder zu diesen 35:20.260 --> 35:21.520 Konfigurationen lande. 35:22.460 --> 35:25.880 Und also durch diese rekursive Unterteilung der Punktmengen kann das 35:25.880 --> 35:29.700 Problem der Erstellung eines Voronoi-Programm auf zwei einfache Fälle 35:29.700 --> 35:30.680 reduziert werden. 35:30.680 --> 35:36.900 Fall 1, ich habe zwei Punkte und die Kante von einem Voronoi-Diagramm 35:36.900 --> 35:41.040 hat den gleichen Abstand zu beiden Punkten, zu beiden Hindernissen. 35:41.280 --> 35:46.380 Das ist also nichts anderes als die Mittelsenkrechte auf die 35:46.380 --> 35:48.680 Verbindungslinie zwischen diesen zwei Punkten. 35:49.720 --> 35:53.580 Also ich verbinde diese zwei Punkte und in der Mitte habe ich die 35:53.580 --> 35:57.560 Senkrechte drauf und das ist ja eine Kante von meinem Voronoi 35:57.560 --> 36:01.630 -Diagramm, was mir sagt, okay, alle Punkte auf dieser Linie haben den 36:01.630 --> 36:03.290 gleichen Abstand zu beiden Hindernissen. 36:03.890 --> 36:06.830 Das Gleiche natürlich bei einem Fall von drei Punkten. 36:07.150 --> 36:11.590 Ich verbinde die Punkte miteinander, ich bilde die Mittelsenkrechten 36:11.590 --> 36:14.030 und schneide sie ab. 36:14.690 --> 36:17.610 Das heißt, sie gehen hier weiter und weiter und weiter. 36:18.130 --> 36:20.850 Aber ich schneide sie an der Stelle hier und dann habe ich einen Teil 36:20.850 --> 36:26.040 von meinem Voronoi-Diagramm und da sieht man hier, dass diese zwei 36:26.040 --> 36:30.400 Punkte den gleichen Abstand zu dieser Linie haben, diese zwei Punkte 36:30.400 --> 36:34.620 den gleichen Abstand und diese zwei Punkte den gleichen Abstand zu 36:34.620 --> 36:35.160 dieser Linie. 36:36.700 --> 36:43.400 Wenn wir das machen in unserem Beispiel, dann bekommen wir so etwas 36:43.400 --> 36:43.640 hier. 36:43.800 --> 36:46.560 Das sind die drei Punkte und das haben wir gemacht mit den 36:46.560 --> 36:50.660 Mittelsenkrechten und dann abschneiden und hier Mittelsenkrechte auf 36:50.660 --> 36:53.320 die Verbindungslinie für die Punkte in P2. 36:54.160 --> 36:57.800 Aber wir haben noch kein komplettes zusammenhängendes Voronoi 36:57.800 --> 36:58.420 -Diagramm. 36:58.980 --> 37:03.900 Was man jetzt noch machen muss, man muss die Punkte am Rand, also 37:03.900 --> 37:10.180 entlang der Trennebene oder der Trennlinien, wo wir getrennt haben, 37:10.740 --> 37:12.420 verbindet man die Punkte miteinander. 37:12.420 --> 37:16.220 Also wir haben hier getrennt, also das ist hier ein Nachbar von dem 37:16.220 --> 37:19.500 und das ist ein Nachbar von dem und das ist hier ein Nachbar von dem 37:19.500 --> 37:22.980 und wenn wir sie miteinander verbinden, dann haben wir auch diese 37:22.980 --> 37:28.660 Linien, dann bilden wir nochmal die Mittelsenkrechten und schneiden 37:28.660 --> 37:29.320 wir ab. 37:29.700 --> 37:34.520 Also Mittelsenkrechte hier, die schneidet den Rest an der Stelle, 37:35.020 --> 37:36.760 alles andere eliminieren wir. 37:36.760 --> 37:40.620 Die Mittelsenkrechte hier schneidet die zwei hier und die 37:40.620 --> 37:45.940 Mittelsenkrechte hier schneidet das hier und wenn wir alle diese 37:45.940 --> 37:50.700 Linien wegtun, dann haben wir eigentlich unser Voronoi-Diagramm, das 37:50.700 --> 37:51.920 wir gesucht haben. 37:52.880 --> 37:54.120 So, was bedeutet das? 37:54.300 --> 37:59.480 Das bedeutet eigentlich, ich weiß, ich habe sehr sichere Linien oder 37:59.480 --> 38:02.460 Bahnen, entlang deren ich fahren kann. 38:03.820 --> 38:09.360 Weil wenn ich jetzt hier beispielsweise von einem Punkt hier, also man 38:09.360 --> 38:13.700 könnte jetzt hier das Problem nochmal veranschaulichen, das heißt, 38:13.820 --> 38:15.800 wenn ich jetzt hier die Aufgabe hätte, 38:20.390 --> 38:26.750 ich soll von Start hier zum Ziel hier kommen. 38:28.470 --> 38:30.310 Ja, was bedeutet unser Problem? 38:30.830 --> 38:35.190 Also das sind unsere Punkte, wir müssen diese Punkte auf irgendwelche 38:35.190 --> 38:37.750 Punkte auf unserem Netz abbilden. 38:38.610 --> 38:45.170 Also zum Beispiel hier, der nächste Punkt ist S-Strich, hier wäre das 38:45.170 --> 38:50.070 Z -Strich und dann kann ich meine kollisionsfreie Trajektorie planen 38:50.070 --> 38:55.490 von S-Strich zu Z-Strich und natürlich, wie man sieht hier, damit ist 38:55.490 --> 38:58.630 die Sache nicht getan, sondern ich brauche so ein bisschen einen 38:58.630 --> 39:05.230 lokalen Planer, der natürlich Z mit Z-Strich und S mit S-Strich 39:05.230 --> 39:07.730 verbindet, damit ich wirklich vom Start zum Ziel komme. 39:11.160 --> 39:15.440 Und wenn man das macht, dann hat man natürlich eine Garantie, dass man 39:15.440 --> 39:18.180 immer mit dem maximalen Abstand zu den Hindernissen fährt. 39:18.400 --> 39:22.600 Also das wäre natürlich die Bahn, die einzige Bahn, die uns vom Start 39:22.600 --> 39:27.940 zum Ziel bringt und überall haben wir den maximalen Abstand zu 39:27.940 --> 39:28.400 Hindernissen. 39:29.300 --> 39:33.940 So, das ist noch ein weiteres Beispiel, also keine punktförmigen 39:33.940 --> 39:38.520 Hindernisse, sondern Hindernisse mit einer bestimmten Ausdehnung, also 39:38.520 --> 39:40.820 die schwarzen Bereiche sind hier die Hindernisse. 39:41.700 --> 39:44.400 Und wenn wir praktisch hier diese Vorhinein-Diagramme bilden, dann 39:44.400 --> 39:45.380 bekommen wir sowas. 39:45.580 --> 39:50.080 Also man sieht hier, das sind ja keine geradlinigen Linien, weil da 39:50.080 --> 39:56.900 müssen wir immer den Abstand, also dieser Punkt hier muss natürlich 39:56.900 --> 40:03.740 den gleichen Abstand zu dem und zu dem haben, und deshalb ist es nicht 40:03.740 --> 40:09.640 notwendigerweise eine Linie, sondern das können ja gekrümmte Kurven 40:09.640 --> 40:10.020 sein. 40:11.100 --> 40:15.000 Und für diesen Konfigurationsraum oder beziehungsweise in diesem 40:15.000 --> 40:19.200 Freiraum, mit diesem Hindernisraum hier, bekommen wir diesen Vorhinein 40:19.200 --> 40:19.820 -Diagramm. 40:20.280 --> 40:23.400 Und wir wissen, wenn wir uns entlang dieser Linien bewegen, dann haben 40:23.400 --> 40:26.520 wir immer den maximalen Abstand zu den Hindernissen. 40:26.520 --> 40:31.080 Und da kommt jetzt hier, was wir gerade vorher mehrmals inzwischen 40:31.080 --> 40:34.720 gesehen haben, das ist unser Ziel oder unser Startpunkt. 40:35.300 --> 40:38.520 Deshalb bilden wir diesen Ziel und Startpunkt zu den nächsten Punkten 40:38.520 --> 40:39.400 auf diesem Netz. 40:40.200 --> 40:44.580 Und dann suchen wir auf diesem Netz ein Pferd von Start zum Ziel und 40:44.580 --> 40:48.300 natürlich am Ende müssen wir hier dieses kleine Stück fahren, also 40:48.300 --> 40:55.680 zwischen Q-Start und Q-Start-Strich, beziehungsweise Q-Ziel und Q-Ziel 40:55.680 --> 40:56.060 -Strich. 40:58.300 --> 41:00.600 Es gibt andere Verfahren. 41:00.920 --> 41:04.660 Zu den Nachteilen, in der Regel ist der gefundene Weg nicht der 41:04.660 --> 41:05.420 kürzeste Weg. 41:05.560 --> 41:06.260 Warum eigentlich? 41:08.600 --> 41:11.320 Warum ist der gefundene Weg nicht der kürzeste Weg? 41:12.280 --> 41:18.600 Genau, eigentlich kann es einen viel kürzeren Weg hier finden, und 41:18.600 --> 41:19.360 zwar so. 41:23.520 --> 41:28.740 Also die Forderung, dass wir immer entlang der Linien fahren, wo wir 41:28.740 --> 41:34.080 die maximale Distanz zu den Objekten garantieren, bedeutet nicht, dass 41:34.080 --> 41:35.800 wir immer den kürzesten Weg kriegen. 41:36.000 --> 41:40.140 Und ich glaube, die rote Linie ist viel kürzer als zum Beispiel jetzt 41:40.140 --> 41:43.640 eine Linie entlang der Kanten des Voronoi-Diagramms. 41:44.400 --> 41:49.920 Bei wenigen Hindernissen werden natürlich wenige Wege generiert. 41:50.040 --> 41:50.680 Das sehen wir hier. 41:50.760 --> 41:54.260 Wir haben zwei Hindernisse und da haben wir ganz wenige Möglichkeiten 41:54.260 --> 41:58.580 eigentlich, wie wir von einem bestimmten Punkt zum anderen in diesem 41:58.580 --> 42:01.620 Konfigurationsraum kommen können. 42:02.520 --> 42:05.860 Es gibt andere Methoden, zum Beispiel Sichtgrafen. 42:06.320 --> 42:09.760 Und bei Sichtgrafen, auch bei Sichtgrafen, geht davon aus, dass man 42:09.760 --> 42:11.060 die Hindernisse kennt. 42:11.260 --> 42:15.420 Also das ist Obstacle 1, Obstacle 2 und Obstacle 3, deshalb O, 42:15.820 --> 42:16.980 Obstacle für Hindernisse. 42:17.840 --> 42:22.380 Und was man macht hier, man verbindet jedes Paar von Eckpunkten von 42:22.380 --> 42:27.560 den Hindernissen, also auf dem Rand von dem Freiraum, durch eine 42:27.560 --> 42:32.600 Linie, wenn diese Linie oder dieses Liniensegment kein Hindernis 42:32.600 --> 42:33.060 schneidet. 42:33.200 --> 42:37.040 Also man nimmt hier diese Ecken und verbindet sie miteinander. 42:38.020 --> 42:39.660 Das ist auch eine Ecke, verbindet sie. 42:40.240 --> 42:45.520 Aber das hier mache ich natürlich nicht, weil das schneidet ja ein 42:45.520 --> 42:46.080 Hindernis. 42:47.140 --> 42:48.800 Also das geht weg. 42:51.600 --> 42:55.260 Und wenn wir alles hier machen, dann bekommen wir so ein Netz und auf 42:55.260 --> 42:56.960 diesem Netz können wir uns dann bewegen. 42:57.960 --> 42:59.420 Und was ist das Problem? 42:59.660 --> 43:07.500 Das Problem, wenn ich jetzt hier von Q-Start zu Q-Ziel kommen will, 43:07.500 --> 43:12.840 dann bilde ich das vielleicht auf dem nächsten Punkt hier ab, also Q 43:12.840 --> 43:23.160 -Ziel -Strich und dann hier Q-Start-Strich. 43:23.440 --> 43:29.240 Ich suche einen Weg zwischen diesem Q-Strich und Q-Strich und dann 43:29.240 --> 43:33.480 muss ich natürlich dafür sorgen, dass ich jetzt hier von Q zu Q-Start 43:33.480 --> 43:36.840 und Q-Ziel zu Q-Ziel komme. 43:36.840 --> 43:38.820 Also die gleiche Vorgehensweise. 43:39.960 --> 43:43.440 Das ist hier ein weiteres Beispiel, also man sieht hier für die 43:43.440 --> 43:47.520 Objekte kann ich dann natürlich nachher vielleicht den kürzesten Weg 43:47.520 --> 43:50.120 suchen von Q-Start zum Q-Ziel. 43:50.740 --> 43:53.020 Und was ist der Nachteil von dieser Methode hier? 43:53.820 --> 43:59.600 Nein, wir haben bis jetzt überhaupt keine Aussagen darüber gemacht, 43:59.740 --> 44:02.180 wie wir den kürzesten Weg berechnen oder nicht. 44:02.180 --> 44:07.240 Also berechnen nicht unbedingt immer den kürzesten Weg, aber wir 44:10.430 --> 44:14.170 können auch keine Kurven fahren, aber das ist alles vielleicht nicht 44:14.170 --> 44:15.090 das Hauptproblem. 44:19.480 --> 44:22.940 Genau, man fährt sehr nah an den Hindernissen vorbei, weil zum 44:22.940 --> 44:28.020 Beispiel eine Kante von einem Hindernis, wie bei O3, kann tatsächlich 44:28.020 --> 44:29.600 eine Kante von einem Graph sein. 44:30.500 --> 44:34.100 Also das ist ja eine Kante, ich habe jetzt hier das verbunden, wenn 44:34.100 --> 44:37.900 ich die zwei miteinander verbinde und ich suche vielleicht den 44:37.900 --> 44:42.480 kürzesten Weg, dann ist der kürzeste Weg ein Weg, wo die Kante hier 44:42.480 --> 44:44.740 entlang der Kante von einem Hindernis ist. 44:45.780 --> 44:50.240 Das heißt, so wird es nicht funktionieren, weil jeder Roboter hat eine 44:50.240 --> 44:54.340 gewisse physikalische Ausdehnung und ist nicht nur punktförmig. 44:54.340 --> 45:01.300 Aber das Verfahren hier, also mit Sichtgrafen, kann man eigentlich 45:01.300 --> 45:05.820 sagen, dass diese Wege, die man findet, optimal sind, zum Beispiel am 45:05.820 --> 45:10.760 kürzesten bei 2D-Problemen und wenn der Roboter und Hindernisse durch 45:10.760 --> 45:12.940 konvexe Polynome darstellbar sind. 45:13.720 --> 45:17.340 Der Nachteil ist, die Wege sind nicht unbedingt kollisionsfrei, denn 45:17.340 --> 45:21.900 Hindernisskanten können auch Wegsegmente sein und abhilfig schafft 45:21.900 --> 45:23.700 hier die Erweiterung von Hindernissen. 45:24.540 --> 45:31.540 Das heißt, man vergrößert die Hindernisse so, dass es nicht zu 45:31.540 --> 45:36.280 Kollisionen kommt, wenn man entlang der Kante eines Hindernisses 45:36.280 --> 45:36.700 fährt. 45:37.660 --> 45:42.360 Und die Methode, die ist jetzt natürlich nur in 2D oder haben wir nur 45:42.360 --> 45:46.500 in 2D kennengelernt, aber die ist auch in 3D anwendbar, aber die Wege, 45:46.600 --> 45:49.440 man kann keine Garantien mehr geben, dass die Wege, die dort gefunden 45:49.440 --> 45:53.060 werden, die kürzesten oder die optimalsten sind. 45:54.000 --> 45:57.460 Und wie man diese Hindernisse erweitert, also damit wir sowas 45:57.460 --> 46:02.180 vermeiden, dass wir entlang der Kante eines Hindernisses fahren, 46:02.360 --> 46:04.880 könnte man sagen, naja, eigentlich ist es ja ganz einfach. 46:05.000 --> 46:09.420 Wenn ich so einen Roboter habe, einen kreisförmigen Roboter, dann 46:09.420 --> 46:13.180 vergrößere ich alle Hindernisse um den Radius von diesem Roboter. 46:13.360 --> 46:18.020 Das heißt, O1 wird ein bisschen größer, und zwar an allen Stellen 46:18.020 --> 46:23.840 genau so um R erweitert, wenn R der Radius vom Roboter ist. 46:24.760 --> 46:29.320 Und wenn ich dann solche Wege finde, wo ich zum Beispiel an der Kante 46:29.320 --> 46:35.600 von einem Hindernis fahre, also normalerweise würden wir hier an 46:35.600 --> 46:38.760 diesem Punkt vorbeifahren und es würde natürlich eine Kollision mit 46:38.760 --> 46:43.340 dem Hindernis kommen, aber dadurch, dass wir dieses Hindernis um R, 46:43.980 --> 46:48.540 wobei R ist hier der Radius von dem Roboter, vergrößert haben, werden 46:48.540 --> 46:53.260 wir natürlich im Abstand von R an dem Hindernis vorbeifahren und somit 46:53.260 --> 46:54.800 diese Kollision vermeiden. 46:56.200 --> 47:01.780 Natürlich ist das jetzt nicht allgemein, also das wäre jetzt für einen 47:01.780 --> 47:05.660 kreisförmigen Roboter, das ist zum Beispiel ein rechteckiger Roboter 47:05.660 --> 47:08.440 und der kann sich in xy-Richtung bewegen. 47:08.920 --> 47:12.260 Und man sieht hier, dass man sich Gedanken darüber machen muss, wie 47:12.260 --> 47:17.460 man diese Hindernisse vergrößern muss, um alle möglichen 47:17.460 --> 47:21.740 Konfigurationen vom Roboter zu betrachten und Lösungen, bei denen man 47:21.740 --> 47:26.560 entlang der Kante eines Hindernisses fahren muss, nicht zu einer 47:26.560 --> 47:27.340 Kollision führen. 47:29.260 --> 47:31.120 Gut, gibt es Fragen dazu? 47:35.240 --> 47:38.080 Okay, das heißt, wir haben ein Voronoi-Diagramm und wir haben 47:38.080 --> 47:40.640 Sichtgrafen kennengelernt. 47:40.780 --> 47:44.820 Die dritte Möglichkeit sind sogenannte Zellenzerlegungen und wir gehen 47:44.820 --> 47:48.060 immer davon aus, wir haben ein vollständiges Umweltmodell. 47:48.280 --> 47:52.020 Das heißt, wir kennen den Konfigurationsraum, wir kennen den Freiraum 47:52.020 --> 47:54.740 und wir kennen den Hindernisraum. 47:55.580 --> 48:00.080 Bei Zellenzerlegung, also eigentlich muss man Tricks finden, wie man 48:00.080 --> 48:04.520 in diesem Freiraum sich bewegen kann, um eine kollisionsfreie 48:04.520 --> 48:05.460 Trajektorie zu finden. 48:05.620 --> 48:10.580 Bei Zellenzerlegung sagt man, wir zerlegen diesen Freiraum in Zellen, 48:10.580 --> 48:13.880 sodass ein Weg zwischen zwei Konfigurationen innerhalb einer Zelle 48:13.880 --> 48:14.980 leicht zu finden ist. 48:15.260 --> 48:19.840 Und man stellt dann die Nachbarschaften zwischen Zellen in einem 48:19.840 --> 48:24.900 Grafen dar und sucht dann den optimalen Weg vom Start zum Ziel in 48:24.900 --> 48:25.620 diesem Grafen. 48:26.500 --> 48:31.120 Und für diese Zellenzerlegung gibt es zwei Arten, einmal eine exakte 48:31.120 --> 48:35.580 Zellenzerlegung und einmal eine approximative Zellenzerlegung. 48:36.270 --> 48:44.240 Und die exakte Zellenzerlegung bedeutet, dass der Freiraum C-free in 48:44.240 --> 48:51.420 Zellen ZI zerlegt wird, sodass keine zwei Zellen sich überlappen. 48:51.640 --> 48:55.940 Also der Durchschnitt von zwei Zellen ist die Leeremenge und die 48:55.940 --> 49:00.700 Vereinigung von allen ZIs, also allen Zellen, in denen man den 49:00.700 --> 49:03.940 Freiraum zerlegt hat, dem Freiraum ergeben. 49:04.760 --> 49:06.500 Und wie macht man das? 49:06.700 --> 49:09.780 Das ist zum Beispiel eine Methode, wie man diese exakte 49:09.780 --> 49:12.640 Zellenzerlegung mit einem kleinen Sweep macht. 49:12.980 --> 49:18.240 Und zwar, man hat hier einen Konfigurationsraum, Hindernisraum ist 49:18.240 --> 49:20.880 schwarz und Freiraum ist weiß. 49:21.600 --> 49:28.920 Und man geht hin und lässt eine Linie über diesen Konfigurationsraum 49:28.920 --> 49:30.700 hinfegen. 49:30.700 --> 49:37.760 Also eine Linie bewegt sich von links nach rechts, diese vertikale 49:37.760 --> 49:40.020 Linie hier in diesem zweidimensionalen Beispiel. 49:40.780 --> 49:44.220 Das ist zunächst mal diese Ecke hier, eine vertikale Linie runter und 49:44.220 --> 49:49.200 dann weiß ich, ich habe hier eine Region 1, dann die nächste Ecke hier 49:49.200 --> 49:49.900 von dem Hindernis. 49:50.980 --> 49:57.560 Und dann, das heißt, diese Linie bewegt sich von links nach rechts und 49:57.560 --> 50:01.740 immer, wenn sie sich auf ein Hindernis oder auf eine Ecke von einem 50:01.740 --> 50:05.320 Hindernis stößt, habe ich eine neue Region. 50:05.700 --> 50:07.440 Ja, also das ist die Region 2. 50:08.040 --> 50:11.020 Dann gehen wir weiter, die Linie bewegt sich. 50:11.020 --> 50:15.320 Dann habe ich hier die Ecke hier und ich gehe mal weiter, wie man 50:15.320 --> 50:20.460 sieht hier, dann habe ich diesen Bereich hier und so weiter hier bei 4 50:20.460 --> 50:24.000 und so weiter und so fort. 50:24.180 --> 50:27.520 Und wenn ich das hier mache, über den gesamten Bereich, dann habe ich 50:27.520 --> 50:33.380 eigentlich meinen Freiraum, also der weiße Bereich hier unterteilt in 50:33.380 --> 50:38.680 mehreren Regionen mit den Nachbarschaften von diesen Regionen. 50:38.680 --> 50:43.200 Und das kann ich jetzt auf einem Graphen abbilden, also 1 und 2 sind 50:43.200 --> 50:44.200 miteinander verbunden. 50:44.660 --> 50:47.840 Und wie man sieht hier, bei 2 habe ich eine Verzweigung zu Region 3 50:47.840 --> 50:53.800 und Region 6 und von Region 3 auf 4 und von 4 auf 5. 50:53.920 --> 50:55.940 Und man sieht hier, von 5 komme ich nie raus. 50:56.080 --> 50:59.480 Das heißt, wenn ich irgendwo in 5 lande, dann ist es eine Sackgasse. 51:01.340 --> 51:03.820 Von 4 komme ich aber weiter zu 7. 51:03.820 --> 51:08.840 7 ist auch mit 6 verbunden, weil ich kann von 6 zu 7 kommen und von 7 51:08.840 --> 51:13.660 zu 8 und von 8, wie man sieht, zu 9, zu 10. 51:15.680 --> 51:19.900 Aber von 7 auch zu 16 und von 16 zu 17. 51:19.900 --> 51:24.160 Und hier von 10 sieht man zu 13 oder zu 11. 51:24.260 --> 51:28.640 Von 13 auch zu 14, wo ich auch hier nie wieder rauskommen würde. 51:29.440 --> 51:31.300 Von 11 wieder zu 12. 51:32.200 --> 51:35.880 Und von 12 zu 19 und von 19 zu 20. 51:35.880 --> 51:42.860 Also das heißt, man hat so eine Zerlegung von dem Freiraum und anhand 51:42.860 --> 51:46.420 von dieser Zerlegung kann man diesen Graphen hier auf eine leichte Art 51:46.420 --> 51:50.340 und Weise erzeugen. 51:50.340 --> 51:54.560 Und jetzt will man ein Planungsproblem führen. 51:54.720 --> 51:59.180 Zum Beispiel sagt man, ich habe meine Startkonfiguration hier und 51:59.180 --> 52:00.640 Zielkonfiguration hier. 52:01.640 --> 52:06.140 Und was man machen muss, ist eigentlich festzustellen, in welcher 52:06.140 --> 52:10.020 Region ist meine Startkonfiguration und meine Zielkonfiguration. 52:10.020 --> 52:18.000 Das ist 3, also das heißt der Knoten 3 hier, mein Start und mein Ziel 52:18.000 --> 52:20.660 ist in der Region 19. 52:21.140 --> 52:25.600 Also eigentlich, ich muss nur in einem Graphen einen Weg zwischen dem 52:25.600 --> 52:27.880 Knoten 3 und dem Knoten 19 suchen. 52:28.700 --> 52:32.760 Und das wäre die Lösung für mein Planungsproblem. 52:32.760 --> 52:40.760 Und man sieht hier, dass das über 4, 7, 8, 9, 10, 13, 15, 17, 18, 19 52:40.760 --> 52:41.060 geht. 52:41.160 --> 52:42.740 Das ist eine Lösung. 52:43.000 --> 52:47.100 Und da wir jetzt hier überhaupt keine Aussagen über Kosten gemacht 52:47.100 --> 52:56.000 haben, ist natürlich auch 3, 4, 7 oder 3, 4, 7, 16, 17, 18, 19 auch 52:56.000 --> 52:56.520 eine Lösung. 52:56.520 --> 53:04.100 Oder 3, 4, 7, 8, 9, 10, 11, 12, 19 auch eine Lösung. 53:06.820 --> 53:08.680 Also eine sehr einfache Methode. 53:08.940 --> 53:14.200 Man hat natürlich diesen Konfigurationsraum mit den Hindernissen, mit 53:14.200 --> 53:15.300 dem Freiraum. 53:15.300 --> 53:22.480 Man lässt eine Linie so über diesen Raum hinfegen und an allen Ecken, 53:22.620 --> 53:26.820 wie man sieht hier, definiert man oder werden diese Regionen definiert 53:26.820 --> 53:36.420 durch diese vertikalen Linien von den Ecken der Hindernissen und dann 53:36.420 --> 53:38.520 im Graph und dann in der Graph-Suche. 53:38.520 --> 53:40.160 Was bedeutet das? 53:40.400 --> 53:46.340 Das heißt, eine einfache Möglichkeit, eigentlich solche Pferde- bzw. 53:47.380 --> 53:49.320 kollisionsfreien Trajektorien zu finden. 53:49.460 --> 53:51.040 Im zweidimensionalen Fall übrigens. 53:52.380 --> 53:57.900 Die approximative Zellenzerlegung ist ein bisschen anders, also 53:57.900 --> 53:59.140 approximativ nicht genau. 53:59.360 --> 54:02.540 Also hier sind wir sehr genau, wie man gesehen hat in dem Beispiel. 54:03.500 --> 54:07.660 Hier zerlegen wir den Freiraum in Zellen von einer vordefinierten 54:07.660 --> 54:08.120 Form. 54:08.120 --> 54:15.460 Also wir sagen zum Beispiel, unsere Zellen sind rechteckig und initial 54:15.460 --> 54:20.840 hat eine Zelle zum Beispiel eine Kantenlänge von 4 cm. 54:21.800 --> 54:28.460 Wenn eine Zelle nicht vollständig im Freiraum passt oder liegt, also 54:28.460 --> 54:33.500 wenn ich jetzt durch diese Kacheln, ich fange an mal Kacheln in diesem 54:33.500 --> 54:38.800 Raum zu legen und wenn eine Kachel zu Kollisionen mit einem Hindernis 54:38.800 --> 54:42.800 kommt, also nicht mehr dort reinpasst, dann sage ich, okay, ich muss 54:42.800 --> 54:46.280 kleinere Kacheln nehmen oder kleinere Zellen nehmen. 54:46.280 --> 54:50.260 Also wenn eine Zelle nicht passt, dann verringern wir die Größe von 54:50.260 --> 54:54.900 dieser Zelle und zerlegen wir weiter, zum Beispiel im Quadri und dann 54:54.900 --> 55:00.520 wiederholen wir diesen Schritt bis zu einer minimalen Größe der Zelle, 55:00.660 --> 55:03.420 weil wir sagen, okay, die kleinsten Zellen, die wir berücksichtigen, 55:03.940 --> 55:12.880 die sollen 1 x 1 cm groß sein, also ausgehend von 4 x 4 cm die 55:12.880 --> 55:15.020 Initialzellen, mit denen wir angefangen haben. 55:15.020 --> 55:19.580 Vorteil, sehr einfache Zerlegung und dadurch natürlich sehr einfache 55:19.580 --> 55:23.700 Wegsuche, weil eigentlich die Wegsuche ist nichts anderes als die 55:23.700 --> 55:28.320 Suche von einer Sequenz von Kacheln oder Zellen, die ich gelegt habe, 55:28.780 --> 55:30.540 von denen ich weiß, die sind frei. 55:31.500 --> 55:34.360 Das heißt, ich habe schon die Informationen eigentlich bei dieser 55:34.360 --> 55:40.060 Zerlegung mit und schleppe sie mit und kann sie nur nutzen, um eine 55:40.060 --> 55:42.960 Kollisionfreie Bahn zu berechnen. 55:42.960 --> 55:46.900 Der Nachteil, der Freiraum kann im Allgemeinen nur annähernd 55:46.900 --> 55:50.320 beschrieben werden, es sei denn, die Hindernisse, die sind alle 55:50.320 --> 55:54.840 quadratisch praktisch, wie die Zellen und deshalb der Name 55:54.840 --> 55:56.280 approximative Zerlegung. 55:56.280 --> 56:01.080 Hier sieht man ein Beispiel, das ist unser Konfigurationsraum mit 56:01.080 --> 56:04.600 Freiraum und Hindernissen, Start- und Endkonfiguration und wir fangen 56:04.600 --> 56:06.580 mit diesen Zellen an. 56:06.580 --> 56:13.180 Wir fangen an, so Zellen mal hinzulegen in den Freiraum und irgendwann 56:13.180 --> 56:17.220 mal versuchen wir mal hier eine Zelle zu legen und merken, das passt 56:17.220 --> 56:17.520 nicht. 56:17.680 --> 56:23.180 Deshalb nehmen wir eine kleinere Zelle, die passt, die passt, die 56:23.180 --> 56:26.340 passt nicht, die passt ein bisschen und deshalb zerlegen wir weiter 56:26.340 --> 56:27.440 und so weiter und so fort. 56:27.440 --> 56:33.700 Und das wollen wir ein bisschen jetzt genauer kennenlernen und zwar, 56:34.200 --> 56:38.320 wir haben jetzt verstanden, dass wir diesen Freiraum irgendwie 56:38.320 --> 56:43.580 repräsentieren müssen als Voronoi-Diagramm, also Freiraum mit 56:43.580 --> 56:47.060 Hindernissen -Voronoi-Diagramm als Graph mit zum Beispiel 56:47.060 --> 56:51.680 Zellenzerlegung und jetzt der nächste Schritt ist eigentlich, den Weg 56:51.680 --> 56:57.060 zu suchen innerhalb von diesen Graphen oder entlang dieser Zellen. 56:57.320 --> 57:02.660 Man sieht hier in dem Beispiel, dass ich das eigentlich hier auf eine 57:02.660 --> 57:06.400 sehr einfache Art und Weise jetzt meinen Weg planen kann von Q-Start 57:06.400 --> 57:07.700 zum Q-Ziel. 57:07.700 --> 57:10.540 Aber das wollen wir ein bisschen genauer angucken, weil wir sind 57:10.540 --> 57:15.080 jetzt, wir haben ja den ersten Schritt erschlagen und wir wollen jetzt 57:15.080 --> 57:21.340 sehen, wie wir tatsächlich in diesem Wegnetz einen Weg mithilfe von 57:21.340 --> 57:23.940 Baumsuche finden können. 57:26.060 --> 57:31.120 So, der Anwendungsfall mobile Roboter, also 2D-Arbeits- oder 57:31.120 --> 57:36.460 Konfigurationsräume und im 2D unterscheidet man dann nicht so sehr 57:36.460 --> 57:38.420 zwischen Arbeits- oder Konfigurationsraum. 57:38.580 --> 57:43.280 Oft spricht man auch von Konfigurationsraum in diesen Fällen. 57:43.280 --> 57:47.720 Wir stellen also jetzt diesen Konfigurationsraum als Quad-Tree. 57:48.240 --> 57:52.580 Wir unterteilen den Konfigurationsraum rekursiv in Kacheln. 57:53.040 --> 57:58.180 Die Kacheln sind dann entweder frei oder belegt, also oder kollidieren 57:58.180 --> 58:01.520 mit einem Hindernis oder enthalten einen Teil von einem Hindernis. 58:01.520 --> 58:06.020 Und die Fahrtplanung ist nichts anderes, als solche Kacheln zu finden, 58:06.600 --> 58:10.120 in denen sich Start- und Zielkonfigurationen befinden und dann 58:10.120 --> 58:14.380 benachbartfreie Kacheln im Baum vom Start zum Ziel miteinander 58:14.380 --> 58:14.980 verbinden. 58:15.620 --> 58:19.560 Und dann natürlich haben wir unsere Bahn. 58:19.560 --> 58:21.880 So, wie sieht das Ganze aus? 58:22.020 --> 58:27.040 Das heißt, nehmen wir mal an, wie stellt man diesen Konfigurationsraum 58:27.040 --> 58:27.880 als Quad-Tree? 58:28.800 --> 58:35.160 Wie ich bereits angedeutet habe, gehen wir von einer Initial-Große, 58:35.320 --> 58:39.320 zum Beispiel von dieser Zelle, also sagen wir mal 4x4. 58:39.320 --> 58:44.640 Schwarz sollen Hindernisregionen sein, weiß sollen freie Regionen oder 58:44.640 --> 58:45.640 Freiraum sein. 58:46.800 --> 58:49.900 Und wir wollen diese Bezeichnung hier verwenden. 58:50.140 --> 58:59.860 Das heißt, alle Quadrate wollen wir also unten links mit 0, dann 1 und 58:59.860 --> 59:01.380 dann 2 und dann 3 haben. 59:01.380 --> 59:09.100 Schwarze Knoten sind Hindernisregionen, weiße Knoten sind Freiraum und 59:09.100 --> 59:14.200 grüne Knoten sind gemischte Knoten. 59:14.460 --> 59:18.660 Also, wo sowohl Freiraum als auch Hindernisraum dort vorhanden ist. 59:19.480 --> 59:20.260 Und was macht man? 59:20.260 --> 59:23.220 Also, wir haben zunächst mal den ganzen Konfigurationsraum, das ist 59:23.220 --> 59:24.980 nur ein Knoten in diesem Baum. 59:25.260 --> 59:29.640 Und zwar, das ist der Knoten hier. 59:30.240 --> 59:34.060 Und diesen Knoten zerlegen wir zunächst mal in 4. 59:39.500 --> 59:40.840 Und was bekommen wir hier? 59:40.840 --> 59:48.680 Wir bekommen eigentlich 4 gemischte Regionen, weil wir haben überhaupt 59:48.680 --> 59:54.660 keine neue Zelle, in der wir nur Hindernisse oder nur Freiraum haben. 59:55.000 --> 59:59.720 Also in 0 haben wir Hindernisse und Freiraum, in 1 haben wir Freiraum 59:59.720 --> 01:00:02.460 und Hindernisse, hier haben wir auch Freiraum und Hindernisse und hier 01:00:02.460 --> 01:00:03.860 haben wir auch Freiraum und Hindernisse. 01:00:03.860 --> 01:00:07.620 Deshalb bekommen wir 4 gemischte Knoten zunächst mal. 01:00:08.560 --> 01:00:13.840 Dann nehmen wir diesen Knoten hier, Knoten 0, und wir zerlegen den 01:00:13.840 --> 01:00:21.240 Knoten nochmal rekursiv in 4 und da bekommen wir für 0 einen weißen 01:00:21.240 --> 01:00:28.040 Knoten, für 1 bekommen wir einen schwarzen, für 2 einen weißen und der 01:00:28.040 --> 01:00:31.820 dritte hier, der dritte Teil ist natürlich gemischt, deshalb bekommen 01:00:31.820 --> 01:00:35.740 wir einen Kreis, einen grünen Kreis. 01:00:36.240 --> 01:00:39.220 Das heißt, den müssen wir wieder zerlegen in 4 Teilen. 01:00:41.160 --> 01:00:44.340 Und wenn wir den in 4 Teilen zerlegen, dann bekommen wir frei 01:00:44.340 --> 01:00:48.740 Hindernisse, also weiß, weiß, schwarz, schwarz. 01:00:48.740 --> 01:00:53.580 Und wenn wir das alles hier machen, bis wir am Ende in diesem Baum 01:00:53.580 --> 01:00:58.340 überhaupt keine Kreise haben, sondern nur schwarze oder weiße 01:00:58.340 --> 01:01:04.100 Quadranten, dann sind wir fertig und das ist dann die Darstellung 01:01:04.100 --> 01:01:08.140 eigentlich von dem freien bzw. 01:01:08.680 --> 01:01:12.940 dem Hindernisraum und da kann man dann die Bestimmung von einer 01:01:12.940 --> 01:01:17.860 kollisionsfreien Bahn als eine Suche in diesem Baum hier definieren. 01:01:19.440 --> 01:01:21.340 So, Beispiel. 01:01:22.880 --> 01:01:26.220 Und zwar, wir hätten hier einen Arbeitsraum mit diesen Hindernissen 01:01:26.220 --> 01:01:28.180 und das ist unser Roboter. 01:01:29.480 --> 01:01:34.340 Und wenn man jetzt solche Planungsprobleme in diesem Raum finden oder 01:01:34.340 --> 01:01:39.860 lösen will, dann muss man natürlich auch die Ausdehnungen von dem 01:01:39.860 --> 01:01:40.980 Roboter hier betrachten. 01:01:40.980 --> 01:01:42.260 Was bedeutet das? 01:01:42.340 --> 01:01:45.660 Wir müssen also das Problem im Konfigurationsraum betrachten, also 01:01:45.660 --> 01:01:50.220 welche Konfiguration vom Roboter, Position, Orientierung vom Roboter 01:01:50.220 --> 01:01:53.180 führen zu Kollisionen mit den Hindernissen. 01:01:53.180 --> 01:01:56.940 Und wenn wir jetzt den Hindernisraum im Konfigurationsraum hier 01:01:56.940 --> 01:01:58.900 bestimmen, dann kommen wir auf sowas aus. 01:01:59.560 --> 01:02:04.420 Es fällt natürlich auf, oder manche Leute würden jetzt hier denken, 01:02:04.540 --> 01:02:07.980 das ist nur eine Vergrößerung von den Hindernissen, aber das ist keine 01:02:07.980 --> 01:02:11.080 reine Vergrößerung von den Hindernissen, sondern das ist ähnlich zu 01:02:11.080 --> 01:02:15.560 dem Beispiel, was wir vorher gesehen haben, wo wir Freiraum und 01:02:15.560 --> 01:02:22.200 Hindernisraum bestimmt haben, weil O1 im Konfigurationsraum nicht die 01:02:22.200 --> 01:02:27.400 gleiche Form hat wie O1 im Arbeitsraum, beziehungsweise auch O2 und 01:02:27.400 --> 01:02:27.860 O3. 01:02:29.260 --> 01:02:34.080 Die Hindernisse sind ein bisschen ausgedehnt, um die Ausdehnungen oder 01:02:34.080 --> 01:02:39.100 die Abmessungen von dem Roboter, aber nicht nur das, weil diese Ecke 01:02:39.100 --> 01:02:44.960 hier von O1 ist ja im Arbeitsraum nicht vorhanden, aber wohl im 01:02:44.960 --> 01:02:45.700 Konfigurationsraum. 01:02:46.500 --> 01:02:49.660 Obwohl das jetzt nur ein 2D-Beispiel ist. 01:02:49.820 --> 01:02:52.800 Und wenn wir jetzt hier diesen Freiraum zerlegen mit unserem Tree, 01:02:53.300 --> 01:02:54.900 dann fangen wir an mit diesen Zellen. 01:02:55.180 --> 01:02:58.720 Da sieht man hier, dass die Zellen kleiner und kleiner werden. 01:02:59.500 --> 01:03:05.340 Und dann können wir jetzt, wenn wir eine kollisionsfreie Bahn zum 01:03:05.340 --> 01:03:09.000 Beispiel zwischen einer Start- und einer Zielkonfiguration haben, dann 01:03:09.000 --> 01:03:13.140 brauchen wir nur eine Folge von freien Zellen, beziehungsweise Kacheln 01:03:13.140 --> 01:03:16.820 zu identifizieren, beziehungsweise zu finden, die das erreichen. 01:03:16.820 --> 01:03:21.320 Also beispielsweise entlang dieser Linie hier vom Start zum Ziel. 01:03:21.940 --> 01:03:27.600 Und mithilfe von dieser Methode kann man sogar reaktives Verhalten 01:03:27.600 --> 01:03:28.280 realisieren. 01:03:28.440 --> 01:03:34.920 Das heißt, man nehme an, unser Arbeitsraum oder Hindernisraum war so 01:03:34.920 --> 01:03:37.640 und jetzt auf einmal kommen ein paar neue Hindernisse dazu. 01:03:37.640 --> 01:03:42.400 Da kann man natürlich hier diese Hindernisse berücksichtigen und dann 01:03:42.400 --> 01:03:48.780 lokale Ausweichmanöver hier planen. 01:03:49.960 --> 01:03:55.960 Okay, das heißt, wir haben jetzt drei Methoden kennengelernt, um diese 01:03:55.960 --> 01:03:57.280 Netze zu bauen. 01:03:58.780 --> 01:04:03.440 Die geben natürlich ein Umweltmodell, das heißt unser Freiraum und 01:04:03.440 --> 01:04:06.960 Hindernisraum und wir haben eine Methode kennengelernt, mit der wir 01:04:06.960 --> 01:04:14.240 tatsächlich die Suche nach einem Pfad, also das Auffinden von einer 01:04:14.240 --> 01:04:18.220 kollisionsfreien Bahn mithilfe von Baumsuche machen können. 01:04:18.780 --> 01:04:23.460 Aber wenn wir jetzt solche Probleme haben oder solche Probleme auf die 01:04:23.460 --> 01:04:26.200 Art und Weise lösen, dann haben wir bis jetzt überhaupt keine Aussagen 01:04:26.200 --> 01:04:33.120 darüber gemacht, ob die Pfade, die wir bestimmt haben, vielleicht die 01:04:33.120 --> 01:04:36.380 optimalsten sind, die kürzesten Pfade beispielsweise. 01:04:36.380 --> 01:04:43.700 Oder ob es überhaupt unterschiedliche Möglichkeiten gibt, zwischen 01:04:43.700 --> 01:04:46.880 denen man wählen kann und nicht nur irgendeine Lösung, sondern 01:04:46.880 --> 01:04:50.520 vielleicht die beste Lösung im Sinne eines Optimalitätskriteriums 01:04:50.520 --> 01:04:51.560 betrachten. 01:04:52.120 --> 01:04:54.360 Und das wollen wir als nächstes hier angucken. 01:04:54.540 --> 01:04:55.920 Aber ich sehe, es gibt eine Frage. 01:04:55.920 --> 01:05:00.620 Die grüne Linie ist dadurch entstanden, dass ich eine Sequenz von 01:05:00.620 --> 01:05:03.940 freien Zellen zwischen Start und Ziel bekomme. 01:05:04.040 --> 01:05:07.680 Ja, das ist nur eine Variante, also nur eine Lösung, die hier 01:05:07.680 --> 01:05:10.540 dargestellt ist. 01:05:12.760 --> 01:05:16.280 Nein, nein, nein, nein. 01:05:16.460 --> 01:05:18.540 Das, was ich gerade erzählt habe als letztes. 01:05:20.280 --> 01:05:24.700 Gut, das heißt, wir wollen uns ein bisschen mal genauer damit 01:05:24.700 --> 01:05:27.760 beschäftigen jetzt als nächstes, wie sieht es aus mit optimalen 01:05:27.760 --> 01:05:31.080 Lösungen, zum Beispiel mit den kürzesten Wegen zwischen einer Start- 01:05:31.080 --> 01:05:32.340 und einer Endkonfiguration. 01:05:32.340 --> 01:05:36.340 Nehmen wir mal an, wir hätten hier den Arma 4 und der soll jetzt in 01:05:36.340 --> 01:05:39.440 diesem Raum von Start zum Ziel kommen. 01:05:39.660 --> 01:05:41.000 Start grün, Ziel rot. 01:05:41.220 --> 01:05:45.800 Und alles, was grau ist, hier ist nicht befahrbar, um zum Beispiel 01:05:45.800 --> 01:05:49.140 diese Müsli-Box hier zu holen. 01:05:49.140 --> 01:05:52.960 Und es ist klar, dass wir eine ganze Menge von Möglichkeiten haben. 01:05:53.160 --> 01:05:56.520 Also wenn wir zum Beispiel hier mit Zellenzerlegung arbeiten, dann 01:05:56.520 --> 01:05:57.520 würde sowas passieren. 01:05:57.880 --> 01:05:58.940 Ja, also da wissen wir nicht. 01:05:59.060 --> 01:06:03.340 Das ist ja irgendeine Sequenz von freien Kacheln oder Zellen, die wir 01:06:03.340 --> 01:06:03.960 nehmen wollen. 01:06:03.960 --> 01:06:09.900 Aber was uns interessiert, ist tatsächlich den Weg zu finden und zwar 01:06:09.900 --> 01:06:12.740 den kürzesten Weg zu finden vom Start zum Zielpunkt. 01:06:13.440 --> 01:06:16.840 Und hierzu gibt es einen sehr bekannten Algorithmus in der Informatik. 01:06:17.000 --> 01:06:20.040 Für die Informatiker ist es natürlich ein sehr bekannter Algorithmus, 01:06:20.200 --> 01:06:21.240 denke ich mal, oder? 01:06:21.840 --> 01:06:23.280 Der A-Stern-Algorithmus. 01:06:23.560 --> 01:06:25.280 Wer kennt den A-Stern-Algorithmus? 01:06:28.100 --> 01:06:30.160 Okay, wer will es uns erklären? 01:06:31.560 --> 01:06:31.860 Nein? 01:06:33.200 --> 01:06:38.360 Also, der A-Stern-Algorithmus ist ein sehr beliebter Algorithmus zur 01:06:38.360 --> 01:06:43.400 Routenplanung und zwar Routenplanung in sogenannten gewichteten 01:06:43.400 --> 01:06:43.760 Graphen. 01:06:43.760 --> 01:06:49.020 Das heißt, damit wir wirklich den kürzesten Weg finden, müssen wir in 01:06:49.020 --> 01:06:53.240 einem Graph, was wir zum Beispiel mit Linesweep oder Ähnliches, müssen 01:06:53.240 --> 01:06:56.620 wir auch Gewichte an den Kanten mal hintun. 01:06:57.380 --> 01:07:01.420 Und da sieht man hier ein Beispiel, das heißt, das ist so ein 01:07:01.420 --> 01:07:06.500 gewichteter Graph mit den Knoten A, B, C und so weiter und so fort bis 01:07:06.500 --> 01:07:06.800 I. 01:07:06.800 --> 01:07:10.640 Und an den Kanten hier sind die Kosten bzw. 01:07:10.900 --> 01:07:12.960 die Gewichte von einer Kante. 01:07:13.180 --> 01:07:18.280 Also man sieht zum Beispiel, dass diese Kante zwischen B und G extrem 01:07:18.280 --> 01:07:22.780 teuer oder stark gewichtet ist, weil es vielleicht so lange dauert, 01:07:22.900 --> 01:07:27.400 von A nach G zu kommen, weil es dort so viele Baustellen gibt. 01:07:28.020 --> 01:07:35.780 Während von B nach H nach E nach G komme ich ja viel schneller mit 8, 01:07:36.100 --> 01:07:41.840 vielleicht 8 als Kostenfaktor oder ja im Vergleich hier zu einer 01:07:41.840 --> 01:07:42.740 direkten Verbindung. 01:07:42.740 --> 01:07:47.840 So, das heißt, wenn man das hier betrachtet, dann sieht man, ich suche 01:07:47.840 --> 01:07:53.880 jetzt irgendeinen Weg oder den Weg mit den minimalsten Kosten zwischen 01:07:53.880 --> 01:07:59.340 A und I, dann sieht man, dass man in diesem Graph mit Hilfe von dieser 01:07:59.340 --> 01:08:03.160 Information hier, also mit Hilfe von den Gewichten, wobei die Gewichte 01:08:03.160 --> 01:08:08.680 hier die Kosten darstellen, dass diese grüne Linie hier die 01:08:08.680 --> 01:08:12.720 optimalste, die kostengünstigste Linie ist. 01:08:12.740 --> 01:08:15.980 Das kann natürlich der Abstand sein, aber das können wirklich 01:08:15.980 --> 01:08:19.360 irgendwelche anderen Kosten, zum Beispiel die Zeit, die man braucht, 01:08:19.500 --> 01:08:24.280 entlang dieser unterschiedlichen Knoten im Graph zu fahren. 01:08:25.060 --> 01:08:27.400 Und wie funktioniert dieser Algorithmus? 01:08:29.220 --> 01:08:29.380 Ja? 01:08:29.780 --> 01:08:30.400 Gibt es Fragen? 01:08:31.580 --> 01:08:34.720 Skypest du mit jemandem oder mit wem redest du dann? 01:08:36.080 --> 01:08:36.360 Okay. 01:08:38.160 --> 01:08:39.400 Gibt es Fragen soweit? 01:08:40.240 --> 01:08:40.500 Nein. 01:08:40.500 --> 01:08:43.580 So, wie funktioniert das Ganze? 01:08:45.440 --> 01:08:49.720 Also natürlich müssen wir das auf unsere Probleme lösen, anwenden. 01:08:49.940 --> 01:08:53.960 Das heißt, wir haben hier einen Konfigurationsraum, das ist unser 01:08:53.960 --> 01:08:57.020 Quadrat hier und wir haben ein Hindernis. 01:08:57.020 --> 01:09:01.720 Und natürlich müssen wir irgendeine approximate Darstellung jetzt von 01:09:01.720 --> 01:09:06.620 diesem Freiraum finden und zwar müssen wir ein Netz dort erzeugen, ein 01:09:06.620 --> 01:09:10.160 Netz und auf diesem Netz natürlich unseren Weg suchen. 01:09:10.880 --> 01:09:14.820 Und was man hier macht, natürlich Diskretisierung zunächst mal von 01:09:14.820 --> 01:09:19.380 diesem Raum ist notwendig und dann, das ist unser Hindernis, das 01:09:19.380 --> 01:09:23.460 heißt, diese Knoten eigentlich, also wir gehen von einer equidistanten 01:09:23.460 --> 01:09:27.120 Diskretisierung von dem Raum hier, sehr vereinfacht dargestellt hier 01:09:27.120 --> 01:09:32.620 das Beispiel und diese Punkte, die zur Kollision mit dem Hindernis 01:09:32.620 --> 01:09:40.100 führen, die können wir überhaupt nicht benutzen bei unserer Suche. 01:09:40.100 --> 01:09:46.420 Deshalb werden sie hier aus diesem Graph eliminiert und bekommen wir 01:09:46.420 --> 01:09:50.740 diesen resultierenden Graph, der beschreibt für uns alle Positionen 01:09:50.740 --> 01:09:51.140 bzw. 01:09:51.560 --> 01:09:56.260 Stationen im Freiraum, die wir bei der Suche nach einem Pfad annehmen 01:09:56.260 --> 01:09:56.640 können. 01:09:56.640 --> 01:09:59.280 Und die Vorgehensweise ist immer gleich. 01:09:59.500 --> 01:10:05.240 Also ich kriege irgendwo in meinem Raum hier einen Q-Start und ich 01:10:05.240 --> 01:10:12.660 kriege irgendwo hier ein Q-Ziel und dann muss ich natürlich diese zwei 01:10:12.660 --> 01:10:17.760 Punkte zu den nächsten Nachbarn auf diesem Netz abbilden und dann 01:10:17.760 --> 01:10:23.700 zwischen diesen zwei Punkten auf dem Netz den kürzesten Pfad finden 01:10:23.700 --> 01:10:30.200 und dann anschließend natürlich zwischen Q-S und Q-S, was ich hier 01:10:30.200 --> 01:10:34.660 jetzt nicht nochmal schreiben werde, über eine lokale Planung auch 01:10:34.660 --> 01:10:35.260 eine Verbindung. 01:10:36.100 --> 01:10:40.420 So und dieser Algorithmus funktioniert wie folgt, man definiert eine 01:10:40.420 --> 01:10:46.400 Kostenfunktion und diese Kostenfunktion f von x ist die Summe von zwei 01:10:46.400 --> 01:10:54.180 Teilfunktionen, eine g und eine h-Funktion und g entspricht den Kosten 01:10:54.180 --> 01:10:57.300 vom Startknoten zu einem Knoten x. 01:10:57.300 --> 01:11:04.360 Also wenn wir zum Beispiel hier einen Knoten x haben, dann beschreibt 01:11:04.360 --> 01:11:10.880 für uns die Funktion g die Kosten, zum Beispiel der Abstand vom Start 01:11:10.880 --> 01:11:18.380 zu x und die Funktion h entspricht den geschätzten Kosten von diesem 01:11:18.380 --> 01:11:20.340 Knoten x zum Zielknoten. 01:11:21.220 --> 01:11:25.860 Das heißt einmal die Kosten vom Start zum Knoten und einmal eine 01:11:25.860 --> 01:11:33.980 Schätzung der Kosten vom Knoten x zum Zielknoten. 01:11:37.140 --> 01:11:42.840 Und der Algorithmus findet dann den optimalen Pfad vom Start zum Ziel, 01:11:43.080 --> 01:11:47.240 also die Knoten bezeichnen wir jetzt mit V und V-Ziel im Gegensatz zu 01:11:47.240 --> 01:11:50.420 Q und Q-Ziel, das sollte ja überhaupt kein Problem sein. 01:11:51.300 --> 01:11:55.820 Und hier ist eine Visualisierung, wie dieser Algorithmus, bevor ich 01:11:55.820 --> 01:11:58.140 den erkläre, funktioniert. 01:11:58.480 --> 01:12:01.360 Das heißt, wir haben jetzt hier den roten Punkt, das ist unser 01:12:01.360 --> 01:12:06.360 Startpunkt und den grünen Punkt, das ist unser Zielpunkt und das ist 01:12:06.360 --> 01:12:07.220 unser Hindernis. 01:12:07.220 --> 01:12:10.540 Und natürlich müssen wir, wie ich bereits erwähnt habe, das Ganze 01:12:10.540 --> 01:12:11.480 diskretisieren. 01:12:12.340 --> 01:12:15.900 Und da sieht man, dass der Algorithmus zunächst mal versuchen wird, 01:12:16.020 --> 01:12:18.560 entlang einer Linie zum Ziel zu kommen. 01:12:19.180 --> 01:12:24.000 Aber er wird ja natürlich an manchen Stellen feststellen, dass es zu 01:12:24.000 --> 01:12:26.640 Kollisionen kommt mit dem Hindernis hier. 01:12:28.120 --> 01:12:31.360 Und man sieht hier in dieser Darstellung, dass wir irgendwelche Punkte 01:12:31.360 --> 01:12:33.740 haben, die sind hellblau markiert. 01:12:33.740 --> 01:12:36.980 Und diese hellblau markierten Punkte, das sind Punkte, zu denen wir 01:12:36.980 --> 01:12:41.240 überhaupt kommen vom Start, aber die sind noch nicht endgültig 01:12:41.240 --> 01:12:45.400 untersucht, ob sie wirklich Teil einer Lösung sind oder nicht. 01:12:46.020 --> 01:12:50.840 Die ausgefüllten Punkte, die sind endgültig untersucht und die haben 01:12:50.840 --> 01:12:56.580 auch zusätzlich die Informationen bezüglich des Abstands zum Ziel. 01:12:56.580 --> 01:13:00.360 Das heißt, je weiter sie vom Ziel sind, diese ausgefüllten Punkte, 01:13:00.740 --> 01:13:04.420 desto roter die sind, also hier rot. 01:13:04.600 --> 01:13:09.660 Und wenn wir abgeschlossen behandelte oder betrachtete Punkte, und ich 01:13:09.660 --> 01:13:14.360 werde gleich erklären, was das bedeutet, wenn wir solche 01:13:14.360 --> 01:13:18.540 abgeschlossenen Punkte haben, die näher zum Ziel sind, dann werden sie 01:13:18.540 --> 01:13:19.000 grüner. 01:13:19.140 --> 01:13:24.200 Also grün heißt abgeschlossen betrachtet, analysiert dieser Punkt, ob 01:13:24.200 --> 01:13:29.640 das wirklich zu einer optimalen Lösung führt und rot, auch analysiert, 01:13:29.800 --> 01:13:34.180 ob das zu einer optimalen Lösung, aber der Abstand zum Ziel ist noch 01:13:34.180 --> 01:13:34.720 sehr weit. 01:13:34.720 --> 01:13:39.460 Und man merkt hier, ganz interessant, ganz am Ende, obwohl der 01:13:39.460 --> 01:13:43.080 Algorithmus jetzt zum Ziel gekommen ist, sucht er noch weiter nach 01:13:43.080 --> 01:13:47.340 anderen Varianten oder nach anderen Knoten, die eventuell zu einer 01:13:47.340 --> 01:13:50.460 besseren oder optimaleren Lösung führen. 01:13:50.460 --> 01:13:52.640 Wie funktioniert das Ganze? 01:13:53.600 --> 01:13:59.840 Das Ganze ist ein iterativer Ansatz und allgemein funktioniert der 01:13:59.840 --> 01:14:04.620 Algorithmus so, dass man zwei Mengen oder Listen von Knoten definiert, 01:14:05.640 --> 01:14:09.860 eine sogenannte Open List und eine Closed List oder Set, 01:14:10.040 --> 01:14:10.480 Entschuldigung. 01:14:10.480 --> 01:14:16.180 Das heißt, die Open Set enthält alle Knoten, die noch zu besuchen 01:14:16.180 --> 01:14:20.040 sind, also zu untersuchen, zu besuchen und zu untersuchen sind. 01:14:21.020 --> 01:14:28.400 Und in dieser Closed Set Menge C alle Knoten, die man bereits 01:14:28.400 --> 01:14:29.220 untersucht hat. 01:14:29.220 --> 01:14:34.780 Und das heißt, man weiß, von diesen Knoten, die führen zu einem Ziel 01:14:34.780 --> 01:14:40.380 oder gar nicht, die werden nicht Teil einer Lösung. 01:14:41.800 --> 01:14:46.580 Und dann macht man einen Update für jeden besuchten Knoten. 01:14:46.580 --> 01:14:50.080 Also wenn wir einen Knoten, wie wir in der Animation vorher gesehen 01:14:50.080 --> 01:14:52.420 haben, vn besuchen, machen wir einen Update. 01:14:52.700 --> 01:14:59.500 Das heißt einmal, was war eigentlich der Vorgänger Knoten zu dem 01:14:59.500 --> 01:15:00.540 aktuellen Knoten? 01:15:01.380 --> 01:15:08.540 Was sind die akkumulierten Kosten, um diesen Knoten vn, den wir gerade 01:15:08.540 --> 01:15:10.380 betrachten, zu erreichen? 01:15:10.380 --> 01:15:14.560 Also die Funktion g von n, das sind die Kosten vom Start bis zu diesem 01:15:14.560 --> 01:15:15.120 Knoten. 01:15:16.420 --> 01:15:19.300 Also immer eigentlich vom Start bis zu diesem Knoten. 01:15:20.040 --> 01:15:24.940 Und dann mithilfe von der gegebenen Heuristik des Algorithmus, welche 01:15:24.940 --> 01:15:31.100 Kosten sind noch zu erwarten, um von diesem aktuellen Knoten vn zum 01:15:31.100 --> 01:15:31.840 Ziel zu kommen. 01:15:33.420 --> 01:15:36.240 Wie initialisiert man den Algorithmus? 01:15:36.680 --> 01:15:41.880 Einmal die Open Set ist natürlich nur der Startknoten. 01:15:43.320 --> 01:15:48.620 Die Closed Set ist zunächst einmal die leere Menge, weil wir haben 01:15:48.620 --> 01:15:52.560 überhaupt keine Knoten besucht und untersucht. 01:15:53.500 --> 01:15:59.380 Damit wir überhaupt die erste Lösung akzeptieren können, ja, und wir 01:15:59.380 --> 01:16:02.740 akzeptieren nur solche Lösungen, die zu geringeren Kosten, die 01:16:02.740 --> 01:16:08.020 geringere Kosten haben, initialisieren wir alle Kosten von allen 01:16:08.020 --> 01:16:12.020 Knoten mit irgendwas ganz Großem, also im Idealfall unendlich. 01:16:12.020 --> 01:16:17.840 Also großen Wert einsetzen für die initialen Kosten von allen Knoten, 01:16:17.960 --> 01:16:19.960 die wir untersuchen sollen. 01:16:20.780 --> 01:16:25.280 Und natürlich die Kosten, um den Startknoten hier zu erreichen, sind 01:16:25.280 --> 01:16:27.900 null, weil ich bin ja im Startknoten. 01:16:29.020 --> 01:16:37.400 So, und dann, solange also dieses Open Set nicht leer ist, bestimmen 01:16:37.400 --> 01:16:39.980 wir immer den zu erweiterten Knoten. 01:16:40.260 --> 01:16:50.260 Also man findet einen Knoten aus der offenen Menge mit einem minimalen 01:16:50.260 --> 01:16:50.580 Kosten. 01:16:50.580 --> 01:16:57.260 Das heißt, die Gesamtfunktion f für diesen Knoten vi ist gleich g von 01:16:57.260 --> 01:16:59.560 vi plus h von i sind minimal. 01:16:59.780 --> 01:17:02.700 Wenn natürlich dieses vi unser Ziel ist, dann haben wir eine Lösung 01:17:02.700 --> 01:17:03.640 bereits gefunden. 01:17:05.520 --> 01:17:09.320 Sonst müssen wir natürlich hier dieses vi nach jeder Untersuchung, 01:17:09.340 --> 01:17:14.560 also wenn wir den besucht und analysiert haben, aus der Open Set 01:17:14.560 --> 01:17:21.420 entfernen und dann natürlich zu der Closed Set hinzufügen. 01:17:21.420 --> 01:17:26.240 Und dann müssen wir in jedem Schritt so ein Update machen, und zwar 01:17:26.240 --> 01:17:31.160 für alle Nachfolger von diesem Knoten, was wir gerade betrachten, also 01:17:31.160 --> 01:17:31.540 vi. 01:17:31.540 --> 01:17:42.800 Und wenn zum Beispiel der Nachfolger von einem Knoten vi in der Closed 01:17:42.800 --> 01:17:46.000 Set ist, dann natürlich überspringen wir das. 01:17:47.120 --> 01:17:51.020 Das heißt, wir haben das schon mal besucht und deshalb brauchen wir 01:17:51.020 --> 01:17:52.160 das nicht mehr zu betrachten. 01:17:52.160 --> 01:17:53.580 Wir überspringen den. 01:17:54.260 --> 01:17:59.100 Wenn der nicht in der Open Set ist, dann müssen wir natürlich das 01:17:59.100 --> 01:18:01.740 hinzufügen, weil wir das noch nicht besucht haben. 01:18:02.720 --> 01:18:04.660 Und dann betrachten wir diese Kosten. 01:18:04.660 --> 01:18:08.600 Also eigentlich muss man sich vorstellen, ich bin jetzt hier im 01:18:08.600 --> 01:18:09.980 Knoten. 01:18:13.250 --> 01:18:18.170 Ich bin im Knoten vi und das ist jetzt mein vi. 01:18:18.170 --> 01:18:18.770 Ja. 01:18:21.670 --> 01:18:30.450 Und wenn jetzt die Kosten von vi, also natürlich starte ich hier 01:18:30.450 --> 01:18:33.210 irgendwo an einem Startpunkt, hier vs. 01:18:34.210 --> 01:18:42.330 So, wenn die Kosten von vi, also natürlich um dorthin zu kommen, habe 01:18:42.330 --> 01:18:48.350 ich hier irgendwelche Kosten, und zwar das ist g von vi und um von vi 01:18:48.350 --> 01:18:52.110 zu vj zu kommen, habe ich natürlich auch Kosten. 01:18:52.970 --> 01:18:56.630 Und das sind Kosten vi, vj. 01:18:58.210 --> 01:19:07.310 Wenn die Kosten von g von vi plus die Kosten um von vi zu vj kleiner 01:19:07.310 --> 01:19:11.710 als die Kosten von vj, weil vj könnte natürlich man erreichen über 01:19:11.710 --> 01:19:12.770 einen anderen Weg. 01:19:14.010 --> 01:19:16.910 Und das wäre jetzt hier die Kosten vj. 01:19:18.190 --> 01:19:23.050 Wenn also diese Summe der Kosten kleiner als alle anderen 01:19:23.050 --> 01:19:29.170 Möglichkeiten, um an den Punkt oder an den Knoten vj zu kommen, dann 01:19:29.170 --> 01:19:37.190 sage ich okay, die Kosten von vj sind die Kosten von vi plus die 01:19:37.190 --> 01:19:38.630 Kosten von vi, vj. 01:19:38.630 --> 01:19:42.990 Also ich akzeptiere eigentlich vj als der nächste Punkt bzw. 01:19:43.250 --> 01:19:45.470 vi als der Vorgänger von vj. 01:19:46.430 --> 01:19:51.270 Und ich muss natürlich diese Heuristik berechnen, das heißt, was sind 01:19:51.270 --> 01:19:54.850 die geschätzten Kosten jetzt von vj zum Ziel, das ist irgendeine 01:19:54.850 --> 01:19:58.470 Heuristikfunktion, die eingegeben ist natürlich durch den Algorithmus. 01:19:58.470 --> 01:20:08.510 Und ich sage, dass der Vorgänger von vj ist vi. 01:20:09.290 --> 01:20:12.070 Also für jeden Knoten muss ich mir das alles merken. 01:20:12.310 --> 01:20:17.710 Einmal muss ich merken, sind die Kosten von dem Vorgänger plus die 01:20:17.710 --> 01:20:21.090 Kosten von dem Vorgänger zu dem jetzigen Punkt, den ich analysiere, 01:20:21.250 --> 01:20:23.170 kleiner als alle anderen Kosten? 01:20:23.170 --> 01:20:29.010 Dann definiere ich diesen neuen Punkt als den Nachfolger bzw. 01:20:29.250 --> 01:20:31.750 vi als den Vorgänger von vj. 01:20:32.190 --> 01:20:35.570 Und ich muss mir diese ganze Information merken, damit ich natürlich 01:20:35.570 --> 01:20:40.950 nachher rückwärts den Weg finde vom Ziel, wenn ich das Ziel erreiche, 01:20:41.190 --> 01:20:42.890 bis zum Startpunkt. 01:20:42.890 --> 01:20:46.670 Und das Ganze wollen wir anhand von einem Beispiel angucken. 01:20:47.010 --> 01:20:51.530 Also das ist so ein Raum, den haben wir diskretisiert hier. 01:20:51.670 --> 01:20:59.070 Wir haben Gitter mit 15 Knoten und wir sollen den optimalen Weg von V2 01:20:59.070 --> 01:21:00.530 nach V13 finden. 01:21:00.870 --> 01:21:03.890 Wir dürfen uns nur vertikal und horizontal bewegen. 01:21:05.630 --> 01:21:10.730 Und wir haben folgende Kosten, wenn wir eine graue Zelle betreten, 01:21:10.890 --> 01:21:14.290 dann haben wir eine Kosten von 1, wenn wir eine gelbe Zelle betreten, 01:21:14.390 --> 01:21:14.730 z.B. 01:21:14.890 --> 01:21:20.870 von V2 nach V5 oder V4 nach V5, dann haben wir Kosten von 4. 01:21:20.870 --> 01:21:26.430 Und unsere Heuristik, die H-Funktion, ist nichts anderes als die 01:21:26.430 --> 01:21:32.730 Heuristik, also die H-Funktion von irgendeiner Zelle, ist nichts 01:21:32.730 --> 01:21:37.410 anderes als die euklidische Distanz zum Ziel, zum Ziel, zu V13. 01:21:37.410 --> 01:21:38.270 Also z.B. 01:21:40.170 --> 01:21:49.870 die Heuristik um H bei Knoten V11 ist nichts anderes als 1 plus 1 zum 01:21:49.870 --> 01:21:51.710 Quadrat, also 2 zum Quadrat. 01:21:51.790 --> 01:21:53.770 Die euklidische Distanz ist Wurzel 2. 01:21:55.090 --> 01:21:58.610 Also das heißt, diese Heuristik muss natürlich immer definiert werden. 01:22:00.670 --> 01:22:04.050 So, und dann die Kosten natürlich pro Schritt. 01:22:05.130 --> 01:22:06.610 Und jetzt, wie gehen wir weiter? 01:22:06.690 --> 01:22:10.530 Wir initialisieren das Ganze, das heißt, wir fangen bei V2, weil wir 01:22:10.530 --> 01:22:12.810 wollen ja von V2 nach V13 kommen. 01:22:13.550 --> 01:22:19.970 Das heißt, unsere Funktion, Kostenfunktion von V2 ist natürlich die G 01:22:19.970 --> 01:22:22.170 -Kosten von V2, die sind 0. 01:22:22.310 --> 01:22:27.710 Wir initialisieren ja die Kosten für den Start, Knoten sind 0, plus 01:22:27.710 --> 01:22:29.510 die Heuristik von V2. 01:22:29.510 --> 01:22:37.230 Das bedeutet, die euklidische Distanz von V2 zu V13, das ist 1, 2, 3, 01:22:37.410 --> 01:22:43.690 4 zum Quadrat, plus 1 zum Quadrat, also Wurzel aus 17, also 4,12. 01:22:45.010 --> 01:22:49.950 So, und die Closed Set ist natürlich noch leer. 01:22:51.310 --> 01:22:52.430 Was machen wir? 01:22:52.530 --> 01:22:57.430 Wir machen jetzt ein Update und zwar bei diesem Update expandieren wir 01:22:57.430 --> 01:23:00.790 jetzt, gucken wir ja, welche Möglichkeiten haben wir jetzt von V2? 01:23:00.970 --> 01:23:04.870 Wir können zu V1 gehen, zu V5 und zu V3. 01:23:04.870 --> 01:23:10.170 Das heißt, unser Open Set ist jetzt V1, V3 und V5. 01:23:10.490 --> 01:23:14.590 Alle benachbarten Knoten von unserem Startknoten. 01:23:15.370 --> 01:23:16.330 Und was müssen wir machen? 01:23:16.430 --> 01:23:23.930 Wir müssen natürlich die Kostenfunktionen von allen Knoten im Open Set 01:23:23.930 --> 01:23:24.690 jetzt bestimmen. 01:23:24.690 --> 01:23:30.190 Und diese Kostenfunktion f ergibt sich aus der Kostenfunktion g plus 01:23:30.190 --> 01:23:31.530 die Heuristik h. 01:23:32.050 --> 01:23:37.070 Also das heißt, wenn ich jetzt hier ein bisschen zurückgehe, das ist 01:23:37.070 --> 01:23:42.390 eigentlich unsere Funktion g. Das ist Funktion g und das ist die 01:23:42.390 --> 01:23:43.190 Funktion h. 01:23:44.030 --> 01:23:54.810 So, das heißt, wenn ich hier zu V1 gehe, von V2, dann betrete ich eine 01:23:54.810 --> 01:23:55.530 graue Zelle. 01:23:55.770 --> 01:24:01.370 Deshalb sind die Kosten 1, um bei V1 zu landen, plus die Heuristik, um 01:24:01.370 --> 01:24:04.010 von V1 zu V13 zu kommen. 01:24:04.010 --> 01:24:06.950 Das sind nur 4 Blöcke, wie man sieht. 01:24:07.190 --> 01:24:09.490 Also Wurzel aus 4 Quadrat ist 4. 01:24:09.710 --> 01:24:11.150 Also 1 plus 4 ist 5. 01:24:11.950 --> 01:24:16.710 Von V3, ich betrete auch eine graue Zelle. 01:24:17.030 --> 01:24:22.090 Deshalb sind die Kosten 1 plus die Heuristik von V3 zu V13. 01:24:22.430 --> 01:24:26.130 Das ist 1, 2, 3, 4 zum Quadrat plus 2 zum Quadrat. 01:24:26.130 --> 01:24:32.710 Also 20 zum Quadrat ist 1 plus, also Wurzel von dem ist gleich 5, das 01:24:32.710 --> 01:24:32.950 hier. 01:24:34.150 --> 01:24:41.370 Und bei 5 sind die Kosten, ich betrete eine gelbe Zelle, deshalb ist g 01:24:41.370 --> 01:24:51.210 von 5 4 plus die Heuristik, die Kosten, also die Heuristik von V5 nach 01:24:51.210 --> 01:24:51.950 V13. 01:24:51.950 --> 01:24:57.550 Das ist 1, 2, 3 zum Quadrat plus 1 zum Quadrat, also 10 zum Quadrat, 01:24:57.710 --> 01:24:59.130 10 und Wurzel daraus. 01:24:59.310 --> 01:25:02.930 Also insgesamt habe ich die Kosten 7,16. 01:25:03.690 --> 01:25:04.790 Was bedeutet das? 01:25:04.850 --> 01:25:05.810 Was haben wir jetzt gemacht? 01:25:06.010 --> 01:25:09.450 Das heißt, wir haben jetzt den Punkt V2 abgeschlossen. 01:25:10.670 --> 01:25:11.990 Was machen wir als nächstes? 01:25:17.040 --> 01:25:19.420 Was ist der nächste Schritt jetzt in dem Algorithmus? 01:25:20.180 --> 01:25:22.020 Ja, das ist ja unser Ziel. 01:25:22.160 --> 01:25:25.100 Unser Ziel ist herauszufinden, welcher Weg der beste ist. 01:25:25.220 --> 01:25:28.060 Aber was genau muss ich jetzt machen als nächster Schritt? 01:25:29.200 --> 01:25:34.040 Genau, wir müssen eigentlich alle Knoten in diesem Open Set mal auf 01:25:34.040 --> 01:25:35.680 die gleiche Art und Weise analysieren. 01:25:35.820 --> 01:25:38.680 Das heißt, wir haben den Zustand, das ist unser Open Set. 01:25:38.680 --> 01:25:43.940 Das sind die Kosten von den Knoten in diesem Open Set und das ist 01:25:43.940 --> 01:25:44.840 unser Closed Set. 01:25:44.940 --> 01:25:46.340 Jetzt müssen wir ein Update machen. 01:25:47.220 --> 01:25:51.940 Wir können sagen, okay, wir expandieren V1 und man sieht hier von V1, 01:25:52.800 --> 01:25:58.880 wenn ich V1 expandiere, dann kommt natürlich V4 hier zum Open Set. 01:25:58.880 --> 01:26:05.780 Und V4, die Kosten sind, um von V2 nach V4 zu kommen, muss ich eine 01:26:05.780 --> 01:26:08.540 graue Zelle und nochmal eine graue Zelle betreten. 01:26:08.800 --> 01:26:14.380 Also deshalb die Kosten 2 plus die Heuristik von V4 zu V13. 01:26:14.760 --> 01:26:15.980 1, 2, 3. 01:26:16.620 --> 01:26:20.200 Wurzel aus 3 zum Quadrat ist 3, also insgesamt 5. 01:26:20.200 --> 01:26:24.440 Und somit habe ich hier V1 abgeschlossen. 01:26:25.020 --> 01:26:30.540 Natürlich von V1 kann man zu V2 gehen, aber V2 ist ja in der Closed 01:26:30.540 --> 01:26:34.120 Loop, deshalb überspringe ich den Schritt hier und brauche ich hier 01:26:34.120 --> 01:26:36.440 diese Analyse nicht mehr zu machen. 01:26:37.380 --> 01:26:41.140 Genau, das Beispiel werden wir in der Übung dann zu Ende führen. 01:26:41.700 --> 01:26:44.600 Ich werde natürlich nicht das ganze Beispiel jetzt hier zu Ende 01:26:44.600 --> 01:26:47.800 führen, damit wir den richtigen bzw. 01:26:48.040 --> 01:26:53.780 den optimalen, kostengünstigeren Weg von V2 nach V13 machen. 01:26:54.980 --> 01:27:01.240 Und ich will nur kurz mit ein paar Eigenschaften, obwohl die Zeit ist 01:27:01.240 --> 01:27:08.140 aus, deshalb machen wir am Donnerstag weiter mit ein paar 01:27:08.140 --> 01:27:11.740 Schlussbetrachtungen hier zum Algorithmus und dann weiter natürlich 01:27:11.740 --> 01:27:15.520 mit der Vorlesung, mit der Bewegungsplanung für Manipulatoren. 01:27:16.240 --> 01:27:19.080 Für heute bedanke ich mich sehr für die Aufmerksamkeit und wünsche 01:27:19.080 --> 01:27:20.260 euch noch einen schönen Abend.