Differential dynamic programming

También llamado: DDP
Categoría: Planning & manipulation › Trajectory optimisation
Etiquetas: trajectory-optimization, optimal-control, model-predictive-control, numerical-optimization, shooting-methods

Un método de optimización de trayectorias que mejora una secuencia de controles mediante pasadas repetidas hacia atrás y hacia adelante, usando modelos cuadráticos locales del coste por recorrer (cost-to-go) a lo largo de la trayectoria actual.

Definición

Programación dinámica diferencial (DDP) (differential dynamic programming) es un algoritmo de optimización de trayectorias: dados un modelo dinámico, un coste sobre estados y controles y un estado inicial, encuentra una secuencia de controles que minimiza localmente el coste total. La introdujo David Mayne en 1966 y se desarrolló más en el libro homónimo de Jacobson y Mayne de 1970. DDP es un método de disparo (shooting): las variables de decisión son los controles y, en su forma clásica, los estados se obtienen siempre simulando la dinámica hacia adelante, de modo que cada iterado es una trayectoria dinámicamente factible.

Cada iteración tiene dos pasadas. La pasada hacia atrás empieza en el último paso de tiempo y avanza hacia el inicio, aplicando localmente el principio de optimalidad de Bellman: construye una aproximación cuadrática del coste por recorrer (cost-to-go) alrededor de la trayectoria actual a partir de las derivadas primeras y segundas de la dinámica y del coste, y resuelve en cada paso una actualización afín del control, formada por un término de prealimentación k y una matriz de ganancias de realimentación K. Después, la pasada hacia adelante simula el sistema con los controles actualizados u = ū + αk + K(x − x̄), donde α es un tamaño de paso de búsqueda lineal. Como el desarrollo incluye términos de segundo orden de la dinámica, DDP converge cuadráticamente cerca de un mínimo local, como el método de Newton, mientras que el trabajo por iteración crece solo linealmente con la longitud del horizonte.

Las derivadas segundas de la dinámica son costosas de calcular, por lo que la variante más usada, el regulador lineal cuadrático iterativo (iLQR), las descarta y conserva un modelo de primer orden de la dinámica, una aproximación de Gauss-Newton. Los solvers prácticos regularizan la pasada hacia atrás para mantenerla bien condicionada y extienden el método a límites de control (control-limited DDP), restricciones generales (métodos de Lagrangiano aumentado como ALTRO), estimaciones iniciales no factibles (feasibility-driven DDP en Crocoddyl) y, como en Parameterized DDP, parámetros invariantes en el tiempo optimizados junto con los controles. DDP solo encuentra óptimos locales, así que los resultados dependen de la estimación inicial. Un subproducto útil es el conjunto de ganancias de realimentación, que puede estabilizar el robot alrededor de la trayectoria optimizada.

Por qué importa

DDP e iLQR están entre los solvers más usados para la optimización de trayectorias de robots y el control predictivo basado en modelo no lineal. Aprovechan la estructura temporal del problema, escalan linealmente con la longitud del horizonte y devuelven una política de realimentación local junto con la trayectoria, por eso los robots con patas, los humanoides y los drones los ejecutan en tiempo real a bordo.

Aplicaciones clave

Control predictivo basado en modelo no lineal para robots con patas y humanoides
Optimización de trayectorias para drones y vehículos ágiles
Planificación de movimiento a nivel de par para brazos robóticos
Levantamiento (swing-up) y equilibrio de sistemas subactuados
Optimización conjunta de trayectorias y de parámetros del modelo o del diseño

En la práctica

Un equipo que construye un control predictivo basado en modelo de cuerpo completo para un cuadrúpedo formula el problema en Crocoddyl. La secuencia de contactos procede de un calendario de marcha fijo, de modo que cada fase tiene contactos conocidos, y el coste combina el seguimiento de la base, la colocación de los pies, el esfuerzo de control y penalizaciones que mantienen las fuerzas de contacto dentro de los conos de fricción. En cada ciclo de control, el solver se inicializa en caliente con la solución anterior desplazada un paso y ejecuta solo una o unas pocas iteraciones. El primer control y su ganancia de realimentación se envían al controlador articular de bajo nivel, que usa la ganancia para corregir los cambios de estado entre actualizaciones del solver. La mayor parte del esfuerzo de ajuste se dedica a los pesos del coste, la regularización y la longitud del horizonte, que equilibra la previsión frente al tiempo de resolución.

Ideas erróneas comunes

DDP encuentra la trayectoria globalmente óptima — es un método local; el resultado depende de la estimación inicial y puede ser un mínimo local pobre
iLQR y DDP son el mismo algoritmo — iLQR omite los términos de segundo orden de la dinámica, lo que da iteraciones mucho más baratas a costa de una convergencia más lenta cerca de la solución
DDP no puede manejar restricciones — el algoritmo básico no tiene restricciones, pero las variantes con límites de control y de Lagrangiano aumentado se usan ampliamente
DDP es programación dinámica sobre todo el espacio de estados — aplica la recursión de Bellman solo a lo largo de una trayectoria, lo que evita la maldición de la dimensionalidad pero da solo resultados locales

Quién debería saberlo

Ingenieros de control que construyen controladores predictivos basados en modelo para robots con patas y drones
Investigadores en optimización de trayectorias
Desarrolladores de humanoides y de control de cuerpo completo
Estudiantes de robótica que estudian control óptimo

Tecnologías relacionadas

iLQR
Crocoddyl
ALTRO
Recursión de Riccati (Riccati Recursion)
Métodos de disparo (Shooting Methods)

Términos relacionados

Proyectos relacionados

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