Forscher des MIT haben nun ein Sicherheitsprüfverfahren entwickelt, das mit hundertprozentiger Genauigkeit nachweisen kann, dass die Bahn eines Roboters kollisionsfrei bleibt (vorausgesetzt, die Roboter- und Umgebungsmodelle sind korrekt). Ihre Methode ist so präzise, ​​dass sie selbst um Millimeter abweichende Bahnen unterscheiden kann und liefert den Beweis in nur wenigen Sekunden.

Der Benutzer muss den Forschern jedoch nicht blind vertrauen: Der mit dieser Technik erzeugte mathematische Beweis lässt sich schnell mit relativ einfachen mathematischen Operationen überprüfen.

Die Forscher erreichten dies mithilfe einer speziellen algorithmischen Technik namens Summen-von-Quadraten-Programmierung, die sie anpassten, um das Sicherheitsprüfungsproblem effektiv zu lösen. Die Summen-von-Quadraten-Programmierung ermöglicht die Verallgemeinerung der Methode auf ein breites Spektrum komplexer Bewegungen.

Diese Technik könnte besonders nützlich sein für Roboter, die sich schnell bewegen und dabei Kollisionen in unübersichtlichen Umgebungen vermeiden müssen, beispielsweise Roboter, die in einer Großküche Speisen zubereiten. Sie eignet sich auch für Situationen, in denen Roboterkollisionen zu Verletzungen führen könnten, etwa bei Gesundheitsrobotern, die gefährdete Patienten behandeln.

„Mit dieser Arbeit haben wir gezeigt, dass sich einige schwierige Probleme mit konzeptionell einfachen Werkzeugen lösen lassen. Die Summe-von-Quadraten-Programmierung ist eine leistungsstarke algorithmische Idee, und obwohl sie nicht alle Probleme löst, kann sie bei sorgfältiger Anwendung einige nicht-triviale Probleme lösen“, sagt Alexandre Amice, Doktorand der Elektrotechnik und Informatik (EECS) und Hauptautor einer Veröffentlichung zu dieser Technik.

Amice verfasste den Artikel gemeinsam mit Peter Werner, ebenfalls Student der Elektrotechnik und Informatik (EECS), sowie mit Russ Tedrake, Toyota-Professor für Luft- und Raumfahrttechnik und Maschinenbau an der EECS und Mitglied des Labors für Informatik und Künstliche Intelligenz (CSAIL). Die Arbeit wird auf der Internationalen Konferenz für Robotik und Automatisierung vorgestellt.

Sicherheit zertifizieren

Viele gängige Methoden zur Überprüfung der Kollisionsfreiheit geplanter Roboterbewegungen simulieren die Bewegungsbahn und prüfen alle paar Sekunden, ob der Roboter mit einem Objekt kollidiert. Diese statischen Sicherheitsprüfungen können jedoch nicht vorhersagen, ob der Roboter in den dazwischenliegenden Sekunden mit einem Objekt kollidieren wird.

Für einen Roboter, der in einem offenen Raum mit wenigen Hindernissen umherstreift, mag dies kein Problem darstellen, aber für Roboter, die in beengten Räumen komplizierte Aufgaben ausführen, können wenige Sekunden Bewegung einen großen Unterschied ausmachen.

Konzeptionell lässt sich demonstrieren, dass ein Roboter nicht auf ein Hindernis zusteuert, indem man ein Blatt Papier hochhält, das den Roboter von allen Hindernissen in seiner Umgebung trennt. Mathematisch wird dieses Blatt Papier als Hyperebene bezeichnet. Viele Sicherheitsalgorithmen generieren diese Hyperebene nur einmal. Bei jeder Bewegung des Roboters muss jedoch eine neue Hyperebene berechnet werden, um die Sicherheitsprüfung durchzuführen.

Im Gegensatz dazu erzeugt diese neue Technik eine Hyperebenenfunktion, die sich mit dem Roboter bewegt, sodass gezeigt werden kann, dass eine gesamte Trajektorie kollisionsfrei ist, anstatt jedes Mal mit einer Hyperebene zu arbeiten.

Die Forscher nutzten die Summe-von-Quadraten-Programmierung, ein algorithmisches Werkzeug, das ein statisches Problem in eine Funktion umwandeln kann. Diese Funktion ist eine Gleichung, die beschreibt, wo die Hyperebene an jedem Punkt entlang des geplanten Pfades liegen muss, um Kollisionen zu vermeiden.

Die Summe der Quadrate lässt sich auf das Optimierungsprogramm zur Bestimmung einer Familie kollisionsfreier Hyperebenen verallgemeinern. Obwohl sie oft als rechenintensive Optimierungsmethode gilt, die sich nur für die Offline-Anwendung eignet, haben Forscher gezeigt, dass sie für dieses Problem äußerst effizient und genau ist.

„Der Schlüssel lag darin, herauszufinden, wie wir die Summe der Quadrate auf unser konkretes Problem anwenden können. Die größte Herausforderung war die Formulierung des Ausgangsproblems. Wenn ich nicht möchte, dass mein Roboter irgendwo gegenstößt, was bedeutet das mathematisch, und kann mir der Computer eine Antwort geben?“, sagt Amice.

Letztendlich ergibt die Summe der Quadrate, wie der Name schon sagt, eine Funktion, die die Summe mehrerer quadrierter Werte ist. Die Funktion ist immer positiv, da das Quadrat einer Zahl immer einen positiven Wert ergibt.

Vertrauen ist gut, Kontrolle ist besser

Indem man überprüft, ob die Hyperebenenfunktion Quadratwerte enthält, kann ein Mensch leicht feststellen, dass die Funktion positiv ist, was bedeutet, dass der Pfad kollisionsfrei ist, erklärt Amice.

Obwohl die Methode mit perfekter Genauigkeit zertifiziert, setzt dies voraus, dass der Benutzer über ein exaktes Modell des Roboters und der Umgebung verfügt; die mathematische Zertifizierung ist nur so gut wie das Modell.

„Das Tolle an dieser Methode ist, dass die Tests sehr leicht zu interpretieren sind, sodass Sie sich nicht darauf verlassen müssen, dass ich sie korrekt codiere, sondern sie selbst überprüfen können“, fügt er hinzu.

Sie testeten ihr Verfahren in Simulationen und bestätigten, dass die komplexen Bewegungsabläufe von ein- und zweiarmigen Robotern kollisionsfrei verlaufen. In der langsamsten Variante benötigte die Methode nur wenige hundert Millisekunden für die Generierung eines Tests und war damit deutlich schneller als andere alternative Verfahren.

Obwohl ihre Methode schnell genug ist, um in einigen realen Situationen als abschließende Sicherheitsprüfung eingesetzt zu werden, ist sie immer noch zu langsam, um direkt in der Bewegungsplanungsschleife eines Roboters angewendet zu werden, wo Entscheidungen im Mikrosekundenbereich getroffen werden müssen, sagt Amice.

Die Forscher planen, den Prozess zu beschleunigen, indem sie Situationen ignorieren, die keine Sicherheitsprüfungen erfordern, beispielsweise wenn sich der Roboter weit von Objekten entfernt befindet, mit denen er kollidieren könnte. Sie wollen außerdem mit spezialisierten Optimierungsalgorithmen experimentieren, die schneller arbeiten können.

Diese Arbeit wurde teilweise von Amazon und dem United States Air Force Research Laboratory finanziert.