💻 computer science

ContactIPM: A Structure-Exploiting Interior-Point Solver for Contact-Implicit Trajectory Optimization

ContactIPM est un nouveau solveur de points intérieurs exploitant la structure qui combine la factorisation de commande optimale par étapes avec la cohérence primal-dual pour résoudre efficacement et robustement des problèmes d'optimisation de trajectoire implicite de contact, démontrant des accélérations significatives et des taux de succès améliorés par rapport aux solveurs existants spécifiques au contact.

Auteurs originaux : Yucheng Chen

Publié 2026-08-13

📖 3 min de lecture☕ Lecture pause café

CC BY 4.0

Auteurs originaux : Yucheng Chen

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez un robot essayant de pousser une boîte lourde à travers une pièce. Pour un humain, cela semble simple : saisir, pousser, faire glisser, s'arrêter. Mais pour le cerveau informatique d'un robot, c'est un cauchemar de mathématiques. Le robot doit décider exactement quand sa main touche la boîte, avec quelle force pousser, et quand lâcher prise, tout en calculant comment bouger ses propres articulations. C'est ce qu'on appelle l'« optimisation de trajectoire implicite de contact ». Voyez cela comme si vous demandiez à un GPS non seulement de trouver un itinéraire, mais aussi de décider s'il doit rouler sur la route, marcher sur le trottoir ou voler par-dessus une clôture, tout en calculant la vitesse parfaite pour chaque seconde.

La partie délicate est le « contact ». En mathématiques, toucher quelque chose est une condition étrange appelée « complémentarité ». C'est comme une règle qui dit : « Soit tu touches la boîte (force > 0), soit tu ne la touches pas (écart > 0), mais tu ne peux jamais faire les deux en même temps. » Cela crée une impasse mathématique où les solveurs informatiques standards s'embrouillent et s'arrêtent, comme une voiture essayant de rouler sur une route qui disparaît soudainement. Pendant longtemps, les scientifiques devaient choisir entre deux mauvaises options : utiliser un solveur très intelligent qui se bloque sur les règles de « contact », ou un solveur plus simple qui ignore la structure du problème et met un temps infini à calculer.

Entrez en scène ContactIPM, un nouvel outil créé par Yucheng Chen qui agit comme un mécanicien expert pour ces problèmes de robotique. Au lieu de choisir entre vitesse et intelligence, ContactIPM combine les deux. Il traite les règles de « contact » non pas comme un mur dur et incassable, mais comme un élastique souple. Cela permet à l'ordinateur de pousser doucement le plan du robot à travers les moments délicats où il doit décider de toucher ou non, sans rester bloqué. Une fois le plan trouvé, il revient brusquement aux règles physiques réelles pour s'assurer que le robot fonctionne réellement.

L'article montre que cette approche change la donne. Lors des tests face à d'autres solveurs de robotique de haut niveau, ContactIPM était souvent 2 à 8 fois plus rapide. Dans un test spécifique impliquant un robot poussant une boîte, il a résolu le problème en seulement 2,08 millisecondes en moyenne, même lorsque le robot était perturbé par du bruit ou des erreurs. Plus impressionnant encore, dans une série de 50 simulations difficiles, proches de la réalité, où le robot devait se remettre de ses erreurs, ContactIPM a réussi dans les 50 cas, alors que d'autres méthodes ont parfois abandonné ou échoué à trouver un chemin valide. Cela prouve qu'il n'est pas nécessaire de sacrifier la vitesse pour que le robot puisse gérer la réalité complexe et collante du contact avec les objets.

Résumé Technique : ContactIPM

Énoncé du Problème

L'optimisation de trajectoire contact-implicite (CITO) cherche à optimiser simultanément les états du robot, les entrées, les forces de contact et les modes de contact sans prescrire de séquence de contact. Cette flexibilité introduit des Programmes Mathématiques avec Contraintes de Complémentarité (MPCC), où le contact unilatéral et le frottement sont modélisés via des conditions de complémentarité (par exemple, $0 \le a \perp b \ge 0$ ).

Ces problèmes présentent un défi numérique fondamental : aux points de MPCC réalisables, les gradients des contraintes de non-négativité actives et des produits sont structurellement dépendants, ce qui provoque l'échec des qualifications de contraintes standard (comme la LICQ). Cette dégénérescence rend les solveurs de programmation non linéaire primal–dual conventionnels peu fiables, entraînant souvent des systèmes KKT singuliers ou mal conditionnés.

