PV-OSIMr: A Lowest Order Complexity Algorithm for Computing the Delassus Matrix

Autoren: Ajay Suresha Sathya, Wilm Decré, Jan Swevers · IEEE Robotics and Automation Letters (RA-L) 2024

Lizenzen

Open Access
Paper: CC BY-SA 4.0

Alles Folgende stützt sich auf das vollständige Paper unter seiner Lizenz CC BY-SA 4.0; die Abbildung wird mit Nennung der Autoren gezeigt.

Kurz gesagt

Ordnet die PV-OSIM-Berechnungen so um, dass propagierte Zwangsbedingungen nie mehr als sechs Dimensionen haben, und erreicht so eine Berechnung der Delassus-Matrix in O(n + m²), die nach Darstellung der Autoren asymptotisch optimal ist.

Warum es wichtig ist

Roboter mit vielen Kontakten, etwa Humanoide mit Füßen und mehrfingrigen Händen, benötigen diese Matrix mit hoher Rate für Simulation und Regelung; weniger Operationen bedeuten daher schnellere Löser. Da der Aufbau einer m × m-Matrix und der Besuch aller n Gelenke unvermeidlich sind, argumentieren die Autoren, dass O(n + m²) die optimale Ordnung ist. Der Algorithmus wurde mit CasADi-Codegenerierung implementiert und laut Paper auch in C++ in der Bibliothek Pinocchio.

Problem

Die Delassus-Matrix, also die inverse Trägheitsmatrix im Operationsraum, verknüpft Zwangskräfte mit Zwangsbeschleunigungen und wird für die Simulation beschränkter Dynamik und Kontaktdynamik sowie für die Regelung im Operationsraum benötigt, wo sie in MPC und RL oft der aufwendigste Schritt ist. Eine naive Berechnung kostet O(n³ + m²n). Der beste bekannte Algorithmus, EFPA, erreicht O(n + md + m²), während das frühere PV-OSIM der Autoren O(n + m²d) hat und schlecht skaliert, wenn viele Zwangsbedingungen durch viele Gelenke propagiert werden müssen.

Lösungsansatz

PV-OSIMr verändert den Rückwärtsdurchlauf von PV-OSIM so, dass statt Matrizen im Zwangsraum, die mit der Anzahl der Zwangsbedingungen wachsen, feste 6×6-Matrizen der erweiterten Kraftpropagatoren und räumliche inverse Trägheiten zwischen aufeinanderfolgenden Verzweigungsgliedern (der Menge N) propagiert werden. Ein begrenzter Vorwärtsdurchlauf über N berechnet die inversen Trägheiten, ein begrenzter Rückwärtsdurchlauf berechnet den Propagator im Zwangsraum für jeden Endeffektor, und jeder Block der Delassus-Matrix wird in konstanter Zeit zusammengesetzt. Daraus ergibt sich eine Komplexität von O(n + m²).

Wichtigste Erkenntnisse

Wenn ein Glied mehr als sechs Zwangsdimensionen trägt, ist es günstiger, räumliche 6D-Größen zu propagieren und die Terme im Zwangsraum später zurückzugewinnen, als die Terme im Zwangsraum direkt zu propagieren.
Aufwendige Größen müssen nur an den nächsten gemeinsamen Vorfahren der beschränkten Glieder berechnet werden, sodass die zusätzlichen Durchläufe über eine reduzierte Menge von Gliedern laufen.
Eine niedrigere asymptotische Komplexität garantiert bei kleinen Robotern nicht weniger Operationen: EFPA war bei fast allen getesteten Mechanismen aufwendiger als PV-OSIM und PV-OSIMr, wegen seiner Struktur mit drei Durchläufen und der Koordinatentransformationen je Glied.
LTL-OSIM schlug trotz höherer Komplexität EFPA bei einer einzelnen Shadow-Hand, weil die Verzweigung der Hand Dünnbesetztheit erzeugt, die es ausnutzt.

Hauptergebnisse

