Verbesserte Roboterwahrnehmung durch GNC-Algorithmus

Als Vasileios Tzoumas, ein Wissenschaftler am Massachusetts Institute of Technology (MIT), besucht eine neue Stadt und erkundet diese gerne beim Joggen. Und manchmal verirrt er sich. Vor ein paar Jahren passierte während eines langen Laufs in Osaka, wo er an einer Konferenz teilnahm, das Unvermeidliche. Doch dann entdeckte Tzoumas einen 7-Eleven, an dem er, wie er sich erinnerte, kurz nach dem Verlassen seines Hotels vorbeigekommen war. Diese Erkenntnis ermöglichte es ihm, den Kreis gedanklich zu schließen und das lose Ende seines Laufwegs mit einem Ort zu verbinden, den er kannte und bei dem er sich sicher war. Auf diese Weise festigte sich seine mentale Karte und er konnte den Weg zurück zum Hotel finden.

Der GNC-Algorithmus (Graduated Nonconvexity) könnte Maschinen dabei helfen, Land, Wasser, Himmel und Weltraum zu durchqueren – und zurückzukommen, um davon zu berichten.

„Den Kreis schließen“ ist eigentlich ein technischer Begriff für etwas, das Roboter häufig tun müssen, wenn sie sich in neuen Umgebungen zurechtfinden. Es ist Teil eines Prozesses namens Simultaneous Localization and Mapping (SLAM). SLAM ist nicht neu. Es wird für Roboterstaubsauger, selbstfahrende Autos, Such- und Rettungsdrohnen sowie Roboter in Fabriken, Lagerhäusern und Bergwerken verwendet. Während autonome Geräte und Fahrzeuge neue Räume erkunden, vom Wohnzimmer bis in den Himmel, erstellen sie während ihrer Reise eine Karte. Außerdem müssen sie mithilfe von Sensoren wie Kameras, GPS und Lidar herausfinden, wo sie sich auf der Karte befinden.

Da SLAM immer mehr Anwendung findet, ist es wichtiger denn je, sicherzustellen, dass SLAM-Algorithmen unter anspruchsvollen realen Bedingungen korrekte Ergebnisse liefern. SLAM-Algorithmen funktionieren oft gut mit perfekten Sensoren oder unter kontrollierten Laborbedingungen, aber sie laufen leicht ins Leere, wenn sie mit mangelhaften Sensoren in der realen Welt implementiert werden. Es überrascht nicht, dass Industriekunden häufig besorgt sind, ob sie diesen Algorithmen vertrauen können.

Forscher am MIT haben mehrere robuste SLAM-Algorithmen sowie Methoden entwickelt, um mathematisch zu beweisen, wie weit wir ihnen vertrauen können. Das Labor von Luca Carlone, dem Leonardo Career Development-Assistenzprofessor am MIT, veröffentlichte einen Artikel über ihren Graduated Non-Convexity-Agorithmus (GNC), der die Zufallsfehler und Unsicherheiten in den SLAM-Ergebnissen reduziert. Und was noch wichtiger ist: Der Algorithmus liefert korrekte Ergebnisse, wo bestehende Methoden „sich verlaufen“. Das Papier von Carlone, Tzoumas und Carlones Studenten Heng Yang und Pasquale Antonante erhielt auf der International Conference on Robotics and Automation (ICRA) die Auszeichnung für den besten Fachartikel im Bereich Robotersehen. Dieser GNC-Algorithmus wird Maschinen dabei helfen, Land, Wasser, Himmel und Weltraum zu durchqueren – und zurückzukommen, um davon zu erzählen.

Alles ist ausgerichtet

