Autonome Roboter folgen Pfaden, die vordefiniert sind oder vom Roboter situativ berechnet werden. Die Randbedingungen, die an solche Pfade gestellt werden, sind aus der subtraktiven und additiven Fertigung bekannt, aber komplex in der Umsetzung. Wir besprechen hier speziell die spiralförmigen Pfade und zeigen auf, welche vorteilhaften Eigenschaften diese bieten.
Roboter, die in von Menschen gestalteten Räumen und mit Menschen agieren sollen, haben es nicht leicht. Bewegen sie sich am Boden (UGV), geschieht dies fast immer fahrend. Dadurch treffen sie unweigerlich auf eine Vielzahl an Hindernissen, die wir Menschen ihnen in den Weg stellen. Roboter, die sich in Innenräumen bewegen, müssen Möbeln, Gegenständen, Menschen und Tieren, Treppen und Türen ausweichen. Im Aussenbereich bewegen sie sich zwischen Flora und Fauna, Wegen, Gebäuden, Gewässern, anspruchsvollen Geländeformen und der Witterung der Jahreszeiten.
Denken wir an staubsaugende oder rasenmähende Roboter, kommt erschwerend dazu, dass ein zentraler Teil ihrer Aufgaben darin besteht, das ganze ihnen zugeteilte Gebiet vollständig abzudecken. Das kann mitunter schlicht unmöglich sein, weil unüberwindbare Hindernisse vorhanden sind.
Bei der Festlegung des Pfads, auf dem sich ein Roboter bewegen soll, können unterschiedliche Ansätze verfolgt werden. Das Zufallsprinzip funktioniert immer, wird aber unter Umständen sehr lange benötigen, um die ganze Fläche abzudecken, und ist daher ineffizient. Eine andere, naheliegende Strategie kann sein, ein Gebiet mit einem einzigen, zusammenhängenden Pfad abzufahren. Dieses Vorgehen macht die sowieso schon anspruchsvolle Aufgabe noch herausfordernder. Was wir dazu benötigen, sind flächenfüllende Kurven. Diese sollten nicht mit den in der Mathematik bekannten raumfüllenden Kurven verwechselt werden. Die Mathematik fordert eine sogenannte Selbstähnlichkeit, d. h. wie bei einem Fraktal, die Eigenschaft, unabhängig von der Skalierung (dem «Zoomfaktor») bei der Betrachtung immer ähnlich auszusehen.
Da Roboter nicht unendlich klein sind, sondern eine bestimmte Grösse haben, macht es keinen Sinn, Pfade zu verwenden, die kleinere Strukturen enthalten. Zum Beispiel gibt es für einen staubsaugenden Roboter einen minimalen Bahnabstand, gegeben durch seine Grösse, den zu unterschreiten keinen Sinn macht. Diese mathematischen Kurven haben auch die Eigenschaft, sehr viele Richtungswechsel zu enthalten (z. B. die im 3D-Druck gebräuchlichen Hilbertkurven) und dadurch sehr lange zu werden, was für unsere Roboter auch eher unsinnig erscheint.
Ich möchte hier exemplarisch auf zwei Projekte eingehen, an denen unsere Hochschule in der näheren Vergangenheit beteiligt war. Zum einen ein Projekt, in dem der Grund von kleinen Seen kartiert werden soll, und zum anderen ein Projekt, bei dem der Grad an Lichtverschmutzung in der Umwelt bestimmt werden soll.
Die Oberfläche von den für uns relevanten Seen ist in der Form ähnlich zu der Umgebung, in der sich staubsaugende oder rasenmähende Roboter bewegen, nur tendenziell einfacher, da meist weniger Inseln vorhanden sind, als es Möbelbeine in einem Wohnzimmer oder Büsche in einem Garten gibt. Ein sehr klassischer Ansatz ist das zeilen- oder spaltenweise Vorgehen, bei dem in einem mäandernden Hin und Her eine Fläche abgedeckt wird (Abbildung 1).
ㅤ
Häufig wird dieses Muster auch gedreht verwendet, also unter einem vorgegebenen Winkel. Dieses Vorgehen ist aber im Falle von Hindernissen nicht so einfach anwendbar (Abbildung 2).
ㅤ
Eine Lösung kann sein, den Pfad zu unterbrechen und jeweils den kürzesten Pfad um das Hindernis herum zur Fortsetzung zu suchen. Dieses Vorgehen führt aber zu vielen ähnlichen Ausweichmanövern und Umwegen (Abbildung 3).
ㅤ
Mithilfe einer Approximate Convex Decomposition (ACD) [1] kann ein solches löchriges und konkaves Gebiet in annähernd konvexe Teilgebiete zerlegt werden. So ist es möglich, die Pfadplanung erfolgreich auf diesen Teilgebieten durchzuführen. Das Finden von Pfaden, die diese Teilgebiete verbinden, ist weniger aufwändig. Allerdings können auch diese zusammengenommen eine nicht zu vernachlässigende Länge aufweisen (Abbildung 4).
Es gibt weitere Ansätze, die aber alle das grundlegende Problem nicht lösen. Als Beispiel dazu sei das Vorgehen von 3D-Filament-Druckern aufgeführt, dort kann dieselbe Problematik beim Erstellen der Füllung (Infill) beobachtet werden. Der Druckkopf hat allerdings den Vorteil, dass er abheben und über die Löcher «fliegen» kann. Trotzdem ist dieser Vergleich hilfreich, da die Forschung in diesem Gebiet in den letzten Jahren mit den Connected Fermat Spirals [2] eine Lösung für unser Problem gefunden hat (Abbildung 5).
Das Vorgehen funktioniert auf sehr komplex geformten Flächen, schlimmstenfalls mit minimalen Überlappungen der Pfade. Aber die Algorithmen können dies in der Regel sehr gut vermeiden, denn im Gegensatz zu unserer Aufgabe, ein Gebiet abzufahren, ist es im Falle von 3D-Druck kritisch, ob eine Stelle mehrfach oder zu nahe passiert wird, das beeinflusst den Materialauftrag negativ. Im erwähnten Projekt hat dieses Vorgehen noch einen weiteren entscheidenden Vorteil, wir können einen See so entlang des Ufers und somit grösstenteils entlang der Höhenlinien des Seebodens befahren. Da wir unter anderem nach Pflanzen suchen, die in bestimmten, eng begrenzten Tiefen leben, ist das ein zusätzlicher, unschätzbarer Vorteil des Vorgehens. In unserem zweiten Projekt dieser Art war das technische Ziel, ein drohnenbasiertes Goniophotometer [3] zu realisieren (Abbildung 6).
Ein Goniophotometer wird dazu verwendet, eine Lichtquelle aus allen Blickwinkeln zu vermessen, also die Oberfläche einer Kugel mit der Lichtquelle im Zentrum mit Messpunkten abzudecken. Bei fest installierten Goniometern im Labor werden typischerweise die Punkte so gewählt, dass sie auf den Schnittpunkten der Längen- und Breitengrade liegen (wenn die Kugel eine Weltkarte wäre). Soll nun eine grosse Kugel von 10 oder 100 Metern Radius anhand einer fliegenden Drohne vermessen werden, stellt sich die Frage nach dem optimalen Flugpfad. Ähnlich wie im vorherigen Fall könnte das Vorgehen zeilen- oder spaltenweise (also entlang der Längen- oder Breitengrade) sein, um nach jedem Umlauf auf den nächsten Ring zu wechseln (Abbildung 7).
Dies wäre für Drohnen mit Schwebefähigkeit (Multi-/Helikopter) möglich, nicht aber für Festflügler (Flugzeuge). Weiter hat es den Nachteil, dass die verschiedenen Punkte bei der Berechnung von Flussgrössen durch die Oberfläche – also z. B. der Abstrahlung – mit unterschiedlichen Gewichten in die Berechnung eingehen. Das ist unpraktisch und insbesondere bei Positionsfehlern auch problematisch. Weiter erlauben diese Art von Pfaden oder Gittern nur eine bestimmte Anzahl von Punkten und Zahlen, die nicht als Produkte von zwei kleineren Zahlen dargestellt werden können, wie Primzahlen, sind beispielsweise nicht möglich. Ein Ansatz zur Lösung dieser Probleme ist die Verwendung von Archimedesspiralen. Sie erlauben es, anhand eines einzigen zusammenhängenden Pfades, die ganze Kugeloberfläche so gleichmässig abzudecken, dass für jeden Messpunkt die Gewichtung gleich gross ist (Abbildung 8).
ㅤ
Über die Oberfläche numerisch zu integrieren, um verschiedene Grössen zu berechnen, ist dann nur noch eine Frage davon, die Messwerte aufzusummieren und skalieren (wie bei einer Mittelung). Diese beiden Spiralpfadansätze bieten zusätzliche, interessante Eigenschaften und Möglichkeiten. So können die Connected Fermat Spirals weiter verallgemeinert werden für beliebig geformte Oberflächen, um z. B. Tunnelsysteme in Bergwerken oder Minenschächten zu kartieren (Abbildung 9).
Es ist auffällig, dass die beschriebenen Probleme der Pfadfindung grosse Ähnlichkeiten mit Problemen in der additiven und subtraktiven Fertigung aufweisen, also im 3D-Druck und der CNC-Bearbeitung. Diese neuen und doch altbekannten Probleme haben keine allgemeinen Lösungen, die hier vorgestellten Ansätze sind aber sehr robust und decken viele Anwendungsgebiete ab.
Weitere Blogs der FH Graubünden gibt es hier zu lesen.
Quellverzeichnis
Wei, Xinyue, Liu, Minghua, Ling, Zhan, Su, Hao. Approximate convex decomposition for 3d meshes with collision-aware concavity and tree search. 2022. CoACD GitHub Repository
Haisen Zhao, Fanglin Gu, Qi-Xing Huang, Jorge Garcia, Yong Chen, Changhe Tu, Bedrich Benes, Hao Zhang, Daniel Cohen-Or, Baoquan Chen. Connected Fermat Spirals for Layered Fabrication. 2016. CFS Project Page
Ursin Solèr, Constantinos A. Bouroussis, Robin Derungs. UAV flight paths for goniometric mapping and numerical integration. 2025. PREPRINT
Ursin Solèr, Dozent FH Graubünden, Institut für Photonics und Robotics (IPR)