Differential dynamic programming

Aussi appelé: DDP
Catégorie: Planning & manipulation › Trajectory optimisation
Mots-clés: trajectory-optimization, optimal-control, model-predictive-control, numerical-optimization, shooting-methods

Une méthode d'optimisation de trajectoire qui améliore une séquence de commandes par des passes arrière et avant répétées, en utilisant des modèles quadratiques locaux du coût restant (cost-to-go) le long de la trajectoire courante.

Définition

Programmation dynamique différentielle (Differential dynamic programming, DDP) : algorithme d'optimisation de trajectoire qui, étant donnés un modèle dynamique, un coût portant sur les états et les commandes, et un état initial, trouve une séquence de commandes qui minimise localement le coût total. Elle a été introduite par David Mayne en 1966 et développée dans le livre de Jacobson et Mayne de 1970 portant le même titre. La DDP est une méthode de tir (shooting) : les variables de décision sont les commandes et, dans sa forme classique, les états sont toujours obtenus en simulant la dynamique vers l'avant, de sorte que chaque itéré est une trajectoire dynamiquement réalisable.

Chaque itération comporte deux passes. La passe arrière part du dernier pas de temps et remonte vers le début en appliquant localement le principe d'optimalité de Bellman : elle construit une approximation quadratique du coût restant (cost-to-go) autour de la trajectoire courante à partir des dérivées premières et secondes de la dynamique et du coût, et calcule à chaque pas une mise à jour affine de la commande, composée d'un terme d'anticipation k et d'une matrice de gains de rétroaction K. La passe avant simule ensuite le système avec les commandes mises à jour u = ū + αk + K(x − x̄), où α est un pas de recherche linéaire. Comme le développement inclut des termes du second ordre de la dynamique, la DDP converge quadratiquement près d'un minimum local, comme la méthode de Newton, tandis que le travail par itération ne croît que linéairement avec la longueur de l'horizon.

Les dérivées secondes de la dynamique sont coûteuses à calculer ; la variante la plus utilisée, le régulateur linéaire quadratique itératif (iterative linear quadratic regulator, iLQR), les abandonne donc et conserve un modèle de la dynamique au premier ordre, une approximation de Gauss-Newton. Les solveurs pratiques régularisent la passe arrière pour qu'elle reste bien conditionnée et étendent la méthode aux bornes sur les commandes (control-limited DDP), aux contraintes générales (méthodes de lagrangien augmenté comme ALTRO), aux estimations initiales non réalisables (feasibility-driven DDP dans Crocoddyl) et, comme dans Parameterized DDP, à des paramètres invariants dans le temps optimisés avec les commandes. La DDP ne trouve que des optima locaux, les résultats dépendent donc de l'estimation initiale. Un sous-produit utile est l'ensemble des gains de rétroaction, qui peuvent stabiliser le robot autour de la trajectoire optimisée.

Pourquoi c'est important

La DDP et l'iLQR comptent parmi les solveurs les plus utilisés pour l'optimisation de trajectoire des robots et la commande prédictive non linéaire. Ils exploitent la structure temporelle du problème, passent à l'échelle linéairement avec la longueur de l'horizon et renvoient une politique de rétroaction locale en plus de la trajectoire ; c'est pourquoi les robots à pattes, les humanoïdes et les drones les exécutent en temps réel à bord.

Applications principales

Commande prédictive non linéaire pour robots à pattes et humanoïdes
Optimisation de trajectoire pour drones et véhicules agiles
Planification de mouvement au niveau des couples pour les manipulateurs
Redressement (swing-up) et équilibre de systèmes sous-actionnés
Optimisation conjointe des trajectoires et des paramètres du modèle ou de conception

En pratique

Une équipe qui développe une commande prédictive corps entier pour un quadrupède formule le problème dans Crocoddyl. La séquence de contacts provient d'un calendrier de démarche fixe, si bien que chaque phase a des contacts connus, et le coût combine le suivi de la base, le placement des pieds, l'effort de commande et des pénalités qui maintiennent les forces de contact à l'intérieur des cônes de frottement. À chaque cycle de commande, le solveur est initialisé à chaud avec la solution précédente décalée d'un pas et n'exécute qu'une ou quelques itérations. La première commande et son gain de rétroaction sont envoyés au contrôleur articulaire de bas niveau, qui utilise le gain pour corriger les changements d'état entre deux mises à jour du solveur. L'essentiel de l'effort de réglage porte sur les poids du coût, la régularisation et la longueur de l'horizon, qui arbitre entre anticipation et temps de résolution.

Idées reçues

La DDP trouve la trajectoire globalement optimale — c'est une méthode locale ; le résultat dépend de l'estimation initiale et peut être un mauvais minimum local
iLQR et DDP sont le même algorithme — l'iLQR omet les termes de la dynamique du second ordre, ce qui rend les itérations bien moins coûteuses au prix d'une convergence plus lente près de la solution
La DDP ne peut pas gérer de contraintes — l'algorithme de base est sans contraintes, mais les variantes à commandes bornées et à lagrangien augmenté sont largement utilisées
La DDP est une programmation dynamique sur tout l'espace d'état — elle n'applique la récursion de Bellman que le long d'une trajectoire, ce qui évite la malédiction de la dimension mais ne donne que des résultats locaux

Qui devrait le savoir

Ingénieurs en automatique qui conçoivent des contrôleurs prédictifs pour robots à pattes et drones
Chercheurs en optimisation de trajectoire
Développeurs d'humanoïdes et de commande corps entier
Étudiants en robotique qui étudient la commande optimale

Technologies associées

iLQR
Crocoddyl
ALTRO
Récursion de Riccati (Riccati Recursion)
Méthodes de tir (Shooting Methods)

Termes associés

Projets associés

PyRoki: Modular Python toolkit for kinematic optimization across CPU, GPU, and TPU via JAX
MuJoCo MPC: DeepMind's interactive real-time model predictive control framework for MuJoCo
python_simple_mppi: MPPI control derived and implemented in numpy, with four worked examples
mjbatch: Runs thousands of MuJoCo simulations in parallel on the CPU
Quadruped-PyMPC: Python MPC framework for quadruped locomotion with gradient and sampling control
STLCG: JAX toolbox for differentiable Signal Temporal Logic robustness