Les approches existantes traitent ce problème de robustesse en abandonnant l'étape de Newton primal–dual entièrement couplée. Des méthodes comme CRISP optimisent uniquement la trajectoire primale via des sous-problèmes convexes, tandis qu'IMPACT utilise une boucle externe de Lagrangien augmenté avec une descente de coordonnées par blocs. Inversement, les solveurs de contrôle optimal (OCP) exploitant la structure (par exemple, acados) utilisent des récursions de Riccati pour l'efficacité mais échouent souvent à générer un contact utile si la complémentarité exacte est imposée sans traitement spécial. Il existe un fossé entre la robustesse spécifique aux MPCC et l'efficacité des solveurs de contrôle optimal (OCP) exploitant la structure.

Méthodologie : ContactIPM

ContactIPM propose une méthode d'intérieur-point primal–dual unifiée qui conserve la structure bloc-bandée de l'OCP requise pour la récursion de Riccati tout en gérant les contraintes de complémentarité de manière robuste.

1. Relaxation Intérieure Élastique Couplée à la Barrière

Au lieu d'utiliser des poids de pénalité ou des Lagrangiens augmentés, ContactIPM introduit une relaxation intérieure élastique par étape pour chaque paire de complémentarité marquée $(a, b)$ :

Variables d'écart (Slacks) : Des écarts du côté positif ( $s_a, s_b$ ) et un écart de produit ( $s_c$ ) sont introduits.
Élévation Élastique : La condition de complémentarité est transformée en un système d'égalités :
$g_a + s_a = 0, \quad g_b + s_b = 0, \quad g_a g_b - \theta(\mu) + s_c = 0$
où $\theta(\mu) = \gamma_{mpcc}\mu$ lie le resserrement de la complémentarité directement au paramètre de barrière $\mu$ .
Régularité : Cette construction garantit que le Jacobien de la contrainte élevée contient un bloc identité par rapport aux variables d'écart. Par conséquent, le problème relaxé satisfait la qualification de indépendance linéaire des contraintes (LICQ) à chaque point intérieur, garantissant des multiplicateurs uniques et un système primal–dual régulier.
Pas de Pénalité Indépendante : Contrairement aux méthodes de pénalité, le resserrement de la complémentarité est contrôlé par le même paramètre de barrière $\mu$ qui définit la trajectoire centrale, éliminant le besoin de coefficients de pénalité réglés indépendamment.

2. Élimination Primal–Dual par Étage et Récursion de Riccati

Le solveur maintient une cohérence primal–dual, mettant à jour la trajectoire, les multiplicateurs de dynamique, les multiplicateurs d'inégalité et les écarts en tant que composantes d'un système KKT perturbé unique.

Élimination Locale : Comme les paires de complémentarité et leurs variables élastiques sont locales à chaque étape, le solveur élimine les variables d'écart locales ( $\Delta s_k$ ) et duales ( $\Delta \lambda_k$ ) par étape.
Système Réduit : Cette élimination ne modifie que l'Hessien local de l'étape ( $\tilde{H}_k$ ) et le gradient ( $\tilde{q}_k$ ). La dynamique reste le seul couplage entre les étapes adjacentes, préservant la structure bloc-bandée.
Résolution Efficace : Le système réduit est résolu à l'aide d'une récursion de Riccati vers l'arrière suivie d'une substitution vers l'avant, atteignant une complexité linéaire $O(N)$ par rapport à la longueur de l'horizon.

3. Récupération MPCC Multi-Phases

Pour gérer les multiples branches stationnaires associées aux différents modes de contact, ContactIPM emploie un calendrier de récupération fixe impliquant :