Die Wahrnehmung von Robotern basiert auf Sensoren, die oft verrauschte oder irreführende Eingaben liefern. Mithilfe des GNC-Algorithmus des MIT kann der Roboter entscheiden, welchen Datenpunkten er vertraut und welche er verwirft. Eine Anwendung des GNC-Algorithmus heißt Formausrichtung. Ein Roboter schätzt den 3D-Standort und die Ausrichtung eines Autos anhand von 2D-Kamerabildern. Der Roboter erhält ein Kamerabild mit vielen Punkten, die durch einen Merkmalserkennungsalgorithmus gekennzeichnet sind: Scheinwerfer, Räder, Spiegel. Außerdem hat er ein 3D-Modell eines Autos im Speicher. Das Ziel besteht darin, das 3D-Modell so zu skalieren, zu drehen und zu platzieren, dass seine Merkmale mit den Merkmalen im Bild übereinstimmen. „Das ist einfach, wenn der Merkmalserkennungsalgorithmus seine Aufgabe perfekt erledigt hat, aber das ist selten der Fall“, sagt Carlone. In realen Anwendungen wird der Roboter mit vielen Ausreißern – falsch bezeichneten Merkmalen – konfrontiert, die mehr als 90% aller Beobachtungen ausmachen können. Hier kommt der GNC-Algorithmus ins Spiel und übertrifft alle Konkurrenten.

Roboter lösen dieses Problem mithilfe einer mathematischen Funktion, die den Abstand zwischen jedem Merkmalspaar berücksichtigt – beispielsweise dem rechten Scheinwerfer im Bild und dem rechten Scheinwerfer im Modell. Sie versuchen, diese Funktion zu „optimieren“ – das Modell so auszurichten, dass alle diese Entfernungen minimiert werden. Je mehr Funktionen, desto schwieriger das Problem.

Eine Möglichkeit, das Problem zu lösen, besteht darin, alle möglichen Lösungen für die Funktion auszuprobieren und zu sehen, welche am besten funktioniert. Allerdings gibt es zu viele, um sie alle auszuprobieren. Eine gängigere Methode, erklären Yang und Antonante, besteht darin, „eine Lösung auszuprobieren und sie dann immer weiter zu verfeinern – beispielsweise die Scheinwerfer im Modell besser an die Scheinwerfer im 2D-Bild anzupassen –, bis keine Verbesserung mehr möglich ist.“ Bei verrauschten Daten wird es nicht perfekt sein – vielleicht passen die Scheinwerfer, aber die Räder nicht –, also können Sie mit einer anderen Lösung neu beginnen und diese so weit wie möglich verfeinern und den Prozess mehrere Male wiederholen, um das beste Ergebnis zu finden. Dennoch sind die Chancen, die bestmögliche Lösung zu finden, gering.

In realen Anwendungen wird der Roboter mit vielen Ausreißern konfrontiert, die mehr als 90% aller Beobachtungen ausmachen können. Hier kommt der GNC-Algorithmus ins Spiel und übertrifft alle Konkurrenten.

Mesh und Punktwolke mit Korrespondenzen (70% Ausreißer)

Erfolgreiche Registrierung durch GNC-TLS

Fehlerhafte Registrierung durch gängige SLAM-Algorithmen

Der GNC-Algorithmus findet die optimale Ausrichtung trotz verrauschter Messungen mit bis zu 70–90% Ausreißern. Bildquelle: MIT

Die Idee hinter GNC besteht darin, zunächst das Problem zu vereinfachen. Sie reduzieren die Funktion, die sie optimieren möchten – also die Funktion, die die Unterschiede zwischen dem 3D-Modell und dem 2D-Bild beschreibt – auf eine Funktion mit einer einzigen besten Lösung. Wenn sie sich nun für eine Lösung entscheiden und diese vorantreiben, werden sie letztendlich die beste Lösung finden. Dann führen sie ein wenig von der Komplexität der ursprünglichen Funktion wieder ein und verfeinern die Lösung, die sie gerade gefunden haben. Sie machen so lange weiter, bis sie die ursprüngliche Funktion und ihre optimale Lösung haben. Die Scheinwerfer sind gut ausgerichtet, ebenso die Räder und Stoßstangen.

Im Kreis gehen

