Complementarity Constraint

Detto anche: complementarity condition, contact complementarity
Categoria: Planning & manipulation › Trajectory optimisation
Tag: contact, trajectory-optimization, nonlinear-programming, physics-simulation, legged-robots

Una coppia di condizioni di non negatività con prodotto nullo, per cui al massimo una delle grandezze può essere positiva; si usa per modellare il contatto, dove la forza esiste solo se la distanza è zero.

Definizione

Un vincolo di complementarità (complementarity constraint) lega due grandezze che devono essere entrambe non negative e il cui prodotto deve essere zero, scritto 0 ≤ a ⊥ b ≥ 0. In ogni soluzione almeno una delle due è zero, e ciascuna può essere positiva solo finché l'altra resta a zero. Questa struttura compare ogni volta che un sistema passa tra due regimi senza una variabile di commutazione esplicita, ed è alla base del problema di complementarità lineare (LCP) e dei programmi matematici con vincoli di complementarità.

Il contatto rigido è l'esempio standard in robotica. La distanza φ(q) tra un piede o un dito e una superficie deve essere non negativa, la forza normale di contatto λ deve essere non negativa perché le superfici possono solo spingere, e la forza può essere diversa da zero solo quando la distanza è zero: 0 ≤ φ(q) ⊥ λ ≥ 0. L'attrito coulombiano si può scrivere con ulteriori condizioni di complementarità che legano la velocità di strisciamento al fatto che la forza di attrito si trovi sul bordo del cono di attrito. I simulatori di corpi rigidi a passi temporali sviluppati negli anni 1990, compresi gli schemi di Stewart e Trinkle e di Anitescu e Potra, risolvono a ogni passo un LCP o un problema di complementarità correlato per trovare gli impulsi di contatto. Nell'ottimizzazione di traiettoria, Posa, Cantu e Tedrake (2014) hanno aggiunto questi vincoli direttamente a un problema di trascrizione diretta, così che l'ottimizzatore sceglie quando e dove i contatti si stabiliscono e si interrompono senza che la sequenza dei contatti sia specificata in anticipo.

L'approccio evita le variabili intere che una formulazione intera mista userebbe per attivare e disattivare il contatto, ma porta con sé una difficoltà propria. I vincoli di complementarità sono non convessi e violano le qualificazioni dei vincoli su cui si basano i solver standard di programmazione non lineare, per cui i solver possono bloccarsi o convergere lentamente. I rimedi comuni sono rilassare la condizione sul prodotto in φλ ≤ ε e stringere ε lungo una sequenza di risoluzioni, spostare il prodotto nel costo come penalità o usare solver progettati per problemi di complementarità. Le buone stime iniziali contano molto, ed è per questo che gli ottimizzatori a contatto implicito ricevono spesso un avvio a caldo da soluzioni più semplici.

Perché è importante

Il contatto è la caratteristica che definisce la locomozione con zampe e la manipolazione, e i vincoli di complementarità sono il modo esatto standard di scrivere il contatto rigido nelle equazioni. Permettono ai simulatori di calcolare le forze di contatto in modo coerente e agli ottimizzatori di scoprire la tempistica dei contatti, invece di richiedere che un ingegnere fissi in anticipo l'andatura o la sequenza dei contatti.

Applicazioni principali

Ottimizzazione di traiettoria a contatto implicito per robot con zampe e manipolazione
Simulazione di corpi rigidi a passi temporali con contatto e attrito
Pianificazione di atterraggi, salti e impatti
Modellazione di vincoli unilaterali come i limiti dei giunti e i cavi
Formulazioni di fisica differenziabile del contatto

In pratica

Un ingegnere pianifica l'atterraggio di un quadrupede lasciato cadere da una certa altezza. L'ottimizzazione di traiettoria usa la trascrizione diretta con punti nodali a intervalli di pochi millisecondi; per ogni piede e ogni nodo aggiunge come variabili l'altezza del piede dal suolo e la forza verticale di reazione del suolo, con le condizioni altezza ≥ 0, forza ≥ 0 e altezza × forza ≤ ε. La prima risoluzione usa un ε largo e una stima iniziale ricavata da un semplice moto di caduta; ogni risoluzione successiva stringe ε e riceve un avvio a caldo dalla soluzione precedente. Il piano finale mostra quali piedi toccano terra per primi e come crescono le forze, e l'ingegnere verifica che la violazione di complementarità residua sia abbastanza piccola da non far dipendere il piano da forze a distanza.

Idee sbagliate comuni

I vincoli di complementarità rendono convessa la pianificazione dei contatti — eliminano le variabili intere ma sono non convessi e numericamente difficili per i solver standard
Una soluzione con un piccolo prodotto rilassato è fisicamente esatta — con φλ ≤ ε l'ottimizzatore può sfruttare piccole forze a piccole distanze, quindi ε e la violazione residua vanno verificati
Tutti i motori fisici risolvono il contatto come un problema di complementarità — molti usano invece modelli di contatto a penalità o cedevoli oppure rilassamenti convessi anziché una complementarità stretta

Chi dovrebbe saperlo

Ingegneri dell'ottimizzazione di traiettoria e della locomozione con zampe
Sviluppatori di simulazione fisica
Ricercatori di manipolazione che pianificano attraverso il contatto
Professionisti dell'ottimizzazione numerica in robotica

Tecnologie correlate

Problema di complementarità lineare (Linear Complementarity Problem, LCP)
MPCC (Mathematical Program with Complementarity Constraints)
IPOPT
Drake
Solver PATH

Termini correlati

Progetti correlati

Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design
ProtoMotions: NVIDIA framework for training simulated digital humans and humanoid robots on GPUs
PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
PHC: Physics-based perpetual humanoid controller with fail-state recovery for real-time avatars
SOFA Framework: Real-time physics simulation framework for medical simulation and soft tissue modeling
Extreme Parkour with Legged Robots: RL system for legged robot parkour trained in under 20 hours