Komplexität: PV-OSIMr O(n + m²) gegenüber PV-OSIM O(n + m²d), EFPA O(n + md + m²), KJR O(n + m²d), LTL-OSIM O(nd² + m²d + md²) und naiv O(n³ + m²n).
Stehender Atlas mit vier 3D-Punktkontakten je Fuß (12D je Fuß): PV-OSIM benötigte 19,9 % mehr Operationen als PV-OSIMr; mit einer 6D-Schweißbedingung je Fuß waren beide Algorithmen identisch.
Atlas mit Shadow-Händen (3D-Zwangsbedingung je Fingerspitze, 15D je Hand): Abschnitt IV-D berichtet bis zu etwa 34 % weniger Operationen als PV-OSIM, der nächsteffiziente Algorithmus, während die Schlussfolgerungen bis zu 24 % Verbesserung bei den Atlas-Beispielen angeben.
Bei einem verzweigten Testmechanismus mit 6D-Schweißbedingungen an jeder Zweigspitze war PV-OSIMr bei einem einzelnen Zweig gleichauf mit PV-OSIM und skalierte ab zwei Zweigen flacher; EFPA schlug PV-OSIM schließlich bei langen Mechanismen mit zehn Zweigen je Seite.
In einem Fall benötigte PV-OSIM etwa 1,5 % weniger Operationen: Atlas mit 6D-Schweißbedingungen an beiden Händen und beiden Füßen, wo die Zwangsbedingungen vor der schwebenden Basis nur drei Gelenke durchlaufen.
Alle Benchmarks sind Operationszählungen aus der CasADi-Implementierung, keine gemessenen Laufzeiten.

Einschränkungen

PV-OSIM kann günstiger sein, wenn mehr als sechs Zwangsdimensionen nur wenige (drei oder weniger) Gelenke mit einem DoF durchlaufen, weil seine Rang-1-Aktualisierungen die zwei Rang-6-Berechnungen von PV-OSIMr schlagen.
Wenn Zwangsbedingungen erst an der schwebenden Basis zusammentreffen oder der Mechanismus eine einzelne Kette ist, bringt PV-OSIMr keinen Gewinn gegenüber PV-OSIM.
Die Ergebnisse werden als Operationszählungen statt als gemessene Laufzeiten angegeben.
Der Algorithmus wird für kinematische Bäume vorgestellt; die C++-Version in Pinocchio sollte erst nach der Annahme veröffentlicht werden.

Wirkung auf das Fachgebiet

Das Paper erhielt den RA-L 2025 Best Paper Award und hat 4 Zitierungen. Die Autoren haben ihre CasADi-Implementierung als Quellcode auf GitHub veröffentlicht und geben an, dass eine C++-Version in der Bibliothek Pinocchio implementiert wurde, die bei Annahme veröffentlicht werden sollte.

Zusammenfassung

Wir stellen PV-OSIMr vor, einen effizienten Algorithmus zur Berechnung der Delassus-Matrix (auch als inverse Trägheitsmatrix im Operationsraum bekannt) für einen kinematischen Baum, mit der niedrigsten in der Literatur bekannten Ordnung der Rechenkomplexität. PV-OSIMr wird hergeleitet, indem die Berechnungen des Popov-Vereshchagin-Lösers (PV) unter Nutzung der Komponierbarkeit der Kraft- und Bewegungspropagatoren optimiert werden. Er hat eine Rechenkomplexität von O(n + m²), verglichen mit O(n + m²d) des ursprünglichen PV-OSIM-Algorithmus und O(n+md+m²) des erweiterten Kraftpropagator-Algorithmus (EFPA), wobei n die Anzahl der Gelenke, m die Anzahl der Zwangsbedingungen und d die Tiefe des kinematischen Baums ist. Da die Berechnung der Delassus-Matrix den Aufbau einer Matrix der Größe m × m erfordert und alle n Gelenke mindestens einmal berücksichtigen muss, ist die asymptotische Rechenkomplexität von PV-OSIMr optimal. Wir vergleichen unseren Algorithmus außerdem in Benchmarks und stellen fest, dass er in der Praxis häufig effizienter ist als PV-OSIM und EFPA.

Open Source Robotics