Das Dokument wendet den GNC-Algorithmus auf Formausrichtung und auf SLAM, sowie weitere Probleme an. Im Fall von SLAM Verwendet der Roboter Sensordaten, um die bisherige Fahrbahn zu ermitteln und eine Karte zu erstellen. Beispielsweise streift ein Roboter über einen Universitätscampus, und sammelt Odometriedaten, die Aufschluss darüber geben, wie weit und in welche Richtung er zwischen 8:00 Uhr und 8:15 Uhr, zwischen 8:15 Uhr und 8:30 Uhr, und so weiter, gegangen ist. Es hat auch Lidar- und Kameradaten bei 8:00 Uhr, 8:15 Uhr, und so weiter. Gelegentlich wird er Schleifen schließen (d.h. zum Ausgangspunkt zurückkehren) und dasselbe zu zwei verschiedenen Zeitpunkten sehen, wie es Tzoumas tat, als er nochmal am 7-Eleven vorbeilief.

Die Forscher stellten fest, dass der GNC-Algorithmus genauer war als die modernsten Techniken und einen höheren Prozentsatz an Ausreißern verarbeiten konnte.

Genau wie bei der Formausrichtung muss ein Optimierungsproblem gelöst werden. Yang, der Erstautor des Artikels, erklärt: „Bei SLAM richtet das System die Merkmale nicht so aus, dass sie einem 3D-Modell entsprechen, sondern verbiegt die Bahn, von der es glaubt, dass es sie zurückgelegt hat, um die Objekte auf der Karte auszurichten.“ Erstens versucht das System, die Unterschiede zwischen den von verschiedenen Sensoren erfassten Fahrten zu minimieren, da es bei jedem Sensor zu Messfehlern kommen kann. Wenn der Kilometerzähler des Roboters beispielsweise anzeigt, dass er zwischen 8:00 und 8:15 Uhr 100 Meter zurückgelegt hat, sollte die auf Grundlage der Lidar- und Kameramessungen aktualisierte Bahn diese Distanz oder einen annähernd ähnlichen Wert wiedergeben. Das System minimiert außerdem die Entfernungen zwischen Standorten, die derselbe Ort zu sein scheinen. Wenn der Roboter beispielsweise um 8:00 Uhr und um 10:00 Uhr denselben 7-Eleven gesehen hat, versucht der Algorithmus, den erinnerten Weg zu ändern – indem er jedes Bein anpasst –, sodass seine abgerufenen Positionen um 8:00 Uhr und um 10:00 Uhr übereinstimmen und der Kreis geschlossen wird.

Roboter kartiert das Innere eines Gebäudes. GNC entschlüsselt unordentliche Daten schrittweise. In relativ wenigen Schritten erstellt der Algorithmus eine genaue Karte des Inneren eines Gebäudes. Bildquelle: MIT

In der Zwischenzeit identifiziert und verwirft der Algorithmus Ausreißer – fehlerhafte Datenpunkte, bei denen er dachte, er würde seine Schritte zurückverfolgen, was aber nicht der Fall war – sowie falsch beschriftete Merkmale bei der Formausrichtung. Eine Schleife soll nicht fälschlicherweise geschlossen werden. Tzoumas erinnert sich an einen Moment, als er durch die Wälder von Maine lief und an einer Ansammlung umgestürzter Baumstämme vorbeikam, die ihm bekannt vorkamen. Er dachte, er hätte die Schleife geschlossen und bog anhand dieses vermeintlichen Orientierungspunkts ab. Erst als er zwanzig Minuten lang nichts Vertrautes sah, bemerkte er seinen Fehler und kehrte um.

Eine abgerufene Bewegungsbahn vor der Optimierung kann wie ein verhedderter Garnknäuel aussehen. Nach dem Entwirren ähnelt es einer Reihe rechtwinkliger Linien, die die Form der Wege und Flure des Campus widerspiegeln, die der Roboter durchquert hat. Der Fachbegriff für diesen SLAM-Prozess lautet Pose-Graph-Optimierung.

In dem Artikel verglichen die Forscher ihren GNC-Algorithmus mit anderen Algorithmen in mehreren Anwendungen, darunter Formausrichtung und Pose-Graph-Optimierung. Sie stellten fest, dass ihre Methode genauer war als die modernsten Techniken und mit einem höheren Prozentsatz an Ausreißern umgehen konnte. Bei SLAM funktionierte es sogar, wenn drei von vier Schleifenschlüssen fehlerhaft waren, was viel mehr Ausreißer sind, als es bei einer Anwendung in der Praxis vorkommen würde. Darüber hinaus ist ihre Methode oft effizienter als andere Algorithmen und erfordert weniger Rechenschritte. Tzoumas sagt: „Eine der Schwierigkeiten bestand darin, einen universellen Algorithmus zu finden, der für viele Anwendungen gut funktioniert.“ Yang sagt, sie hätten es bei mehr als 10 versucht. Am Ende, sagt Tzoumas, hätten sie „optimalen Punkt“ gefunden.

