Complementarity Constraint

Auch genannt: complementarity condition, contact complementarity
Kategorie: Planning & manipulation › Trajectory optimisation
Schlagwörter: contact, trajectory-optimization, nonlinear-programming, physics-simulation, legged-robots

Ein Paar von Nichtnegativitätsbedingungen mit Produkt null, sodass höchstens eine Größe positiv sein kann; dient zur Modellierung von Kontakt, bei dem eine Kraft nur existiert, wenn der Abstand null ist.

Definition

Eine Komplementaritätsnebenbedingung (complementarity constraint) verknüpft zwei Größen, die beide nichtnegativ sein müssen und deren Produkt null sein muss, geschrieben 0 ≤ a ⊥ b ≥ 0. In jeder Lösung ist mindestens eine der beiden null, und jede darf nur positiv sein, solange die andere bei null bleibt. Diese Struktur tritt immer dann auf, wenn ein System ohne explizite Schaltvariable zwischen zwei Regimen wechselt, und sie ist die Grundlage des linearen Komplementaritätsproblems (linear complementarity problem, LCP) und mathematischer Programme mit Komplementaritätsnebenbedingungen.

Starrer Kontakt ist das Standardbeispiel in der Robotik. Der Abstand φ(q) zwischen einem Fuß oder Finger und einer Oberfläche muss nichtnegativ sein, die Normalkontaktkraft λ muss nichtnegativ sein, weil Oberflächen nur drücken können, und die Kraft kann nur dann ungleich null sein, wenn der Abstand null ist: 0 ≤ φ(q) ⊥ λ ≥ 0. Coulomb-Reibung lässt sich mit weiteren Komplementaritätsbedingungen schreiben, die die Gleitgeschwindigkeit damit verknüpfen, ob die Reibkraft auf dem Rand des Reibungskegels liegt. Zeitschrittverfahren für Starrkörpersimulatoren, die in den 1990er-Jahren entwickelt wurden, darunter die Schemata von Stewart und Trinkle sowie von Anitescu und Potra, lösen in jedem Schritt ein LCP oder ein verwandtes Komplementaritätsproblem, um die Kontaktimpulse zu bestimmen. In der Trajektorienoptimierung fügten Posa, Cantu und Tedrake (2014) diese Nebenbedingungen direkt in ein Problem der direkten Transkription ein, sodass der Optimierer wählt, wann und wo Kontakte geschlossen und gelöst werden, ohne dass die Kontaktfolge vorab festgelegt wird.

Der Ansatz vermeidet die ganzzahligen Variablen, die eine gemischt-ganzzahlige Formulierung für Kontakt an und aus verwenden würde, bringt aber eigene Schwierigkeiten mit sich. Komplementaritätsnebenbedingungen sind nichtkonvex und verletzen die Constraint Qualifications, auf die sich Standardlöser für nichtlineare Optimierung stützen, sodass Löser stecken bleiben oder langsam konvergieren können. Übliche Abhilfen sind, die Produktbedingung zu φλ ≤ ε zu relaxieren und ε über eine Folge von Lösungsläufen zu verkleinern, das Produkt als Strafterm in die Kostenfunktion zu verlagern oder Löser zu verwenden, die für Komplementaritätsprobleme ausgelegt sind. Gute Startschätzungen sind sehr wichtig, weshalb kontaktimplizite Optimierer oft per Warmstart von einfacheren Lösungen aus gestartet werden.

Warum es wichtig ist

Kontakt ist das prägende Merkmal von Beinfortbewegung und Manipulation, und Komplementaritätsnebenbedingungen sind die übliche exakte Art, starren Kontakt in Gleichungen zu fassen. Mit ihnen berechnen Simulatoren Kontaktkräfte konsistent, und Optimierer finden das Kontakttiming selbst, statt dass ein Ingenieur die Gangart oder Kontaktfolge vorab festlegen muss.

Wichtige Anwendungen

Kontaktimplizite Trajektorienoptimierung für Laufroboter und Manipulation
Zeitschrittbasierte Starrkörpersimulation mit Kontakt und Reibung
Planung von Landungen, Sprüngen und Stößen
Modellierung einseitiger Nebenbedingungen wie Gelenkgrenzen und Seile
Differenzierbare Physikformulierungen von Kontakt

In der Praxis

Ein Ingenieur plant die Landung eines Vierbeiners, der aus einer gewissen Höhe fallen gelassen wird. Die Trajektorienoptimierung verwendet direkte Transkription mit Stützstellen alle paar Millisekunden; für jeden Fuß und jede Stützstelle fügt sie die Höhe des Fußes über dem Boden und die vertikale Bodenreaktionskraft als Variablen mit den Bedingungen Höhe ≥ 0, Kraft ≥ 0 und Höhe × Kraft ≤ ε hinzu. Der erste Lösungslauf verwendet ein großzügiges ε und eine Startschätzung aus einer einfachen Fallbewegung; jeder weitere Lauf verkleinert ε und startet per Warmstart von der vorherigen Lösung. Der endgültige Plan zeigt, welche Füße zuerst aufsetzen und wie die Kräfte ansteigen, und der Ingenieur prüft, dass die verbleibende Komplementaritätsverletzung klein genug ist, damit der Plan nicht auf Kräfte über eine Distanz angewiesen ist.

Häufige Missverständnisse

Komplementaritätsnebenbedingungen machen die Kontaktplanung konvex — sie beseitigen ganzzahlige Variablen, sind aber nichtkonvex und für Standardlöser numerisch schwierig
Eine Lösung mit kleinem relaxiertem Produkt ist physikalisch exakt — mit φλ ≤ ε kann der Optimierer kleine Kräfte bei kleinen Abständen ausnutzen, daher müssen ε und die verbleibende Verletzung geprüft werden
Alle Physik-Engines lösen Kontakt als Komplementaritätsproblem — viele verwenden stattdessen Straf- oder nachgiebige Kontaktmodelle oder konvexe Relaxationen statt strikter Komplementarität

Wer das wissen sollte

Ingenieure für Trajektorienoptimierung und Beinfortbewegung
Entwickler von Physiksimulationen
Manipulationsforschende, die Planung durch Kontakt betreiben
Praktiker numerischer Optimierung in der Robotik

Open Source Robotics