Direct Collocation

Aussi appelé: collocation, direct transcription
Catégorie: Planning & manipulation › Trajectory optimisation
Mots-clés: trajectory-optimization, optimal-control, nonlinear-programming, motion-planning, dynamics

Méthode d'optimisation de trajectoire qui traite les états et les commandes à des instants échantillonnés comme des variables et impose la dynamique sous forme de contraintes entre échantillons voisins.

Définition

Collocation directe (direct collocation) : manière de transformer un problème de commande optimale, trouver les commandes au cours du temps qui amènent un système du départ au but au moindre coût, en un programme non linéaire fini qu'un solveur standard peut traiter. La trajectoire est découpée en un certain nombre d'instants, appelés nœuds (knot points). L'état et la commande à chaque nœud deviennent tous deux des variables de décision, et la dynamique du système est imposée sous forme de contraintes d'égalité, appelées contraintes de défaut (defect constraints), qui exigent que les états voisins soient cohérents avec une règle d'intégration telle que la règle des trapèzes ou celle de Hermite–Simpson. Les méthodes pseudo-spectrales forment une famille apparentée qui utilise des polynômes d'ordre plus élevé sur toute la trajectoire.

Cela diffère des méthodes de tir (shooting), dans lesquelles seules les commandes sont des variables de décision et les états sont obtenus en simulant la dynamique vers l'avant. La collocation produit un problème plus grand mais très creux, résolu avec des solveurs de programmation non linéaire creuse tels qu'IPOPT ou SNOPT. Ses avantages : les limites sur les états, comme les plages articulaires, la distance aux obstacles ou les conditions de contact, sont faciles à imposer directement ; le solveur peut partir d'une estimation qui n'est pas physiquement cohérente, comme une droite traversant les obstacles ; et elle tend à mieux se comporter que le tir simple sur de longs horizons et pour des systèmes instables.

Une conséquence de cette structure est que les itérés intermédiaires n'ont pas besoin de respecter la dynamique : le solveur est libre de violer les contraintes de défaut au début et ne les satisfait qu'à la convergence. Les formulations qui déplacent les contraintes de dynamique ou de collision dans des termes de pénalité rendent cela explicite, en laissant la solution traverser des régions infaisables avant que la pénalité ne la repousse. Cette idée a été reprise en apprentissage robotique, par exemple en laissant d'abord un robot simulé traverser les obstacles avec une pénalité, puis en imposant plus tard des collisions strictes. Comme la plupart des méthodes d'optimisation de trajectoire, la collocation directe trouve des optima locaux, de sorte que le résultat dépend de l'estimation initiale.

Pourquoi c'est important

La collocation directe est l'un des principaux outils de l'optimisation de trajectoire pour les robots à pattes, les drones et les manipulateurs, parce qu'elle gère bien les contraintes et démarre facilement à partir d'estimations grossières. La comprendre éclaire aussi une idée de conception utile en apprentissage robotique : relâcher d'abord la physique, puis l'imposer progressivement.

Applications principales

Optimisation de trajectoire pour les sauts, saltos et allures des robots à pattes
Trajectoires optimales en temps et en énergie pour manipulateurs et drones
Planification de trajectoires de recherche et de couverture pour robots mobiles
Génération de mouvements de référence pour des politiques apprises et des contrôleurs de suivi
Conception de trajectoires d'engins spatiaux et d'aéronefs

En pratique

Un ingénieur qui planifie un saut pour un robot à pattes dans Drake ou CasADi pose un problème avec, par exemple, un nombre fixe de nœuds sur la durée du saut, chacun contenant l'état du robot et les couples articulaires. Les contraintes de défaut relient les nœuds consécutifs par la dynamique du robot, des contraintes supplémentaires maintiennent les couples dans les limites des moteurs et les pieds au sol pendant l'appui, et le coût pénalise l'effort et l'erreur finale. Il initialise avec une simple interpolation entre les poses de départ et d'atterrissage, qui viole la dynamique, et laisse IPOPT trouver une trajectoire cohérente. Si le solveur échoue, il ajoute des nœuds, met les variables à l'échelle ou améliore l'estimation initiale. La trajectoire obtenue est ensuite suivie par un contrôleur à rétroaction ou utilisée comme référence pour une politique apprise.

Idées reçues

Chaque itéré du solveur est une trajectoire physiquement valide — la dynamique n'est satisfaite qu'à la convergence ; les solutions intermédiaires peuvent la violer
La collocation directe trouve la meilleure trajectoire globale — elle résout localement un problème non convexe, de sorte que des estimations initiales différentes peuvent donner des réponses différentes
La collocation et le tir résolvent des problèmes différents — ce sont deux transcriptions du même problème de commande optimale, avec des comportements numériques différents

Qui devrait le savoir

Ingénieurs en optimisation de trajectoire et en planification de mouvement
Développeurs de commande pour robots à pattes et drones
Chercheurs en apprentissage robotique qui utilisent des mouvements de référence optimisés
Étudiants en robotique qui étudient la commande optimale

Technologies associées

Drake
CasADi
IPOPT
SNOPT
Tir multiple (Multiple Shooting)
Méthodes pseudo-spectrales (Pseudospectral Methods)

Termes associés

Projets associés

Drake: MIT robotics toolbox for model-based dynamics, optimization, and control system design
OMPL: Sampling-based motion planning library powering MoveIt and countless robotics applications
MoveIt 2: Motion planning framework for ROS 2 robot arms, with kinematics and collision checking
PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
mink: Python inverse kinematics library built on MuJoCo supporting 20+ robot platforms
Ruckig: Real-time jerk-constrained time-optimal trajectory generation for robots and machines