Der GNC-Algorithmus rekonstruiert korrekt eine Karte des Inneren des MIT Great Dome. — MATLAB generierte Karten aus Daten, die von einem Rasenmäherroboter stammen. Links: Originalkarte des Rasens. Mitte: Mit gängigen SLAM-Algorithmen optimierte Karte, die falsch beschriftete Daten aus unbekannten Ausreißer-Loop-Closures einbezieht. Rechts: Mit GNC-Algorithmus optimierte Karte.

„Der Übergang von der Forschung zur Produktion ist ein wichtiger Schritt, damit die Forschungsergebnisse im großen Maßstab etwas bewirken“, sagt Roberto G. Valenti, Robotik-Forscher bei MathWorks. MathWorks hat mit Carlones Labor zusammengearbeitet, um die GNC-Algorithmen als Teil der Navigation Toolbox™ in MATLAB zu integrieren, die Unternehmen zur Implementierung von SLAM auf kommerziellen und industriellen autonomen Systemen verwenden.

Raus aus dem Wald

Carlones Labor arbeitet an Möglichkeiten, die Fähigkeiten ihres GNC-Algorithmus zu erweitern. Yangs Ziel ist es beispielsweise, Wahrnehmungsalgorithmen zu entwickeln, deren Richtigkeit zertifiziert werden kann. Und Antonante findet Wege, Inkonsistenzen zwischen verschiedenen Algorithmen zu bewältigen: Wenn das SLAM-Modul eines autonomen Fahrzeugs anzeigt, dass die Straße geradeaus verläuft, das Fahrspurerkennungsmodul jedoch angibt, dass sie nach rechts abbiegt, liegt ein Problem vor.

Der GNC-Algorithmus ist der neue Maßstab, wenn es darum geht, Robotern zu ermöglichen, ihre eigenen Fehler zu erkennen.

Tzoumas untersucht, wie sich nicht nur die Interaktion zwischen mehreren Algorithmen in einem Roboter, sondern auch die Zusammenarbeit zwischen mehreren Robotern skalieren lässt. In früheren Arbeiten programmierte er fliegende Drohnen, um Ziele zu verfolgen, etwa Kriminelle, die zu Fuß oder mit dem Auto zu fliehen versuchten. In Zukunft könnten möglicherweise mehrere Maschinen den GNC-Algorithmus gemeinsam ausführen. Jeder würde seinen Nachbarn Teilinformationen übermitteln und gemeinsam würden sie eine Weltkarte erstellen – von Orten auf der Erde oder anderswo. Dieses Jahr wechselt er in die Fakultät für Luft- und Raumfahrttechnik der University of Michigan, um dort an vertrauenswürdiger Autonomie für die Planung und Selbstnavigation mehrerer Roboter zu arbeiten – selbst in schwierigen Umgebungen wie Schlachtfeldern und anderen Planeten.

„Nicht zu wissen, wie sich KI und Wahrnehmungsalgorithmen verhalten, ist ein großes Hindernis für deren Einsatz“, sagt Antonante. Er weist darauf hin, dass man Robotern, die Museumsführer einsetzen, nicht trauen würde, wenn die Gefahr besteht, dass sie mit Besuchern oder der Mona Lisa zusammenstoßen: „Sie möchten, dass Ihr System sowohl seine Umgebung als auch sich selbst genau versteht, damit es seine eigenen Fehler erkennen kann.“ Der GNC-Algorithmus ist der neue Maßstab, wenn es darum geht, Robotern zu ermöglichen, ihre eigenen Fehler zu erkennen. Und was am wichtigsten ist: „Er hilft Ihnen, aus dem Gröbsten herauszukommen“, wie Tzoumas sagt.