Continuation : Resserrement progressif du paramètre de barrière tout en tentant de rester dans le bassin du mode de contact actuel.
Redémarrage (Restart) : Si la continuation échoue (par exemple, en raison d'une perte de conditionnement), le solveur restaure la conjecture primale originale et redémarre avec un paramètre de barrière plus grand et une courbure de Gauss–Newton pour explorer différents bassins.
Terminaison : Le solveur se termine uniquement lorsque le résidu de complémentarité physique non relaxé ( $r_{phys} = \max |a_k b_k|$ ) tombe sous un seuil spécifié, garantissant que la trajectoire finale satisfait le modèle de contact physique, et non seulement la formulation relaxée.

4. Mise à l'Échelle et Globalisation

La méthode applique une mise à l'échelle de coordonnées diagonale cohérente avec l'horizon, dérivée des magnitudes de dérivées par étape. La globalisation est réalisée via une recherche de ligne à filtre qui équilibre la réduction de l'objectif et la violation des contraintes, avec une règle de fraction de bordure pour maintenir des écarts positifs.

Contributions Clés

Formulation Unifiée : Une formulation par étape convertissant les paires de complémentarité marquées en lignes de produit élastiques couplées à la barrière au sein d'un cadre de dynamique, de coût et d'inégalité non linéaire.
Méthode de Newton Primal–Dual Sensible aux MPCC : Une méthode qui préserve la structure KKT perturbée couplée tout en utilisant l'élimination locale des écarts/duaux et la récursion de Riccati. Elle inclut un préconditionnement de l'échelle de la trajectoire et une politique de récupération multi-phases.
Évaluation Reproductible : Une suite expérimentale complète comparant ContactIPM à CRISP, IMPACT, et une base de référence acados structurée en OCP (avec complémentarité exacte), incluant 50 essais en boucle fermée sous diverses perturbations.

Résultats Expérimentaux

Performance vs. CRISP

Vitesse : Sur quatre cas de référence fixes (Cartpole, Push Box, Transport, Push T), ContactIPM est 2,17× à 8,87× plus rapide que CRISP sur 20 répétitions de temps appariées.
Robustesse : ContactIPM égale CRISP sur Cartpole et Transport mais réussit dans 5 cas supplémentaires de Push Box (24/25 contre 19/25). Sur la suite Push T, ContactIPM réussit dans les 50 cas, alors que CRISP ne réussit que dans 27/50 lorsqu'une complémentarité physique stricte est imposée.

Performance vs. IMPACT

Vitesse : ContactIPM est 2,96× plus rapide sur Push T et 4,91× plus rapide sur Cart Transport. Cependant, IMPACT est 4,46× plus rapide sur Push Box.
Robustesse : ContactIPM réussit dans 150/150 cas sur trois suites de 50 cas (Push Box, Push T, Cart Transport), contre 147/150 pour IMPACT.

Comparaison avec la Base de Référence Structurée OCP (acados)

Lorsque acados est configuré avec une complémentarité exacte (sans relaxation élastique), il échoue fréquemment à générer un contact utile. Par exemple, dans le benchmark Push Box, acados passe les tests de faisabilité physique dans les 25 cas mais 0/25 n'atteignent l'objectif terminal, se terminant souvent sur une trajectoire de contact nul.
À travers 165 cas riches en contacts (CRISP Transport, CRISP Push T, IMPACT Push T, et IMPACT Cart Transport), acados n'a produit qu'une seule trajectoire acceptée, tandis que ContactIPM a réussi dans 158 cas. Cela démontre que l'exploitation de la structure OCP seule est insuffisante pour surmonter la dégénérescence des MPCC.

Validation en Boucle Fermée

Dans 50 essais en boucle fermée de Push Box impliquant des erreurs de modèle, du bruit et des réinitialisations d'état, ContactIPM a réussi dans les 50 cas.
Latence : Le temps de résolution médian était de 2,08 ms, avec 99,37 % des résolutions respectant une échéance de contrôle de 100 ms.
Faisabilité : Le feedback en boucle fermée a maintenu la faisabilité primale et la complémentarité physique, avec des produits de complémentarité physique maximaux restant en dessous de $1,01 \times 10^{-6}$ .

Signification et Revendications

L'article affirme que la robustesse des MPCC, la cohérence primal–dual et la structure de contrôle optimal peuvent coexister dans un seul solveur. ContactIPM démontre que la séparation du traitement de la complémentarité de l'étape de Newton primal–dual (comme vu dans CRISP et IMPACT) n'est pas un coût inévitable de la complémentarité de contact. En combinant une relaxation intérieure élastique avec l'élimination par étape et la récursion de Riccati, le solveur atteint à la fois la robustesse numérique requise pour les problèmes de contact-implicite et l'efficacité de calcul du contrôle optimal. Les résultats suggèrent qu'un traitement spécialisé des MPCC est nécessaire, même lors de l'utilisation de techniques avancées de l'algèbre linéaire OCP.