Line-Search Filter Differential Dynamic Programming for Optimal Control with Nonlinear Equality Constraints

Resumen Técnico: FilterDDP para el Control Óptimo con Restricciones de Igualdad No Lineales

Formulación del Problema
El artículo aborda problemas de control óptimo en tiempo discreto (OCP, por sus siglas en inglés) que involucran restricciones de igualdad no lineales. Estos problemas son frecuentes en la robótica para tareas como la planificación de movimiento, la dinámica inversa y la optimización de trayectorias implícitas de contacto (por ejemplo, locomoción de robots con patas, manipulación). La formulación específica del OCP minimiza una función de costo acumulativa sujeta a condiciones iniciales de estado, la dinámica del sistema y restricciones de igualdad no lineales $c(x_t, u_t) = 0$. Aunque la Programación Dinámica Diferencial (DDP) es eficiente para problemas sin restricciones, extenderla para manejar restricciones de igualdad no lineales de manera robusta ha sido un área poco explorada. Los enfoques existentes suelen depender de métodos de Lagrangiano Aumentado (AL) o funciones de mérito, los cuales pueden sufrir de una capacidad limitada de garantías formales de convergencia o inestabilidad numérica.

Metodología: FilterDDP
Los autores proponen FilterDDP, un algoritmo de filtro de búsqueda de línea que integra el marco de trabajo de DDP con un mecanismo de filtro de paso, similar al enfoque utilizado en el solver de programación no lineal general IPOPT. El algoritmo alterna entre un paso hacia atrás (backward pass) y un paso hacia adelante (forward pass):

1. Paso hacia atrás (Backward Pass): El algoritmo computa las derivadas de primera orden y de perturbación de la función de valor subóptima. Aplica un paso de Newton perturbado a las condiciones de estacionariedad del Lagrangiano. Una innovación clave es la introducción de términos de perturbación ($\delta_w I$ y $-\delta_c I$) en la matriz KKT para asegurar que la matriz tenga una inercia específica (autovalores positivos, negativos, cero), garantizando la no singularidad y la estabilidad.
2. Paso hacia adelante (Forward Pass): Se genera una trayectoria de prueba utilizando una búsqueda de línea de retroceso (backtracking line search). El tamaño del paso $\gamma$ se ajusta basándose en un criterio de filtro.
3. Criterios de Filtro: A diferencia de los enfoques tradicionales de función de mérito, FilterDDP utiliza un filtro basado en dos cantidades:
   • Violación de Restricciones ($\theta$): La suma de las normas $L_1$ de las violaciones de las restricciones.
   • Lagrangiano ($L$): El valor de la función Lagrangiana, en lugar de la función de costo bruta.
     Un punto de prueba se acepta si produce un descenso suficiente en la violación de la restricción o en el Lagrangiano, siempre que no caiga en una región "tabú" definida por el filtro.

Elecciones de Diseño Clave y Contribuciones Teóricas
El artículo identifica y justifica rigurosamente dos elecciones de diseño críticas que mejoran el rendimiento numérico:

1. Lagrangiano vs. Costo en la Aceptación del Paso: Los autores reemplazan la función de costo por el Lagrangiano en el criterio de aceptación del paso. Demuestran que la condición de descenso suficiente en el Lagrangiano es análoga a la condición de Armijo en la optimización sin restricciones. Esta elección está respaldada por una prueba formal que muestra que la derivada direccional del Lagrangiano corresponde a la dirección de búsqueda utilizada en el algoritmo.
2. Hesianas Perturbadas y Variables Duales: En el paso hacia atrás, el algoritmo utiliza Hesianas perturbadas y actualiza el gradiente de la función de valor utilizando una variable dual estimada de las restricciones de la dinámica en lugar del gradiente bruto de la función de valor.
   • Convergencia Cuadrática Local: Los autores proporcionan una prueba formal de convergencia cuadrática local para FilterDDP dentro de un vecindad de la solución. Esto generaliza las pruebas existentes para DDP sin restricciones (estados/controles escalares) al entorno de valores vectoriales con restricciones. La prueba se basa en demostrar que el punto óptimo es un punto fijo del algoritmo y que las iteraciones convergen cuadráticamente cuando están suficientemente cerca de la solución.
3. Extensión Primal-Dual: El artículo presenta una extensión para manejar restricciones de desigualdad utilizando un marco de punto interior primal-dual. Esto implica la introducción de variables duales para las restricciones de desigualdad y la resolución de una secuencia de subproblemas de barrera con condiciones de complementariedad perturbadas.

Resultados Experimentales
FilterDDP fue validado en tres problemas desafiantes de optimización de trayectoria implícita de contacto derivados de la robótica:

1. Balanceo de péndulo sobre carro (Cart-pole swing-up) con fricción de Coulomb.
2. Balanceo de Acrobot (Acrobot swing-up) con límites de articulación rígidos.
3. Empuje no prensil (Non-prehensile pushing) (manipulación) con evasión de obstáculos.

El algoritmo se comparó contra:

• IPOPT: Un solver de programación no lineal general de última generación.
• IPOPT (B): Una variante L-BFGS de IPOPT.
• ProxDDP: Un algoritmo DDP basado en AL existente.

Hallazgos:

• Robustez: FilterDDP demostró una robustez significativamente mayor en comparación con los métodos de primer orden (ProxDDP e IPOPT (B)). Notablemente, ProxDDP e IPOPT (B) fallaron en resolver la tarea del Acrobot, produciendo soluciones infactibles o degeneradas.
• Eficiencia: FilterDDP logró la convergencia en menos iteraciones y en un tiempo de ejecución (wall-clock time) significativamente menor en comparación con IPOPT. En las tres tareas, el tiempo medio de ejecución de FilterDDP fue aproximadamente del 10–27% del tiempo de IPOPT y del 1–5% del tiempo de IPOPT (B).
• Convergencia: Los resultados empíricos confirmaron la convergencia cuadrática local, validando el análisis teórico.
• Estudio de Ablación: Eliminar las propuestas de diseño (usar el costo en lugar del Lagrangiano, o Hesianas no perturbadas) resultó en un aumento en el número de iteraciones y mayores tasas de fallo, confirmando la necesidad de estas modificaciones.

Significado y Reivindicaciones
El artículo afirma que FilterDDP ofrece una alternativa robusta y eficiente para resolver OCPs con restricciones de igualdad en robótica. Al alejarse de los enfoques de Lagrangiano Aumentado y adoptar un marco de filtro de búsqueda de línea con modificaciones teóricas específicas (aceptación basada en el Lagrangiano y Hesianas perturbadas), los autores logran propiedades de convergencia más fuertes y un mejor rendimiento numérico. El trabajo cierra la brecha entre la eficiencia de DDP y la robustez requerida para tareas robóticas complejas y con restricciones, proporcionando un solver que es más rápido que los solvers de propósito general como IPOPT mientras mantiene una robustez comparable o superior. Los autores señalan que el trabajo futuro se centrará en aplicar FilterDDP a la locomoción de robots con patas de alta dimensión y en establecer formalmente la convergencia global.