Complementarity Constraint

• Aussi appelé: complementarity condition, contact complementarity
• Catégorie: Planning & manipulation › Trajectory optimisation
• Mots-clés: contact, trajectory-optimization, nonlinear-programming, physics-simulation, legged-robots

Paire de conditions de positivité dont le produit est nul, de sorte qu'au plus une grandeur peut être strictement positive ; sert à modéliser le contact, où une force n'existe que si l'écart est nul.

Définition

Une contrainte de complémentarité (complementarity constraint) relie deux grandeurs qui doivent toutes deux être positives ou nulles et dont le produit doit être nul, ce qui s'écrit 0 ≤ a ⊥ b ≥ 0. En toute solution, au moins l'une des deux est nulle, et chacune ne peut être strictement positive que tant que l'autre reste nulle. Cette structure apparaît chaque fois qu'un système bascule entre deux régimes sans variable de commutation explicite, et elle est à la base du problème de complémentarité linéaire (linear complementarity problem, LCP) et des programmes mathématiques avec contraintes de complémentarité.

Le contact rigide est l'exemple type en robotique. La distance φ(q) entre un pied ou un doigt et une surface doit être positive ou nulle, la force de contact normale λ doit être positive ou nulle parce qu'une surface ne peut que pousser, et la force ne peut être non nulle que lorsque la distance est nulle : 0 ≤ φ(q) ⊥ λ ≥ 0. Le frottement de Coulomb peut s'écrire avec des conditions de complémentarité supplémentaires qui relient la vitesse de glissement au fait que la force de frottement se trouve ou non sur le bord du cône de frottement. Les simulateurs de corps rigides à pas de temps développés dans les années 1990, dont les schémas de Stewart et Trinkle et d'Anitescu et Potra, résolvent à chaque pas un LCP ou un problème de complémentarité apparenté pour obtenir les impulsions de contact. En optimisation de trajectoire, Posa, Cantu et Tedrake (2014) ont ajouté ces contraintes directement à un problème de transcription directe, de sorte que l'optimiseur choisit quand et où les contacts s'établissent et se rompent sans que la séquence de contacts soit spécifiée à l'avance.

L'approche évite les variables entières qu'une formulation en nombres entiers mixtes utiliserait pour l'activation et la désactivation du contact, mais elle apporte sa propre difficulté. Les contraintes de complémentarité sont non convexes et violent les conditions de qualification des contraintes sur lesquelles reposent les solveurs standard de programmation non linéaire, si bien que les solveurs peuvent stagner ou converger lentement. Les remèdes courants consistent à relâcher la condition sur le produit en φλ ≤ ε et à resserrer ε au fil d'une suite de résolutions, à reporter le produit dans le coût sous forme de pénalité, ou à utiliser des solveurs conçus pour les problèmes de complémentarité. De bonnes estimations initiales comptent beaucoup, c'est pourquoi les optimiseurs à contact implicite sont souvent lancés par démarrage à chaud à partir de solutions plus simples.

Pourquoi c'est important

Le contact est le trait distinctif de la locomotion à pattes et de la manipulation, et les contraintes de complémentarité sont la manière exacte standard d'écrire le contact rigide sous forme d'équations. Elles permettent aux simulateurs de calculer les forces de contact de façon cohérente et aux optimiseurs de découvrir le séquencement des contacts, au lieu d'exiger qu'un ingénieur fixe à l'avance l'allure ou la séquence de contacts.

Applications principales

• Optimisation de trajectoire à contact implicite pour les robots à pattes et la manipulation
• Simulation de corps rigides à pas de temps avec contact et frottement
• Planification d'atterrissages, de sauts et d'impacts
• Modélisation de contraintes unilatérales comme les butées articulaires et les câbles
• Formulations différentiables du contact en physique

En pratique

Un ingénieur planifie l'atterrissage d'un quadrupède lâché d'une certaine hauteur. L'optimisation de trajectoire utilise la transcription directe avec des points de collocation toutes les quelques millisecondes ; pour chaque pied et chaque point, elle ajoute comme variables la hauteur du pied au-dessus du sol et la force de réaction verticale du sol, avec les conditions hauteur ≥ 0, force ≥ 0 et hauteur × force ≤ ε. La première résolution utilise un ε lâche et une estimation initiale tirée d'un simple mouvement de chute ; chaque résolution suivante resserre ε et part par démarrage à chaud de la solution précédente. Le plan final montre quels pieds touchent le sol en premier et comment les forces montent, et l'ingénieur vérifie que la violation de complémentarité restante est assez faible pour que le plan ne repose pas sur des forces à distance.

Idées reçues

• Les contraintes de complémentarité rendent la planification de contacts convexe — elles suppriment les variables entières mais sont non convexes et numériquement difficiles pour les solveurs standard
• Une solution dont le produit relâché est petit est physiquement exacte — avec φλ ≤ ε, l'optimiseur peut exploiter de petites forces à de petites distances, il faut donc vérifier ε et la violation restante
• Tous les moteurs physiques résolvent le contact comme un problème de complémentarité — beaucoup utilisent plutôt des modèles de contact par pénalité ou compliants, ou des relaxations convexes, au lieu d'une complémentarité stricte

Qui devrait le savoir

• Ingénieurs en optimisation de trajectoire et en locomotion à pattes
• Développeurs de simulation physique
• Chercheurs en manipulation qui planifient à travers le contact
• Praticiens de l'optimisation numérique en robotique

Technologies associées

• Problème de complémentarité linéaire (Linear Complementarity Problem, LCP)
• MPCC (Mathematical Program with Complementarity Constraints)
• IPOPT
• Drake
• Solveur PATH

Termes associés

• Contact mode
• Mixed-Integer Programming
• Direct Collocation
• Penalty-Based Contact Model
• Coulomb Friction
• Warm Start

Projets associés

• 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